この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
34. ALDS_10_A – フィボナッチ数
愚直に再帰関数で実装すると、第 n 項を求めるときに再帰関数を呼び出す回数 g(n) は以下の漸化式を満たします。
g(n) = \begin{cases}
1&(n = 0) \\
1&(n = 1) \\
g(n – 1) + g(n – 2) + 1
\end{cases}
fib(n) = (g(n) + 1) / 2 であるため、フィボナッチ数列の一般項から以下が g(n) の一般項となります。フィボナッチ数列の一般項については例えば 高校数学の美しい物語 フィボナッチ数列の一般項と数学的帰納法 を参照ください。
g(n) = \frac{2}{\sqrt{5}} \left ( \left ( \frac{1 + \sqrt{5}}{2}\right )^{n + 1} – \left ( \frac{1 – \sqrt{5}}{2}\right )^{n + 1} \right ) – 1
計算量は 1.6<(1 + \sqrt{5}) / 2 を使って下から評価すると \Omega(g(n)) \geq \Omega(1.6^n) = 10^9 程度となるため、時間制限に違反しそうです。
メモ化再帰を使うと、各項を一度計算するだけで第 n 項が求まるため、計算量を O(n) に抑えることができます。メモ化再帰については 再帰関数を学ぶと、どんな世界が広がるか の「1-3. 動的計画法 (メモ化再帰) へ」をお読みください。
再帰関数を使わない場合 (動的計画法の for 文を使った実装) についても上記の web ページに説明があります。
35. DPL_1_B – 0,1ナップザック問題
N \leq 100 であるため、ビット全探索は難しそうです。
動的計画法を使うと O(NW) = 10^6 程度の計算量で求解できます。詳細は 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ 「2 ナップサック問題」を参照ください。
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 の「1. ナップサック DP」にある通り、動的計画法のテーブルを使い回すことも可能です。
36. DPL_1_C – ナップザック問題
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 の「2. 個数制限なしナップサックの場合」に解説があります。
計算量は O(NW) = 10^6 程度です。この問題も動的計画法のテーブルを使いまわすことが可能です。
37. DPL_1_A – コイン問題
個数の制限の無いナップザック問題と同様に考えて動的計画法で解きます。ナップザック問題では価値を最大化しましたが、本問題では枚数の最小化を行います。
\mathrm{dp}[i][j] を i 番目までのコインを利用できる場合に j 円支払うときのコインの最小の枚数とします。
ナップザック問題と同様に考えると、以下の更新式が立式できます。
\mathrm{dp}[i][j] = \min(\mathrm{dp}[i][j – c_i] + 1, \mathrm{dp}[i – 1][j])
コインが無い場合は 0 円のみ支払えるため、\mathrm{dp}[0][0] は 0 で初期化します。それ以外の \mathrm{dp}[i][j] は取りうるコインの枚数の最大値より大きい値で初期化します。この問題では額面が 1 円のコインが存在するため、最大値は n です。n \leq 50,000 であるため、例えば 10^6 で初期化します。
j = 0 から j = n まで順に前述の更新を行えば求解できます。計算量は O(mn) = 10^6 程度です。
38. ALDS_10_C – 最長共通部分列
X, Y の長さが最大 1000 であるため、部分列を全探索する解法は時間制限に違反しそうです。
典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～ の「問題 8: 最長共通部分列 (LCS) 問題」に本問題の解説があります。基本的な考え方はこのページの通りです。
ここでは例として X=\{a,b,c,b,d,a,b\}, Y=\{b,d,c,a,b,a\} のときの動的計画法の表を書き下してみます。動的計画法の表は下表のように
- 縦: X の先頭部分の部分列の長さ
- 横: Y の先頭部分の部分列の長さ
- 値: 上記の部分列の最長共通部分列の長さ
の表になります。この表では最長共通部分列が複数ある場合は X の部分列が短い方、X の部分列が同じ場合は Y の部分列が短い方を採用しています。
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | |
|---|---|---|---|---|---|---|---|
| 0 | 0 (\{\}) | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 0 | 0 | 0 | 1 (\{a\}) | 1 | 1 |
| 2 | 0 | 1 (\{b\}) | 1 | 1 | 1 | 2 (\{a, b\}) | 2 |
| 3 | 0 | 1 | 1 | 2 (\{b, c\}) | 2 | 2 | 2 |
| 4 | 0 | 1 | 1 | 2 | 2 | 2 | 2 |
| 5 | 0 | 1 | 2 (\{b, d\}) | 2 | 2 | 2 | 2 |
| 6 | 0 | 1 | 2 | 2 | 3 (\{b, c, a\}) | 3 | 3 |
| 7 | 0 | 1 | 2 | 2 | 3 | 4 (\{b, c,a, b\}) | 4 |
左上から行優先、あるいは列優先に動的計画法のテーブルを更新していくため、1 データセットに対する計算量は O(q|X||Y|) です。ここで |W| は列 W の長さとします。
X または Y の長さが 100 を超えるデータセットが含まれる場合、q は 20 以下である。
と記載されているため、計算量は 10^8 程度に収まります。
39. JOI 2011 予選 4 – 1 年生
+ と – の組み合わせを全列挙するのは \Omega(2^N) = 10^{30} 程度かかるため、実行時間制限に違反しそうです。
a_i を与えられた数字の列の第 i 項とします。式を固定 ( + と – の組み合わせを固定 ) して、f(i) を式の左から a_i まで計算した値とします。例えば、 8 + 3 – 2 – 4 + 8 – 7 – 2 – 4 – 0 + 8 = 8 という式に対し f(4) = 5 です。f について以下の漸化式が成立します。
f(i + 1) = \begin{cases}
f(i) + a_{i + 1}& (i \text{番目の演算子が} + \text{のとき}) \\
f(i) – a_{i + 1}& (i \text{番目の演算子が} – \text{のとき}) \\
\end{cases}
上記の式は f(i + 1) を計算するためには、1 つ前の値 f(i), i 番目の演算子、a_{i + 1} の 3 つが分かれば十分であることを表しています。このことをもとに \{a_1, \dots, a_N\} の部分列 \{a_1, \dots, a_i\} での式の個数から部分列 \{a_1, \dots, a_{i+1}\} での式の個数を計算できないか考えます。
\{a_1, \dots, a_N\} の部分列 \{a_1, \dots, a_i\} の項と項の間に + または – を入れてできる式のうち、以下を満たす式を「第 i 項までの式で値が j になる式」と呼び、その個数を \mathrm{dp}[i][j] とします。
- 左から計算したとき計算の途中で現れる数が全て 0 以上 20 以下です。
- 式の計算結果は j です。
上記の f についての漸化式を j について書き直してみます。
j = \begin{cases}
(j – a_{i + 1}) + a_{i + 1}& (i \text{番目の演算子が} + \text{のとき}) \\
(j + a_{i + 1}) – a_{i + 1}& (i \text{番目の演算子が} – \text{のとき}) \\
\end{cases}
第 i + 1 項までの式で値が j になる式は上記の式に従って、第 i 項までの式で値が j – a_{i + 1} になる式、または第 i 項までの式で値が j + a_{i + 1} になる式からのみ遷移することがわかります。よって \mathrm{dp}[i + 1][j] は \mathrm{dp}[i][j – a_{i + 1}] と \mathrm{dp}[i][j + a_{i + 1}] の和になります。ただし、j – a_{i + 1} が負になる場合や j + a_{i + 1} が 20 を超える場合は除外します。
\mathrm{dp}[i][j] の更新式は以下の通りです。
\mathrm{dp}[i + 1][j]= \begin{cases}
\mathrm{dp}[i][j – a_{i + 1}]&(j + a_{i + 1} > 20) \\
\mathrm{dp}[i][j + a_{i + 1}]&(j – a_{i + 1}<0) \\
\mathrm{dp}[i][j - a_{i + 1}] + \mathrm{dp}[i][j + a_{i + 1}] &
(0 \leq j - a_{i + 1}, j + a_{i + 1} \leq 20)\\
\end{cases}
\mathrm{dp}[1][j] は第 1 項、つまり a_1 で表せる式のうち、値が j になる式の個数です。よって、\mathrm{dp}[1][j] は以下のようになります。
\mathrm{dp}[1][j] = \begin{cases}
1&(j = a_1) \\
0&(j \neq a_1) \\
\end{cases}
求める等式の個数は第 N – 1 項までの式で値が a_N である式の個数 \mathrm{dp}[N – 1][a_N] です。
式を左から計算したとき計算の途中で現れる数が全て 0 以上 20 以下であるため、\mathrm{dp}[i][j] の 2 つめの添字 j の範囲は 0 \leq j \leq 20 です。このため、\mathrm{dp}[i][j] のために確保するメモリは O(N) で済みます。
\mathrm{dp}[i][j] の 1 回の更新は O(1) で i = 2 から i = N – 1 まで更新するため、(時間) 計算量は O(N) = 10^2 程度です。
場合の数は大きくなりやすくオーバーフローが発生しやすいですが、問題文に以下の記述があるため、\mathrm{dp}[i][j] の型を 64 ビット以上の値を表現できる整数型にすればオーバーフローは発生しません。
与えられる入力データの全てにおいて，JOI君が作り，確かめることができる正しい等式の個数は 2^{63} − 1 を超えない．
40. JOI 2012 予選 4 – パスタ
予定を全探索するには \Omega(3^N) の計算量がかかります。N \leq 100 であるため、実行時間制限に違反しそうです。
数え上げる予定が満たす条件は以下の 2 つです。
- 同じパスタを 3 日以上連続して選んではいけません。
- 決められた K 日分の予定に従います。
条件 1 について、第 j + 1 日の予定を決めるには前日、前々日である第 j 日、第 j – 1 日の予定が必要です。そこで \mathrm{dp}[j][k][l] を以下の満たす第 j 日目までの予定の数とします。
- 第 j 日目にパスタ k を食べます。
- 第 j – 1 日目にパスタ l を食べます。
条件 1 に基づく \mathrm{dp}[j][k][l] の更新式は以下の通りです。
\mathrm{dp}[j + 1][k][l] = \begin{cases}
\sum_{p} \mathrm{dp}[j][l][p]&(k \neq l) \\
\sum_{p \neq k} \mathrm{dp}[j][l][p]&(k = l)
\end{cases}
条件 2 については k = B_i である \mathrm{dp}[A_i][k][l] は条件 1 の更新式で更新し、k \neq B_i である \mathrm{dp}[A_i][k][l] は 0 とすれば良いです。
\mathrm{dp}[2][k][l] は 1 日目、2 日目の予定がともに決まっていない場合はすべて 1 とします。どちらかの予定が決まっている場合は該当する \mathrm{dp}[2][k][l] のみ 1 とし、残りは 0 とします。
パスタは 3 種類であるため、計算量は O(N) = 10^2 程度です。
答えは場合の数を 10000 で割ったときの余りであるため、更新後の \mathrm{dp}[i][j][k] を都度 10000 で割ったときの余りに変換するとオーバーフローを避けて求解できます。
