この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
95. AtCoder Beginner Contest 149 B – Greedy Takahashi
愚直に K 回シミュレーションすると \Omega(K) = 10^{12} 程度の計算量になり、実行時間制限に違反しそうです。
高橋君がクッキーを持っている限り、高橋君のクッキーを 1 枚食べて、クッキーの所持数を 1 つ減らして行動を終了します。つまり、最初の \min(A, K) 回は高橋君のクッキーが 1 枚づつ減ります。
もし K \leq A なら、K 回の行動の後、高橋君は A – K 枚、青木君は B 枚のクッキーを持っています。
K > A のとき、A + 1 回から \min(A + B, K) 回までは、高橋君はクッキーを持っておらず、青木君のみクッキーを持っています。このとき、高橋君は青木君のクッキーを 1 枚食べます。つまり、青木君のクッキーが 1 枚づつ減ります。
もし K \leq A + B なら、K 回の行動後、高橋君は 0 枚、青木君は B – (K – A) 枚のクッキーを持っています。
K > A + B のときは高橋君のクッキーも、青木君のクッキーも食べ尽くしてしまうため、二人とも 0 枚のクッキーを持っています。
以上の場合分けをプログラムに落とすと O(1) で解答できます。
96. AtCoder Beginner Contest 139 D – ModSum
順列全探索は \Omega(N!) かかり、N \leq 10^9 より実行時間制限に違反しそうです。
i を P_i で割った余りが M_i であるため、以下の不等式が成り立ちます。
M_i \leq P_i – 1
両辺の i = 1, \dots, N の和をとると以下の不等式が成立します。
\sum_{i = 1}^N M_i \leq \sum_{i=1}^N (P_i – 1)
{P_1, P_2, \dots, P_N} は {1,2,\dots,N} を並べ替えた数列であるため、上の不等式の右辺は以下のように計算できます。
\sum_{i=1}^N (P_i – 1) = \sum_{i=1}^N i – N
\sum_{i = 1}^N M_i の {P_1, P_2, \dots, P_N} の選び方によらない上界を求められました。
最後の式を見ると、i \leq N – 1 までは P_i で割った余り M_i が i と一致して、i = N だけ割り切れているように見えます。実際、i \leq N – 1 のとき P_i = i + 1 とおき、P_{N} = 1 とおくと以下の等式が成立します。
\sum_{i = 1}^N M_i = \sum_{i=1}^N i – N
\sum_{i=1}^N i – N は \sum_{i = 1}^N M_i の上界であり、等式が成立する {P_1, P_2, \dots, P_N} が存在するため、\sum_{i = 1}^N M_i の最大値です。
等差数列の和の公式から最大値は (N + 1) N / 2 – N = (N – 1) N / 2 となり、O(1) で計算できます。
97. AtCoder Beginner Contest 150 D – Semi Common Multiple
M \leq 10^9 かつ N \leq 10^5 であることから、M までの数について A の半公倍数であることを確認すると \Omega(MN) = 10^{14} 程度かかり、実行時間制限に違反しそうです。
a_k が偶数であることが保証されているため、b_k = a_k / 2 として半公倍数 X の満たす式を以下のように変形します。
X = b_{k} \times (2 p + 1)
B = b_1, b_2, \dots, b_N とすると、A の半公倍数は B の公倍数のうち、任意の b_k で割ったときの商が奇数になる数と言い換えられます。
もう少し半公倍数について調べるため、X = b_i \times (2 p_i + 1) = b_j \times (2 p_j + 1) とおいてみます。
2 p_i + 1, 2 p_j + 1 は奇数のため、X の 2 で割り切れる回数、b_i を 2 で割り切れる回数、b_j を 2 で割り切れる回数は一致します。もし、ある i \neq j について、b_i の 2 で割り切れる回数と b_j の 2 で割り切れる回数が異なる場合、条件を満たす X は存在しません。このとき、半公倍数の個数は 0 になります。
任意の b_k について 2 で割り切れる回数が同じであるかの判定は B の最小公倍数を最大公約数で割ったときの商が奇数かどうかで判定できます。素因数分解を考えると最小公倍数の 2 で割り切れる回数は b_k の 2 で割り切れる回数の最大値であり、最大公約数の 2 で割り切れる回数は b_k の 2 で割り切れる回数の最小値であるため、最小公倍数を最大公約数で割ったときの商が奇数ならば、最大値と最小値が一致し、一定であることがわかります。
以下、任意の b_k について 2 で割り切れる回数が同じときを考えます。
上記より、B の最小公倍数を b_k で割ったときの商は奇数になります。つまり、B の最小公倍数は A の半公倍数になります。任意の公倍数は最小公倍数の倍数であるため、B の最小公倍数の倍数について、A の半公倍数になるか考えます。
B の最小公倍数の偶数倍を b_k で割ったときの商は偶数になります。そのため、偶数倍は A の半公倍数にはなりません。一方、B の最小公倍数の奇数倍を b_k で割ったときの商は奇数になります。そのため、奇数倍は A の半公倍数になります。
まとめると、B の最小公倍数を \mathrm{LCM}(B) とおくとき、A の半公倍数の一般項は以下のように書けます。
\mathrm{LCM}(B) \times (2 i – 1) \quad (i = 1, 2, \dots)
上記の等差数列の M 以下の項の個数は以下の不等式を満たす最大の i になります。
\mathrm{LCM}(B) \times (2 i – 1) \leq M
よって、答えは \lfloor (M + \mathrm{LCM}(B))/ (2 \mathrm{LCM} (B)) \rfloor になります。
A から B を計算するのに O(N), B の最大公約数と最小公倍数を求めるのに O(N \log \max a_i) かかるため、全体の計算量は O(N \log \max a_i) = 10^7 程度です。実行時間制限に違反せず、解答できます。
98. 三井住友信託銀行プログラミングコンテスト2019 予選 E – Colorful Hats 2
帽子の色の列を全探索すると \Omega(3^N) はかかります。実行時間制限に違反しそうです。
i 番目までの場合の数から、i + 1 番目の場合の数が計算できないか、考えます。
\mathrm{dp}[i][j][k][l] を赤色の帽子を被っている人が j 人、青色の帽子を被っている人が k 人、緑色の帽子を被っている人が l 人いる、i 番目までの人の列の場合の数とします。
I_{j}(x) を x = j ならば 1、それ以外なら 0 となる関数として、以下の更新式が成立します。
\begin{aligned}
&X = I_{j-1}(A_{i + 1}) \mathrm{dp}[i][j – 1][k][l] \\
&Y = I_{k-1}(A_{i + 1}) \mathrm{dp}[i][j][k – 1][l] \\
&Z = I_{l-1}(A_{i + 1}) \mathrm{dp}[i][j][k][l – 1] \\
&\mathrm{dp}[i + 1][j][k][l] = X + Y + Z
\end{aligned}
上記の i についての更新を愚直に j, k, l の 3 重ループで行う場合、全体の計算量は \Omega(N^4)= 10^{20} 程度になるため、計算量の削減を検討します。
まず、I_{j}(x) の定義を考えると、更新に必要な \mathrm{dp}[i][j][k][l] は j = A_{i + 1}, k = A_{i + 1}, l = A_{i + 1} のいずれかが成立している必要があります。また、i 番目までの人の列の帽子の数は i であるため、例えば j = A_{i + 1} のとき更新に必要な \mathrm{dp}[i][j][k][l] は l = i – j – k が成立します。これらを踏まえると i についての更新を j, k, l それぞれの 1 重ループで行うことができるため、計算量は \Omega(N^2) まで削減できます。ただ、もう少し削減が必要です。
A_i と A_{i + 1} の並びに着目します。
A_i + 2 \leq A_{i + 1} または A_i \geq A_{i + 1} のとき、i 番目の人の帽子の色と i + 1 番目の人の帽子の色は異なります。そのため、更新に必要な i 時点の j, k, l について \{j, k, l\} = \{A_i + 1, A_{i+1}, i – 1 – A_i – A_{i+1}\} が成立します。よって j, k, l の組み合わせは高々 6 通りに絞られます。
A_i + 1 = A_{i + 1} のときは、i 番目の人の帽子の色と i + 1 番目の人の帽子の色は異なる場合もあれば、一致する場合もあります。異なる場合は前述の通り、高々 6 通りです。一致する場合は、i のときに更新した \mathrm{dp}[i][j][k][l] の i 番目の人と i + 1 番目の人の帽子の色に対応する添字を 1 つ大きくして、\mathrm{dp}[i + 1][j][k][l] を更新します。
上記より、一見 A_i + 1 = A_{i + 1} が続く場合は、更新すべき j, k, l が最悪、公差 6 の等差数列的に増えていくように見えます。しかし、実際は次のように更新すべき j,k,l の組み合わせは抑えられます。
\{A_i\}_{i = i_{0}}^{i_1} が A_i + 1 = A_{i + 1} を満たすとき、i 番目の帽子の色の場合分けを考えてみます。3 色のすべての帽子について i より手前に被っている人がいる場合、A_{i} + 1 = A_{i + 1} より、i 番目の人の帽子の色は i – 1 番目の人の帽子の色と一致している必要があります。そのため、{A_i}_{i = i_{0}}^{i_1} の間に更新すべき、i, j, k が増える要因である直前の人と異なる色の帽子を被る場合は i_{0} と i_i の大きさによらず、高々 2 回しか発生しません。そのため、更新すべき i, j, k の組み合わせは高々 6 \times 3 = 18 程度しかありません。
以下に 1 つ例を記載します。
| i | A_i | 色 | 前の人と同じ色 |
|---|---|---|---|
| 3 | 5 | 青 | – |
| 4 | 6 | 青 | ○ |
| 5 | 7 | 赤 | × |
| 6 | 8 | 赤 | ○ |
| 7 | 9 | 緑 | × (青にすると A_4 と矛盾) |
| 8 以降 | (i – 8) + 10 | 緑 | ○ (赤にすると A_6 と矛盾、青にすると A_4 と矛盾) |
以上より、\mathrm{dp}[i][j][k][l] に O(1) でアクセスできれば、i 番目の更新を O(1) でできることがわかりました。ただし、i, j, k, l \leq N \leq 10^5 のため、配列で持っておくとメモリ制限に違反しそうです。
j + k + l = i であることから、i が異なれば (j, k, l) は異なるため、i を削除して \mathrm{dp}[j][k][l] を (j, k, l) をキーとする map で管理します。map に追加する要素数は O(N) 程度のため、メモリ制限の違反はなさそうです。
また、前回の更新に出てきた j, k, l を管理しておくと、上記の計算量の見積のために考えた場合分けを実装する必要はありません。単純に前回の更新に出てきた j, k, l から遷移可能な \mathrm{dp}[i + 1][j][k][l] のみ更新すればよくなります。
要素の取り出しに O(\log N) 程度かかるため、全体の計算量は O(N \log N) = 10^7 程度です。実行時間制限に違反せず、解答できます。
上記の解答例では、動的計画法で直に場合の数を数え上げました。AtCoder の解説 にあるように、各 i 番目の人までの各色 (ただし、赤色・青色・緑色という絶対的な色ではなく、相対的な色) の帽子を被っている人の人数を求めた上で数え上げることもできます。
x_i, y_i, z_i を i 番目までの人のうち、最も多い色の帽子の数、2 番目に多い帽子の数、3 番目に多い帽子の数とします。x_i \geq y_i \geq z_i が成立します。
各 A_i は i – 1 番目の人までの帽子の数のため、x_{i – 1}, y_{i – 1}, z_{i – 1} のいずれかと一致します。そこで x_i, y_i, z_i を次のように更新ます。
x_{i – 1} = A_i ならば、x_i = x_{i – 1} + 1, y_i = y_{i – 1}, z_i = z_{i – 1} と更新します。
x_{i – 1} \neq A_i, y_{i – 1} = A_i ならば、y_i = y_{i – 1} + 1, z_i = z_{i – 1}, x_i = x_{i – 1} と更新します。
x_{i – 1} \neq A_i, y_{i – 1} \neq A_i, z_{i – 1} = A_i ならば、z_i = z_{i – 1} + 1, x_i = x_{i – 1}, y_i = y_{i – 1} と更新します。
x_i から優先的に更新しているのは、x_i \geq y_i \geq z_i を維持するためです。上記の計算で、各 i についての x_i, y_i, z_i が計算できます。
場合の数は i = 1 から各人の帽子の被り方をもとに場合の数の積の法則で計算します。
i – 1 番目までの 3 色の帽子の数のうち A_{i} と一致する数の個数だけ、i 番目の人の帽子の被り方があります。それらを掛け合わせると答えになります。
計算量は x_i, y_i, z_i の算出に O(N), 場合の数の数え上げに O(N) かかるため、O(N) = 10^5 程度です。
99. DDCC2020 予選 D – Digit Sum Replace
2 \leq c_1 + \cdots + c_M \leq 10^{15} であるため、シミュレーションする場合、最初の連続する 2 桁を試すだけで、実行時間制限に違反しそうです。
参加人数 X に対し、1 回のラウンドで勝ち残る人数を Y とおきます。選んだ連続する 2 桁の数字の和で場合分けし、Y について調べます。
場合 1 選んだ連続する 2 桁の数字の和が 1 桁の数になるとき ( 例 : 12 \rightarrow 3 )
Y は以下の性質を持ちます。
- 各桁の和は X の各桁の和と等しいです。
- 桁数は X の桁数より 1 小さいです。
場合 2 選んだ連続する 2 桁の数字の和が 2 桁の数になるとき ( 例 : 38 \rightarrow 11 )
Y は以下の性質を持ちます。
- 各桁の和は X の各桁の和より 9 小さいです。
- 桁数は X の桁数と等しいです。
以上から、有限回のラウンドで参加人数を 1 桁にできることがわかります。
有限回のラウンドで勝ち残る人数を 1 桁にできない参加人数があると仮定して背理法で示します。有限回のラウンドで勝ち残る人数を 1 桁にできない参加人数の最小値を X とします。
X に対し、場合 1 のラウンドが起きる場合、Y は X より桁数が小さくなるため、X の最小性から Y は有限回のラウンドで勝ち残る人数を 1 桁にできます。このとき、Y のラウンド数 + 1 回のラウンドで X から勝ち残る人数を 1 桁にできます。これは X の仮定に反します。そのため、X に対し場合 1 の処ラウンドは発生しません。
つまり、X に対し、場合 2 のラウンドを何回も行うことができます。場合 2 のラウンドを X 回行った後の勝ち残る人数を Z とおいたとき、Z の各桁の和は X の各桁の和から 9X 引いた値になります。X の各桁の和は X 以下であるため、Z の各桁の和が負になります。各桁の和が正であることに矛盾します。
よって、仮定は否定されます。
次に勝ち残る人数が 1 桁になるまでに場合 1 と場合 2 のラウンドが何回起こるか考えます。場合 1 が起こるラウンドの回数を n_1, 場合 2 が起こるラウンドの回数を n_2 とおきます。
参加人数 N に対し n_1 + n_2 回目のラウンド終了後に勝ち残る人数を Z とおきます。Z について、以下の性質が成り立ちます。
- 桁数は N の桁数 \sum_{i = 1}^M c_i より n_1 \times 1 + n_2 \times 0 = n_1 小さい。
- 各桁の和は N の各桁の和 \sum_{i = 1}^M c_i d_i より n_1 \times 0 + n_2 \times 9 = 9 n_2 小さい。
Z が 1 桁の数であるとき、Z の桁数は 1 であり、Z の各桁の和は 1 桁であるため、以下の式が成立します。
\begin{aligned}
\sum_{i = 1}^M c_i – n_1 = 1,&&1 \leq \sum_{i = 1}^M c_i d_i – 9 n_2 \leq 9
\end{aligned}
各桁の和は 0 にはならないことに注意します。勝ち残る人数の各桁の和が 0 になるには、直前のラウンドの参加者の人数の桁数が 2 以上、各桁の和が 9 であることが必要です。このとき、任意の連続する 2 桁の和は各桁の和 9 以下です。そのため、直前のラウンドは必ず、場合 1 のラウンドで、桁数のみ 1 小さくなり、各桁の和は 9 のまま変わりません。
上記の式には n_1, n_2 について一意解が存在します。そのため、問題文には「できるだけ多くの予選ラウンド」とありますが、本戦参加者が 9 人までのとき、予選ラウンドの回数は上記を満たす n_1, n_2 を用いて n_1 + n_2 回と一意に定まります。
答えは次のように定式化できます。
n_1 + n_2 = \sum_{i = 1}^M c_i – 1 + \left \lfloor \frac{\sum_{i = 1}^M c_i d_i – 1}{9} \right \rfloor
計算量は O(M) = 10^6 程度です。実行時間制限を満たして解答できます。
100. Tenka1 Programmer Beginner Contest D – Crossing
全探索する場合、k = N の場合だけでも \Omega(2^{N^2}) の計算量がかかります。N \leq 10^5 のため、実行時間制限に違反しそうです。
与えられた条件から集合の個数 k や集合 S_i の要素数 |S_i| の範囲を絞れないか考えます。
条件 1 1, 2, \dots, N のうちどの整数も、S_1, S_2, \dots, S_k のうちちょうど 2 つに含まれる
という条件から、以下の等式が成立します。
\begin{aligned}
& S_i = \bigcup_{j \neq i} (S_i \cap S_j) \\
& \sum_{i = 1}^k | S_i | = 2 N
\end{aligned}
次に以下の条件も併せて考えます。
条件 2 S_1, S_2, \dots, S_k のうちどの 2 つの集合をとっても、それらに共通して含まれる要素はちょうど 1 つである。
集合 S_i, S_j ( i \neq j ) に共通して含まれる唯一の数を a_{ij} とおきます。前述の集合の等式と組み合わせると以下の式が成立します。
S_i = \bigcup_{j \neq i} (S_i \cap S_j) = \bigcup_{j \neq i} \{a_{ij}\}
i, j, k を互いに異なる添字としたとき a_{ij} \neq a_{ik} が成立します。一致すると仮定すると a_{ij} は S_i, S_j, S_k という 3 つの集合に属する数です。これは、1 つめの条件に違反します。これより、以下が成り立ちます。
| S_i | = \sum_{j \neq i} | \{a_{ij}\} | = k – 1
以上から、条件を満たす部分集合の組が存在するとき、N と k について以下の関係が成り立ちます。
2 N = \sum_{i = 1}^k | S_i | = \sum_{i = 1}^k (k – 1) = k (k – 1)
与えられた N に対し、上記を満たす整数 k が存在しない場合は条件を満たす部分集合は存在しません。
逆に 2 N = k (k – 1) を満たす k が存在するときに条件を満たす部分集合の組を構成できないか考えます。
等式を次のように変形します。
N = \frac{k(k – 1)}{2} = {}_k C_2
これは k 個の集合から異なる 2 つの集合の組み合わせを選ぶ場合の数が N であることを表します。そのため、すべての組み合わせにもれなく重複なく 1 から N までの番号をつけることができます。組み合わせ (i, j) の番号を f(i, j) と書くことにします。以下のように S_i を定義すれば、f(i, j) = a_{ij} が成立し、条件を満たす部分集合の組を構成できます。
S_i = \{f(i, j) | j \neq i \}
等式の成立の判定に O(\sqrt{N}), 部分集合の組の構成に O({}_k C_2) = O(N) かかるため、全体の計算量は O(N) = 10^5 程度です。実行時間制限を満たして解答できます。
