先日開催された、AtCoder Beginner Contest 345の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。
公式解説
A ～ C
FAはそれぞれhiroyuk1さん、firiexpさん、rin204さんでした。
おめでとうございます。
Pythonの場合、切り上げ除算は- ( - A // B)で可能です。
D Tiling
解法
かなり手こずりました。
$N \leq 7$の制約から、タイルの置き順を全探索する階乗オーダーの解法で考えます。
置く順番が決まっているなら、左上から詰めて置けばよいので、縦向き・横向きあわせて$O(2^N × N!)$通りを試せばよいです。
計算量ですが、愚直に毎回左上から置く場所を探すと$O(2^N × N! × NHW)$です。
置ける場所はタイルの枚数に従い単調増加することを考慮すると$O(2^N × N! × HW)$にまで落ちます。
計算量解析
$N$枚のタイルの面積を、置く順に$S_1, S_2, ･･･ , S_N$とします。
簡単のため、$ΣS_i = HW$とします。
今までに$n$枚のタイルを置き終えた状態から、$n + 1$枚目のタイルを置くことを考えます。
- 空いている最も左上のマスを探すのに、$O(Σ{i = 1}^n S_i)$
- $n + 1$枚目のタイルを置けるか判定するのに、$O(S_{n + 1})$
となり、従って$N$枚ぶんの合計は$N × S_1 + (N - 1) × S_2 + ･･･ + 1 × S_N$で抑えられます。
置く順番を全探索することを考えると、それぞれのタイルは1回のトライごとに平均$(N + 1) / 2$回確認することになります。
$(N, H, W) = (7, 10, 10)$とするとこれはおおよそ$2×10^8$であり、各演算が単純であること・実際は途中で打ち切るケースが多数存在することを考慮すると、愚直な並べ方でも十分間に合います。(終)
Pythonの非再帰DFSのほうが早く動作しますが、実装に一癖あるので慣れないうちはdef文で書くことをおすすめします。
実装例: 再帰DFS(621ms), 非再帰DFS(310ms)
E Colorful Subsequence
解法
DP高速化の問題です。
以下、$i$番目のボールの情報(色, 価値)は$B[i]$に格納してあるものとします。
愚直解 $O(N^2K)$
愚直なDPを考えると
DP[i][k][c]: B[i]を決める直前で、飛ばしたボールがk個で、最後の色がcとなる最大価値
となります。遷移は
DP[i + 1][k + 1][d] ← DP[i][k][d] : B[i]を採用しない遷移
DP[i + 1][k][c] ← DP[i][k][d] if d != c : B[i]を採用する遷移
となります。
制約上、色は$O(N)$通り存在するので、この解法の計算量は時間・空間ともに$O(N^2K)$となります。
空間計算量は2個のDPテーブルを使いまわすことで$O(NK)$に落とすことが可能です。詳細はH20さんの記事が大変詳しいです。
TLE解法1: セグメント木 $O(NKlogN), O(NK)$
不変量を考えると、i - kが等しければ、最後に採用したボールの状況が同じことに気づきます。
ST[i - k][c]: B[i]の採用を決める直前で、飛ばしたボールがk個、最後のボール色がcの最大価値
とセグメント木を$N + 1$本建ててみます。遷移は
ST[(i + 1) - (k + 1)][c] ← ST[i - k][c]: 採用しない遷移
ST[(i + 1) - k][c] ← ST[i - k][c以外]: 採用する遷移
となります。不変量を考えたことで採用しない遷移が不要となります。
後者の遷移は$C_i$以外の色のボールの最大価値が高速に取得できればよく、セグメント木を使うことで$O(logN)$で実行可能です。
さらに高速化します。
このままだとセグメント木の宣言に$O(N^2)$の時間・空間計算量が必要となってしまいますが、$K$の制約から直前$K + 1$個の配列さえ参照できれば十分とわかります。
なのでセグメント木の宣言数を$K + 2$個に制限し、毎回$O(KlogN)$時間で配列初期化を行うことにすると、時間計算量$O(NKlogN)$・空間計算量$O(NK)$に落とすことができます。
しかし、これでもTLEします。
TLE解法2: $K$の制約に着目 $O(NK^2), O(K^2)$
この項は1-indexedで説明します。
実装上は、$0$番目の(色$0$・価値$0$)のボールを採用したとすればよいです。
$K$の制約の小ささに着目すると、$B_i$番目のボールのひとつ前のボールは$B_{i - K}$までだと分かります。
そのため、各ボールの色を陽に持たず、後ろから高々$K$個のボールを調べればよいと分かります。
DPテーブルの持ち方は2通りありえます。
DP[i][x][k]: B[i]の採用を決めた後で、最後に使用したボールがB[i - x]、飛ばしたボールがk個の最大価値
とする、ややテクニカルなDP定義を紹介します。遷移は
DP[i][x + 1][k + 1] ← DP[i - 1][x][k]: 採用しない遷移
DP[i][0][k] ← DP[i - 1][x][k]: 採用する遷移
とします。
このままだと空間計算量が$O(NK^2)$となりますが、上述のnext DPテクニックを使うことで$O(K^2)$に落とすことが可能です。
もうひとつのDPテーブルの定義は
DP[i][k]: 最後に採用したボールがB[i]で、飛ばしたボールがk個の最大価値
とすることで、こちらは愚直な遷移が可能です。
保持するべき配列は高々$K + 2$種類なので、これを使い回すことで空間計算量$O(K^2)$になります。
AC解法 $O(NK), O(K)$
セグメント木の解法をさらに洗練させます。
すべての色を陽に持つ必要はなく、価値上位2種類だけが分かれば遷移が可能という性質を利用します。
DP[i][k]: B[i]の採用を決める前で、飛ばしたボールがk個の(最大価値, 色, 2番目の価値, 色)
と定義します。初期化は(価値 = 色 = $0$)とします。
遷移先に同じ色がある場合と、順位変動に注意して実装すればギリギリで間に合います。
全解法の実装例(AC解法: 3260ms, 130Mb)
F Many Lamps
解法
1回の操作で点灯数が奇数個変化することはあり得ないので、$K$が奇数のときは常に不可能です。
なので、$K$が偶数の時のみを考えます。
同一連結成分内の頂点数を$n$個とすると、ランプがつけられる個数は$n$以下の最大の偶数個であることがわかります。
これが「DFS木を葉側から貪欲に操作する」ことで達成可能な証明は公式解説にあります。
ここでは、帰納法により「達成可能である」の部分だけを示します。
帰納法 概略
$n$が奇数のときは、葉のひとつを取り除いて$n$が偶数のときの議論に帰着すればよいです。
以下、$n$が偶数のときにすべてのランプを点灯させることが可能という証明をします。
- $n = 2$の連結グラフでは、$2$頂点をつなぐ辺を操作することで達成可能です。
- $n = 2k$のときに全ランプを消灯可能であると仮定します。
$n = 2k + 2$のグラフは$n = 2k$のグラフに$2$頂点を足した形とみなすことが可能です。
他の頂点の点灯状況を変えることなく、追加した$2$頂点だけを点灯させることは、パス上の辺を追加で$1$回ずつ操作することで達成可能です。
ここで、同一の辺を$2$回操作することと、$1$回も操作しないことは等価なので、辺の操作回数は各辺高々1回で抑えられます。(終)
残りはグラフをDFS木とみなして貪欲に採用すればよく、これは$O(N + M)$で可能です。
実装上は$K = 0$のコーナーケースに注意してください。
実装例(420ms)
おわりに
おわりです。
とてもむずかしかったです。