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 e_dividing_chocolate():
    # 参考: https://note.com/tanon_cp/n/ne70a87d249ed
    H, W, K = [int(i) for i in input().split()]
    Choco = [list(input()) for _ in range(H)]

    # 左上のマスを (0, 0)、右下のマスを (col, row) としたとき、2 点で張られる
    # 長方形区間の内部に含まれる 1 (ホワイトチョコレートのマス) の数を累積和で管理
    cumsum = [[0] * W for _ in range(H)]
    for row in range(H):
        for col in range(W):
            if Choco[row][col] == '1':
                cumsum[row][col] += 1
            if row != 0:
                cumsum[row][col] += cumsum[row - 1][col]
            if col != 0:
                cumsum[row][col] += cumsum[row][col - 1]
            if row != 0 and col != 0:
                cumsum[row][col] -= cumsum[row - 1][col - 1]

    def count_white_chocolate(x1, y1, x2, y2):
        """左上のマスを (x1, y1)、右下のマスを (x2, y2) としたとき、2 点で張られる
        長方形区間の内部に含まれる 1 (ホワイトチョコレートのマス) の数"""
        ret = cumsum[y2][x2]
        if x1 != 0:
            ret -= cumsum[y2][x1 - 1]
        if y1 != 0:
            ret -= cumsum[y1 - 1][x2]
        if x1 != 0 and y1 != 0:
            ret += cumsum[y1 - 1][x1 - 1]
        return ret

    ans = (H - 1) + (W - 1)  # 1 マスに分けてしまえば要求を満たすことは保証されている
    # 横の切り方は全探索する
    for bits in range(1 << (H - 1)):
        count = 0  # 何回チョコに切り込みを入れたか？

        # 横の切り込みをどこに入れるかを決める
        cut_row = []
        cut_flag = format(bits, 'b')[::-1]
        for k, flag in enumerate(cut_flag):
            if flag == '1':
                count += 1
                # k 行目と (k+1) 行目の間を切るとき、長方形区間の最下段は k 行目
                cut_row.append(k)
        cut_row.append(H - 1)  # チョコ全体での最下段も加えておく

        # col1-col2 の間は切り込みを入れないでもホワイトチョコが K 個以下である
        col1 = 0
        for col2 in range(W - 1):
            row1 = 0
            for row2 in cut_row:
                if count_white_chocolate(col1, row1, col2, row2) > K:
                    count = float('inf')  # 現在の横の切り込みの入れ方では要求を満たせない

                # col2 列目と col2+1 列目の間に縦に切り込みを入れなければならない
                if (count_white_chocolate(col1, row1, col2, row2) <= K
                        and count_white_chocolate(col1, row1, col2 + 1, row2) > K):
                    # ここで縦に切り込みを入れ、右の区画へ移動
                    count += 1
                    col1 = col2 + 1
                    break
                row1 = row2 + 1  # 下の区画へ移動

        # 最後に縦に切り込みを入れた区画の右の区画はまだ調べていないので、調べる
        row1 = 0
        for row2 in cut_row:
            if count_white_chocolate(col1, row1, W - 1, row2) > K:
                count = float('inf')
            row1 = row2 + 1

        ans = min(ans, count)
    return ans

print(e_dividing_chocolate())

Submission status: Accepted

Solution code:
import itertools
 
H,W,K=map(int, input().split())
S=[]
for _ in range(H):
  S.append([int(s) for s in input()])
 
ans=2000
for t in itertools.product([0,1],repeat=H-1):
  cnt=t.count(1)
  lst=[[s for s in S[0]]]
  for h in range(H - 1):
    if t[h]==1:
      lst.append(S[h+1])
    else:
      lst[-1]=[lst[-1][i]+S[h+1][i] for i in range(W)]
  L=len(lst)
  R=[0]*L
  for w in range(W):
    if max(lst[i][w] for i in range(L))>K:
      break
    tmp=[R[i]+lst[i][w] for i in range(L)]
    if max(tmp)>K:
      cnt+=1
      R=[lst[i][w] for i in range(L)]
    else:
      R=tmp
  else:
    ans=min(ans,cnt)
print(ans)

Submission status: Accepted

Solution code:
h, w, k = map(int, input().split())
s = [[0] * (w+1)] + [[0] + list(map(int, list(input()))) for _ in range(h)]

c = [[0 for _ in range(w+1)] for _ in range(h+1)]

for i in range(1, h+1):
    temp = 0
    for j, x in enumerate(s[i]):
        temp += x
        c[i][j] = c[i-1][j] + temp

inf = float('inf')
ans = inf
mb = 1 << (h-1)
for i in range(1 << (h-1)):
    b = list(map(int, list(reversed(bin(mb + i)[2:]))))
    temp = sum(b) - 1
    L = 0
    #print(b)
    for R in range(1, w+1):
        U = 0
        for D in range(1, h+1):
            if b[D-1] == 1:
                if c[D][R] - c[U][R] - c[D][L] + c[U][L] > k:
                    #print(c[D][R],c[U][R],c[D][L],c[U][L])
                    if R - L == 1:
                        temp = inf
                    else:
                        temp += 1
                    L = R - 1
                    break
                U = D
        #print(temp)
        if temp == inf:
            break
    ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools
h, w, k = [int(i) for i in input().split()]
choco = ([input() for j in range(h)])
ans = float("inf")

for i in itertools.product([0,1], repeat=h-1):
    list_yoko = []
    list_temp = []
    list_temp.append(0)
    for j in range(h-1):
        if i[j] == 1:
            list_yoko.append(list_temp)
            list_temp = []
            list_temp.append(j+1)
        else:
            list_temp.append(j+1)
    else:
        list_yoko.append(list_temp)


    count = 0
    count_list = [0 for _ in range(len(list_yoko))]

    for j in range(w):
        count_list_ = [0 for _ in range(len(list_yoko))]

        for m in range(len(list_yoko)):
            for l in list_yoko[m]:
                count_list_[m] += int(choco[l][j])

        if max(count_list) > k :
            count = float("inf")

        else:
            if max([count_list[_] + count_list_[_] for _ in range(len(list_yoko))]) > k:
                count += 1
                count_list = count_list_[:]

            else:
                count_list = [count_list[_] + count_list_[_] for _ in range(len(list_yoko))]

    ans = min(count+sum(i), ans)

print(ans)

Submission status: Accepted

Solution code:
from itertools import accumulate
import sys
input = sys.stdin.readline

H, W, K = map(int, input().split())
S = [list(map(int, input().rstrip())) for _ in range(H)]
cum = [list(accumulate(S[i])) for i in range(H)]
ans = float('inf')
for bit in range(1 << (H-1)):
    cnt = 0
    prev = -1
    for h in range(H-1):
        cnt += (bit >> h) & 1
    bit += 1 << (H-1)
    w = 0
    while w < W:
        s = 0
        cut = False
        for h in range(H):
            s += cum[h][w] - (cum[h][prev] if prev >= 0 else 0)
            if bit >> h & 1:
                if s > K:
                    cut = True
                    break
                s = 0
        if cut:
            if w-1 == prev:
                break
            cnt += 1
            prev = w-1
        else:
            w += 1
    else:
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])
#print(rui)

ans = MAX_INT
for x in range(1<<(H-1)):
  l = 0
  num = 0
  for h in range(H-1):
    if (x >> h) & 1 == 1: # 割る
      num += 1

  for w in range(W):
    # 1行で割れるか判定
    judge = int(a[0][w])
    for h in range(H-1):
      if (x >> h) & 1 == 0: # 割らない
        judge += int(a[h+1][w])
      else: # 割る
        judge = 0
        judge += int(a[h+1][w])
      if judge > K: #どうやって割ってもダメ
        break
    else:
      continue
    break
  else:
    cnt = 0
    for w in range(W):
      #print("w:",w)
      cnt = rui[0][w+1] - rui[0][l]
      if cnt > K:
        num += 1
        l = w
        #print("break1")
        continue

      for h in range(H-1):
        #print("cnt",cnt)
        if (x >> h) & 1 == 0: # 割らない
          cnt += rui[h+1][w+1] - rui[h+1][l]
        else: # 割る
          cnt = rui[h+1][w+1] - rui[h+1][l]
        #print(rui[h+1][w+1],rui[h+1][l])

        if cnt > K:
          num += 1
          l = w
          #print("break")
          break
      #print("--")
    else:
      ans = min(ans, num)
      #print(num)

print(ans)

Submission status: Accepted

Solution code:
import sys
 
MAX_INT = int(10e15)
MIN_INT = -MAX_INT
mod = 1000000007
sys.setrecursionlimit(1000000)
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

H,W,K = IL()
a = [list(S()) for i in range(H)]

nnn = 0
for i in range(H):
  for j in range(W):
    nnn += int(a[i][j])
else:
  if nnn <= K:
    print(0)
    exit()

rui = [[0]*(W+1) for i in range(H)]
for i in range(H):
  for j in range(W):
    rui[i][j+1] = rui[i][j] + int(a[i][j])
#print(rui)
ans = MAX_INT
for x in range(1<<(H-1)):
  l = 0
  num = 0
  for h in range(H-1):
    if (x >> h) & 1 == 1: # 割る
      num += 1

  for w in range(W):
    # 1行で割れるか判定
    judge = int(a[0][w])
    for h in range(H-1):
      if (x >> h) & 1 == 0: # 割らない
        judge += int(a[h+1][w])
      else: # 割る
        judge = 0
        judge += int(a[h+1][w])
      if judge > K: #どうやって割ってもダメ
        break
    else:
      continue
    break
  else:
    cnt = 0
    for w in range(W):
      #print("w:",w)

      cnt = rui[0][w+1] - rui[0][l]
      if cnt > K:
        num += 1
        l = w
        #print("break1")
        continue
      for h in range(H-1):
        #print("cnt",cnt)
        if (x >> h) & 1 == 0: # 割らない
          cnt += rui[h+1][w+1] - rui[h+1][l]
        else: # 割る
          cnt = rui[h+1][w+1] - rui[h+1][l]
        #print(rui[h+1][w+1],rui[h+1][l])

        if cnt > K:
          num += 1
          l = w
          #print("break")
          break
      #print("--")
    else:
      ans = min(ans, num)
      #print(num)
print(ans)

Submission status: Accepted

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

h, w, K = [int(x) for x in input().split()]
s = [input().rstrip() for _ in range(h)]
# print(s)
# print(len(s[1]))

# ans = h + w - 2
ans = h + w - 2
for i in range(2 ** (h - 1)):
    new_s = []
    cnt = 0
    i_bin = bin(i)[2:].zfill(h - 1)
    add = []
    for j in range(h - 1):
        if i_bin[j] == "1":
            cnt += 1
            add.append(s[j])
            new_s.append(add)
            add = []
        else:
            add.append(s[j])
        if j == h - 2:
            add.append(s[-1])
            new_s.append(add)
    if h == 1:
        new_s = [s]
    #print(len(new_s))
    total = [0] * len(new_s)
    #print(new_s)
    for k in range(w):
        # print(k)
        tmp_list = [0]*len(new_s)
        #print(total)
        flag = 0
        for l in range(len(new_s)):
            tmp = sum([int(new_s[l][x][k]) for x in range(len(new_s[l]))])
            # tmp_list[l] = tmp
            # print(tmp)
            if tmp > K:
                cnt = 10**18
                flag = 1
                break
            tmp_list[l] = tmp
            total[l] += tmp
        if flag:
            break
        for m in total:
            flag_2 = 1
            if m > K:
                cnt += 1
                total = tmp_list
                flag_2 = 0
                break
        # if flag_2:
        #     for m in total:
        #         if m == K and k != w - 1:
        #             cnt += 1
        #             total = [0]*len(new_s)
        #             break
    if not flag:
        #print(cnt)
        ans = min(ans, cnt)
print(ans)

Submission status: Accepted

Solution code:
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
import numpy as np
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

def main():
	H, W, K = MAP()
	S = np.array([list(map(int, list(input()))) for _ in range(H)])

	ans = INF
	for x in product([0, 1], repeat=H-1):
		cut = np.sum(x)
		if cut >= ans:
				continue
		r = 0
		l = []
		for i in range(H-1):
			if x[i]:
				l.append(np.sum(S[r:i+1, :], axis=0))
				r = i + 1
		l.append(np.sum(S[r:, :], axis=0))
		l = np.array(l)
		if np.max(l) > K:
			continue
		tmp = np.zeros(len(l), dtype=int)
		for i in range(W):
			tmp += l[:, i]
			if np.max(tmp) > K:
				cut += 1
				tmp = l[:, i]
			if cut >= ans:
				break

		ans = ans if ans <= cut else cut

	print(ans)

if __name__ == '__main__':
	main()

Submission status: Accepted

Solution code:
from operator import add
import sys
sys.setrecursionlimit(10 ** 7)

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# AC
# 解説見た
# 半分全列挙
# bit全探索

H, W, K = map(int, input().split())
MEIJI = []
for _ in range(H):
    MEIJI.append(list(map(int, list(input()))))

# 全部のカットを試す
INF = 10 ** 5
ans = INF
for h in range(2 ** (H - 1)):
    # 先に横の分割の数
    row = 1
    for i in range(H - 1):
        row += (h >> i) & 1

    num_cut = row - 1
    cnt = [0] * row

    #print("cut == ", h, "row == ", row)

    # 列は貪欲にカット
    for c in range(W):
        idx = 0
        tmp_cnt = [0] * row
        for r in range(H):

            if r != 0 and (h >> r - 1) & 1:
                idx += 1

            tmp_cnt[idx] += MEIJI[r][c]

        # チェック
        new_cnt = list(map(add, cnt, tmp_cnt))

        if any([K < x for x in new_cnt]):
            # 1行だけでもK以下が作れないならばbreak
            if any([K < x for x in tmp_cnt]):
                num_cut = INF
                break

            cnt = tmp_cnt
            num_cut += 1
        else:
            cnt = new_cnt

        #print("column:", c, tmp_cnt)

    ans = min(num_cut, ans)

print(ans)

Submission status: Accepted

Solution code:
import sys


def input():
    return sys.stdin.readline().strip()


def get_sum(x1, x2, y1, y2):
    return acc[x2][y2] - acc[x1][y2] - acc[x2][y1] + acc[x1][y1]


h, w, k = map(int, input().split())
s = [[int(c) for c in input()] for i in range(h)]

acc = [[0 for j in range(w + 1)] for i in range(h + 1)]
for i in range(h):
    for j in range(w):
        acc[i + 1][j + 1] = acc[i][j + 1] + acc[i + 1][j] - acc[i][j] + s[i][j]

ans = h + w

for h_div in range(1 << (h - 1)):
    h_ranges = []
    h_begin = 0
    for i in range(h - 1):
        if h_div >> i & 1:
            h_ranges.append([h_begin, i + 1])
            h_begin = i + 1
    h_ranges.append([h_begin, h])
    div_cnt = len(h_ranges) - 1

    def is_addable():
        for h_range in h_ranges:
            if get_sum(h_range[1], h_range[0], j + 1, w_begin) > k:
                return False
        return True

    w_begin = 0
    for j in range(w):
        if not is_addable():
            w_begin = j
            div_cnt += 1
            if not is_addable():
                div_cnt = h + w
                break
    ans = min(ans, div_cnt)

print(ans)

Submission status: Accepted

Solution code:
def main():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = float('inf')
    for i in range(2 ** (H - 1)):
        group = 0
        h_id = [0] * H
        for j in range(H):
            h_id[j] = group
            if i >> j & 1:
                group += 1
        
        group += 1
        c = [[0] * W for _ in range(group)]
        for h in range(H):
            for w in range(W):
                c[h_id[h]][w] += S[h][w]
        g_flag = True
        for g in range(group):
            for w in range(W):
                if c[g][w] > K:
                    g_flag = False

        if not g_flag:
            continue

        cnt = group - 1
        now = [0] * group
        flag = True
        for w in range(W):
            for g in range(group):
                now[g] += c[g][w]
                if now[g] > K:
                    flag = False
                    cnt += 1
                    break
            
            if not flag:
                for g in range(group):
                    now[g] = c[g][w]
                flag = True
        ans = min(ans, cnt)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 足し合わせしすぎてるのでTLE
import sys
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    grid = [list(map(int, list(input().strip()))) for _ in range(H)]

    # 折れる箇所全部で折った数が最大値
    ans = (H - 1) * (W - 1)

    # 横線で割るパターン全てについて縦線での降り方を考える
    for i in range(2 ** (H - 1)):
        snap = 0

        # 横線で折った後に縦線でみたときのwcの数を計算しておく
        hori_grid = [grid[0]]
        for j in range(H - 1):
            if ((i >> j) & 1):
                hori_grid.append(grid[j+1])
                snap += 1
            else:
                hori_grid[-1] = [a + b for a,b in zip(hori_grid[-1], grid[j+1])]

        # 先頭列のwcの数を保存
        wc_count = [hori_grid[y][0] for y in range(snap + 1)]

        # 最初の列で超えてる場合はスキップ
        if max(wc_count) > K:
            continue

        # 横方向にみていき、制限をこえたらその前の縦線で折る
        for x in range(1, W):
            now_wc_count = [hori_grid[y][x] for y in range(len(wc_count))]
            next_wc_count = [a+b for a,b in zip(wc_count, now_wc_count)]

            if max(next_wc_count) > K:
                # 超えてるのでおる。折った箇所より左側は無視
                snap += 1
                wc_count = now_wc_count
            else:
                # おらないので、wcの数に単純に加算したものをwcの数としてみる
                wc_count = next_wc_count

        ans = min(ans, snap)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# 足し合わせしすぎてるのでTLE
import sys
input = sys.stdin.readline

def main():
    H, W, K = map(int, input().split())
    grid = [list(map(int, list(input().strip()))) for _ in range(H)]

    # 折れる箇所全部で折った数が最大値
    ans = (H - 1) * (W - 1)

    # 横線で割るパターン全てについて縦線での降り方を考える
    for i in range(2 ** (H - 1)):
        snap = 0

        hori_grid = [grid[0]]
        for j in range(H - 1):
            if ((i >> j) & 1):
                hori_grid.append(grid[j+1])
                snap += 1
            else:
                hori_grid[-1] = [a + b for a,b in zip(hori_grid[-1], grid[j+1])]

        wc_count = [hori_grid[y][0] for y in range(snap + 1)]

        # 最初の列で超えてる場合はスキップ
        if max(wc_count) > K:
            continue

        for x in range(1, W):
            now_wc_count = [hori_grid[y][x] for y in range(len(wc_count))]
            next_wc_count = [a+b for a,b in zip(wc_count, now_wc_count)]

            if max(next_wc_count) > K:
                snap += 1
                wc_count = now_wc_count
            else:
                wc_count = next_wc_count

        ans = min(ans, snap)

    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
from itertools import accumulate, combinations

def I(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LMI(): return list(map(int, sys.stdin.readline().split()))
MOD = 10 ** 9 + 7
INF = float('inf')


H, W, K = MI()
S = [[int(x) for x in list(input())] for _ in range(H)]


def fn(bits):
    slice = 0
    n = bin(bits).count("1")
    block_cnts = [0] * n
    for j in range(W):
        sec = 0
        col_cnts = [0] * n
        for i in range(H):
            col_cnts[sec] += S[i][j]
            if col_cnts[sec] > K:
                return -1
            if (bits >> i) & 1:
                sec += 1
        if all(block_cnts[sec] + col_cnts[sec] <= K for sec in range(n)):
            for sec in range(n):
                block_cnts[sec] += col_cnts[sec]
        else:
            slice += 1
            block_cnts = col_cnts
    return slice


ans = INF
for bits in range(1 << (H - 1)):
    hslice = bin(bits).count("1")
    wslice = fn(bits + (1 << (H - 1)))
    if wslice > -1:
        ans = min(ans, hslice + wslice)
print(ans)

Submission status: Accepted

Solution code:
def getChoco(choco, w, t):
  for h in range(H):
    if S[h][w] == '1':
      choco[t[h]] += 1
  return choco

def solve(i):
  t = dict()
  t[0] = 0
  g = 0 # group index
  for h in range(H-1):
    if (i>>h)%2 == 1: 
      g += 1 # バイナリ表示したときに1となる桁で区切る（次のグループに移る）
      t[h+1] = g
    else:
      t[h+1] = g
  
  ret = g
  choco = [0 for _ in range(g+1)]
  # print(i, t, choco)
  for w in range(W):
    choco = getChoco(choco,w,t)
    if any(c>K for c in choco):
      # 分割を実行（chocoをリセット，wの分割を1増やす）
      choco = getChoco([0 for _ in range(g+1)],w,t)
      if any(c>K for c in choco): 
        return 10**9 # 分割した直後に条件を満たさない場合には，H方向の分割が不足しているため，解とならない
      else:
        ret += 1
  return ret

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

ans = H + W - 2
for i in range(2**(H - 1)):
    ans = min(ans, solve(i))
print(ans)

Submission status: Accepted

Solution code:
import sys, itertools
input = sys.stdin.readline
H, W, K = list(map(int, input().split()))

choco = []
for i in range(H):
  s = input().strip()
  a = list(map(int, list(s)))
  choco.append(a)

def min_split(h):
  sum_cnt = [0] * H
  num_split = 0
  for j in range(W):
    c = 0
    cnt = [0] * H
    flag = False
    for i in range(H):
      if choco[i][j] == 1:
        cnt[c] += 1
        if cnt[c] > K:
          return float('inf')
        if cnt[c] + sum_cnt[c] > K:
          flag = True
      if i < H-1 and h[i] == 1:
        c += 1
    if flag:
      num_split += 1
      sum_cnt = cnt
    else:
      for i in range(len(cnt)):
      	sum_cnt[i] += cnt[i]
  return num_split + sum(h)

min_m = float('inf')
for h in itertools.product([0,1], repeat=H-1):
  m = min_split(h)
  min_m = min(min_m, m)
print(min_m)

Submission status: Accepted

Solution code:
#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    H, W, K = iim()
    S = [input() for i in range(H)]
    C = "1"

    H1, W1 = H+1, W+1
    S1 = [[0] * (W1) for i in range(H1)]
    ans = 0

    for i in range(1, H1):
        for j in range(1, W1):
            S1[i][j] = S1[i-1][j] + S1[i][j-1] - S1[i-1][j-1] + (1 if S[i-1][j-1] == C else 0)

    #for s1 in S1: print(s1)
    if S1[-1][-1] < K:
        print(0)
        return

    inf = H+W
    ans = inf
    ii = [0] + [1<<i for i in range(H)]
    cnt = 0
    H2 = 1<<H
    for i in range(H2>>1, H2):
        i0 = j0 = 0
        jx = W
        cnt = bin(i).count("1") - 1
        ng = False
        while j0 < W:
            i0 = 0
            for i1 in range(1, H1):
                k = ii[i1]
                if i & k:
                    for j1 in range(j0+1, W1):
                        cx = S1[i1][j1] - S1[i1][j0] - S1[i0][j1] + S1[i0][j0]
                        if cx > K:
                            j1 -= 1
                            break
                    break

            if j1 == j0:
                ng = True
                break


            i0, jx = i1, j1
            for i1 in range(i1, H1):
                k = ii[i1]
                if i & k:
                    for j1 in range(jx, j0, -1):
                        cx = S1[i1][j1] - S1[i1][j0] - S1[i0][j1] + S1[i0][j0]
                        if cx <= K:
                            jx = j1
                            break
                    else:
                        ng = True
                        break
                    i0 = i1
            if ng:
                break
            j0 = jx
            cnt += 1

            if ans <= cnt:
                ng = True
                break

        if not ng:
            ans = cnt
    print(ans-1)


if __name__ == "__main__":
    resolve()

Submission status: Accepted

Solution code:
import sys
h, w, k = map(int, sys.stdin.readline().split())
graph = [list(sys.stdin.readline().rstrip()) for _ in range(h)]
ans = 10**9+1

for div in range(2**(h-1)):
    # 1. 縦で切った時のグループ数を計算する
    id = [0] * h # 各行がどのグループに属しているか記録する
    group = 0 # グループの番号
    for j in range(h):
        id[j] = group
        if (div >> j) & 1:
            group += 1
    group += 1

    # 2. グループの各行にある白チョコ数を出す
    c = [[0] * w for _ in range(group)]
    for j in range(w):
        for i in range(h):
            if graph[i][j] == '1':
                c[id[i]][j] += 1

    temp = group-1 # このdivにおける分割回数
    now = [0] * group # 探索中に各グループが持つ白チョコ数を格納

    def add(now, j):
        # 各グループへ白チョコの数を反映
        for i in range(group):
            now[i] += c[i][j]

    def judge(now):
        # 現在のグループ分けで白チョコがk個以下か判定する
        for i in range(group):
            if now[i] > k: return False
        return True

    # 3. 横方向に探索し、グループがk個を超えたら分割する
    for j in range(w):
        add(now, j)
        if not judge(now):
            # k個を超えた→分割したとしてnowを初期化
            temp += 1
            now = [0] * group

            # k個以下を満たせない場合を検出する
            add(now, j)
            if not judge(now):
                temp = 10**9 + 1
                break

    ans = min(ans, temp)

print(ans)

Submission status: Accepted

Solution code:
import itertools

h, w, k = map(int, input().split())
s = [input() for _ in range(h)]

divide = list(itertools.product([0, 1], repeat=h-1))

MIN = 10**10
for d in divide:
    SUM = [0]*(sum(d)+1)
    ans = 0
    reset = False
    ok = True

    for i in range(w):
        # start
        now = 0
        for g in range(h-1):
            if d[g] == 0:
                if s[g][i] == '1':
                    SUM[now] += 1

            elif d[g] == 1:
                if s[g][i] == '1':
                    SUM[now] += 1
                now += 1
        if s[-1][i] == '1':
            SUM[-1] += 1
        # end

        for l in SUM:
            if l > k:
                reset = True
                break

        if reset:
            reset = False
            ans += 1
            SUM = [0]*(sum(d)+1)
            # start
            now = 0
            for g in range(h-1):
                if d[g] == 0:
                    if s[g][i] == '1':
                        SUM[now] += 1

                elif d[g] == 1:
                    if s[g][i] == '1':
                        SUM[now] += 1
                    now += 1
            if s[-1][i] == '1':
                SUM[-1] += 1
            # end
            for l in SUM:
                if l > k:
                    ok = False
                    break
        if ok is False:
            break
    if ok:
        MIN = min(MIN, ans+sum(d))

print(MIN)

Submission status: Accepted

Solution code:
#ABC159-E Dviding Chocolate
"""
(ループで変数kを使いたい為、入力kはgとして受け取っているので注意)
process1:
まず、Hの制約が10以下であることから、どこで分割するかをbit全探索する。(最大2**9回)
次にresを空のリストで用意し、分割数だけ累積和で圧縮した横方向のチョコレートを入れる。
分割されたそれぞれのチョコレートについて、累積和をとったので、例えば
1101
0101　のように分割されたチョコレートは、
↓
1202　というように1行に圧縮して表される。

process2-#1:
次に、それぞれの部分チョコレートについて、それぞれの一列が条件を満たしているかどうかを調べる
必要があるが、これは後回しにする。

process3:
実際に縦方向に最低何分割する必要があるかをサーチする。この時、各部分チョコレートについて
回してしまうと、最適な分割数を求めることができない。
横方向にループを回して、すべての部分チョコレートについて並行にサーチし、初めてg > count
(countは1の数)となってしまった列で分割数を+1し、縦方向の分割数(これはblstの各要素の1の数
から求める。)との合計をとってansを更新する。

process2-#2:
さてここで、process3の分割の条件は"各部分チョコレートについて、初めて条件を満たさなくなった時
に分割を増やす"であったが、既に1列がg >= countを満たさない場合、どのように縦方向で分割しても
条件を満たさないので、これは横方向の分割の時点で弾かなければならない。
例；
3 4 1
1101
0001
0001
横方向に必ず3分割しないと条件を満たさないので、他のものを弾く。
"""
import sys
readline = sys.stdin.buffer.readline

h,w,g = map(int,readline().split())

maze = []
for i in range(h):
    s = readline().rstrip().decode('utf-8')
    maze.append(s)

#ビット全探索
def bit_list(dig): #引数に何桁かを入れる
    lst = []
    for i in range(2**dig):
        lst.append(list(format(i,"b").zfill(dig)))
    return lst
#帰ってくるのは[[0,0,1],[0,1,0],[0,1,1],[1,0,0]...[1,1,1]]のようなリスト

blst = bit_list(h-1) #どこで分割するかが入っているリスト
ans = 10**9

for i in range(len(blst)):
    res = []
    lst1 = [0]*w
    #process1
    for k in range(w): #分割数はn-1なので、最初の1行目は手動で
                lst1[k] += 1 if maze[0][k] == "1" else 0
    
    for index,j in enumerate(blst[i],1):
        if j== "0": #分割しない
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
        else:
            res.append(lst1)
            lst1 = [0]*w
            for k in range(w):
                lst1[k] += 1 if maze[index][k] == "1" else 0
    
    res.append(lst1)

    #process2
    #横分割しなかった部分について、縦分割することで必ず条件を満たせる必要がある。
    flag = 0
    for j in res:
        if any(k > g for k in j):
            flag = 1
            break
    if flag:
        continue

    #process3
    w_cut = 0
    count = [0]*len(res)
    for j in range(w):
        now_count = [0]*len(res)
        for index,k in enumerate(res):
            count[index] += k[j]
            now_count[index] += k[j]
        if any(l > g for l in count):
            count = now_count
            w_cut += 1


    ans = min(ans,blst[i].count("1")+w_cut)

print(ans)

Submission status: Accepted

Solution code:
import itertools

H, W, K = map(int, input().split())
S = []
for _ in range(H):
    S.append([int(s) for s in input()])
    #行ごと指定できるのが良い

ans = 2000
for t in itertools.product([0, 1], repeat=H - 1):
    cnt = t.count(1)
    #print(cnt)
    lst = [[s for s in S[0]]]
    for h in range(H - 1):
        #(H-1)にしたのはｔにあわせるため
        #print(lst
        #th=1:切ってる、th=0、切ってない
        if t[h]:
            lst.append(S[h + 1])
            #一つしたの段の要素をリストごと足していることで後で網羅
        else:
            lst[-1] = [lst[-1][i] + S[h + 1][i] for i in range(W)]
            #既存の最後の要素に一つ下の段の要素を足している
        #print(lst)
    L = len(lst)
    #print(L)
    sum_lst = [0] * L
    #とりあえずゼロ配列作るプラス要素数を可変にする
    for w in range(W):
        if max(lst[i][w] for i in range(L)) > K:
            break
            #どれか一行でも超えたらあうと
        tmp = [sum_lst[i] + lst[i][w] for i in range(L)]
        if max(tmp) > K:
            cnt += 1 #前と一緒で合計超えてた場合は切る、切った回数を１足す
            sum_lst = [lst[i][w] for i in range(L)]
        else:
            sum_lst = tmp #合計リストをW回使いまわす#前から切ってない場合の分も足し合わせる
    else:
        ans = min(ans, cnt)
        #アンサーを最小化したら更新する
print(ans)