成立証明から構成解を復元する

概要

構成解・witness復元

「条件を満たすものがある」と判定できても、その具体例を出力できるとは限らない。条件を満たす実物や操作列を構成解と呼び、それが条件の成立を示す証拠になるという意味で witness とも呼ぶ。このUnitでは、存在の証明を、実際に選ぶ辺・並べ方・操作の手順へつなぐ。

まず、次の三つの要求を区別する。

要求答えに必要なもの
存在判定条件を満たす解があるかどうか
最適値の計算解のうち最小の費用や最大の得点
構成解の出力条件を満たす具体的な対象、またはそこへ至る操作列

最適値だけを求めるDPでは、値が同じ二つの選択を区別せずに済むことがある。構成まで求めるなら、その値を実現する選択を一つ取り出せるようにする。一方、何らかの解を一つ出せばよい問題では、操作回数まで最小化する必要があるかを問題文で確認する。

考え方

小さい木で、確定する場所を選ぶ

各頂点に駒が一つずつあり、駒にも頂点と同じ番号が重複なく付いているとする。辺で隣り合う二頂点の駒を交換して、駒を同じ番号の頂点へ置きたい。駒は辺を通ってしか動けないので、各駒の現在位置と目的地が同じ連結成分にあることが必要である。これは、解があるなら必ず満たす「必要条件」であり、まだ交換の手順ではない。

連結な成分では、全頂点を結び閉路を持たない辺の集合、すなわち全域木だけを使うことにする。使う辺を減らしても各頂点へ到達できる。ただし、頂点を番号順に完成させるだけでは、後の駒を運ぶ経路が完成済みの頂点を通り、その駒を動かしてしまう。

そこで、木の葉、つまり残っている辺が一本だけの頂点から確定する。葉を取り除いても、残った頂点同士はつながっている。この性質が、後の操作で確定済みの駒を動かさずに済む理由になる。

例えば、辺が 1−2−3−41-2-3-4 という道をなし、各頂点の駒が順に (2,4,1,3)(2,4,1,3) である場合を考える。葉1へ駒1を運ぶには、駒1の現在位置である頂点3から、頂点2を経由して頂点1まで交換する。

操作と確定する頂点頂点1・2・3・4の駒
開始時(2,4,1,3)(2,4,1,3)
辺 2−32-3 で交換(2,1,4,3)(2,1,4,3)
辺 1−21-2 で交換し、葉1を確定(1,2,4,3)(1,2,4,3)
残った道の葉2は既に正しいので、交換せず確定(1,2,4,3)(1,2,4,3)
辺 3−43-4 で交換し、残りも完成(1,2,3,4)(1,2,3,4)

未確定部分に何を許し、何を保つか

途中の未確定頂点では、駒の順序が乱れていてもよい。保つべきものは、確定済みの頂点を使わずに、残る駒をそれぞれの目的地へ運べることである。

具体的には、各成分の未確定部分が木としてつながり、そこに残る駒の番号の集合が、未確定頂点の番号の集合と一致している状態を保つ。選んだ葉の目的の駒はこの木の中にあるので、木の経路に沿って運べる。その葉に正しい駒を置いてから葉と駒を一つずつ除くと、残りも同じ条件を満たす。頂点が一つになれば、残る駒もその頂点の番号である。

このように、条件を満たす入力に対して必ず次の操作ができ、より小さい同じ形の問題へ進めることを示せば、その条件の十分性、つまり「条件を満たせば解がある」ことまで証明できる。各操作の前後で保たれる条件を不変条件という。必要条件を列挙した後は、「次の一手で何を確定し、残りのどの条件を保つか」を探す。

同じ葉への着目でも、ABC239 F「Construct Highway」の解説では辺そのものを作る。目標は、既存辺を残し、指定された各頂点の次数を満たす木を作ることである。既存辺が森であること、各頂点の現在次数が指定次数を超えないこと、指定次数の総和が 2N−22N-2 であることを調べる。ここで NN は頂点数である。さらに、複数の成分が残るなら、どの成分にも外へ接続する余地が必要になる。

各頂点の不足次数一つを「接続口」一つと考え、既存の連結成分ごとにまとめる。接続口には元の頂点番号を残しておく。既存辺が MM 本の森なら、成分数は c=N−Mc=N-M である。既存辺一本につき両端の次数を一つずつ使っているので、残る口の総数は 2N−2−2M=2c−22N-2-2M=2c-2 になる。接続口が一つの成分を葉として、二つ以上ある成分へつなぐと、二つの口を使って成分が一つ減る。併合後にも口が一つ以上残り、総数は 2(c−1)−22(c-1)-2 となる。

例えば、三成分の口の数が (1,2,1)(1,2,1) なら、中央の成分へ両側を順に結べる。先に両端の一口同士を結ぶと、その二成分は口を使い切り、中央の成分をつなげなくなる。合計数が正しいだけでは、任意の一手を選んでよいことにはならない。

各成分の口が正で総数が 2c−22c-2 なら、平均が2未満なので一口の成分がある。三成分以上では総数が cc より大きいため、二口以上の成分もある。従って上の操作を続けられ、最後の二成分は一口ずつなので、それらを結べば完成する。異なる成分だけを結ぶため閉路はできず、各頂点の口をちょうど使い切るため指定次数も満たす。

証明した選択を、出力へ戻す

証明が操作を与えている場合は、実際に行った選択をその場で記録する。辺を追加する構成なら元の頂点番号の組、交換する構成なら入力で指定された辺の番号を実行順に残す。縮約した成分の番号や、最終配置だけでは、求められた出力へ戻せない場合がある。

DPや探索で値を求めてから復元する場合は、各状態へ至った直前の状態を親情報として、選択とともに保存し、終状態からたどって順序を反転する。あるいは、保存した値と整合する遷移をもう一度調べ、始状態から選び直す。値が等しい候補が複数あれば有効な一つを選べばよいが、状態の段階が一方向へ進むなど、同じ状態へ戻らない規則を決める。更新済みの配列を過去の状態だと思って参照したり、同値の親をたどって循環したりしないよう、必要な段階の情報を保持する。

成立条件と計算量

成立する範囲と、止まるべき境界

葉からの交換が使えるのは、成分内の木の辺に沿う交換が許され、未確定頂点間で必要な駒を運べる場合である。成分を越えなければ目的地へ届かない駒があれば不可能と判定する。方向付きの移動や、交換ごとの追加制約がある問題へは、そのまま使えない。

辺を作る構成でも、閉路を残したまま木にはできず、接続口がない成分を他の成分へつなぐことはできない。逆に、既に一成分で必要な辺と次数が完成している場合には、追加する辺はない。「全ての段階で接続口が正」という条件は複数成分が残る間のものであり、完成後まで要求しない。

全体計算量と出力上限を分ける

構成の計算量には、存在条件の検査、候補や経路の探索、選択の記録、出力までを含める。出力する辺や操作の個数を KK とすれば、それらを書くだけでも Ω(K)\Omega(K) 時間が必要である。答えを全て保存すれば、そのために O(K)O(K) 空間も使う。局所操作が定数時間でも、操作を何回行うかは別に評価する。

葉へ駒を運ぶ方法では、各段階で駒の位置と木の経路を探索し直しても、一段階は O(N)O(N) 時間で済む。NN 頂点・MM 辺の入力から探索で全域森を作る O(N+M)O(N+M) の前処理と、高々 N−1N-1 段階の処理を合わせ、全体は O(N2+M)O(N^2+M) 時間となる。入力グラフ・森・位置情報と全交換列を保存するなら、空間は O(N+M+K)O(N+M+K) である。

さらに、実行時間に収まることとは別に、出力の操作上限も示す。残り rr 頂点の木で一つの葉へ運ぶ交換は高々 r−1r-1 回なので、全体の交換回数は

K≤(N−1)+(N−2)+⋯+1=N(N−1)2K\leq (N-1)+(N-2)+\cdots+1=\frac{N(N-1)}{2}

となる。ABC233 F「Swap and Sort」の解説では N≤1000N\leq 1000 なので高々499,500回となり、問題の500,000回以下という上限を満たす。これは交換回数の最小値を求めたという意味ではない。

元の出力条件で検査する

構成を終えたら、証明で使った要約量だけでなく、出力を元の入力へ適用した結果を確認する。

  • 辺の追加なら、指定本数か、頂点番号が範囲内か、自己ループや既存辺を含む重複がないかを確認する。ABC239 Fでは、追加辺が N−M−1N-M-1 本で、元の辺と合わせて連結になり、各頂点の次数が指定通りになることまで調べる。
  • 交換列なら、各番号が入力の辺を指すか、回数が上限以下かを確認する。その順で交換を再現し、全ての頂点に正しい駒が置かれるかを調べる。同じ辺を複数回使うことは許されるので、辺の追加における重複禁止と混同しない。
  • グリッドの構成なら、小さい模様の中だけでなく、模様同士の接続部分や外周でも隣接条件を満たすかを調べる。経路を出すなら始点・終点、各移動の隣接性、再訪を許すかどうかも元の条件へ戻す。

小さい例での再現は、必要条件の判定、局所操作の十分性、記録からの復元を別々に確かめる助けになる。全入力での保証には、各段階で残りの条件が保たれる理由と、必ず終了する理由も必要である。

問題一覧

各問題の解説は問題ごとの本文として執筆します。各項目には主題・追加で学ぶ技能・既習技能の役割を示します。

関連問題

前提・学習成果・出典

習得対象の目安: 水色(1200–1599)。存在判定の証明に操作列や親情報を対応させ、具体的な解へ戻す。

対象色の読み方は本書の読み方を参照してください。

概念上の親: モデル変換とアルゴリズム設計。問題へ進む前に、下記の直接前提のうち未習得の単元を確認する。

Canonical taxonomy: FinalTaxonomyBuild final-taxonomy-build-initial digest f1ae39bc7201c3374c108e800284e1e0068ce6f7a57f15b2a9e5219616e3c4fe / LearningUnit unit-constructive-witness

習得する技能

  • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

前提と範囲

共通前提: prereq-abc-advanced-v1 (1.0.0)。

直接の前提単元: なし。

このUnitを直接前提とする単元: なし。

存在条件の証明に対応する親・選択・局所操作を記録し、実際の構成へ戻す。

このUnitでは扱わないもの

  • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

根拠

葉を確定する交換と、成分の接続口を使う構成は、以下のABC233 F・ABC239 Fの公式問題文と個別公式解説を2026-10-23に再照合した。