ABC 306 Ex — Balance Scale

考察

同じ重さだと分かったおもりを一つにまとめると、残る比較は「軽い側から重い側へ」の有向辺になる。このグラフが閉路を持たなければ比較結果を実現できる。そこで、入ってくる辺のない成分を取り除く部分集合DPを考える。ただし、取り除ける成分が複数あると同じ比較結果を重複して数えるため、包除原理で補正する。

数えるのは入力の辺上の比較結果

おもりを頂点、入力で比較する二頂点の組を無向辺とするグラフを G=(V,E)G=(V,E) と置く。V={1,…,N}V=\{1,\ldots,N\}、辺数は MM である。辺ごとに <・=・> を割り当て、その全てを満たす重さが存在する結果だけを数えたい。全割当ての列挙は 3M3^M 通りで、M≤136M\leq136 では大きすぎる。一方、N≤17N\leq17 なので、頂点集合を状態にする余地がある。

ここで、重さそのものや全頂点の大小関係を数えると、同じ比較結果を何度も数えてしまう。頂点 ii の重さを wiw_i とする。例えば三頂点の道 1−2−31-2-3 では、重さの列が (1,3,1)(1,3,1)、(1,3,2)(1,3,2)、(2,3,1)(2,3,1) のどれでも、観測する結果は w1<w2w_1<w_2、w2>w3w_2>w_3 で同じである。比較しない頂点1と3の関係が等しい・小さい・大きいと変わっても、答えへの寄与は合わせて1通りである。

等値辺を縮約して実現可能性を表す

比較結果を一つ固定する。= を割り当てた辺だけを残し、その連結成分を一頂点へ縮約する。成分内のおもりは全て同じ重さである必要があるので、以下ではこの成分を等値成分と呼ぶ。厳密な大小を表す辺は、必ず軽い側から重い側へ向ける。

縮約後に有向辺の自己ループが残るなら、一つの等値成分内で厳密な大小を要求しており矛盾する。有向閉路も、辺に沿って重さが増え続けて元へ戻るので実現できない。逆に、自己ループも有向閉路もない有向非循環グラフ(DAG)なら、トポロジカル順に並べた成分へ順に重さ 1,2,…1,2,\ldots を与えれば、全比較を実現できる。従って、有効な比較結果であることと、等値辺の縮約後がDAGであることは同値である。

この縮約では、入力の等値辺で結ばれた頂点だけをまとめる。先ほどの道で w1=w3w_1=w_3 としても、頂点1と3の間に等値辺の道はなく、二つの別の等値成分として扱う。DAGに重さを付ける方法やトポロジカル順の個数は数えず、元の各辺に割り当てた比較結果を一度だけ数える。

取り除くsourceを固定すると残りだけを数えられる

有向グラフの入次数0の頂点を source と呼ぶ。ここでは縮約後の等値成分が一頂点なので、sourceも一つの等値成分を指す。非空のDAGには必ずsourceがあるため、これを取り除き、残る頂点集合に同じ問題を解けばよさそうである。

残っている元の頂点集合を T⊆VT\subseteq V とする。G[T]G[T] は、TT 内の頂点と、その両端が TT にある入力辺だけを残した誘導部分グラフである。縮約後のsourceをいくつか選び、それらに含まれる元の頂点の和集合を、非空集合 s⊆Ts\subseteq T と置く。選ばないsourceが残っていてもよい。

このような選択では、ss に関係する辺の結果は全て決まる。

  • 両端が ss 内にある辺は全て =。 厳密な比較なら、その到着先の等値成分に入辺ができ、選んだ成分がsourceでなくなる。従って、G[s]G[s] の各連結成分がちょうど一つの選択された等値成分になる。
  • ss と T∖sT\setminus s を結ぶ辺は全て ss から外向き。 = なら同じ等値成分の一部を残したことになり、内向きならsourceの条件に反する。各比較では ss 側を軽くする以外にない。

逆に、任意の非空集合 s⊆Ts\subseteq T と、補集合 T∖sT\setminus s の有効な比較結果を一つ取ろう。ss 内の辺を全て =、補集合への辺を全て外向きにすれば、一つの完成結果が一意に定まる。追加した等値成分には入辺がなく、補集合内は既にDAGなので、新しい閉路は生じない。よって、この拡張は常に有効で、G[s]G[s] の各連結成分は確かにsourceとなる。元の結果から選んだsourceを除く操作と、この拡張操作は互いに逆である。

この対応で固定しているのは「選んだ成分がsourceである」ことであり、「sourceがそれらだけである」ことではない。この違いが、次の重複補正につながる。

完成結果ごとの寄与を1にする

一つずつsourceを選んで足すだけでは、sourceが二つある同じ完成結果を2回数える。二つをまとめて選んだ分を1回引けば、寄与は +1,+1,−1+1,+1,-1 で合計1になる。

道 1−2−31-2-3 の結果 1→2←31\to2\leftarrow3 では、sourceは頂点1と3の二つである。s={1}s=\{1\} と s={3}s=\{3\} で各1回足し、s={1,3}s=\{1,3\} で1回引く。最後の集合は非連結であり、二つのsourceを選ぶので符号が負になる。一方、同じ道の結果が w1=w2<w3w_1=w_2<w_3 なら、s={1,2}s=\{1,2\} は二頂点でも一つのsourceであり、符号は正となる。選んだsourceの個数は、一般には頂点数ではなく、G[s]G[s] の連結成分数で求まる。

一般に、固定した完成結果が kk 個のsourceを持つとする。k≥1k\geq1 であり、そのうち jj 個を選ぶ方法は (kj)\binom{k}{j} 通りある。選ぶ個数が奇数なら足し、偶数なら引くと、完成結果一つの合計係数は

∑j=1k(−1)j+1(kj)=1\sum_{j=1}^{k}(-1)^{j+1}\binom{k}{j}=1

となる。これは ∑j=0k(−1)j(kj)=(1−1)k=0\sum_{j=0}^{k}(-1)^j\binom{k}{j}=(1-1)^k=0 から、空の選択の項1を移せば分かる。全sourceを一度に選ぶよう強制する必要はなく、非空の部分集合を全て選んで符号を付ければ、どの完成結果も一度だけ数えられる。

部分集合DPの式と計算順

dp[T]dp[T] を、G[T]G[T] 上の有効な比較結果の個数とする。頂点がない場合は、比較もない空の結果が1通りなので

dp[∅]=1dp[\varnothing]=1

と初期化する。c(s)c(s) を、等値縮約する前の無向グラフ G[s]G[s] の連結成分数と定義する。前述の対応から、選択するsource数は c(s)c(s)、各選択で補集合から拡張できる結果数は dp[T∖s]dp[T\setminus s] である。従って、非空の TT について

dp[T]=∑∅≠s⊆T(−1)c(s)+1dp[T∖s]dp[T]=\sum_{\varnothing\ne s\subseteq T} (-1)^{c(s)+1}dp[T\setminus s]

を得る。ここでは G[s]G[s] の連結成分数を使う。ss の頂点数や、補集合の連結成分数を符号に使ってはならない。

まず全ての ss について c(s)c(s) を前計算する。入力を隣接行列で持ち、各誘導部分グラフをDFSやBFSで探索すれば、一集合あたり O(N2)O(N^2) 時間でよい。続いて、集合サイズの昇順、またはbitmaskの整数値の昇順に dp[T]dp[T] を求める。ss は非空なので、参照先は必ず真部分集合であり、先に計算できる。答えは dp[V]dp[V] を 998244353998244353 で割った余りである。

三頂点の道と三角形で違いを確かめる

道 1−2−31-2-3 では、二辺の三値比較の全 32=93^2=9 通りを実現できる。特に s={1,3}s=\{1,3\} は二成分なので符号が負となり、先ほどの二sourceの重複を引く。一方、s=Vs=V は連結なので、一成分を全て等値にする結果を正の符号で足す。

三角形 K3K_3 では全ての頂点対を比較する。有効な結果は、全て等しい1通り、二つだけ等しい 3×2=63\times2=6 通り、全て異なる 3!=63!=6 通りの合計13通りで、公式の入力例1と一致する。等値辺の連結性だけで全てを受理してはいけない。例えば w1=w2w_1=w_2、w2=w3w_2=w_3、w1<w3w_1<w_3 は縮約後の自己ループで不正となり、w1<w2<w3<w1w_1<w_2<w_3<w_1 は有向閉路で不正となる。

典型の発動条件

DAGのsource除去と包除原理

対象をDAGとして表し、入次数0の成分を取り除いて小さい問題へ帰着できるときに候補になる。除去可能な成分が複数あると、一成分ずつ足す再帰は同じ完成結果を重複して数える。選んだ成分を同時にsourceにする条件を調べ、残りの有効な結果との一対一対応が得られるなら、非空のsource選択に交互符号を付けて補正できる。

全subsetの連結成分数前計算

頂点数が小さく、部分集合DPの係数が誘導部分グラフだけで決まるときは、係数を全 2N2^N 集合について先に求める。各DP遷移で探索を繰り返さず、前計算した値を参照すれば、全ての部分集合とその部分集合の列挙を O(3N)O(3^N) 時間で処理できる。

問題固有の要素

= の結果は双方向の有向辺として扱わず、等値辺でつながる頂点の縮約として表す。一方、同じ重さを割り当てられることだけを理由に、入力辺でつながらない二成分をまとめない。観測する辺だけに注目したからこそ、sourceを選ぶ集合 ss の内部と境界の比較が一意に決まり、重さの割当てを列挙せずに済む。

正当性

等値辺の各連結成分を縮約し、厳密な比較を軽い側から重い側への辺とする。実現可能な比較結果から自己ループや有向閉路は生じない。逆に縮約後がDAGなら、トポロジカル順の位置を成分の重さにできるため、比較結果は実現可能である。

非空集合 s⊆Ts\subseteq T を選び、内部辺を全て等値、補集合との辺を全て外向きに固定する。この操作は、補集合の有効な比較結果から、G[s]G[s] の各連結成分をsourceとする有効な結果への一意な拡張である。反対に、完成結果からsourceの非空な部分集合を選ぶと、その和集合 ss の内部辺と境界辺はこの固定と一致する。従って、選択されたsource数は c(s)c(s) となり、各選択の完成結果を数える項は dp[T∖s]dp[T\setminus s] に対応する。

任意の非空の有効な結果は少なくとも一つのsourceを持つ。source数が kk の結果は、jj 個を選ぶ (kj)\binom{k}{j} 通りに符号 (−1)j+1(-1)^{j+1} を付けた和で数えられ、その係数は1である。不正な結果は拡張で生成されない。空の結果を1通りとする初期値から、真部分集合の値を用いてこの包除を行うことで、全ての有効な比較結果を過不足なく数える。

実装上の注意

  • 頂点 ii をbit i−1i-1 に対応させる。集合の整数表現を mask、その非空部分集合を s とすると、s = mask から始め、s = (s - 1) & mask で0になる直前まで列挙できる。mask ^ s が補集合であり、mask より小さいので昇順のDPで参照できる。
  • c(s)c(s) が奇数なら加算、偶数なら減算する。演算は 998244353998244353 を法として行い、減算後の負値を正規化する。
  • s=Ts=T の項も含める。残りが空のとき dp[∅]=1dp[\varnothing]=1 が必要で、0では全ての値が0になってしまう。
  • 孤立頂点は誘導部分グラフの一成分として数える。ただし比較辺がないので、その重さを選ぶ追加の係数は掛けない。辺のない集合上の比較結果は空の結果1通りであり、離れた成分の重さを並べる方法も掛けない。

復習の核

  • 比較結果を数えるときは、入力で比較していない頂点間の大小を勝手に補って数えない。
  • 等値辺で縮約し、厳密な大小を一方向へそろえると、実現可能性をDAGの条件へ移せる。
  • 包除の符号は「何個の条件を同時に選んだか」で決まる。本問では選んだ頂点数ではなく、選んだsource数、すなわち誘導部分グラフの連結成分数を見る。
  • 遷移を導くときは、小さい結果からの拡張と完成結果からの分解を両方確認し、固定した完成結果一つの係数を調べる。

計算量と制約

時間

O(3N+N22N)O(3^N+N^2 2^N)。全誘導部分グラフの成分数を隣接行列上の探索で前計算する部分が O(N22N)O(N^2 2^N)。DPでは各頂点が「ss 内」「T∖sT\setminus s 内」「TT 外」の三つのいずれかに属するため、全ての組 (T,s)(T,s) は 3N3^N 通りで、非空の ss を使う遷移数は 3N−2N3^N-2^N 通りとなる。

空間

O(2N+N2)O(2^N+N^2)。dpdp と連結成分数の配列が O(2N)O(2^N)、隣接行列が O(N2)O(N^2)、各探索で使う一時領域が O(N)O(N) である。

制約との対応

2≤N≤172\leq N\leq17、1≤M≤N(N−1)/21\leq M\leq N(N-1)/2 で、同じ頂点対の比較は重複しない。最大で M=136M=136 となるため辺の全割当て列挙は使わず、217=1310722^{17}=131072 状態、317−217=1290090913^{17}-2^{17}=129009091 遷移の頂点集合DPを用いる。全ての状態で答えを 998244353998244353 を法として保持する。入力の上限は実行時間3秒・メモリ1024 MiBであり、各遷移を配列参照と剰余の加減算だけにする。

出典

分類・前提・執筆情報

掲載状態: 収録済み

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

最終確認:

学習上の位置付け

主題の単元: 包除・Möbius反転で重複を補正する

主題
追加で学ぶ技能
    なし
    既習技能
    • 部分集合・bitmask状態DP: bitmaskの各bitが表す意味を定め、部分集合間の遷移を正しく設計できる。
    • DAGのtopological processing: 依存辺の向きを定め、入次数またはpostorderからtopological順を作って制約伝播・DP・scheduleを処理する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    主タグ: 集合上の包除原理

    補助タグ: DAGのtopological processing 部分集合・bitmask状態DP

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

    学習の位置

    体系上の位置: 包除・Möbius反転で重複を補正する

    • 条件集合の重なり構造を特定し、包除またはMöbius反転の符号と範囲を正しく設定できる。

    先に読む単元:

    • DAGのtopological processing — 状態グラフのモデリングと探索で得た考え方と実装を再利用し、DAGのtopological processingの発動条件・正当化・境界を重複なく学ぶ。
    • 部分集合・bitmask状態DP — DPの最小十分状態で得た考え方と実装を再利用し、部分集合・bitmask状態DPの発動条件・正当化・境界を重複なく学ぶ。

    この解説で扱わないこと:

    • 選択順を二項係数だけで式化する数え上げ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題