ちゅこだい、響きがちゅこ
全探索。上手く実装しましょうという問題。
普通にやると $16!$ とかかかるところ、 「次に決めるペアのうち1人は必ず残っている中で番号最小の人」とすることで、 重複を除けて $15 \times 13 \times ... \times 1 \simeq 2 \times 10^6$ 程度に収まる。
で、それをどうやって実装するか。
たとえばグローバルに used = [0,0,0,0,…]
のような長さ $2N$ の配列を持っておく。
人 $i$ をペアに使うと仮定したら used[i]=1
にする。
再帰関数が呼ばれたら、現在のusedから未使用のペアを1つ仮定して(usedを変更して)次の再帰に渡す。
再帰から帰ってきて次のペアの再帰を呼ぶとき、関数を抜けるとき、きちんと仮定した状態を元に戻す。
よくあるbitDPのような手法も使える。
$S$ の小さい方から計算していける。
立っているbitが奇数の場合は飛ばすなどする。
立っている中で一番小さいbit $i$ と、もう1つ立っているbit $j$ をペアにするとして、
今回、求めるべきスコアがXORのため、 途中ではどの暫定スコアが結果的に最大を実現できるかわからなくて、全部持っておく必要がある。
そのため、結果的には再帰より遅くなる。まぁそれでも十分間に合う範囲なので、bitDPの書き方に慣れていれば。
重複のないペアの作り方は、特定の条件を満たす順列と1対1対応できる。
条件を満たす順列に限定した中で次に大きいものを求めるのは、償却 $O(1)$ で行える。
上手く言い換えての二分探索。
DPで直接求めようとするなら、たとえば以下のようにして平均値の最大値が求められるが、$O(N^2)$ かかる。
このような場合、答えを仮定して「平均値 $X$ 以上が実現可能か?」を二分探索する方法がある。
判定が $O(N)$ でできるなら、全体で $O(N \log{A_{max}})$ で可能。
これなら個数を気にせず、常に総和が大きいものだけをDPに記録すればよくなる。
中央値に関しては、定義によって以上・未満の境界が変わるので注意する。
グラフ問題で、頂点 $s→t$ をちょうど $L$ 回で移動するときの○○を求めよ($L$ はそれなりに巨大)、 という問題は、経路数で見たことがある。
(特に時刻により追加されるとかではない)普通のグラフがあったとして、 ちょうど $L$ 回で $s→t$ に移動できる経路の個数を求めたい。
$$ A[u][v] = \begin{cases} 1 & (u→vに辺があるとき) \\ 0 & (ないとき) \end{cases} $$
とすると、$A^L[s][t]$ がその答えとなる。
ダブリングにより高速化すると、
行列1回の乗算 $O(N^3)$ を $\log{L}$ 回行えばよいので、$O(N^3 \log{L})$ で全て求められる。
ある頂点 $k$ について、
これを $k=1~N$ まで足し合わせると $A^{X+Y}[i][j]$ となるが、この式は行列の乗算と同じことになるということ。
今回はこれの応用バージョンとなる。
$+,\times$ の演算子を、$\min, \max$ にそれぞれ置き換えてしまうと、この問題の解法となる。
(もう少し言葉を添えると、$A^X[i][k]$ は 「$i→k$ まで $X$ ステップで行く経路 $P$ の中で最後に追加された辺の時刻を $t_P$ として、 全てのそのような経路の中での $t_P$ の最小値」)
時刻的に最も早いものが求められているので、$k=1~N$ の中でのminが $A^{X+Y}[i][j]$ となる。
今回と演算子は異なるが、可能な条件が以下に説明されている。こちらは最短距離を求めている。
$+,\times$ に相当する演算子と集合が、半環 であればよいらしい。つまり、
包除原理。状態のまとめ方がきれいだが、かなり難しい。
以下、方針は概ね公式Editorialと同様。
$A_i$ が全て異なるという条件がないなら話は簡単で、 $1~M$ の中に $D_i$ の倍数は $\dfrac{M}{D_i}$(切り捨て)個あるのだから、 $i=1~N$ について全て掛け合わせればよい。
しかし実際は同じ値があってはならない。
包除原理を使えそうだが、何を1つの状態として、$(-1)^k$ の $k$ に相当する部分を数えればよいか?
添字のペア $(i,j)$ について、「$A_i$ と $A_j$ が(明示的に)同じ」ことを1つとして、 $\frac{N(N-1)}{2}$ 通りのペアのうち何個が同じかを数えればよい。
これは、$N$ 頂点の無向グラフで、ペアを辺として考えるとイメージしやすい。
ひとつながりになった連結成分の頂点に相当する $A_i$ は全て同じ値となる。
この時、$(1,2)$ かつ $(2,3)$ が同じなら自動的に $(1,3)$ も同じになるが、
包除原理の上では機械的に「$S$ として $(1,3)$ を含む場合」「含まない場合」別々に数えなければならない。
(なんとなく直感に反する)
D = (② ③ ⑤ ⑦) Sに含む:1 含まない:0 ②③ ②⑤ ②⑦ ③⑤ ③⑦ ⑤⑦ パターン数 0 0 0 0 0 0 → + M/2 * M/3 * M/5 * M/7 1 0 0 0 0 0 → - M/6 * M/5 * M/7 0 1 0 0 0 0 → - M/10 * M/3 * M/7 1 1 0 0 0 0 → + M/30 * M/7 1 1 0 1 0 0 → - M/30 * M/7 ...
さて、これで方針は決まったが、困ったことも残る。
頂点ならともかく、辺について含む/含まないの全組み合わせは $2^{\frac{N(N-1)}{2}}$ で最大 $2^{120}$ になる。
制約からして、なんとか頂点集合である $2^N$ 通りくらいにまとめたい。
しかしこれ、たとえば $V=\{②③⑤⑦\}$ に関係するような $S$ を考えると、 連結のしかたにいろんなパターンがあってそれぞれ個数が異なるし、 連結のしかたが同じでも辺の組み合わせや数が異なる場合もあるしで、結構まとめづらそう。
全体が複数の連結成分に分かれているかもしれないことが複雑さに拍車をかけているので、 例えば「番号最小の頂点 $u$ が含まれる連結成分の頂点集合 $V'$」を固定する。
一部分でも連結であることが保証されると、幾分か計算しやすくなる。各頂点集合について
とすると、$u$ を含む連結成分については、その寄与は $g(V')h(V')$ で求められる。
$V'$ 以外の部分については、より小さい部分集合の $DP$ を利用できる。
なので、$g(),h()$ を求めれば計算できそうなことがわかった。
$g()$ については、集合のLCMを小さい方から計算していくと、$M$ をそれで割った値が該当する。
LCMがオーバーフローするが、$M$ を超えたら $g()$ は0なので、$M+1$ で天井を切っておくなどすればよい。
$h()$ については、定義上、$V$ のサイズが同じなら答えも同じとなる。
サイズを引数にとることにして、$h(1)~h(N)$ を求められればよい。
特に連結を考慮しない全ての辺集合の集合($2^{\frac{|V|(|V|-1)}{2}}$ 通り)から、 連結でないものを除くことを考える。
連結でない場合、ある頂点 $u$ を固定して、$u$ の含まれる連結成分以外にいくつかの非連結頂点が存在する。
u--○ ○--○ | ○ ↑非連結頂点
非連結となった頂点集合 $U$ 内での(連結を考慮しない)辺の張り方は、 完全グラフの辺 $\frac{|U|(|U|-1)}{2}$ 本から 何本かを選ぶことに相当するので、二項係数で表現できるのだが、
完全グラフの辺数を n として、そこから0本、1本、... n本選ぶ場合の数は nC0, nC1, ..., nCn
ここで、二項係数での左から奇数番目の和と偶数番目の和は、等しくなる。
1 3 3 1 1+3 = 3+1 = 4 1 6 15 20 15 6 1 1+15+15+1 = 6+20+6 = 32
なので、ほとんどの $U$ において、その間の辺の張り方で奇数と偶数は等しい。
$u$ を含む連結成分側の辺数の偶奇がどっちだろうが、○+偶数 と ○+奇数 の個数が同じなので、
辺数の偶奇による+1と-1は互いに打ち消しあうことになる。
唯一、$|U|=1$ の場合のみ、$U$ 内で張れる辺の候補は0本(偶数)の1通りのみとなり、+1 として寄与する。
よって、非連結となる1頂点の選び方が $|V|-1$ 通り、 $u$ が含まれる連結成分内の辺の張り方の寄与が $h(|V|-1)$ なので、漸化式によって求めることができる。
要は階乗 $(|V|-1)!$ を $|V|$ の偶奇によって正または負にすればよい。
$DP[\phi]=1$ として、以上のやり方でDPを小さい方から計算していける。
計算量は、$V$ を全通り、さらにその中で $V$ の部分集合を全通り試すので、$O(3^N)$ となる。
頂点集合 $V$ を固定し、その中で固定した頂点 $u$ を含む連結成分を考える、という手法が2回登場する。
グラフの数え上げでは、それだけよく使う手法なのだろう。