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: Time Limit Exceeded

Solution code:
import sys
from itertools import product
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
h, w, k = map(int, input().rstrip().split())
CHOCO = [list(map(int, input().rstrip())) for _ in range(h)]
INF = 10**5
it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))

    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

    ans = 10 ** 6

    def calc(lst): #lst: 区切りを与える
        n = sum(lst) + 1 #n+1個に縦を区切る
        tmp = [0] * n
        count = n - 1 #区切る本数
        for w in range(W):
            position = 0
            now = [0] * n
            for h in range(H):
                if S[h][w] == '1': #ホワイトチョコレートのとき
                    now[position] += 1
                if lst[h] == 1:
                    position += 1
            
            flag = True
            for i in range(n):
                if tmp[i] + now[i] > K:
                    flag = False

            if flag:
                for i in range(n):
                    tmp[i] += now[i]
            else:
                count += 1
                for i in range(n):
                    tmp[i] = now[i]
        for i in range(n):
            if now[i] > K:
                count += 10 ** 6
                
        return count

    for i in range(2 ** (H - 1)):
        lst = [0] * (H)
        for j in range(H - 1):
            if (i >> j) & 1:
                lst[j] = 1
        ans = min(calc(lst), ans)

    print (ans)

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa += kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

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

ans = 10 ** 6

def calc(lst): #lst: 区切りを与える
    n = sum(lst) + 1 #n+1個に縦を区切る
    tmp = [0] * n
    count = n - 1 #区切る本数
    for w in range(W):
        position = 0
        now = [0] * n
        for h in range(H):
            if S[h][w] == '1': #ホワイトチョコレートのとき
                now[position] += 1
            if lst[h] == 1:
                position += 1
        
        flag = True
        for i in range(n):
            if tmp[i] + now[i] > K:
                flag = False

        if flag:
            for i in range(n):
                tmp[i] += now[i]
        else:
            count += 1
            for i in range(n):
                tmp[i] = now[i]
    for i in range(n):
        if now[i] > K:
            count += 10 ** 6
            
    return count

for i in range(2 ** (H - 1)):
    lst = [0] * (H)
    for j in range(H - 1):
        if (i >> j) & 1:
            lst[j] = 1
    ans = min(calc(lst), ans)

print (ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)
    
    if cnt > ans: continue
    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            if cnt > ans: break
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    agg = [[0]*(w) for _ in range(cnt+1)]
    *ls, = map(int, x+('1',))
    for i in range(w):
        prev = c = 0
        for j, split in enumerate(ls):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False

    for xyz in zip(*agg):
        cannot_split = False
        can_continue = True
        for i, x in enumerate(xyz):
            if x > k:
                cannot_split = True
                break
            if x+tmp[i] > k:
                can_continue = False
                break

        if cannot_split:
            break

        if can_continue:
            for i, x in enumerate(xyz):
                tmp[i] += x
                continue
        else:
            for i, x in enumerate(xyz):
                tmp[i] = x
            cnt += 1

    if cannot_split:
        continue

    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    if np.any(kouryo>k): continue

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = np.array([[0 for _ in range(w)]])
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo = np.concatenate((kouryo, s_arr[start:j+1].sum(axis=0, keepdims=True)), axis=0)
            start=j+1
    kouryo = np.concatenate((kouryo, s_arr[start:].sum(axis=0, keepdims=True)), axis=0)

    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        if np.any(kouryo[:, j]>k): cnt += 10**9
        if cnt >= 10**9: break
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = []
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo.append(list(s_arr[start:j+1].sum(axis=0)))
            start=j+1
    kouryo.append(list(s_arr[start:].sum(axis=0)))

    kouryo = np.array(kouryo)
    wa = np.array([0 for _ in range(len(kouryo))])
    for j in range(w):
        if np.any(kouryo[:, j]>k): cnt += 10**9
        if cnt >= 10**9: break
        wa = wa + kouryo[:, j]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from itertools import product
h, w, k = map(int, input().split())
CHOCO = [list(map(int, input())) for _ in range(h)]
INF = 10**5

it = ["01"]*(h-1)
ans = INF
for x in product(*it):
    cnt = sum(map(int, x))
    L = 0
    R = 0
    
    agg = [[0]*(w) for _ in range(cnt+1)]
    prev = 0
    for i in range(w):
        c = 0
        for j, split in enumerate(map(int, x+('1',))):
            if split:
                agg[c][i] = prev+CHOCO[j][i]
                prev = 0
                c += 1
            else:
                prev += CHOCO[j][i]

    tmp = [0]*(cnt+1)
    cannot_split = False
    for xyz in zip(*agg):
        if any(x > k for x in xyz):
            cannot_split = True
            break

        if all(x+tmp[i] <= k for i, x in enumerate(xyz)):
            for i, x in enumerate(xyz):
                tmp[i] += x
            continue
        for i, x in enumerate(xyz):
            tmp[i] = x
        cnt += 1

    if cannot_split:
        continue
        
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

h, w, k = map(int, input().split())
s = []
for i in range(h):
    string = input()
    temp = []
    for j in range(w):
        temp.append(int(string[j]))
    s.append(temp)

s_arr = np.array(s)

ans = 10**9
for i in range(2**(h-1)):
    bin_str = format(i, '0'+str(h-1)+'b')
    kouryo = []
    cnt = 0
    start = 0
    for j in range(h-1):
        if bin_str[j] == '1':
            cnt += 1
            kouryo.append(list(s_arr[start:j+1].sum(axis=0)))
            start=j+1
    kouryo.append(list(s_arr[start:].sum(axis=0)))

    kouryo = np.array(kouryo)
    wa = np.array([[0] for _ in range(len(kouryo))])
    for j in range(w):
        if np.any(kouryo[:, j]>k): cnt += 10**9
        if cnt >= 10**9: break
        wa = wa + kouryo[:, j, None]
        if np.any(wa>k):
            cnt += 1
            wa = kouryo[:, j, None]
    ans = min(ans, cnt)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.copy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.deepcopy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
                break
            last_spl=i-1
        nxt_cnt=[0]*num_sp
        if not ok:
            break
    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
input=sys.stdin.readline
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.deepcopy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
            last_spl=i-1
        nxt_cnt=[0]*num_sp

    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
h,w,k = map(int, input().split())
l = [None]*h
for i in range(h):
    l[i] = list(input())

from itertools import *
ans=10**10
import copy
for tmp in list(product([True,False], repeat=h-1)):
    num_sp = sum(tmp)+1
    cnt=[0]*num_sp
    nxt_cnt=[0]*num_sp
    last_spl=-1
    ok=True

 #   print(tmp)
    cur_ans=sum(tmp)
    for i in range(w):
        for j in range(h):
            spl = sum(tmp[:j])
            nxt_cnt[spl] += int(l[j][i])
            cnt[spl] += int(l[j][i])

        if max(cnt) > k:
#            print("split",i,cnt)
            cur_ans+=1
            cnt=copy.deepcopy(nxt_cnt)
            if last_spl+1 == i or max(nxt_cnt)>k:
                ok=False
            last_spl=i-1
        nxt_cnt=[0]*num_sp

    if ok:
        ans=min(ans,cur_ans)

#    print("  ",cur_ans,ok)
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import math
import string
import fractions
import random
from operator import itemgetter
import itertools
from collections import deque
import copy
import heapq
from bisect import bisect, bisect_left, bisect_right

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)

def solve():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = INF
    for i in range(2 ** (H - 1)):
        p = deque()
        for j in range(H - 1):
            if (i >> j) & 1:
                p.append(j + 1)
        num = len(p)
        if len(p) == 0:
            check = 0
            for j in range(W):
                temp_sum = sum([S[l][j] for l in range(H)])
                if temp_sum > K:
                    num = INF
                if check + temp_sum > K:
                    check = temp_sum
                    num += 1
                else:
                    check += temp_sum
        else:
            p.appendleft(0)
            p.append(H)
            check = [0] * (len(p) - 1)
            for j in range(W):
                for l in range(len(p) - 1):
                    if p[l + 1] - p[l] == 1:
                        check[l] += S[l][j]
                    else:
                        temp_sum = sum([S[t][j] for t in range(p[l], p[l + 1])])
                        if temp_sum > K:
                            num = INF
                            break
                        check[l] += temp_sum
                for l in check:
                    if l > K:
                        num += 1
                        for k in range(len(p) - 1):
                            if p[k + 1] - p[k] == 1:
                                check[k] = S[k][j]
                            else:
                                temp_sum = sum([S[t][j] for t in range(p[k], p[k + 1])])
                                if temp_sum > K:
                                    num = INF
                                check[k] = temp_sum
                        break
        if num < ans:
            ans = num
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def split(ar, k, w):
    a = 0
    if np.sum(ar>k) > 0:
        return -1
    tm = ar[0]
    for i in range(1, w):
        tm += ar[i]
        if np.sum(tm > k) > 0:
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
s = np.array(s)
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0].copy()
    sp = bin(i+2**h)[4:]
    if ans <= sp.count("1"):
        continue
    for j in range(1, h):
        if sp[j-1] == "0":
            temp += s[j]
        else:
            data.append(temp)
            temp = s[j].copy()
    data.append(temp)
    ans_ = split(np.array(data).T, k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
import numpy as np

MOD = 10 ** 9 + 7
INF = float('inf')
input = lambda: sys.stdin.readline().strip()

sys.setrecursionlimit(10 ** 8)


def solve():
    H, W, K = map(int, input().split())
    S = [list(map(int, list(input()))) for _ in range(H)]
    ans = INF
    for i in range(2 ** (H - 1)):
        num = 0
        p = [0]
        S_part = []
        for j in range(H - 1):
            if (i >> j) & 1:
                if j + 1 - p[-1] > 1:
                    S_part.append(S[p[-1]:j + 1])
                else:
                    temp_S_part = S[p[-1]:j + 1]
                    temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
                    S_part.append(temp_S_part)
                p.append(j + 1)
        if p[-1] != H:
            temp_S_part = S[p[-1]:H]
            temp_S_part = np.insert(temp_S_part, 1, np.zeros(W), axis=0)
            S_part.append(temp_S_part)
        num = len(S_part) - 1
        if len(S_part) == 1:
            S_part.append(np.zeros((2, W)))
        for j in range(len(S_part)):
            S_part[j] = np.cumsum(S_part[j], axis=0)
        check = [0] * (len(S_part))
        for j in range(W):
            for l in range(len(S_part)):
                check[l] += S_part[l][-1][j]
            for l in range(len(S_part)):
                if check[l] > K:
                    if j == 0:
                        num += INF
                    check = [S_part[l][-1][j] for l in range(len(S_part))]
                    num += 1
                    break
        if ans > num:
            ans = num
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

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

res = 10**5
for div in range(2**(h-1)):
    cut = []
    for i in range(h-1):
        if ((div >> i) & 1):
            cut.append(i+1)
    fr = 0
    part = []
    for i in range(len(cut)):
        to = cut[i]
        part.append(S[fr:to])
        fr = to
    else:
        part.append(S[fr:])
    comp_arr = []
    for p in part:
        p_ = np.array(p).astype(np.int)
        comp_arr.append(p_.sum(axis=0))
    comp_arr_T = np.array(comp_arr).T
    
    cnt = len(cut)

    tank = [0]*len(comp_arr)
    
    for m in range(w):
        for n in range(len(comp_arr)):
            tank[n] += comp_arr[n][m]

        if any([c>k for c in tank]):
            cnt += 1
            for n in range(len(comp_arr)):
                tank[n] = comp_arr[n][m]

    res = min(res, cnt)
print(res)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

def split(ar, k, w):
    a = 0
    if np.sum(ar>k) > 0:
        return -1
    tm = ar[0]
    for i in range(1, w):
        tm += ar[i]
        if np.sum(tm > k) > 0:
            a += 1
            tm = ar[i]
    return a
            

h, w, k = map(int, input().split())
s = [[int(i) for i in input()] for j in range(h)]
s = np.array(s)
ans = h*w

for i in range(2**(h-1)):
    data = []
    temp = s[0].copy()
    sp = bin(i+2**h)[4:]
    for j in range(1, h):
        if sp[j-1] == "0":
            temp += s[j]
        else:
            data.append(temp)
            temp = s[j].copy()
    data.append(temp)
    ans_ = split(np.array(data).T, k, w)
    if ans_ == -1:
        continue
    ans_ += sp.count("1")
    if ans > ans_:
        ans = ans_
print(ans)

Submission status: Time Limit Exceeded

Solution code:




H,W,K = map(int, input().split())

# 縦1マスなら、たての分割は行わず横だけ見て行く
if H == 1:
    S = input()
    cnt = 0
    ans = 0

    for i in range(W):
        if S[i] == "1":
            cnt += 1
        if cnt > K:
            ans += 1
            cnt = 1


    
    print(ans)
    exit()

# 横1マスなら、横の分割は行わずに縦だけ見て行く
elif W == 1:
    S = [input() for _ in range(H)]
    cnt = 0
    ans = 0
    for i in range(H):
        if S[i] == "1":
            cnt += 1

        if cnt > K:
            ans += 1
            cnt = 1
    print(ans)
    exit()


S = [input() for _ in range(H)]

ans = (H-1) + (W - 1)
for bit in range(1 << (H-1)):
    is_valid = True
    nums = bin(bit).count("1") + 1
    cnt_cut = bin(bit).count("1")


    # 横方向に割った時の、同じ区間かつ現在の列より左のホワイトチョコの数を管理するlist
    cnt_white_prev = [0] * nums

    for w in range(W):
        # 横方向に割った時の、現在の列のホワイトチョコの数を管理するlist
        cnt_white_curr = [0] * nums
        idx = 0

        # ある列にあるホワイトの数を数える
        for h in range(H):
            if S[h][w] == "1":
                cnt_white_curr[idx] += 1
            if h < H-1 and bit & (1 << h):
                idx += 1

        # K個を上回るブロックがあったか
        is_over_K = False
        
        for i in range(nums):

            
            if cnt_white_prev[i] + cnt_white_curr[i] > K:
                is_over_K = True
                if cnt_white_curr[i] > K:
                    is_valid = False
                break


        
        # K個を超えるブロックがあった場合、かつ、横方向の割り方は妥当な場合
        if is_over_K:
            cnt_cut += 1

            for i in range(nums):
                cnt_white_prev[i] = cnt_white_curr[i]
        else:
            for i in range(nums):
                cnt_white_prev[i] += cnt_white_curr[i]
    



    if is_valid:
        ans = min(ans, cnt_cut)

    

        

print(ans)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


def solve(grid, ranges, K):
    blocks = np.array([grid[lo:hi].sum(axis=0) for (lo, hi) in ranges])
    nblocks, ncols = blocks.shape

    pos = 0
    counts = np.zeros((nblocks,), dtype=int)
    init = True
    res = len(ranges)-1  # horizontal cut
    while pos < ncols:
        counts += blocks[:, pos]
        if np.any(counts > K):
            if init:
                return float("inf")
            res += 1
            counts = np.zeros((nblocks,), dtype=int)
            init = True
        else:
            pos += 1
            init = False
    return res


def main():
    H,W,K = [int(x) for x in input().split()]
    grid = [[int(x) for x in input()] for _ in range(H)]
    grid = np.array(grid, dtype=int)

    if K>=grid.sum():
        print(0)
        return

    # build ranges O(2^H)
    ranges = [[(0, H)]]
    for r in range(1, H):
        for borders in itertools.combinations(range(1, H), r=r):
            borders = (0,) + borders + (H,)
            ranges.append([(lo, hi) for lo, hi in zip(borders[:-1], borders[1:])])

    ans = float("inf")
    for rng in ranges:
        # print(rng)
        cnt = solve(grid, rng, K)
        ans = min(ans, cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

"""
bit全探索の考え方

for div in range(2**3):
    print(div)
    # divの値を2進数で考えると、
    # 0000
    # 0001
    # 0010
    # 0011
    # 0100
    # 0101
    # ...
    # となるので、全探索を考えやすい

"""

import numpy as np


def solve():
    """
    最初に横に切る方法を全探索し、
    次に、ギリギリのラインを縦に切っていく
    O(2**H W)

    Note1:
        1 << K  =>  2**k

    Note2:
        div>>i&1
        => divのi桁目が1であるかどうか
    """
    H, W, K = list(map(int, input().split()))
    S = ["" for _ in range(H)]
    for i in range(H):
        s = input()
        S[i] += s
    ans = float("inf")

    # 横に切るのを全部試す
    # divのbitが1のところで切る
    # gはグループ数
    for div in range(0, 1<<(H-1)):  # 2**(H-1)を全探索するとき、bitで考えたほうがラク
        g = 0
        ids = [0 for _ in range(H)]
        for i in range(H):
            ids[i] = g
            if div>>i&1:
                g += 1
        g += 1

        c = np.array([[0 for _ in range(1005)] for __ in range(10)])

        for i in range(H):
            for j in range(W):
                c[ids[i]][j] += int(S[i][j])

        num = g-1  # g-1回、横に切る
        now = np.array([0 for _ in range(g)])  # 今、各グループに何個のホワイトチョコレートがあるか
        def add(j, now, c):
            for i in range(g):
                now[i] += c[i][j]
            for i in range(g):
                if now[i] > K: return False
            return True

        for j in range(W):
            if not add(j, now, c):
                num += 1
                now = np.array([0 for _ in range(g)])
                if not add(j, now, c):
                    num = float("inf")
                    break
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    solve()

Submission status: Time Limit Exceeded

Solution code:
import numpy as np
import itertools


def solve(grid, ranges, K):
    blocks = np.array([grid[lo:hi].sum(axis=0) for (lo, hi) in ranges])
    nrows, ncols = blocks.shape
    nblocks = len(blocks)

    # print(ranges)
    # print(blocks)
    # print()

    prev = -1
    pos = 0
    counts = [0] * ncols
    res = len(ranges)-1  # horizontal cut
    while pos < ncols:
        for i in range(nblocks):
            counts[i] += blocks[i, pos]
        if any(c>K for c in counts):
            res += 1
            counts = [0] * ncols
            if prev == pos:  # looping?
                return float("inf")
        else:
            prev = pos
            pos += 1
    return res


def main():
    H,W,K = [int(x) for x in input().split()]
    grid = [[int(x) for x in input()] for _ in range(H)]
    grid = np.array(grid, dtype=int)

    if K>=grid.sum():
        print(0)
        return

    ans = float("inf")
    ranges = [[(0, H)]]
    for r in range(1, H):
        for borders in itertools.combinations(range(1,H), r=r):
            borders = (0,) + borders + (H,)
            ranges.append([(lo, hi) for lo, hi in zip(borders[:-1], borders[1:])])

    for rng in ranges:
        cnt = solve(grid, rng, K)
        ans = min(ans, cnt)
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding:utf-8 -*-

"""
bit全探索の考え方

for div in range(2**3):
    print(div)
    # divの値を2進数で考えると、
    # 0000
    # 0001
    # 0010
    # 0011
    # 0100
    # 0101
    # ...
    # となるので、全探索を考えやすい

"""

def solve():
    """
    最初に横に切る方法を全探索し、
    次に、ギリギリのラインを縦に切っていく
    O(2**H W)

    Note1:
        1 << K  =>  2**k

    Note2:
        div>>i&1
        => divのi桁目が1であるかどうか
    """
    H, W, K = list(map(int, input().split()))
    S = ["" for _ in range(H)]
    for i in range(H):
        s = input()
        S[i] += s
    ans = float("inf")

    # 横に切るのを全部試す
    # divのbitが1のところで切る
    # gはグループ数
    for div in range(0, 1<<(H-1)):  # 2**(H-1)を全探索するとき、bitで考えたほうがラク
        g = 0
        ids = [0 for _ in range(H)]
        for i in range(H):
            ids[i] = g
            if div>>i&1:
                g += 1
        g += 1

        c = [[0 for _ in range(1005)] for __ in range(10)]
        for i in range(H):
            for j in range(W):
                c[ids[i]][j] += int(S[i][j])

        num = g-1  # g-1回、横に切る
        now = [0 for _ in range(g)]  # 今、各グループに何個のホワイトチョコレートがあるか
        def add(j, now, c):
            for i in range(g):
                now[i] += c[i][j]
            for i in range(g):
                if now[i] > K: return False
            return True

        for j in range(W):
            if not add(j, now, c):
                num += 1
                now = [0 for _ in range(g)]
                if not add(j, now, c):
                    num = float("inf")
                    break
        ans = min(ans, num)
    print(ans)


if __name__ == "__main__":
    solve()