一応黄パフォ相当なのでいいけど、Dの2ペナは酷い。今週は競プロモチベが久しぶりに消え失せた（黄色防衛という目標を達成してしまったためと思われる）。コンテスト開始後も（コンテスト中にしては）やる気がなく、WAを出さないようゆっくりやっていた。録画していた。順位表は見ていなかった（普段は見ている）。
A - Star
難しくてよくわからないままACしてしまった感じ。サンプルが十分強いのでこれで通るなら通るはず。今考えると、次の100の倍数までの距離だからあまりのぶんだけ減るよねとは思うが。どちらかというと 100 - x % 100 で通る都合のいい問題が存在することを信じられなかったのが大きいかな。
B - uNrEaDaBlE sTrInG
これもよくわかんないから条件をxorして逆じゃなさそうなので提出（それとその否定のどっちかは正しい）。
C - Kaprekar Number
Kが小さいので愚直が間に合う。各桁を求めたらソートして小さいほうを求め、リバースして大きいほうを求める。この問題だとあまり関係ないけど、各桁を求めるときは下位から求まり、復元するときは上位から追加していく。
D - Base n
Dで2ペナ。2桁以上なら指数関数的に増えると思ってたら多項式だったのでTLE、二分探索でbaseがMまででいいだろと思ってたら半開区間なので[d+1, M+1)のケースもありWA。
— merom686 (@merom686) February 20, 2021
人並みにペナ出すのマジでやめたいが、これが実力か。認めたくないね。
1桁のときは何進法でも変わらないので場合分けしておいて、2桁あれば同じ値にならないのでn（何進法か）を数える。Mが大きく、基数が大きいときにオーバーフローするので、掛け算する前に割り算で大雑把に確認。境界がかなり不安なのだが、割って1を足しておけば最大でMくらいしかずれない（2桁以上でM+1進法がM以下になることはないので）。M*2 くらいならllで余裕で扱える。あとは二分探索するだけ。
E - Train
ダイクストラやるだけに見えるが本当だろうか。まあダイクストラ法を貼ってから考える。最初、これから使う辺ではなく、さっき使った辺のKで計算していた（ひどい）。さて、これから使う辺のKを考慮する。まず普通のダイクストラでその都市までの最速はわかる。その時刻がわかっていれば、各列車について最速でいつ出発できるかもわかる。こういう、コストが動的に求まるの難しいんだよね。
F - Potion
ΣAがX以下。1種類だけ選んでひたすら待てばちょうどXにはできる。k種類のときはk個のA_iの合計がkで割ったあまりがXと同じならいける。ということで、N個の中からK個を選んだ和であってmod KでXと等しい最大が各Kについてわかればいい。どうするんだと思ってしばらく悩んだが、DPでできるじゃん。最初のi個の中からj個を選んであまりがb（変数名が酷い）になるときの和の最大でDP。時間計算量はO(N^4)になるが定数倍が軽い。空間計算量はO(N^2)にできた。dp[0][0]だけ0にして他は-INFで初期化。サンプル全然合わない。dp[k][x % k]が負のときスキップする。A_iを足してなかったので足す。
全体としてけっこう時間をかけた印象だが、思ったより時間が残っていた。
