ABCDFの5完。前回の新年用の問題の残りみたいな感じだった。
A - Long Loong
難しい問題みたいな形式で簡単なのいいね。string(n, 'o')を使う。
B - CTZ
問題文にctzと書いてあるので__builtin_ctzを使う。0が与えられることはないのでこれでいいだろう。解説見たらcountr_zeroと書いてあって負けた気分に。
C - Even Digits
Nから1を引いておく。いやまあ見た瞬間わかるんだけど、5進法と同じことだとはっきりわかるまでには時間がかかった。stringにpushしていってreverseして出力。0がコーナーケースなの相当いやらしいと思った。
D - Pyramid
ピラミッドの頂点をどこにするか決めれば、ありえる最大のサイズをそこからの距離で更新できてO(N)で求まる。難しそう。片側ずつ考えることを思いつき、もやもやしてるけどできそう。時間が経つと当たり前にも思えるが、これは難しい。頂点を含む片側ピラミッドを考えて、サイズkの片側ピラミッドから1個進むと最大でサイズk+1ができてA_iで律速される（この更新ができることが難しい）。これを両側からやるが、実装上はreverseしながら2回ループした（得られた結果も片方はreverseする）。片側ピラミッドの頂点同士がぶつかるので、得られた2個の結果の各位置の最小値の最大値が答え。
E - Digit Sum Divisible
直感的にはできるわけがない設定。実験して規則性が見えない。Nが9の倍数なら桁和の9の倍数だなとか、良い整数は10倍しても良い整数だなとか、考えても進まない。Fと交互に考えていた。あるとき、桁DPだと気づき、Fに専念した。Fを通して戻ってきて15分以上残っていたが、間に合うわけがないのであせらず実装していた。まだ実装というか計算量よくわかってないけど。N以下を求めるのが面倒で何が嬉しいのかわからなくてやりたくないし時間かかるんだよな。
（追記）頑張ってupsolve。10^14以下の非負整数の桁和の最大値は126。u未満の非負整数で、dで割ってrあまる桁和がsのものの個数を持つ（ここにN%u未満という条件を加えたものも求めなくちゃいけないのが桁DP）。テーブルが大きくなりそうなので桁数分は持たず節約する。また、最終的な桁和毎に求めて足せばいいということに自分では気づかなかったがそういうツイートを見たのでそのように実装する（使用メモリがだいぶ減った）。あとは普通に書けばいつの間にか完成している。配るけど考え方は貰う、みたいな実装。初期値の設定で0未満のものは0個なのに間違えてサンプル通らなかった。桁和の最大値は126だが、10^14の位を処理するとき126から更に足そうとしてRE。126より大きいものは使わないので全部127に入れておくことにして対処、AC。
F - Rotation Puzzle
H,Wが小さく、20回なので半分全列挙だろう。操作は4通りなので4^10個を列挙すればできそうだ。最初3*8が最大と制約を誤読していたが8*8だった（あの制約の書き方のデメリットだよなあと思うが、簡潔に書けるメリットも大きいのでやめてほしいとは思っていない）。さて、64!通りあるので、さすがに情報量が大きい。64バイトにエンコードするとして、std::setに入れて計算時間やメモリが大丈夫か不明（このとき、setはvectorとかよりはるかにメモリを食うと思っていたが、今思えば追加で必要なメモリは要素あたり定数だろうから64バイトだからって心配なかった）。ということでもう少し踏み込んで考える。回転の処理を書くときに気づいたが、これは同じ操作を2回やると元に戻る。求めるのは操作回数の最小値だから、同じ操作を連続ですることはないとしてよい。ということで、4^10から3^10に激減。安心して実装に入る。
再帰が必要になったので、ラムダ式で書いていたのをグローバル関数に変更する。ラムダ式の再帰も書けるんだけど、こういう負荷が高そうな実装のときは自分がネイティブに書ける領域で戦いたい。再帰を使う理由は、回数分オーダーの操作を毎回する必要もなくBFSのような追加メモリもいらないこと。自分が考えた方針だと、回数が0のときと1~10のときと11~20のときの処理を書く必要がある。0は場合分けしておく。10までは再帰内で最小値を求める（DFSなので最初に見つけたやつとは限らない）。そうして末端（10回操作した盤面）だけをsetに入れる。10回以内にできないときは、反対側から同じようなDFSをする。完成形からDFSして、今度はその盤面がsetに含まれているかを見る。ここでも最小値を求め、見つからなかったら-1、見つかってたら10を足して出力。半分全列挙が最初から見えていて実装は重めだが、考え方が楽しかった。setに保存するのはDFSの末端だけで、setにあるか見るのは全部。meet-in-the-middleっていうけど、真ん中からだいぶ離れた場所で出会うこともあるんだね。いや気持ちいい。
