結果

問題 No.1345 Beautiful BINGO
ユーザー LyricalMaestro
提出日時 2025-07-26 14:47:03
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 449 ms / 2,000 ms
コード長 3,979 bytes
コンパイル時間 464 ms
コンパイル使用メモリ 82,272 KB
実行使用メモリ 77,388 KB
最終ジャッジ日時 2025-07-26 14:47:17
合計ジャッジ時間 12,359 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 61
権限があれば一括ダウンロードができます

ソースコード

diff # 

## https://yukicoder.me/problems/no/1345


def solve(N, M, A):
    col_sums = [0] * N
    for w in range(N):
        for h in range(N):
            col_sums[w] += A[h][w]
    
    answer = sum(col_sums) # 全て開けるも解答の一つ
    for col_bit in range((2 ** N) - 1):
        row = [0] * N
        m = 0
        ans = 0
        for w in range(N):
            if col_bit & (1 << w) > 0:
                m += 1
                ans += col_sums[w]
            else:
                for h in range(N):
                    row[h] += A[h][w]
        
        # 斜めを考慮しない場合
        rows = row.copy()
        rows.sort()
        ans0 = ans
        if m < M:
            r = M - m
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 斜めを考慮する場合
        # 1. x + 1
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            if col_bit & (1 << i) == 0:
                ans0 += A[i][i]
                rows[i] -= A[i][i]
        m0 = m + 1
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 2. x - 1
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            x1 = N - 1 - i
            if col_bit & (1 << x1) == 0:
                ans0 += A[i][x1]
                rows[i] -= A[i][x1]

        m0 = m + 1
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

        # 両方
        rows = row.copy()
        ans0 = ans
        for i in range(N):
            x0 = i
            x1 = N - 1 - i
            if x0 == x1:
                if col_bit & (1 << x0) == 0:
                    ans0 += A[i][x0]
                    rows[i] -= A[i][x0]
            else:
                if col_bit & (1 << x0) == 0:
                    ans0 += A[i][x0]
                    rows[i] -= A[i][x0]
                if col_bit & (1 << x1) == 0:
                    ans0 += A[i][x1]
                    rows[i] -= A[i][x1]


        m0 = m + 2
        rows.sort()
        if m0 < M:
            r = M - m0
            if r <= len(rows):
                for x in range(r):
                    ans0 += rows[x]
            else:
                ans0 = float("inf")
        answer = min(answer, ans0)

    print(answer)

def solve2(N, M, A):
    total = N ** 2
    cells = [[0] * N for _ in range(N)]
    answer = float("inf")
    for bit in range(2 ** total):
        cost = 0
        for x in range(total):
            h = x // N
            w = x % N
            if bit & (1 << x) > 0:
                cost += A[h][w]
                cells[h][w] = 1
            else:
                cells[h][w] = 0
        m = 0        
        for h in range(N):
            x = 0
            for w in range(N):
                x += cells[h][w]
            if x == N:
                m += 1
        for w in range(N):
            x = 0
            for h in range(N):
                x += cells[h][w]
            if x == N:
                m += 1

        x = 0
        for i in range(N):
            x += cells[i][i]
            if x == N:
                m += 1
        x = 0
        for i in range(N):
            x += cells[i][N - 1 - i]
            if x == N:
                m += 1
        
        if m >= M:
            answer = min(answer, cost)
    print(answer)





def main():
    N, M = map(int, input().split())
    A = []
    for _ in range(N):
        A.append(list(map(int, input().split())))

    solve(N, M, A)


if __name__ == "__main__":
    main()
0