ABC 285 G — Tatami

考察

大きいタイルを置く場所だけ決めれば、残りは小さいタイルで埋められる。そこで、隣接する2マスを選ぶ辺が互いに端点を共有しないようにし、文字 2 のマスをすべて選ぶ問題へ置き換える。「各マスは高々1回使う」を容量1で、「このマスは必ず使う」を流量の下限1で表すと、左右どちらにある必須マスも同じ仕組みで扱える。

タイル配置を必須頂点のあるマッチングにする

1×21\times2 のタイルは、隣接する2マスを結ぶ辺に対応する。文字 1 は必ず 1×11\times1 のタイルで覆うので、初めからグラフから除く。残るマスの間に上下左右の隣接辺を張ると、重ならない大きいタイルの集合は、端点を共有しない辺の集合、すなわちマッチングになる。文字 2 の頂点は必ずマッチングに含め、文字 ? の頂点は含めても含めなくてもよい。

必須マスから順に空いている相手を選ぶ貪欲法では、後の必須マスの唯一の相手を奪うことがある。例えば1行の ?221 で左側の 2 を左端の ? と結ぶと、右側の 2 を覆えない。中央の 22 を結べば両方を覆える。辺を選び直せるマッチングの算法を使いたい。一方、通常の最大マッチングを求めるだけでは、ある必須頂点を覆わない解が返る可能性がある。例えば 2?? の最大マッチングは1本だが、右の2マスを結ぶ解は 2 を覆わない。本数を最大化する条件と、指定した頂点をすべて使う条件は区別する必要がある。

行・列を1始まりとし、i+ji+j が偶数のマスを左側 LL、奇数のマスを右側 RR とする。隣接マスは必ず異なる側なので、グラフは二部グラフである。始点 ss、終点 tt を追加し、辺の下限・上限を次のように設定する。下限は必ず流す量、上限は流してよい最大量を表す。

辺下限上限
s→v (v∈L)s\to v\ (v\in L)vv が 2 なら1、? なら01
隣接する左マス vv から右マス ww への v→wv\to w01
v→t (v∈R)v\to t\ (v\in R)vv が 2 なら1、? なら01

整数流を考えると、左マスへの流入と右マスからの流出が高々1なので、流量1の隣接辺はマッチングになる。さらに、2 に接する入口・出口辺の下限1が、そのマスをちょうど1本のタイルで覆う条件になる。

下限による流入超過を追加の流出で直す

まず t→st\to s に下限0・上限 K=min⁡(∣L∣,∣R∣)K=\min(|L|,|R|) の辺を加える。タイルは左右のマスを1個ずつ使うので、マッチング本数は高々 KK である。ss から tt へ送った量をこの辺で戻せば、すべての頂点で流入と流出が等しい循環流になる。

ここからは、この閉鎖辺も含めた各辺 ee の流量・下限・上限をそれぞれ xe,le,uex_e,l_e,u_e とする。下限分を先に流したとみなし、追加で流す量 fef_e に分ける。

xe=le+fe,0≤fe≤ue−lex_e=l_e+f_e,\qquad 0\leq f_e\leq u_e-l_e

したがって、最大流に渡す元の辺の容量は ue−leu_e-l_e である。下限分だけでは流量保存が崩れるので、各頂点 vv の収支を

b(v)=∑e: vへ流入le−∑e: vから流出leb(v)=\sum_{e:\,v\text{へ流入}}l_e-\sum_{e:\,v\text{から流出}}l_e

と定める。元の流量保存に xe=le+fex_e=l_e+f_e を代入して整理すると、追加流が満たすべき条件は

∑e: vから流出fe−∑e: vへ流入fe=b(v)\sum_{e:\,v\text{から流出}}f_e-\sum_{e:\,v\text{へ流入}}f_e=b(v)

となる。b(v)>0b(v)>0 は、下限だけで流入が多すぎる状態である。その分を追加で外へ流す必要があるので、補助始点 SSSS から vv へ容量 b(v)b(v) の辺を張る。この辺を飽和させると、通常の流量保存が元辺上の「流出超過 b(v)b(v)」をちょうど要求する。逆に b(v)<0b(v)<0 なら、追加で受け取る必要があるため、vv から補助終点 TTTT へ容量 −b(v)-b(v) の辺を張る。

辺 a→ca\to c の下限 ll を処理するときは、b(a)b(a) から ll を引き、b(c)b(c) に ll を足す。全収支の和は0なので、SSSS から出る容量の総和と TTTT へ入る容量の総和は等しい。この共通の値を

D=∑vmax⁡(b(v),0)D=\sum_v\max(b(v),0)

とする。残容量と補助辺だけを持つグラフの流量を0で初期化し、SSSS から TTTT への最大流を求める。その値が DD なら Yes、小さければ No である。

本問では、左側の 2 の個数を aa、右側の 2 の個数を cc とすると、b(s)=−a,b(t)=cb(s)=-a,b(t)=c である。各左側の 2 は b=1b=1、各右側の 2 は b=−1b=-1 となり、? は0のままである。従って D=a+cD=a+c、つまり 2 の総数になる。左右両方の下限を処理し、s,ts,t の収支も忘れずに補助辺へ反映する。

1行の盤面で符号と補修経路を追う

1行2列では左のマスが LL、右のマスが RR に属する。以下では、それぞれを頂点 p,qp,q と呼ぶ。

2? では s→ps\to p の下限が1なので、b(s)=−1,b(p)=1b(s)=-1,b(p)=1、他は0であり、D=1D=1 となる。s→ps\to p の残容量は0だが、下限の1は既に流したとみなしている。補助最大流では

SS→p→q→t→s→TTSS\to p\to q\to t\to s\to TT

に1を流せる。下限で pp に入った1を qq 側へ流し、ss の不足を閉鎖辺で補っている。補助辺を取り除き、下限を戻すと、s→p→q→ts\to p\to q\to t の流量が1になり、大きいタイル1枚を得る。

?2 では q→tq\to t の下限が1なので、b(q)=−1,b(t)=1b(q)=-1,b(t)=1、D=1D=1 となる。今度の補修経路は

SS→t→s→p→q→TTSS\to t\to s\to p\to q\to TT

である。右側にある 2 も、同じ規則で必ずマッチングに含まれる。

22 では両方の下限が付き、b(s)=−1,b(p)=1,b(q)=−1,b(t)=1b(s)=-1,b(p)=1,b(q)=-1,b(t)=1、D=2D=2 となる。SS→p→q→TTSS\to p\to q\to TT と SS→t→s→TTSS\to t\to s\to TT に1ずつ流せる。必要流量2は必須頂点2個の収支を直す量であって、タイルを2枚置く意味ではない。復元されるタイルは1枚である。

21 では右マスがグラフから除かれる。pp から出る隣接辺がなく、SS→pSS\to p を飽和できないため No となる。?? と 11 はどちらも D=0D=0 で、何も流さず Yes になる。大きいタイルを置かず、全マスを小さいタイルで埋めればよい。

典型の発動条件

gridの二部matching

上下左右に隣接する2マスを、マスを共有しない組として選びたいとき、市松模様の色分けを調べる。各辺が必ず異なる色を結べば二部マッチングにできる。斜めの隣接など、同じ色を結ぶ辺を許す問題では、この色分けをそのまま使えない。

lower-bound flow feasibility

「各頂点は高々1回使う」に加えて「一部の頂点は必ず使う」と要求されるとき、入口・出口辺への下限が候補になる。下限を先に流した収支を求め、補助辺の全飽和へ帰着する。必須頂点が始点側と終点側の両方にあっても、同じ流量保存の式で扱える。

問題固有の要素

文字 1 を除き、文字 2 だけを必須、文字 ? を任意とすれば、小さいタイルを選ぶ変数は不要になる。これは、残ったどのマスも小さいタイルで単独に覆えるからである。別のタイル配置問題でも、大きいタイルだけを選んで残りを自由に埋められるかを先に調べると、配置全体を管理する状態を減らせる。

正当性

条件を満たすタイル配置があるとする。大きいタイルの辺は端点を共有せず、すべての 2 を覆い、1 を使わない。それぞれについて s→L→R→ts\to L\to R\to t に1を流せば、各辺の上下限を満たす整数流になる。その本数を t→st\to s に戻すと循環流 xx を得る。各元辺に fe=xe−lef_e=x_e-l_e を流し、各補助辺を容量まで流せば、収支の式により元頂点で流量が保存される。従って、補助最大流は DD に達する。

逆に補助最大流が DD なら、SSSS の出辺はすべて飽和する。TTTT の入辺も容量の総和が DD なので、すべて飽和する。補助辺を除いた追加流 ff は各頂点で流出超過 b(v)b(v) を持つため、xe=le+fex_e=l_e+f_e は上下限と流量保存を満たす循環流になる。整数容量から整数流が得られ、入口・出口の上限1により、流量1の隣接辺は端点を共有しない。2 の入口または出口は下限1なので、すべての 2 がそのマッチングに含まれる。選んだ辺へ大きいタイルを置き、残る ? と除いておいた 1 を小さいタイルで覆えば、条件を満たす配置になる。

以上から、補助最大流が DD であることと、条件を満たすタイル配置が存在することは同値である。

実装上の注意

  • 収支配列を0で初期化し、下限 ll の辺 v→wv\to w ごとに b(v)−=l,b(w)+=lb(v)\mathrel{-}=l,b(w)\mathrel{+}=l と更新する。元辺には残容量 u−lu-l だけを登録し、下限を最大流でもう一度流そうとしない。
  • s,ts,t も元頂点に含めて収支を処理する。正なら SS→vSS\to v、負なら v→TTv\to TT とし、最大流の値を DD と比較する。D=0D=0 なら直ちに Yes としてよい。
  • 以下の計算量を直接適用できる実装として、容量が整数 kk の補助辺は、同じ向きの容量1の辺 kk 本に分けて登録する。対象は t→st\to s、SS→tSS\to t、s→TTs\to TT で、本数の合計は K+a+c≤3HW/2K+a+c\leq 3HW/2 である。容量0の辺は省いてよい。単位容量の辺をまとめ直さず、並行辺を保持できる隣接リストを使う。
  • 行列番号を頂点番号へ変換し、各左マスから上下左右の右マスへ1回ずつ辺を張る。逆辺は残余グラフ用として別に管理する。配置も欲しい場合は隣接辺のIDを保存し、最大流後に下限を戻した流量1の辺を取り出す。
  • Dinic法では各段階でBFSによる距離と、DFSで次に調べる辺の位置を初期化する。増加路が長くなる場合もあるので、再帰DFSを使うなら実行環境のスタック容量にも注意する。

復習の核

  • 残りを小さいタイルで自由に埋められるなら、大きいタイルの選択だけをマッチングとして考える。
  • 「高々1回」と「必ず1回」は、容量上限1と下限1へそれぞれ対応させる。最大マッチングの本数だけでは必須頂点の被覆は保証されない。
  • b=下限流入−下限流出b=\text{下限流入}-\text{下限流出} と定義したら、正の頂点は追加で外へ流す。そのための入口が SS→vSS\to v である。符号を丸暗記せず、追加流の保存式から導く。
  • 下限変換後の容量を確認してから最大流の計算量を評価する。元のマッチング網が単位容量でも、閉鎖辺や補助辺には容量が集まる。

計算量と制約

時間

N=HWN=HW と置く。各マスからの隣接辺は高々4本なので、入力の走査・辺の構築・収支計算は O(N)O(N) 時間である。

変換後の閉鎖辺 t→st\to s は容量 KK、補助辺 SS→tSS\to t と s→TTs\to TT は容量 c,ac,a を持ち、元のままでは全辺が単位容量とはいえない。本稿ではこれらを容量1の並行辺に分ける。K≤N/2,a+c≤NK\leq N/2,a+c\leq N なので、分割後も頂点数・辺数はともに O(N)O(N) であり、全辺の容量は0か1になる。分割した辺の流量を合計すれば元の辺の流量になり、逆に整数流量を各辺へ1ずつ配れるので、この変更で可否は変わらない。

分割後の辺数を MM とすると、単位容量のネットワークに対するDinic法は、並行辺があっても O(MM)O(M\sqrt M) 時間である。その理由は、各辺の走査位置を保持すれば、1段階の閉塞流(現在の最短距離の増加路をすべて塞ぐ流れ)を O(M)O(M) 時間で求められることにある。成功した増加路の辺は容量1を使い切り、その段階では再利用されない。段階が進むたびに SSSS から TTTT への残余最短距離は増える。距離が M\sqrt M を超えるまで高々 O(M)O(\sqrt M) 段階で、その後の追加可能な流れは、辺を共有しない長さ M\sqrt M 超の経路へ分解できるため高々 O(M)O(\sqrt M) 単位である。従って残りの段階数も O(M)O(\sqrt M) となる。

M=O(N)M=O(N) を代入すると、前処理を含む全体は O(NN)=O((HW)3/2)O(N\sqrt N)=O((HW)^{3/2}) 時間になる。一般の下限付きフローでは、容量の総和が巨大になり得るため、この辺の分割と評価をそのまま適用できるとは限らない。

空間

盤面、収支配列、単位容量へ分割した辺とその残余逆辺、Dinic法の距離・走査位置・探索用領域は、いずれも O(HW)O(HW) 空間である。

制約との対応

公式制約は 1≤H,W≤3001\leq H,W\leq300、従って HW≤90000HW\leq90000 である。文字は 1、2、? のいずれかで、時間制限は3秒、メモリ制限は1024 MiB。盤面全体の隣接辺と、線形本数に収まる単位容量の補助辺を持ち、上記の O((HW)3/2)O((HW)^{3/2}) 時間・O(HW)O(HW) 空間の算法を使う。D≤HWD\leq HW、閉鎖辺の総容量 K≤HW/2K\leq HW/2 なので、無限大を表す巨大な容量は不要である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Tatami の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 下限制約付きflowの実現可能性

主題
  • 下限制約付きflowの実現可能性: 各辺のlower boundを先に流して頂点需要へ変換し、super source/sinkを加えたcirculationの飽和可能性を判定する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 最大流・最小カット: 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 下限制約付きflowの実現可能性

    補助タグ: 最大流・最小カット

    執筆: abc-explanation-author1.1.1 / revision 3

    学習の位置

    体系上の位置: 下限制約付きflowの実現可能性

    • 各辺のlower boundを先に流して頂点需要へ変換し、super source/sinkを加えたcirculationの飽和可能性を判定する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 最大流・最小カット — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、最大流・最小カットの発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題