この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
42. JOI 2015 予選 4 – シルクロード
移動と待機の組み合わせをすべて列挙して疲労度の合計を探索する場合、計算量は \Omega(2^{M} N) となり、M \leq 10^3 であることから、実行時間制限に違反しそうです。
1 日の行動は次の都市への移動と待機の 2 パターンしかないため、j 日目には都市 i に到着している移動の j 日目までの疲労度の最小値を \mathrm{dp}[i][j] とすると以下の更新式が立式できます。
\begin{aligned}
\mathrm{dp}[i + 1][j + 1] &= \min (\mathrm{dp}[i + 1][j + 1], \mathrm{dp}[i][j] + D_{i + 1} \times C_j) \\
\mathrm{dp}[i][j + 1] &= \min(\mathrm{dp}[i][j + 1], \mathrm{dp}[i][j])
\end{aligned}
\mathrm{dp}[i][j] の初期化ですが、JOI 君が 0 日目に都市 0 に疲労度 0 で滞在していると考え、\mathrm{dp}[0][0] は 0 で初期化し、それ以外の \mathrm{dp}[i][j] はどのような移動でも蓄積できないほど大きな疲労度で初期化します。具体的には M \max_{ij} D_i C_j \leq 10^9 より 10^9 + 1 で初期化します。
\mathrm{dp}[N][M] が答えになります。
計算量は 1 日分の計算をするのに O(N) かかるため、全体で O(MN) = 10^6 程度です。
43. パ研杯2019 D – パ研軍旗
各列の色の組み合わせを列挙しながら塗り替えるマスの個数を探索する場合、雑に考えると計算量は \Omega(3^N) になります。有志コンテストの解説 には正確な場合の数が記載されています。そちらをもとに見積もると計算量は \Omega(2^N) です。いずれにせよ N \leq 999 のため、制限時間以内に求解するのは難しそうです。
旗を 1 列目から列ごとに塗り替えるとします。j 列目まで塗り替えが終わった段階で、j + 1 列目の塗り替えの場合は以下の 3 通りです。
- 第 j 列が青ならば第 j + 1 列は白または赤で塗る。
- 第 j 列が白ならば第 j + 1 列は赤または青で塗る。
- 第 j 列が赤ならば第 j + 1 列は青または白で塗る。
1 列目から j – 1 列目までの各列の色は上記の場合分けに影響しないことに着目します。
\mathrm{dp}[j][s] を j 列が s 色であるデザインの第 j 列までに塗り替えたマスの個数の最小値とします。以下の更新式を立式できます。
\begin{aligned}
\mathrm{dp}[j + 1][\text{青}] &= \min(\mathrm{dp}[j][\text{白}], \mathrm{dp}[j][\text{赤}]) + 5 – \text{第} j + 1 \text{列の青のマスの個数} \\
\mathrm{dp}[j + 1][\text{白}] &= \min(\mathrm{dp}[j][\text{赤}], \mathrm{dp}[j][\text{青}]) + 5 – \text{第} j + 1 \text{列の白のマスの個数} \\
\mathrm{dp}[j + 1][\text{赤}] &= \min(\mathrm{dp}[j][\text{青}], \mathrm{dp}[j][\text{白}]) + 5 – \text{第} j + 1 \text{列の赤のマスの個数} \\
\end{aligned}
\mathrm{dp}[j][s] の初期化ですが、第 0 列を用意して \mathrm{dp}[0][s] = 0 にしておくと 1 列目の計算も上記の更新式で計算できます。j > 0 の \mathrm{dp}[j][s] については旗のマスの総数より大きな値で初期化します。N \leq 999 より、例えば 10^4 (> 5 N) で初期化します。
\min_s \mathrm{dp}[N][s] が答えになります。
計算量は O(N) = 10^3 程度です。
44. AOJ 1167 – ポロック予想
10^6 より小さい正四面体数の個数は \frac{1}{6} n(n + 1)(n + 2)<10^6 を満たす最大の n です。この n を n_0 とおきます。以下の計算から 100 \leq n_0<200 であることがわかります。
100 \times 101 \times 102<100 \times 200 \times 200<6 \times 10^6<200 \times 200 \times 200<200 \times 201 \times 202
T_{i} を i (i \leq n_0) 番目の正四面体数とします。T_{i} は公式が与えられているため、O(n_0) の計算量で \{T_i\}_{i=1}^{n_0} を用意できます。
各正四面体数の利用する個数を列挙する場合、下記のように T_2 = 4 を使う回数と T_3 = 10 を使う回数の組み合わせだけで 10^{10} を超えるため、時間制限に違反しそうです。
\sum_{i = 0}^{10^6 / 4} \frac{10^6 – 4 i}{10} = \sum_{i = 0}^{10^6 / 4} \frac{4 i}{10} = \frac{4}{10} \frac{1}{2} \frac{10^6}{4} \left(\frac{10^6}{4} + 1 \right) > \frac{10^{12}}{80} > 10^{10}
個数制限のないナップザック問題と同様に考えて動的計画法で解きます。
\mathrm{dp}[i][j] を i 番目の正四面体数まで使えるときの j を表すのに必要な正四面体数の個数の最小値とします。以下の更新式を立式できます。
\mathrm{dp}[i + 1][j] = \min(\mathrm{dp}[i][j], \mathrm{dp}[i + 1][j – T_{i + 1}] + 1)
初期化は \mathrm{dp}[0][0] は 0 で初期化し、それ以外の \mathrm{dp}[i][j] は T_1 = 1 が 10^6 個あれば j を表現することは可能であるため、10^6 で初期化します。
同じ T_i を何度も使用してよいため更新は j = 0 から j = 10^6 – 1 まで順に行います。あとは入力された各性整数 q に対して \mathrm{dp}[n_0][q] を出力すれば答えになります。奇数の正四面体数のみ使える場合も同様に計算します。
メモリ制限が 131072 KB, およそ 10^8 B であるため、\mathrm{dp}[i][j] を n_0 \times 10^6 で用意するとメモリ制限に違反します。
そこで動的計画法の表は使いまわします。使いまわす場合、メモリの使用量は 10^7 B 程度になり、制限に違反しません。
計算量は 2 \times n_0 \times 10^6<4 \times 10^8 程度です。時間制限が 8 秒であるため、違反せずに求解できます。
45. AOJ 2199 – 差分パルス符号変調
すべてのコードブックの値の組み合わせを列挙して探索する場合、計算量は \Omega(M^N) となり、1 つのデータセットでも時間制限に違反しそうです。
以下に着目して動的計画法で解くことを考えます。
- 第 n 番目の信号の復元には以下があれば十分であること。
- 第 n – 1 番目の復号化後の主力信号 y_{n-1}
- 使用するコードブックの値 C[k_n]
- 第 n 番目までの元の入力信号と復号化後の出力信号との差の二乗和は以下が分かれば計算できること。
- 第 n – 1 番目までの二乗和
- 元の信号 x_n
- 復号化後の出力信号 y_n
\mathrm{dp}[n][y] を復号化後の n 番目の出力信号が y になる復号化の n 番目までの二乗和の最小値とします。f(y) \coloneqq \max (0, \min(255, y)) として以下の更新式を立てることができます。
\mathrm{dp}[n + 1][f(y + C_j)] = \min(\mathrm{dp}[n + 1][f(y + C_j)], \mathrm{dp}[n][y] + (f(y + C_j) – x_{n + 1})^2)
初期化は y_0 = 128 であることから \mathrm{dp}[0][128] は 0 で初期化し、それ以外の \mathrm{dp}[n][y] は N 番目までの二乗和の最大値を超える値にします。例えば 256^2 \times N で初期化します。
\min_{y} \mathrm{dp}[N][y] が求める二乗和の最小値です。
計算量は 1 つのデータセットに対し O(MN) = 10^6 程度、y の取りうる範囲の大きさ 256 を考慮すると10^8 程度です
問題文にデータセットの個数の上限が記載されておりません。上記の解法は各データセットごとに処理する解法であるため、提出前に時間制限に違反するかは不明です。ただ、数個のデータセットには耐えられる程度の速度で求解できます。実際、下記の解答例では制限時間内に求解できました。
