ABC336 勉強メモ

先日開催された、AtCoder Beginner Contest 336の勉強メモです。
問題への言及がありますので、今後解く予定の方はご注意ください。
使用言語はPython・提出はPyPy3です。

# 公式解説

https://atcoder.jp/contests/abc336/editorial


# A～B

FAはそれぞれhiroyuk1さん、firiexpさんでした。
おめでとうございます。

# C Even Digits

[問題文はこちら](https://atcoder.jp/contests/abc336/tasks/abc336_c)

__解法__
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)です。

<details><summary>桁DPについて</summary>

下位の桁から決める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`として数えます。(終)

</details>

判定関数が用意できたら、「良い整数」の個数は解の二分探索で求められます。
具体的には「X以下の非負整数に、良い整数はN個以上あるか？」で判定します。
解の上界は$10^{18}$とすれば十分なので、判定回数は60回強と見積もれます。

提出例: [numpy 5進数変換](https://atcoder.jp/contests/abc336/submissions/49319759), [while文](https://atcoder.jp/contests/abc336/submissions/49338756), [桁DP・解の二分探索](https://atcoder.jp/contests/abc336/submissions/49319670)

# D Pyramid

[問題文はこちら](https://atcoder.jp/contests/abc336/tasks/abc336_d)

__解法__
ここでやられました。
図はExcelごり押しで作りました。説明の雰囲気が伝われば嬉しいです。

__ピラミッドの分割__
ピラミッドを左半分・右半分に分割します。
各iについて、頂点をiとした左/右上がりの半ピラミッド数列の最大長を数えることにします。
これは下図のように、「右上がりの半ピラミッドを進めるだけ進める」とする尺取法を実装すればよいです。
左上がりの半ピラミッドは、数列を反転させて同じことを行えばよいです。

![ABC336D Excelパワーソリューション.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/fb25aaa2-9729-ab59-1ce4-885991dff48e.png)

ところで遷移を工夫すると、`DP[i+1] = min(DP[i]+1, A[i+1])`となります。
こちらのほうが簡潔ですね。
どちらでも、計算量は$O(N)$です。

__解の二分探索・尺取法__
「サイズhのピラミッド数列を作れるか？」という判定問題を解きます。
ここで、可能な限りピラミッドを __左詰め__ すると1判定あたり$O(N)$にできます。
具体例として、サイズ4のピラミッド数列を作るケースを図示します。ピラミッドが作れない場合、可能な限り左詰めした状態からやり直すことがコツです。
判定問題は$O(logN)$回解くので、合計の計算量は$O(NlogN)$です。

![ABC336D Excel 2.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/3624214/f0bb5447-cba2-bbea-c996-8691e02a1b18.png)

__解の二分探索・セグメント木__
「サイズ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)$となります。

提出例: [ピラミッド分割・尺取法](https://atcoder.jp/contests/abc336/submissions/49321128), [ピラミッド分割・DP](https://atcoder.jp/contests/abc336/submissions/49321431), [解の二分探索・尺取法(120ms)](https://atcoder.jp/contests/abc336/submissions/49338499), [解の二分探索・セグ木(1486ms)](https://atcoder.jp/contests/abc336/submissions/49322506), [セグ木高速化(400ms)](https://atcoder.jp/contests/abc336/submissions/49348076)

# E Digit Sum Divisible

[問題文はこちら](https://atcoder.jp/contests/abc336/tasks/abc336_e)

__解法__
$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)](https://atcoder.jp/contests/abc336/submissions/49322669), [平方分割 高速化(7768ms)](https://atcoder.jp/contests/abc336/submissions/49332802), [平方分割 お祈り成功(9642ms)](https://atcoder.jp/contests/abc336/submissions/49347606), [お祈り失敗(TLE1 10049ms)](https://atcoder.jp/contests/abc336/submissions/49332024)

# F Rotation Puzzle

[問題文はこちら](https://atcoder.jp/contests/abc336/tasks/abc336_f)

__解法__
長方形の選び方は1操作あたり高々4通りしかありません。
なのでBFSで全探索すれば$4^{20}$通り(実際は$4×3^{19}$通り)で網羅可能です。
ですがこれは$4.7×10^9$程度で、状態の判定に$O(HW)$かかることを考えるとTLEは必至です。
そこで、うまくすると通ります。詳細は折りたたみにします。
提出例: [想定解(1882ms)](https://atcoder.jp/contests/abc336/submissions/49322868), [多倍長整数 高速化(1470ms)](https://atcoder.jp/contests/abc336/submissions/49323079)

<details><summary>うまくする の詳細</summary>

半分全列挙を行いましょう。
初期盤面と終了盤面から10ステップずつBFSを行えばよいです。

Pythonの場合、tuple型に変換さえしてしまえば、盤面がそのままdictに入ります。
Pythonは本当に便利ですね。(終)

</details>

# おわりに

おわりです。
かんがえることがおおくてむずかしかったなとおもいました。