全国統一プログラミング王決定戦本戦
Updated:
Source codes
Solutions
A - Abundant Resources
$1 \leq k \leq N$ に対し、以下のことを行う。
まず $S = \sum _ {i \in k} A _ i$ を求める。 $M = S$ とする。その後 $i = k, \dots, N - 1$ に対し、 $S \gets S + A _ i - A _ {i - k}$ とし $M \gets \max(M, S)$ とする。この後 $M$ を出力する。
ポイント
計算量は $O(N^2)$ である。
B - Big Integers
$X$ の $K$ 進法表記が $\{ A _ i \}$ であり、 $Y$ の $K$ 進法表記が $\{ B _ j \}$ である。私は vector<ll> を用いて leading zeros を擬似的に追加し、桁数を揃えて比較した。
ポイント
普通にやるだけである。
C - Come Together
まずこの問題は縦と横を独立の $1$ 次元の問題として考えることができる。次の問題を $O(H + W)$ で $2$ 回解いてその和が答えである。
横一列に $L$ 個のマスがある。座標 $i$ のマスの上に $X[i]$ 個の駒がある。このときあるマスに全ての駒を集結させたい。その移動回数の最小値を求めよ。
$Y = \infty$, $A = 0$, $B = \sum _ {i \in L} X[i]$, $Z = \sum _ {i \in L} i X[i]$ とする。 $i = 0, 1, \dots, L - 1$ に対し、以下の操作を実行する。
$Y \gets \min(Y, Z)$ とする。 $A \mathbin{ {+} {=} } X[i]$, $B \mathbin{ {-} {=} } X[i]$ とする。 $Z = Z + A - B$ とする。
最終的に出てきた $Y$ が答えである。
ポイント
これも $1$ 次元に落とし込めれば難しくはない。例を手計算しているうちに思いついた。実装する際は ll H[2]; のようにした。
D - Deforestation
まず竹の気持ちになって考える。伐採イベントが来るたびに竹は切られ、その長さの和がが得点となるのであるが、どうせすくすくと毎時刻伸びて行くのだから、最後の伐採以外に全く意味がない。したがって、その伐採時刻がその竹が切られることによって得られる得点である。
竹の番号 $i \in N$ でシミュレーションをすればよろしい。すなわち set<ll> S; を定義する。 typedef tuple<ll, ll, int> event; とする。 (番号, 時刻, L or R) とする。 L or R は L の方が早くないと意味がないので $0$ とし、 R は $1$ とする。あとは vector<event> V; に全てのイベントを入れておいて、尺取り法の要領で進めて行く。 $2$ 項目が $0$ の場合は時刻を $S$ に突っ込んでおく。 $S$ を見て最も大きい数が竹 $i$ を最後に切る時刻であるからスコアに加える。その後 $2$ 項目が $1$ の場合は時刻を $S$ から外しておく。これを繰り返す。計算量は $O(N \log N)$ である。
ポイント
これは割とすんなり。
E - Erasure
箱を消す魔法を唱えるのは数学やりすぎて魔法使いになってしまった私としては嬉しい表記だが、面倒なので、マスを塗ることにする。
DP による解法
DP による。 $0$-indexed とする。以下を定める。
$DP[i][j] = [0, i)$ は塗られているが、マス $i$ は塗られていない。その他のマスはどうでもいい。ここまで $[0, j)$ の部分区間のみ考えており、それらは全て考慮済みとする。そのような場合の数。
初期状態： $DP[0][0] = 1$, $DP[i][j] = 0$ (otherwise). 答え： $DP[N][N]$ 。遷移は「配る DP 」である。 $DP[i][j]$ で $j$ を増やすことを考察する。これから考慮する区間は $[k, j + 1])$ の形だけである。ゆえに、次の $2$ 通りしかない。
- $DP[i][j] \mapsto DP[i][j + 1]$,
- $DP[i][j] \mapsto DP[j + 1][j + 1]$.
このうち 1. の場合の数は、次の集合を好きに選ぶ場合の数である。 \[ A = \{ [k, j + 1) \subset [i + 1, j + 1) \mid j + 1 - k > K \}. \] 次式が成立する。同型は、集合の同型、つまり全単射がある、ここでは有限集合なので個数が一致することを意味している。 \[ A \cong \{ k \in \mathbb{N} \mid i + 1 \leq k < j + 1 - K \}. \] 後者が $\emptyset$ ならば $0$ 個であるし、そうでないならば $j - i - K$ 個である。よってこの時の場合の数は $\sharp \mathcal{P}(A) = 2 ^ {\max(0, j - i - K)}$ 通りである。
次に 2. であるが、まず次の集合を考察する。 \[ B = \{ [k, j + 1) \subset [0, j + 1) \mid j + 1 - k > K \}. \] 次式が成立する。 \[ B \cong \{ k \in \mathbb{N} \mid 0 \leq k < j + 1 - K \}. \] 求める場合の数は、 $B$ を好きに選ぶ場合の数から $A$ を好きに選ぶ場合の数を引いたものである。すなわち以下である。 \[ \sharp \mathcal{P}(B) - \sharp \mathcal{P}(A) = 2 ^ {\max(0, j + 1 - K)} - 2 ^ {\max(0, j - i - K)} \]
よって、遷移は以下の通りにまとめられる。 $j \in N$ に対し、 $0 \leq i \leq j$ に対し、
\[
\begin{align}
DP[i][j + 1] &\mathbin{ {+} {=} } DP[i][j] \times 2 ^ {\max(0, j - i - K)}, \\
DP[j + 1][j + 1] &\mathbin{ {+} {=} } DP[i][j] \times \left( 2 ^ {\max(0, j + 1 - K)} - 2 ^ {\max(0, j - i - K)} \right).
\end{align}
\]
包除原理による解法
定跡を $2$ つ使用するのだが、後者の定跡を私は使用したことがなかったので、そこを丁寧に議論したいと思う。
以下、絶対塗らないことを決めたマスを「 forbidden されたマス」と呼ぶことにする。 $S \subset N$ に対し、
$f(S) = S$ の全てのマスが forbidden され、他のマスはどうでもよい時の場合の数
と定める。包除原理により、解答は以下で与えられる。 \[ A = \sum _ {S \subset N} (-1)^{\lvert S \rvert} f(S). \] 包除原理の定跡 (その 1) に基づき、サイズで場合分けをする。すなわち、 \[ sum[k] = \sum _ {S \subset N, \lvert S \rvert = k} f(S) \] と定めると、以下が成立する。 \[ A = \sum _ {k = 0} ^ N (-1)^k sum[k]. \tag{E.1} \]
以上では $0$-indexed としていたが、以下では $1$-indexed とする。
$O(N^3)$ の解法 (TLE)
ここで $sum[k]$ を求めるべく、 DP をすることにする。以下を定める。
$DP[i][j][k] = i$ 個のマスが forbidden されており、そのうち最も大きい番号が $j$ である。ただし $i = 0$ のときは $j = 0$ とする。今まで $[1, k)$ の部分区間のみ考えていて、その検討は既に終わっている。そのような場合の数。
すると、初期条件は $DP[0][0][1] = 1$, $DP[i][j][k] = 0$ (otherwise). 答えは \[ sum[i] = \sum _ {j = 0} ^ N DP[i][j][N + 1] \tag{E.2} \] である。
遷移は $k$ を伸ばす。配る DP である。以下の $2$ パターンがありえる。
- $k$ を forbid する。すなわち $DP[i][j][k] \mapsto DP[i + 1][k][k + 1]$.
- $k$ を forbid しない。すなわち $DP[i][j][k] \mapsto DP[i][j][k + 1]$.
まず 1. の場合、今採用を検討している区間は $[x, k + 1)$ の形をしているので、 $k$ を forbid している以上、採用できない。つまり「検討している区間を全て採用しない」の $1$ 通りしかない。
次に 2. の場合は、 $j$ を forbid していてそれ以降は forbidden でないので、次の集合を好きに選んで良い場合の数である。
\[
\{ [x, k + 1) \subset [j + 1, k + 1) \mid k + 1 - x > K \}
\]
さっきと同様に、この場合の数は $2 ^ {\max(0, k - j - K)}$ 通りである。ゆえに遷移は以下の通りである。 $k = 1, \dots, N$ に対し、 $j = 0, \dots, k$ に対し、 $i = 0, \dots, k$ に対し、
\[
\begin{align}
DP[i + 1][k][k + 1] &\mathbin{ {+} {=} } DP[i][j][k], \\
DP[i][j][k + 1] &\mathbin{ {+} {=} } DP[i][j][k] \times 2 ^ {\max(0, k - j - K)}.
\end{align} \tag{E.3}
\]
ところがこれだと $O(N^3)$ であるから、さらに高速化をする必要がある。
定跡の解説 ( $\mathbb{Z}/2\mathbb{Z}$ に落とす)
まず (E.1) 式と (E.2) 式を組み合わせると、最終的な解答は、 $0 \leq i \leq N$ として、
\[
\begin{align}
A &= \sum _ {i \% 2 = 0} sum[i] - \sum _ {i \% 2 = 1} sum[i] \\
&= \sum _ {j = 0} ^ N \left( \sum _ {i \% 2 = 0} DP[i][j][N + 1] \right)
- \sum _ {j = 0} ^ N \left( \sum _ {i \% 2 = 1} DP[i][j][N + 1] \right) \tag{E.4}
\end{align}
\]
であるとわかる。 この観点から (E.3) 式を見直すと、 $i \in \mathbb{N}$ で持っておく必要がないことがわかる。つまり $i \in \mathbb{N}/2 \mathbb{N}$ で持っておけば十分である。 これが定跡である。
$O(N^2)$ の解答 (AC)
具体的には、
\[
dp[i][j][k] = \sum _ {l \% 2 = i} DP[l][j][k]
\]
と定める。つまり ll dp[2][5010][5010]; を確保する。すると初期条件は $dp[0][0][1] = 1$, $dp[i][j][k] = 0$ (otherwise). 答えは、 (E.4) 式である。すなわち、
\[
A = \sum _ {j = 0} ^ N dp[0][j][N + 1] - \sum _ {j = 0} ^ N dp[1][j][N + 1]
\]
である。遷移は (E.3) 式より、 $k = 1, \dots, N$ に対し、 $j = 0, \dots, k$ に対し、 $i = 0, 1$ に対し、
\[
\begin{align}
dp[1 - i][k][k + 1] &\mathbin{ {+} {=} } dp[i][j][k], \\
dp[i][j][k + 1] &\mathbin{ {+} {=} } dp[i][j][k] \times 2 ^ {\max(0, k - j - K)}.
\end{align}
\]
以上の時間計算量、空間計算量は $O(N^2)$ であるから、これで答えが出る。
ポイント
本番ではできなかった。 DP と包除原理の方針は両方思い浮かんだが、どっちにもトライして、どっちもできなかった。 あくまで末尾に注目する のがポイントだった。 DEGwer さんの『数え上げテクニック集』で反省しよう。
DP の解法
「区間は終端でソート」 と同じと考えられる。
区間がいくつか与えられ、そのうちのいくつかを選んで特定の被覆条件を満たすようにする方法は何通りか、という問題はしばしば出題されます。このような問題では、与えられた区間たちを終点座標の昇順に見ていくのが非常に強力です。これには、区間スケジューリング問題が貪欲法で解けることと同様の性質を使っています。 (『数え上げテクニック集』 3.3 節 by DEGwer さん)
包除原理
まず前半の定跡については、私の経験もあって、すぐに思いついた。
- $S$ のサイズ $k$ を固定すると $f(S)$ の値が一定だったりする
- DP によってサイズ $k$ の値でまとめたときの $f(S)$ の総和が求められたりする
といった構造を利用することがほとんどになる。今回は 2 番目の方法で明快に解くことができる。 (by けんちょんさんの解説記事「解法 3: 包除原理」)
後半の定跡は存在だけは知っていた。初めてやってみた。
さて、今、k をそのまま持つ必要はあるでしょうか? 包除原理の定義式に立ち返れば、 $k$ が偶数の場合の $DP[n][k]$ の和と、$k$ が奇数の場合の $DP[n][k]$ の和の差のみが重要であることが分かります。 (『数え上げテクニック集』 15.2 節 by DEGwer さん)
今回の場合は $\mathbb{Z} / 2 \mathbb{Z}$ で持っておけば十分だと思うが、差をいきなり持つ DP もあるようだ。
参考文献
- 全国統一プログラミング王決定戦 本選 E - Erasure (700 点) by けんちょんさん。 DP の方はこれと同じです。いつも参考にしています。
- 全国統一プログラミング王決定戦本戦-E Erasure by olphe さん。包除原理で「定跡」の部分を参考にした。
- 数え上げテクニック集 by DEGwer さん。