6完1TLE。2週間ほとんど競プロやってなかったけど、昼間のOUPCがいい準備運動になった気がする。ratedならではの感覚は久しぶりに思い出すという感じだったけど。いい状態で臨めた。
A - 202<s>3</s>
ブログにそのまま貼り付けたら壊れる問題名やめてくれｗ
s.back() = '4'; としたけど、++でもよかったんだねえ（秒単位で実装時間短縮できる）。
B - Tetrahedral Number
3重forで、各要素がN以下の組を辞書順に全て列挙できるので、和がN以下か判定して出力していく。
（追記）N=21のとき2024通りらしいです。
C - Loong Tracking
一見難しそうだが、単に過去の頭の位置を答えるだけ（パーツは存在せず過去にN-1回移動していたことにする）。しかし実装が思ったよりきつい。特にRLUDをデコードするのが面倒。
D - Loong and Takahashi
まずサンプルを見る。うずまきでできるか考えてみると、できる。サンプルに答え書いてあるんかい！まあ、それが常に使えることがわかるのも実力だからな。グリッドを(N+1)/2層に「回」みたく分けて、左上隅から1周して次の層の左上隅に移動できる。1周する処理を書けばよい。正方形の上と下と左と右の端の座標を持って4回の直線移動で1周、終わったら座標を1ずつ内側へ寄せて(N-1)/2回まわる。特に詰まった記憶はないが、10分以上かかってしまった。
E - Non-Decreasing Colorful Path
メチャクチャ難しい。何かのはずみでACするコードは書けそうだが、正当性を示して書くのは相当きつそう。そこに挑んでいく。ダイクストラ法のコードをベースにする。どんな順番で探索するか。書かれている整数か、そこまでの得点か。ここに到達した時点での得点の最大とかでDPできそうに見えてなかなかはまってくれない。有効そうな指標が2つあるとしんどい。2倍じゃ済まない（野球の変化球みたいな）。そもそも、どっち優先で探索しても、同じ整数の書かれた場所へどっちから訪れるかで計算量が壊れる可能性が見える。既に20分以上が経過していて焦る。
書かれている整数が等しい頂点同士をつなぐ辺だけを使ってUnionFindで同一視すればいいというのを思いつくが、さすがに実装したくない。ということで一旦Fへ。頭を冷やす。結果的に時間を損したわけではないが、早めにFを読まなかったのは反省点。
もはやちゃんと証明をするというような状態ではない。ダイクストラみたいにして、Aが小さいもの、同じなら現在のスコアが大きいものを優先して探索。これで提出してTLE。TLEは自尊心が壊れる。正しい答えを出すアルゴリズムかしか気にしてなかった。計算量を見ようと読み直すがもうよくわからん。とりあえず、得点が0になる経路は探索しないように変更。広義単調増加の経路が存在しなければ答えは0なんだから、最初からそうするべきだった。どうしても、難しい問題だと設定通りに書くことに甘えてしまう。しばらくして、Aを大きい順に探索していたことに気づく。priority_queueは逆だから確かに混乱していたよさっき。そもそも得点と不等号の向きが揃ってるのがおかしかったけど、脳内で大きい順とか呼んでたので、イメージは正しくても言葉が間違っていた。これでAC。一見ただのケアレスミスだけど、こういうガチで難しい問題のときにこういうミスはめちゃくちゃ増える。
（追記）書かれている整数が全て異なるなら、得点が0になる辺を除けばDAGになり、DPできる。冷静にこの考察をしたかった。無理だったとは思うけど、目指すのはこれなんだよな。同一視するやつを実装してみたが、なかなか見えなかったので解説の実装例ガン見して書いた。これはちょっと、コンテスト中にやろうとしてもまともな時間では書き切れなかったと思う。
F - Hop Sugoroku
まず愚直DPを書いてみる。頭で考えてるときは貰うDPだったけど、コードは配るDPになった。簡単に書けてサンプルも合う。ここまで、高速化の方法が存在する気がしなかったが、A_iが大きいときは普通に配ればいいので小さいときどうにかならないかと考えて、平方分割になった。A_iがsqrt(N)未満程度に小さいとき、「A_iで割っていくつあまったところにこれだけ足す」というのをサイズN程度の2次元配列で管理できる。その配列に足すのはO(1)で、その配列の必要な情報をチェックするのにO(sqrt(N))かかる。14分程度でACしており、スピードが出ている。問題設定がシンプルだった。
（追記）歩幅と位置によって同一視できるものがある。同じのに当たったらそこから先の加算はそいつに預けることができる（そいつへ余分に足せばよくて、答えがずれる分は補正する）。計算量だが、A_iがsqrt(N)以上のぶんはO(N*sqrt(N))。sqrt(N)より小さいのの寄与は、各位置毎に受け取り回数を見ると同じ歩幅からは1回しか受け取らないので当然sqrt(N)未満。こういう、陽に平方分割しない平方分割いいよな。以前にもグラフ問題であった。
G - Discrete Logarithm Problems
原始根関係を色々ググって、原始根とかP-1の約数とか考えるけど、10^13近くも候補があるのに何乗して初めて1になるかとかわかるわけねーし。
（追記）位数というんだね。位数が（P-1の約数だとはいえ）わかるわけないと思っていたけど、k乗を試して1にならないなら位数がkの約数でないとわかるので、だんだん素因数を減らしながら試せばよい。次に、位数がわかったところでと思っていたけど、なんか構造がよくわかってなかっただけで、割り切れればいいらしい。計算には普通に__int128を使った（え）（まあCPUレベルでは今回の内容なら乗算も除算も普通にできるんで）。あとは位数をソートしてランレングスして愚直に2重ループすれば答えが求まる（アルゴ式の高度合成数一覧で多くても1万ちょっとだとわかる）。提出してAC。まあ原始根を一つ固定してそれの何乗って考えればそりゃそうか。まだよくわかってないし、最初はもっとわかってなかった。
約数の高速ゼータ変換も書いた。素因数分解の何が何個という情報が入ってるvectorの端を、その方向に足すやつに入れ替えながら再帰で対象の数を構成して（小さいほうから）足していく。1万個しかないのでmapで問題ない。それなりに理解していたつもりの高速ゼータ変換だったが、何時間もかかった。SSRSさんの提出を見たら、いつもの2進法の高速ゼータ変換みたいに変則進法でできるんだななるほど（普通そうするんだろうけどなんもわかってなかったんで声が出た）。いきなりこの問題でやるのは難しすぎたので、練習としてPAST15のI問題を高速ゼータ変換で解いた（こちらは足す向きが逆）。
