ABC 227 H — Eat Them All

考察

3×3盤面を9頂点12辺の無向二部グラフとみる。各マスでは餌を食べるたびに1本の辺から出発し、最終的に始点へ戻るので、頂点vを端点とする辺の総通過回数は2A_vでなければならない。 A_vは最大100で行動列を直接探索する分岐は大きいが、盤面の辺数は12で固定されている。先に各辺を何回通るか決めれば、残る条件は次数と正の辺の連結性になる。 辺eの通過回数x_eを多重辺数とみなすと、各頂点の次数は2A_vで全て偶数になる。正の多重辺のsupportが連結ならEuler閉路が存在し、その各出発がちょうど1缶を消費するので元の行動列へ戻せる。 gridは市松模様の二部グラフなので、黒頂点の残余次数をsource側、白頂点の残余次数をsink側に置き、盤面辺へ流す量を追加通過回数と解釈できる。

棄却する候補: 現在位置と9マスの残量を状態にして、行動列をDFSまたはDPで探索する。

残量状態は最大101^9通りで、同じ最終的な辺通過回数へ至る多数の順序も重複してしまう。

採用する候補: 連結性を保証するspanning treeを列挙し、その辺へ1の下限制約を置いた次数充足問題を二部グラフの最大流で解く。

12辺の部分集合は全列挙でき、tree分を引いた残余次数は各辺の追加通過回数を流量とするbipartite flowに一致する。

12辺の部分集合から9頂点を結ぶtreeを選び、各tree辺を1回使う分だけ端点の要求次数2A_vを減らす。残余要求を最大流で全て満たせたら辺多重度を復元し、(1,1)からHierholzer法でEuler閉路を構築して各辺をL/R/U/Dへ変換する。

典型の発動条件

閉じたwalkの辺多重度とEuler閉路への変換

発動条件: 各頂点での訪問・出発回数が指定され、実際のwalkを構成する問題で、順序より辺の使用回数を先に決められるとき。

消費回数を頂点次数へ翻訳し、偶数次数かつ連結な多重グラフを作ってHierholzer法で行動順を復元する。

二部グラフ上の次数列実現を最大流で解く

発動条件: 二部グラフの各頂点に必要次数があり、各辺へ非負整数の多重度を割り当てたいとき。

黒側要求をsource容量、白側要求をsink容量、盤面辺を十分大きい容量として、全要求を満たすflowを辺多重度にする。

小さい辺集合で連結性のwitnessを全列挙する

発動条件: 量の割当はflowなどで解ける一方、正の辺の連結性だけが非線形で、候補辺数が十分小さいとき。

連結supportが含むspanning treeを12辺から列挙し、tree辺に下限1を課すことで連結性を局所的な次数制約へ落とす。

問題固有の要素

固定3×3盤面では辺が12本しかないため、通常は扱いにくい「使用辺が連結」という条件をspanning treeの全列挙で保証できる。

別の問題へ持ち帰る視点: 構成のsupport条件に困ったら、入力全体ではなく候補辺数が小さくないかを数え、連結性の証人となるtreeを先に固定する方法を検討する。

正当性

通過多重度の次数2A_vと連結supportがEuler閉路必要十分で、各出発は一缶消費に対応。連結supportはspanning treeを含むのでtreeを全列挙し一回分引けば残余次数を二部flowへ表せる。全残余需要が流れるとEuler復元で元操作列を実現する。

実装上の注意

  • tree辺の下限1を引いた後の残余次数が負ならそのtreeは不可能であり、黒側と白側の残余次数総和も一致する必要がある。
  • Euler構築では無向辺の残り多重度を両端で共有して1ずつ減らし、帰りがけに記録した頂点列を反転して移動文字へ直す。

復習の核

  • 行動列を直接追う前に、各頂点から何回出るかを数え、閉じたwalkなら次数がその2倍になることを小さい往復で確かめる。
  • 次数が合うだけでは離れた閉路ができる反例を忘れず、連結性をspanning treeという明示的witnessで保証する。

計算量と制約

時間

3×3固定9頂点12辺。2^12 subsetを検査、各固定サイズflow O(1)のgraph演算(容量整数幅固定)。Euler出力長 L=ΣA_v に O(L)。

空間

固定network O(1)、Euler多重辺出力 O(L)。

制約との対応

公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: 1 \leq A_{i,j} \leq 100; All values in input are integers.

出典

分類・前提・執筆情報

掲載状態: 収録済み

Eat Them All の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最大流・最小カット

主題
  • 最大流・最小カット: 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
  • Euler trail・circuit: 全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
既習技能

主タグ: Euler trail・circuit 最大流・最小カット

補助タグ: 有界全列挙・有限case分解

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

学習の位置

体系上の位置: 最大流・最小カット

  • 選択・排反・closure・頂点容量をcapacity networkへ写し、残余グラフとmax-flow min-cut定理から最適値とcut側を復元する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
  • 全辺を一度ずつ使うEuler trail・circuitについて、無向graphの奇数次数条件または有向graphの入出次数条件と辺を持つ部分の連結性から存在を判定し、具体的な辺列が必要ならHierholzer法で構成する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

先に読む単元:

  • 候補数を界して全列挙・有限case分解する — 候補総数を直接界す全列挙と、鳩ノ巣原理で成功前の失敗回数だけを界す探索を分け、実際に処理する回数を証明する。
  • 状態グラフのモデリングと探索 — 暗黙状態と重みなし合法遷移を頂点・辺へ写し、探索目的・訪問条件・frontierに応じてBFS・DFS・backtrackingを選ぶ。その発動条件と正当化原理を比較可能な独立教材として学ぶ。

学習記録

状況更新: 更新記録なし

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

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

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

同じ単元の問題