結果

問題 No.421 しろくろチョコレート
コンテスト
ユーザー hotcoffee
提出日時 2026-07-24 09:47:33
言語 Python3
(3.14.3 + numpy 2.4.4 + scipy 1.17.1)
コンパイル:
python3 -mpy_compile _filename_
実行:
python3 _filename_
結果
AC  
実行時間 122 ms / 2,000 ms
+ 250µs
コード長 914 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 999 ms
コンパイル使用メモリ 21,412 KB
実行使用メモリ 15,868 KB
最終ジャッジ日時 2026-07-24 09:47:44
合計ジャッジ時間 10,371 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge2_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

def dfs(v):
    used[v] = True
    for u in G[v]:
        w = match[u]
        if w < 0 or not used[w] and dfs(w):
            match[u] = v
            return True
    return False

N, M = map(int, input().split())
S = [input() for _ in range(N)]
X = (N * M + 1) // 2
Y = N * M // 2
G = [[] for _ in range(X)]
V = [0, 0]
for n in range(N):
    for m in range(M):
        if S[n][m] == '.': continue
        V[wb := (n + m) % 2] += 1
        if wb: continue
        x = (n * M + m) // 2
        for dn, dm in ((-1, 0), (1, 0), (0, -1), (0, 1)):
            n2 = n + dn
            m2 = m + dm
            if 0 <= n2 < N and 0 <= m2 < M and S[n2][m2] != '.':
                y = (n2 * M + m2) // 2
                G[x].append(y)

meth3 = 0
match = [-1] * Y
for v in range(X):
    used = [0] * X
    if dfs(v):
        meth3 += 1
meth2 = min(V) - meth3
meth1 = abs(V[0] - V[1])
print(meth1 + meth2 * 10 + meth3 * 100)
0