先日開催された、AtCoder Beginner Contest 336の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。
公式解説
A～B
FAはそれぞれhiroyuk1さん、firiexpさんでした。
おめでとうございます。
C Even Digits
解法
5進数変換に気づけたなら一瞬です。
Pythonならnumpy.base_repr(N-1, 5)で進数変換ができます。
ですがコンテスト中は気づけなかったので、別解を考えます。
while文ごり押し
たとえば、200未満の非負整数のうち、「良い整数」は25個存在します。
1の位が0,2,4,6,8の5通り、10の位が0,2,4,6,8の5通りなので$5^2$個です。
(100の位は0の1通りしかあり得ません)
これを拡張すると、以下の事実が判明します。
$2×10^k$未満の非負整数に含まれる、「良い整数」の個数は$5^k$個である。
これを使用すると、「良い整数」を$5^k$単位で飛び飛びに数えられるようになります。
あとはwhile文で、ちょうどN個目の「良い整数」を探せばよいです。
計算量は$O(B × (logN)^2)$(B = 5)で、工夫すればもう少し早くなります。
実装上はバグりやすいですが、境界条件をガチャガチャいじればいつか通ります。
桁DP・解の二分探索
非負整数Xを固定して、「X以下の非負整数のうち、全桁が偶数のものの個数は？」の判定を行います。
これは桁DPで可能です。DP部分の計算量は$O(BlogN)$(B = 5)です。
桁DPについて
下位の桁から決めるDPを考えます。慣例的には竹DPと呼ぶらしいです。
DP[k][f]: 下からk桁目までを見て、Xの下位k桁目と比較した以下フラグがfの個数
として、下位の桁から0,2,4,6,8をあてはめてみればよいです。
以下フラグはよく未満フラグとも呼ばれるものです。
「下位k桁目までで比較した時点で、Nの下位k桁目以下かどうか？」を保持します。
N = 3 1 4 1 の2桁目を考えます。41との大小を判定します。
------------
6 x
5 x --- 2桁目が5以上なら、1桁目以下を問わず「41より大きい」
4 2
4 1 2桁目が4で等しいときは、それまでの桁の大小関係を維持する。
4 0 1桁目が1,0 なら以下フラグはTrue → f = 1
3 x --- 2桁目が3以下なら、常に「41以下」
2 x
なお、考える桁より小さい数字はゼロ埋めして扱うことにしています。
たとえば2や4はDP[1]では2や4として、DP[2]では02や04として数えます。(終)
判定関数が用意できたら、「良い整数」の個数は解の二分探索で求められます。
具体的には「X以下の非負整数に、良い整数はN個以上あるか？」で判定します。
解の上界は$10^{18}$とすれば十分なので、判定回数は60回強と見積もれます。
提出例: numpy 5進数変換, while文, 桁DP・解の二分探索
D Pyramid
解法
ここでやられました。
図はExcelごり押しで作りました。説明の雰囲気が伝われば嬉しいです。
ピラミッドの分割
ピラミッドを左半分・右半分に分割します。
各iについて、頂点をiとした左/右上がりの半ピラミッド数列の最大長を数えることにします。
これは下図のように、「右上がりの半ピラミッドを進めるだけ進める」とする尺取法を実装すればよいです。
左上がりの半ピラミッドは、数列を反転させて同じことを行えばよいです。
ところで遷移を工夫すると、DP[i+1] = min(DP[i]+1, A[i+1])となります。
こちらのほうが簡潔ですね。
どちらでも、計算量は$O(N)$です。
解の二分探索・尺取法
「サイズhのピラミッド数列を作れるか？」という判定問題を解きます。
ここで、可能な限りピラミッドを 左詰め すると1判定あたり$O(N)$にできます。
具体例として、サイズ4のピラミッド数列を作るケースを図示します。ピラミッドが作れない場合、可能な限り左詰めした状態からやり直すことがコツです。
判定問題は$O(logN)$回解くので、合計の計算量は$O(NlogN)$です。
解の二分探索・セグメント木
「サイズhのピラミッド数列を作れるか？」という判定問題を解きます。
中心がA[d]で、サイズがhであるピラミッド数列を作れる条件は
$A_i \geq h - d + i (d-h < i \leq d)$ ･･･ (1)
$A_i \geq h - i + d (d \leq i < d+h)$ ･･･ (2)
となります。これらをiの添字ごとにまとめると
(1) → $min(A_i - i) \geq h - d(d-h < i \leq d)$ ･･･ (3)
(2) → $min(A_i + i) \geq h + d(d \leq i < d+h)$ ･･･ (4)
となります。(3), (4)は区間minの形をしているので、セグ木に乗ります。
中心座標dを全探索し、各座標ごとにセグ木で$O(logN)$で判定すれば、解の二分探索の部分と合わせて$O(N × (logN)^2)$で答えることができました。
さらに高速化することもできます。
ピラミッド数列の最大サイズは、中心が1変化するたびに最大で±1の範囲でしか変化しません。
これに気づくと解の探索回数を$O(logN)$から$O(1)$に落とせます。
この場合の計算量は$O(NlogN)$となります。
提出例: ピラミッド分割・尺取法, ピラミッド分割・DP, 解の二分探索・尺取法(120ms), 解の二分探索・セグ木(1486ms), セグ木高速化(400ms)
E Digit Sum Divisible
解法
$N \leq 10^{14}$の制約下では桁和は高々9×14 = 126なので、桁和を全探索すればよいです。
桁和Mを決め打ったとき、N以下の各値がMで割りきれるかどうかは桁DPで判定できます。
DP[k][f][m][s]: 下位k桁目の時点で、以下フラグがf、値がm mod M、桁和がsの場合の数
とすればよいです。
Nを上下7桁ずつに分割した平方分割でも解けますが、PythonだとギリギリTLEします。
桁和列挙の計算量を$O(√NlogN)$から$O(√N)$に落とす、除算回数を減らす、祈る、といった工夫をすれば通ります。
計算量は$O(B√NlogN + (BlogN)^4)$(B = 9)です。
提出例: 桁DP(5006ms), 平方分割 高速化(7768ms), 平方分割 お祈り成功(9642ms), お祈り失敗(TLE1 10049ms)
F Rotation Puzzle
解法
長方形の選び方は1操作あたり高々4通りしかありません。
なのでBFSで全探索すれば$4^{20}$通り(実際は$4×3^{19}$通り)で網羅可能です。
ですがこれは$4.7×10^9$程度で、状態の判定に$O(HW)$かかることを考えるとTLEは必至です。
そこで、うまくすると通ります。詳細は折りたたみにします。
提出例: 想定解(1882ms), 多倍長整数 高速化(1470ms)
うまくする の詳細
半分全列挙を行いましょう。
初期盤面と終了盤面から10ステップずつBFSを行えばよいです。
Pythonの場合、tuple型に変換さえしてしまえば、盤面がそのままdictに入ります。
Pythonは本当に便利ですね。(終)
おわりに
おわりです。
かんがえることがおおくてむずかしかったなとおもいました。