Problem:


Score : 500 points

Problem Statement

We have a chocolate bar partitioned into H horizontal rows and W vertical columns of squares.

The square (i, j) at the i-th row from the top and the j-th column from the left is dark if S_{i,j} is 0, and white if S_{i,j} is 1.

We will cut the bar some number of times to divide it into some number of blocks. In each cut, we cut the whole bar by a line running along some boundaries of squares from end to end of the bar.

How many times do we need to cut the bar so that every block after the cuts has K or less white squares?

Constraints

1 \leq H \leq 10

1 \leq W \leq 1000

1 \leq K \leq H \times W

S_{i,j} is 0 or 1.

Input

Input is given from Standard Input in the following format:

H W K
S_{1,1}S_{1,2}...S_{1,W}
:
S_{H,1}S_{H,2}...S_{H,W}

Output

Print the number of minimum times the bar needs to be cut so that every block after the cuts has K or less white squares.

Sample Input 1

3 5 4
11100
10001
00111

Sample Output 1

2

For example, cutting between the 1-st and 2-nd rows and between the 3-rd and 4-th columns - as shown in the figure to the left - works.

Note that we cannot cut the bar in the ways shown in the two figures to the right.

Sample Input 2

3 5 8
11100
10001
00111

Sample Output 2

0

No cut is needed.

Sample Input 3

4 10 4
1110010010
1000101110
0011101001
1101000111

Sample Output 3

3



Sample input:
3 5 4
11100
10001
00111


Sample output:
2

Submission status: Accepted

Solution code:
def main():
	H, W, K = map(int, input().split())
	g = [input() for _ in range(H)]
	ans = 1 << 100
	for i in range(1 << H - 1):
		need = bin(i).count("1")
		sz = need + 1
		cnt = [0] * sz
		f = 1
		for j in range(W):
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == "1"
				if cnt[c] > K:
					break
				c += (i >> k) & 1
			else:
				continue
			cnt = [0] * sz
			need += 1
			if need > ans:
				f = 0
				break
			c = 0
			for k in range(H):
				cnt[c] += g[k][j] == "1"
				if cnt[c] > K:
					break
				c += (i >> k) & 1
			else:
				continue
			f = 0
			break
		if f:
			ans = min(ans, need)
	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
def main():
    from itertools import product

    H, W, K = map(int, input().split())
    S = [input() for _ in range(H)]
    S_T = [[int(s[w]) for s in S] for w in range(W)]
    sumS = sum(map(sum, S_T))
    ans = (H - 1) * (W - 1)

    if sumS <= K:
        print(0)
    else:
        for i in product([True, False], repeat=H-1):
            cnt = sum(i)
            if cnt >= ans:
                continue
            M = [[0]]
            for j, k in enumerate(i):
                if k:
                    M.append([])
                M[-1].append(j+1)
            A = [0] * len(M)
            for s_t in S_T:
                for l, m in enumerate(M):
                    A[l] += sum(s_t[i] for i in m)
                if any(a > K for a in A):
                    cnt += 1
                    if cnt >= ans:
                        break
                    A = [sum(s_t[i] for i in m) for m in M]
                    if any(a > K for a in A):
                        cnt = ans + 1
                        break
            ans = min(cnt, ans)
        print(ans)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
from itertools import product

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
S_T = [[int(s[w]) for s in S] for w in range(W)]
sumS = sum(map(sum, S_T))
ans = (H - 1) * (W - 1)

if sumS <= K:
    print(0)
else:
    for i in product([True, False], repeat=H-1):
        cnt = sum(i)
        if cnt >= ans:
            continue
        M = [[0]]
        for j, k in enumerate(i):
            if k:
                M.append([])
            M[-1].append(j+1)
        A = [0] * len(M)
        for s_t in S_T:
            for l, m in enumerate(M):
                A[l] += sum(s_t[i] for i in m)
            if any(a > K for a in A):
                cnt += 1
                if cnt >= ans:
                    break
                A = [sum(s_t[i] for i in m) for m in M]
                if any(a > K for a in A):
                    cnt = ans + 1
                    break
        ans = min(cnt, ans)
    print(ans)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]

# chocoのj列目の0(white)の個数を数える
def count_col_whites(choco, j):
    res = 0
    for c in choco:
        if c[j]=="1":
            res += 1
    return res

# チョコレートをヨコ方向にカットする
def cut_chocolate(i):
    if i == 0:
        return [S]
    else:
        res = []
        pre = 0
        tmp = 0
        while i > 0:
            tmp += 1
            if i%2 == 1:
                res.append(S[pre:tmp])
                pre = tmp
            i //= 2
        res.append(S[pre:len(S)])
        return res

def is_less_than_or_equal_to_K(cut):
    for c in cut:
        for j in range(W):
            tmp = 0
            for i in range(len(c)):
                if c[i][j] == "1":
                    tmp += 1
            if tmp > K:
                return False
    return True

ans = 10**10
for i in range(2**(H-1)):
    # 横方向にカットしたときのかたまりをcutに格納
    cut = cut_chocolate(i)
    tmp_ans = len(cut)-1
    # 縦方向にみていって、1列中の白チョコの個数がK個より大きければそもそも無理
    if not is_less_than_or_equal_to_K(cut):
        continue
    # 縦方向にみていって、白チョコがK個以下のかたまりになるようカットする
    current_white_nums = [0 for _ in range(len(cut))]
    for j in range(W):
        for i in range(len(cut)):
            white_num = count_col_whites(cut[i], j)
            if white_num + current_white_nums[i] <= K:
                current_white_nums[i] += white_num
            else:
                current_white_nums = [count_col_whites(cut[_], j) for _ in range(len(cut))]
                tmp_ans += 1
                break
    ans = min(ans, tmp_ans)
print(ans)

Submission status: Accepted

Solution code:
# Problem E - Dividing Chocolate

# input
H, W, K = map(int, input().split())
board = [['']*W for i in range(H)]
for i in range(H):
    s = list(input())
    for j in range(W):
        board[i][j] = s[j]

# initialization
min_divide = 10**10
s = [0]*(H-1) # 横線の入り方 0:無 1:有
is_ok = True

# search
for i in range(2**(H-1)): # bit全探索
    # sの初期化
    h_count = 0
    w_count = 0
    for j in range(H-1):
        if ((i>>j)&1):
            s[j] = 1
            h_count += 1
        else:
            s[j] = 0

    # 列の全探索
    s_score = [0]*H # 各区域のスコア
    s_cur = [0]*H
    for j in range(W):
        c = 0
        s_cur = [0]*H

        for k in range(H):
            if board[k][j]=='1':
                s_cur[c] += 1

            # Kを超えていないかのチェック
            if s_cur[c]>K:
                is_ok = False
                break

            # 次の遷移先(横線の有無でグループが別れる)
            if k+1<H:
                if s[k]==1:
                    c += 1
        # Kを超えていたらループ中止
        if not is_ok:
            break
        # 前の列のグループと足してみてKを超えていないかチェック
        # 超えていれば縦線分割を施す
        group_smaller = True
        if j>0:
            for c_num in range(c+1):
                if s_score[c_num]+s_cur[c_num]>K:
                    group_smaller = False
        else:
            group_smaller = True

        if group_smaller:
            for c_num in range(c+1):
                s_score[c_num] += s_cur[c_num]
        else:
            w_count += 1
            for c_num in range(c+1):
                s_score[c_num] = s_cur[c_num]

    if not is_ok:
        is_ok = True
        continue

    for c_num in range(h_count+1):
        if s_score[c_num]>K:
            h_count = 10 ** 6

    # 縦線と横線の合計でmin_divideを更新
    min_divide = min(min_divide, w_count + h_count)

# output
print(min_divide)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

H,W,K = map(int,input().split())
choco = [input() for _ in range(H)]
num =(2**(H-1))

white_count = list()
min_div_count =10**6
for i in range(num):
    bin_str = format(i, 'b')
    zero = str()
    if H != len(bin_str):
        for _ in range(H-len(bin_str)):
            zero += "0"
        bin_str = zero + bin_str
    white_count = [0 for s in bin_str if s == "1"]
    white_count.append(0)
    div_count=len(white_count)-1
    
    for j in range(W):
        block_count = 0
        white_list = [0]*len(white_count)
        #print("j:"+str(j))
        is_over = False
        for k in range(len(bin_str)):
            if bin_str[k] == "1":
                block_count += 1
            
            white_list[block_count] += int(choco[k][j])
            white_count[block_count] += int(choco[k][j])
            if white_count[block_count] > K:
                is_over = True

        if max(white_list)>K:
            break


        if is_over:
            div_count += 1
            white_count = white_list


        #print(white_list)   
        #print(white_count)
        #print("div_count"+str(div_count))
        if div_count >= min_div_count:
            break
    else:
        min_div_count = div_count
print(min_div_count)

Submission status: Accepted

Solution code:
from itertools import accumulate
from operator import add


h, w, k = map(int, input().split())

white_count = [0] * (w+1)
prev = [0] * (w+1)
for _ in range(h):
    line = iter('0'+input())
    cumsum_1d = accumulate(map(int, line))
    cumsum_2d = list(map(add, prev, cumsum_1d))
    prev = cumsum_2d
    white_count += cumsum_2d


def get_white(sy, sx, ny, nx):
    a = sy*(w+1) + sx
    b = sy*(w+1) + nx
    c = ny*(w+1) + sx
    d = ny*(w+1) + nx
    return white_count[d] - white_count[c] - white_count[b] + white_count[a]


ans = []
for pattern in range(2**(h-1)):
    dived = [0] + [y+1 for y in range(h-1) if (pattern>>y) & 1] + [h]
    slash_count = len(dived) - 2

    prev_x = 0
    for div_x in range(1, w + 1):
        for idx in range(len(dived)-1):
            prev_y = dived[idx]
            div_y = dived[idx+1]
            white = get_white(prev_y, prev_x, div_y, div_x)
            if white > k:
                break
        else:
            continue

        slash_count += 1
        if prev_x == div_x - 1:
            break
        prev_x = div_x - 1

    else:
        ans.append(slash_count)

print(min(ans))

Submission status: Accepted

Solution code:
def f(nums, K, w):
  h=len(nums)
  counter=[nums[x][0] for x in range(h)]
  if max(counter)>K:
    return float('inf')
  
  out=0
  for i in range(1, w):
    for x in range(h):
      counter[x]+=nums[x][i]
      
    if max(counter)>K:
      out+=1
      counter=[nums[x][i] for x in range(h)]
      
  return out

H, W, K=map(int, input().split())
S=[input() for _ in range(H)]
S=[[int(S[i][j]) for j in range(W)] for i in range(H)]
ans=float('inf')
for p in range(2**(H-1)):
  q='0'+format(p, '0'+str(H-1)+'b')+'1'
  i=0
  c=0
  nums=[]
  while i<H:
    j=1
    while i+j<H and q[i+j]=='0':
      j+=1
    tmp=S[i:i+j]
    nums.append([sum([tmp[y][x] for y in range(j)]) for x in range(W)])
    i+=j
    
  cand=f(nums, K, W)+q.count('1')-1
  if ans>cand:
    ans=cand
    
print(ans)

Submission status: Accepted

Solution code:
import re

H,W,K = map(int,input().split())
grid = [[0 for i in range(W+1)]]
for i in range(H):
  S = input()
  grid.append([0]+[ int(S[i]) for i in range(W) ])

#累積和gridの作成
#行について
for i in range(H+1):
  for j in range(W):
    grid[i][j+1] += grid[i][j]
#列について
for j in range(W+1):
  for i in range(H):
    grid[i+1][j] += grid[i][j]   

min_cnt = (H-1)*(W-1)
#横の区切りを作る
for h in range(2**(H-1)):
  cnt = 0
  #二進数の文字列を取得
  bin_str = format(h,"0{}b".format(H-1)) 
  #区切りのインデックスリスト
  l_p =[1]+[ x.start()+2 for x in re.finditer("1",bin_str) ] +[H+1]

  #cntに区切りの分だけ付け加える
  cnt = cnt + len(l_p) - 2
  
  ws = 0
  for w in range(1,W+1):
    for k in range(len(l_p)-1):
      if grid[l_p[k+1]-1][w]-grid[l_p[k+1]-1][w-1] > K:
        min_cnt=(H-1)*(W-1)+1
      if grid[l_p[k+1]-1][w]- (grid[l_p[k]-1][w]+grid[l_p[k+1]-1][ws]-grid[l_p[k]-1][ws]) > K:
        cnt = cnt + 1
        ws = w-1
        break    
  min_cnt = min(min_cnt,cnt)

###
print(min_cnt)

Submission status: Accepted

Solution code:
h,w,k = map(int,input().split())
s = [list(map(int,input())) for _ in range(h)]
    
ans = h*w
for div in range(1<<(h-1)):
    row = 0
    S = [[0]*w]
    S[row] = [s[0][i] for i in range(w)]
    for i in range(1,h):
        if 1&(div>>i-1):
            row += 1
            S.append([s[i][j] for j in range(w)])
        else:
            S[row] = [S[row][j]+s[i][j] for j in range(w)]
            
    count = [0]*(row+1)
    ans_ = row
    a = True
    for i in range(w):
        for j in range(row+1):
            if S[j][i] > k:
                a = False
                break
            count[j] += S[j][i]
            if count[j] > k:
                ans_+=1
                count = [0]*(row+1)
                for l in range(row+1):
                    count[l] += S[l][i]
                break
        if ans_ >= ans or a==False:
            break
    
    if a:
        ans = min(ans,ans_)

print(ans)

Submission status: Accepted

Solution code:
def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    mod=10**9+7
    H,W,K=MI()
    S=[[]for _ in range(H)]
    for i in range(H):
        S[i]=list(input())
        
    ans=10**10
    
    import itertools
    import bisect
    
    for ite in itertools.product([0,1], repeat=H):
        #高さ方向で全探索，0,1の切り替わりでグループを分ける
        g=[]#各グループの末尾列の番号
        cnt=[]#数えるよう,合計
        cnt2=[]#数えるよう,その列だけ
        now=-1
        for i in range(len(ite)):
            if ite[i]!=now:
                g.append(i-1)
                cnt.append(0)
                cnt2.append(0)
                now=ite[i]
        g.append(H-1)
        cnt.append(0)
        cnt2.append(0)
        temp=len(g)-2
        last=[0]#最後に追ったところを保存
        fl=0#Kを超えたら
        fl2=0#無理なとき
        for j in range(W):
            for k in range(len(cnt2)):
                cnt2[k]=0
            if fl2==1:
                break
            for i in range(H):
                if S[i][j]=="1":
                    num=bisect.bisect_left(g,i)
                    cnt[num]+=1
                    cnt2[num]+=1
                    if cnt[num]>K:
                        fl=1
                    
            if fl==1:
                for k in range(len(cnt)):
                    cnt[k]=cnt2[k]
                    cnt2[k]=0
                fl=0
                temp+=1
                last.append(j)
                if last[-1]==last[-2]:
                    temp=10**10
                    fl2=1
                    break
                
        #print(ite,temp,g,last)
        ans=min(ans,temp)
        
    print(ans)
                
                
                    
                    
                
        
        
    

main()

Submission status: Accepted

Solution code:
    #端から端まで割る
#h<=10に対しては全探索
#wについては極力割らない

h,w,k = map(int, input().split( ))

s= [list(map(int,list(input()))) for i in range(h)]

bit = 1<<h
ans = 10000
for b in range(bit):
    cut = [0]+[j for j in range(1,h) if (b>>j)&1]+[h]
    tmp = len(cut)-2
    white = [0]*h
    for j in range(w):
        for i in range(h): 
            white[i] += (s[i][j])&1
        for u in range(1,len(cut)):
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp += 1
                white = [s[x][j] for x in range(h)]##
            
        for u in range(1,len(cut)):###1列でもアウトな場合
            tmp2 = 0
            for t in range(cut[u-1],cut[u]):
                tmp2 += white[t]
            if tmp2>k and j:##
                tmp = 100000
                white = [s[x][j] for x in range(h)]##
                break##    
    if ans > tmp:
        ans = tmp
print(ans)

Submission status: Accepted

Solution code:
def main():
  H,W,K = map(int,input().split())
  S = [[] for _ in range(H)]
  for i in range(H):
    for s in input():
      S[i].append(int(s))
  #print(S)
  
  ans = 10000
  for i in range(2**(H-1)):
    # 横方向の割り方を全検索する。
    # T:横方向の割り方を固定したときに、同じブロック内のホワイトチョコの個数を縦方向に集約した配列。
    th = bin(i).count('1')
    T = [[0 for _ in range(W)] for _ in range(th+1)]
    ti = 0
    for j in range(H):
      for k in range(W):
        T[ti][k] += S[j][k]
      if (i>>j)&1 == 1:
        ti += 1
    #print(th,T)

    # 縦方向の1列分の中に、Kより大きい個数のホワイトチョコが含まれる場合は
    # どのように割っても条件を満たさないのでスキップする。
    f = True
    for k in range(W):
      for j in range(th+1):
        if T[j][k] > K:
          f = False
    if not f:
      continue

    # 横方向に順にホワイトチョコの数を数えていき、Kを超える場合は割る回数ans0を+1する。
    ans0 = th
    T0 = [0 for _ in range(th+1)]
    for k in range(W):
      f = True
      for j in range(th+1):
        T0[j] += T[j][k]
        if T0[j] > K:
          f = False
      if not f:
        ans0 += 1
        # 割った場合は、カウントしていたホワイトチョコの数をカレントの1列分に戻す。
        for j in range(th+1):
          T0[j] = T[j][k]
    ans = min(ans0,ans)
  print(ans)

main()

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H,W,K = map(int,input().split())
S = [input() for i in range(H)]
 
C = [[int(S[i][k]) for i in range(H)] for k in range(W)]
answer = H*W #出力がこれを超えることはない
for X in product([False,True],repeat = H-1):
  M = [[0]]
  ans = sum(X)
  if ans > answer:#初期値がanswerよりも大きかったら考える必要がない
    continue
  for i,x in enumerate(X):#配列Mの作成
    if x:
      M.append([])
    M[-1].append(i+1)
  D = [0]*len(M)
  for c in C:
    for k,m in enumerate(M):
      D[k] += sum(c[i] for i in m)#k番目の要素に足していく
      #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
    if any(d>K for d in D):#一つでもKを超えていたら
      ans += 1
      if ans >answer:
        break
      D = [sum(c[i] for i in m) for m in M]#超えた行について再び調査
      if any(d>K for d in D):
        ans = answer + 1
        #デフォルトanswerの結果より高い値にしてこの結果が出力にならないように設定する
        break
  answer = min(answer,ans)#あるXに対してanswerを算出(更新)
print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H,W,K = map(int,input().split())
S = [input() for i in range(H)]

C = [[int(S[i][k]) for i in range(H)] for k in range(W)]
answer = H*W #出力がこれを超えることはない
for X in product([True,False],repeat = H-1):
  M = [[0]]
  ans = sum(X)
  if ans > answer:#初期値がanswerよりも大きかったら考える必要がない
    continue
  for i,x in enumerate(X):#配列Mの作成
    if x:
      M.append([])
    M[-1].append(i+1)
  D = [0]*len(M)
  for c in C:
    for k,m in enumerate(M):
      D[k] += sum(c[i] for i in m)#k番目の要素に足していく
      #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
    if any(d>K for d in D):#一つでもKを超えていたら
      ans += 1
      if ans >answer:
        break
      D = [sum(c[i] for i in m) for m in M]#超えた行について再び調査
      if any(d>K for d in D):
        ans = answer + 1
        #デフォルトanswerの結果より高い値にしてこの結果が出力にならないように設定する
        break
  answer = min(answer,ans)#あるXに対してanswerを算出(更新)
print(answer)

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
A = [[int(x) for x in input()] for _ in range(H)]

def solve(blocks):
    n_block = len(blocks)
    n_cut = n_block - 1
    sums = [0 for _ in range(n_block)]

    for c in range(W):
        adds = [block[c] for block in blocks]
        if any(a > K for a in adds):
            return H * W
        
        sums = [s + a for s, a in zip(sums, adds)]
        if any(s > K for s in sums):
            n_cut += 1
            sums = adds
    
    return n_cut

ans = H * W
for mask in itertools.product([0, 1], repeat=H - 1):
    mask = [1] + list(mask) + [1]
    pivots = [r for r in range(H + 1) if mask[r]]
    blocks = [A[p1:p2] for p1, p2 in zip(pivots[:-1], pivots[1:])]
    blocks = [[sum(row[c] for row in block) for c in range(W)] for block in blocks]
    ans = min(ans, solve(blocks))
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする

total = sum(sum(c) for c in C)#すべての値の合計を算出
 
answer = H * W
for X in product([False, True], repeat=H-1):#Hは行数
  #あるXについて一回目のfor文が回る
  ans = sum(X)#Trueの数を換算
  if ans > answer:
    continue
  M = [[0]]
  for i, x in enumerate(X):
    if x:#Trueなら実行
      M.append([])#Trueの数の配列が作成される
    M[-1].append(i+1)#一番最後にその番目をappendする
  D = [0] * len(M)#初期値を設定
  for c in C:
    for k, m in enumerate(M):
      D[k] += sum(c[i] for i in m)#k番目の要素に足していく
      #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
    if any(d > K for d in D):#一つでもKを超えていたら
      ans += 1
      if ans > answer:
        break
      D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
      if any(d > K for d in D):#一つでもKを超えていたら
        ans = answer + 1#ansの更新
        break
  answer = min(answer, ans)

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする
 
total = sum(sum(c) for c in C)#すべての値の合計を算出
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):#Hは行数
    #あるXについて一回目のfor文が回る
    ans = sum(X)#Trueの数を換算
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:#Trueなら実行
        M.append([])#Trueの数の配列が作成される
      M[-1].append(i+1)#一番最後にその番目をappendする
    D = [0] * len(M)#初期値を設定
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)#k番目の要素に足していく
        #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
      if any(d > K for d in D):#一つでもKを超えていたら
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
        if any(d > K for d in D):#一つでもKを超えていたら
          ans = answer + 1#ansの更新
          break
    answer = min(answer, ans)

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
from itertools import product
 
H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
 
i = 0
while i < len(S):
  if '1' in S[i]:
    i += 1
  else:
    del S[i]
H = len(S)
 
C = [[int(s[i]) for s in S] for i in range(W)]#列を一括りにする
 
total = sum(sum(c) for c in C)#すべての値の合計を算出
 
if total <= K:
  answer = 0
else:
  answer = H * W
  for X in product([False, True], repeat=H-1):#Hは行数
    #あるXについて一回目のfor文が回る
    ans = sum(X)#Trueの数を換算
    if ans > answer:
      continue
    M = [[0]]
    for i, x in enumerate(X):
      if x:#Trueなら実行
        M.append([])#Trueの数の配列が作成される
      M[-1].append(i+1)#一番最後にその番目をappendする
    D = [0] * len(M)#初期値を設定
    for c in C:
      for k, m in enumerate(M):
        D[k] += sum(c[i] for i in m)#k番目の要素に足していく
        #Dにどんどん代入することによってどの列まで足すことができるか算出することができる
      if any(d > K for d in D):#一つでもKを超えていたら
        ans += 1
        if ans > answer:
          break
        D = [sum(c[i] for i in m) for m in M]#Dの更新(1番最初のDに戻る)
        if any(d > K for d in D):#一つでもKを超えていたら
          ans = answer + 1#ansの更新
          break
    answer = min(answer, ans)

print(answer)

Submission status: Accepted

Solution code:
def W_tips(j):
    global K,g,now,tips
    for i in range(g):
        now[i]+=tips[i][j]
    for i in range(g):
        if now[i] > K:
            return False
    return True

f_inf=float("inf")
H,W,K=map(int,input().split())
S=[list(map(int,list(input()))) for _ in range(H)]
ans = f_inf
for div in range(1 << (H-1)):
    g=0
    tips=[[0]*W]
    tips[g]=[s+b for s, b in zip(S[0],tips[g])]
    for i in range(1,H):
        if div >> (i-1) &1:
            g+=1
            tips.append([0]*W)
        tips[g]=[s + b for s, b in zip(S[i],tips[g])]
    num=g
    g+=1
    now=[0]*g
    for j in range(W):
        if W_tips(j)==False:
            num+=1
            now=[0]*g
            if W_tips(j)==False:
                num=f_inf
                break
    ans=min(ans,num)
print(ans)

Submission status: Accepted

Solution code:
def read():
    H, W, K = list(map(int, input().strip().split()))
    S = list()
    for i in range(H):
        s = list(map(int, input()))
        S.append(s)
    return H, W, K, S


def init_n_splits(H, ptn):
    n_splits = 0
    for h in range(1, H):
        if ptn & 1 == 1:
            n_splits += 1
        ptn >>= 1
    return n_splits


def check_first_column(w, H, K, ptn, S):
    k = [0 for h in range(H)]
    k[0] = S[0][w]
    if k[0] > K:
        return [-1 for h in range(H)]
    for h in range(1, H):
        if ptn & 1 == 1:
            k[h] = S[h][w]
        else:
            k[h] = S[h][w] + k[h-1]
        if k[h] > K:
            return [-1 for h in range(H)]
        ptn >>= 1
    return k


def check_next_column(w, H, K, ptn, S, prev):
    k = [0 for h in range(H)]
    k[0] = S[0][w]
    if k[0] + prev[0] > K:
        return [-1 for h in range(H)]
    for h in range(1, H):
        if ptn & 1 == 1:
            k[h] = S[h][w]
        else:
            k[h] = S[h][w] + k[h-1]
        if k[h] + prev[h] > K:
            return [-1 for h in range(H)]
        ptn >>= 1
    return [i + j for i, j in zip(k, prev)]


def solve(H, W, K, S, INF=10000000):
    ptns = 2 ** (H-1)
    min_n_splits = W * H
    for ptn in range(ptns):
        update = True
        n_splits = init_n_splits(H, ptn)
        ret = check_first_column(0, H, K, ptn, S)
        if ret[0] == -1:
            update = False
        else:
            for w in range(1, W):
                prev = ret
                ret = check_next_column(w, H, K, ptn, S, prev)
                if ret[0] == -1:
                    n_splits += 1
                    ret = check_first_column(w, H, K, ptn, S)
                    if ret[0] == -1:
                        update = False
                        break
        if update:
            min_n_splits = min(n_splits, min_n_splits)
    return min_n_splits

if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
S = [input() for _ in range(H)]
ans = 1e4
for t in itertools.product([0, 1], repeat=H-1):
    cnt = t.count(1)
    SW = []
    tmp = [int(s) for s in S[0]]
    for i, c in enumerate(t):
        if c:
            SW.append(tmp)
            tmp = [int(s) for s in S[i+1]]
        else:
            tmp = [tmp[j] + int(S[i+1][j]) for j in range(W)]
    SW.append(tmp)
    H_ = len(SW)
    sums = [0] * H_
    if max(itertools.chain.from_iterable(SW)) > K:
        continue
    for w in range(W):
        sumtmp = [sums[i] + SW[i][w] for i in range(H_)]
        if max(sumtmp) > K:
            cnt += 1
            sums = [SW[i][w] for i in range(H_)]
        else:
            sums = sumtmp
    ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
H,W,K=map(int,input().split())
S=[[] for i in range(0,H)]
for i in range(0,H):
    S[i]=input()

sumtable=[[0 for i in range(0,W)] for j in range(0,H+1)]
for i in range(1,H+1):
    for j in range(0,W):
        sumtable[i][j]=sumtable[i-1][j]+(int(S[i-1][j])&1)


ans=10**4
for i in range(0,2**(H-1)):
    segment=[]
    start=0
    end=0
    for j in range(0,H-1):
        if (i>>j) & 1==1:
            end=j
            segment.append((start,end))
            start=end+1
    segment.append((start,H-1))
    white=[0 for j in range(0,len(segment))]
    count=0
    for j in range(0,W):
        for k in range(0,len(segment)):
            start,end=segment[k]
            white[k]+=sumtable[end+1][j]-sumtable[start][j]
        if max(white)>K:
            count+=1
            for k in range(0,len(segment)):
                start,end=segment[k]
                white[k]=sumtable[end+1][j]-sumtable[start][j]
            if max(white)>K:
                break
    else:
        test=count+len(segment)-1
        if test<ans:
            ans=test

print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
S = [ [ int(i) for i in input()] for _ in range(h) ]
res = 10**4
for i in range( 1<<(h-1) ):
    pos = [0]*h
    x = 0
    for j in range(h-1):
        if i & ( 1 << j ):
            x += 1
        pos[j+1] = x

    ret = x
    x = 0
    cnt = [0]*h
    flag = 0
    while x < w:
        for y in range(h):
            cnt[pos[y]] += S[y][x]
            if cnt[pos[y]] > k:
                cnt = [0]*h
                ret += 1
                flag += 1
                break
        else:
            x += 1
            flag = 0

        if flag == 2:
            ret = 10**4
            break

    res = min(res, ret)
print(res)

Submission status: Accepted

Solution code:
H,W,K = map(int,input().split())
A = [0]*H
for i in range(H):
    A[i] = input()
s = 10000
for i in range(2**(H-1)):
    count = 0
    B = [0]*H
    B[H-1] = 1
    for j in range(H-1):
        if ((i >> j) & 1):
            B[j] = 1
            count += 1
    C = [0]*(count + 1)
    for j in range(W):
        a = [0]*(count + 1)
        n = 0
        max = C[0]
        maxa = a[0]
        for k in range(H):
            a[n] += int(A[k][j])
            C[n] += int(A[k][j])
            if B[k] == 1:
                if max < C[n]:
                    max = C[n]
                if maxa < a[n]:
                    maxa = a[n]
                n += 1
        if max > K:
            count += 1
            C[:] = a[:]
        if maxa > K:
            count = 10000
            break
    if s > count:
        s = count
print(s)

Submission status: Accepted

Solution code:
H, W, K = map(int, input().split())
S = [0] * H
INF = 1000000

for h in range(H):
    S[h] = list(input())


def check(divH):
    MAP = [0] * H
    BitDivH = "".join(["{:0", str(H - 1), "b}"]).format(divH)
    cnt = 0
    for i, bit in enumerate(BitDivH):
        if bit == "1":
            cnt += 1
            MAP[i + 1] = cnt
        else:
            MAP[i + 1] = cnt
    after_tmp = [0] * (MAP[-1] + 1)
    cnt = 0
    out = 0
    for w in range(W):
        for h in range(H):
            after_tmp[MAP[h]] += int(S[h][w])
        for af in after_tmp:
            if af > K:
                out = 1
                break
        else:
            after_tmp = [0] * (MAP[-1] + 1)
    if out == 1:
        return INF
    else:
        for w in range(W):
            for h in range(H):
                after_tmp[MAP[h]] += int(S[h][w])
            for af in after_tmp:
                if af > K:
                    cnt += 1
                    after_tmp = [0] * (MAP[-1] + 1)
                    for h2 in range(H):
                        after_tmp[MAP[h2]] += int(S[h2][w])
                    break
        return cnt + MAP[-1]

MIN = INF
for i in range(2**(H - 1)):
    MIN = min(MIN, check(i))

print(MIN)