✅abc193f

NISHIO Hirokazu [Translate]
✅ABC193F
F - Zebraness
整理
2色で塗り分け→グラフのカット
グラフのカットとはグラフの頂点集合を二つの集合に分けたもののこと
つまり2色での塗り分けとグラフのカットは本質的に同じもの
最大カット→二部グラフなら片側を反転
グラフの最小カットは最大流で解ける
しかしこの問題は最大カット(色が違っている数を増やしたい問題設定)
グラフがグリッドグラフなので、二部グラフ
二部グラフの片側の頂点の塗りを反転すれば、すべての辺について「同じ色か異なる色か」が反転する
これで「色が違っていれば+1」が「色が同じならば+1」に変わる
色が違ってる辺を最小にする、つまり最小カット


----
from ABC193
ABC193F
F - Zebraness
考えたこと
横幅が最大100
2^100はメモリに持てないので上からDPするのはダメそう
2色で塗るので二部グラフになる？
隣が同じ色になるしかない時もある
グリーディな解法がある？
サンプルは通ったが提出したら20WA、やっぱダメか
連結したハテナの塊ごとに2種類の市松模様のどちらかを選ぶ？
2個以上の連結成分を最悪2500個作れるので2^2500は無理
それぞれは独立に計算できるか…
タイムアウト
公式解説
Project Selection Problemに帰着して最大流
知識としては知ってたのに全く思いつかなかったなぁ…
改めて考察
まず「グラフの頂点を白黒2色に塗り分ける」という設定を「グラフのカットについて考える」と理解すべきだった
グラフのカットとはグラフの頂点集合を二つの集合に分けたもののこと
カットだと理解した上で「最小カットなら最大流で解ける」と連想がつながる
今回は「グラフの隣り合う頂点の色が異なっていれば+1」
色が異なってる(カットエッジである)ことをプラスに評価している
これでは最大カット問題になる、一般的にはNP完全
グリッドグラフが二部グラフであることを利用
「二部グラフの片側の頂点の色を反転」する
すると、すべての辺の「頂点の色が異なっているか」が反転する
これで「隣り合う頂点の色が異なっていれば-1」にできる
グリッドグラフの場合、要するに市松模様の頂点を反転するということ
実装
N=1の時に0を返す
Dinicの実装自体にバグがあった
グラフに孤立点があると頂点数を間違えて配列を必要な量より小さくしてしまう
頂点数を明示的に渡すようにした
AC
pydef solve(N, world):
    if N == 1:
        return 0

    d = Dinic(N * N + 2)
    for u, v in world.allEdges():
        d.add_edge(u, v, 1, True)

    start = N * N
    goal = start + 1
    for pos in world.allPosition():
        x, y = divmod(pos, N)
        if world.mapdata[pos] != CHAR_Q:
            p1 = (world.mapdata[pos] == CHAR_B)
            p2 = ((x + y) % 2 == 0)
            if p1 ^ p2:
                d.add_edge(start, pos, 100)
            else:
                d.add_edge(pos, goal, 100)

    f = d.max_flow(start, goal)
    return (2 * N * (N - 1)) - f
"Engineer's way of creating knowledge" the English version of my book is now available on [Engineer's way of creating knowledge]
(C)NISHIO Hirokazu / Converted from [Scrapbox] at 11/23/2025, 5:19:34 PM[Edit]
Related Pages
