AtCoder Regular Contest 087
Updated:
Source codes
Solutions
C - Good Sequence
$a_i > N$ は消すしかない。$k = a_i$ たちの個数を数えて、 $k$ 個以上なら $k$ 個にする。$k$ 個未満なら $0$ 個にする。
D - FT Robot
$x$ 軸と $y$ 軸に沿った合計の移動距離がそれぞれ決まる。最初以外は、それらが正であるか負であるかを自由に選ぶことができる。よってそれぞれ DP で目的の座標に到達できるか判定できる。
解析学風に書く。$x$ 軸方向の $n$ ステップ目の移動を $f(n)$ とする。 $f_+ = \max(f, 0)$ 、 $f_- = \min(f, 0)$ とする。 $\lvert f \rvert = f_+ - f_-$ はわかっているので $S = \sum \lvert f \rvert = \sum f_+ - \sum f_-$ は既知である。あとは割り振って $\sum f = \sum f_+ + \sum f_- = X$ が達成できるかどうか確かめればよろしいのだが、 $\sum f_+ = (S+X)/2$ とできるかどうかを DP で調べる。 Partition は weakly NP-hard であり、 DP で解決可能である。
ポイント
最初は正にしか動けないことに注意。これで 2 WA 。
E - Prefix-free Game
(まだ AC していない)
ポイント
完全二分木はすぐわかった。 Grundy 数も気づいた。(同じものが 2 つあった時に真似っこで勝てるゲームは Grundy 数)
rng さん曰く 「Grundy 数だと気づいたら、考えるのをやめて実験しろ」 とのことだった。これは衝撃的だった。私には無理かもしれない。昔中学入試の格言で「筑駒の算数は全部列挙しろ！」というのがあったがあれに近いものを感じた。
実験の仕方も具体的に教えてくれた。その上で、必要ならプログラムを書いてみるといいでしょうとのことだった。
F - Squirrel Migration
包除原理の前まで
全てのリスが重心を通るような方法が引っ越しのコスト最大を達成する。このことは各辺 $(u, v)$ に対し、 $u$ 側の頂点数 $N_u$ と $v$ 側の頂点数 $N_v$ の小さい方の $2$ 倍を全て達成するからである。
重心が 2 つある場合は、 $(N/2)! \times (N/2)!$ である。
問題は重心が 1 つしかない場合である。この場合、重心を除いてできる木を $T_1, \dots, T_X$ とする。 $T = T_1 \cup \dots \cup T_X$ とする。
包除原理
求める場合の数は「全ての頂点のリスの引っ越し先が、違う木である」場合の数である。木はいっぱいあるから、同じ木に移動する場合の数を数える方がはるかに簡単である。包除原理を使用すると「余事象」を求めていることになる。だから、 $S \subset T$ に対し、
$f_S = S$ に含まれる頂点のリスが、同じ木に移動する場合の数 ($T \setminus S$ の頂点のリスはどこに行ってもいい)
と定めると、求める場合の数 $A$ は
\[ A = \sum_{S \subset T} (-1)^{\lvert S \rvert} f_S \]
となる。余事象に興味があるので、 $(-1)$ の右肩はこれで合っていることに注意されたい。特に $S = \emptyset$ の場合を含んでいることに注意されたい。
さて問題は $f_S$ である。混乱しやすいので、まず $S = S_1 \subset T_1$ の場合を考察しよう。まず、 $S_1$ の頂点のそれぞれのリスの行き先を選ぶ。これは 組合せ数ではなく順列 である。しかしコンテストのライブラリでは、適切な準備をした後、組合せ数は $O(1)$ で求まるので、 あえて組合せ数に階乗をかけて順列とする方が見通しがよかろう 1。というわけでここでは組合せ数に階乗をかけることで表す。残りのリスの行き先は階乗で表されるので、求める場合の数は
\[ f_{S_1} = \lvert S_1 \rvert! \begin{pmatrix} \lvert T_1 \rvert \\ \lvert S_1 \rvert \end{pmatrix} (N - \lvert S_1 \rvert)! \]
と求まる。これを一般の場合に拡張するのは容易である。 $i = 1, \dots, X$ に対し、 $S_i \subset T_i$ に対し、
\[ f_{S_1 \cup \dots \cup S_X} = \left( \prod_{i = 1}^X \lvert S_i \rvert! \begin{pmatrix} \lvert T_i \rvert \\ \lvert S_i \rvert \end{pmatrix} \right) \left( N - \sum_{i=1}^X \lvert S_i \rvert \right)! \]
と求まる。これを元の数式に戻すと、
\[ A = \sum_{S_i \subset T_i} (-1)^{\sum \lvert S_i \rvert} \left( \prod_{i = 1}^X \lvert S_i \rvert! \begin{pmatrix} \lvert T_i \rvert \\ \lvert S_i \rvert \end{pmatrix} \right) \left( N - \sum_{i=1}^X \lvert S_i \rvert \right)! \]
となる。
個数でまとめて DP
さてここで愚直に $(S_1, \dots, S_X)$ の組ごとに総和記号の中を計算していては間に合わない。まず動きやすいところから始めよう。直感的にも事実を追っても明らかなように、本問題は「$S_i \subset T_i$ で何を選ぶか」ではなく「選んだ頂点の数 $\lvert S_i \rvert$」だけが重要であるはずである。ところが上の式は何を選んだかにまだ依存している。現在のところ、依存している唯一の部分は総和記号のところだけなので、これを改良する。 $\lvert T_i \rvert$ 個のうちから $k_i$ 個選ぶ場合の数は $\begin{pmatrix} \lvert T_i \rvert \\ k_i \end{pmatrix}$ であるので、この分の計算がまとまる。ゆえに、以下の通りになる。
\[ A = \sum_{0 \leq k_i \leq \lvert T_i \rvert} (-1)^{\sum k_i} \left( \prod_{i = 1}^X k_i! \begin{pmatrix} \lvert T_i \rvert \\ k_i \end{pmatrix}^2 \right) \left( N - \sum_{i=1}^X k_i \right)! \]
これでも間に合わない。包除原理で計算量を減らす定跡である 「個数でまとめて DP 」 をここで使用する。すなわち、 $k = \sum_{i=1}^X k_i$ とすると、
\[ \begin{align} A &= \sum_{k = 0}^N \sum_{0 \leq k_i \leq \lvert T_i \rvert, \sum k_i = k} (-1)^{k} \left( \prod_{i = 1}^X k_i! \begin{pmatrix} \lvert T_i \rvert \\ k_i \end{pmatrix}^2 \right) \left( N - k \right)! \\ &= \sum_{k = 0}^N (-1)^{k} \left( N - k \right)! \sum_{0 \leq k_i \leq \lvert T_i \rvert, \sum k_i = k} \left( \prod_{i = 1}^X k_i! \begin{pmatrix} \lvert T_i \rvert \\ k_i \end{pmatrix}^2 \right) \end{align} \]
である。あとは総和記号を DP する。
\[ DP[x][k] = \sum_{1 \leq i \leq x, 0 \leq k_i \leq \lvert T_i \rvert, \sum k_i = k} \left( \prod_{i = 1}^x k_i! \begin{pmatrix} \lvert T_i \rvert \\ k_i \end{pmatrix}^2 \right) \]
と定める。答えは、
\[ A = \sum_{k = 0}^N (-1)^{k} \left( N - k \right)! DP[X][k] \]
である。初期状態は $DP[0][0] = 1$, その他は $0$ である。遷移の仕方はほぼ明らかな部類に入ると思う。数式をいじっても良いが、直感的に次のように理解できる。つまり、今 $x$ 番目の木から $i$ 匹選び、 $(x-1)$ 番目までの木から $k$ 匹選ぶとする。 $(x-1)$ 番目までの木から $k$ 匹どのように選んだとしても、その遷移の仕方は、それぞれの項に $i ! \begin{pmatrix} \lvert T_x \rvert \\ i \end{pmatrix}^2$ をかけたものであるのは共通している。以上より遷移の仕方は、全ての $1 \leq x \leq X$ に対し、全ての $0 \leq i \leq \lvert T_x \rvert$ に対し、全ての $0 \leq k \leq N - i$ に対し、
\[ DP[x][k+i] += DP[x-1][k] \times i ! \begin{pmatrix} \lvert T_x \rvert \\ i \end{pmatrix}^2 \]
である。あとは実装するだけ。
計算量
重心を求めるのに $O(N)$ 、階乗と組合せ数の下準備に $O(N)$ かかり、これ以降は任意の階乗や組合せ数は $O(1)$ で求めることができる。 DP の遷移はよく見ると $O(N^2)$ になっている。答えを求めるのに $O(N)$ である。全体の計算量は $O(N^2)$ である。
ポイント
Editorial の数式は一部間違っている。集合の選び方と集合の選ぶ個数を混同している。上が正しい。
実装でミスしたところ： Q.pop() し忘れ。 root の親を -1 としていて初期化も -1 としていた。 $DP[x][k]$ の添字を逆にしていてしばらく気づかなかった。最後のは結構アホだと思う。
Others
rng さんが言っていた典型問題に慣れていれば、私の考察力で十分クリアできるものばかりだった。
-
もちろん適切な準備をすれば順列だって $O(1)$ で求まる。しかし、例えば大学入試では「順列で考えると混乱の元だから、順列の記号は使わない。組合せ数を主に使用する方が良い」という指導方針が一部である。私も受験生時代からこうしていた。この editorial を作った方も順列を使っていない。決しておかしな方針ではない。 ↩