SOMPO HD プログラミングコンテスト2021(AtCoder Beginner Contest 192)
88:38 全完、9ペナ (？？？？) で レートは1881 → 1883 (+2) perf. 1901
A - Star
100 - X%100
B - uNrEaDaBlE sTrInG
大文字小文字判定ができますか？
C - Kaprekar Number
ギョッとしたけどやるだけ、直前に自作したstoi関数が火を吹いたぜ！
D - Base n
まず、適当な嘘 (最上位がMを超えないような最大のBをにぶたんで見つけてその周辺を探索する) を投げてWA、落ち着いてEにいった。
E - Train
あえて遅く到着するのが最適であることはあり得ないので、ダイクストラをちょびっと改造すればいけそう、順位表からも簡単なことが判明していたので素直にやって投げる。
D - Base n (再)
最上位だけじゃなくて全部見れば良くない？になる。ちゃっちゃと書き直して投げるとWA(2) 。明らかなバグを直し、にぶたんの範囲を変更して投げるとWA(3)。REが出たので、ああ、0徐算かとなってにぶたんの範囲を戻して投げるとWA(4)。ふと手元で|X|=1のケースを試してみると明らかにバグってるのを見つける。|X|=1のとき、無限じゃない？となって混乱。|X|=1のときは0を返すようにして提出 (なんで？？？？) 当然WA (5)。問題文を良く読んでみるとnの種類数ではなくn進数で見たときのXの値の種類数であることがわかる。つまり|X|=1のときは1ね！として投げるとWA(6)。原因が分からずに苦し紛れににぶたんの範囲だけ変更して投げる、WA(7)。|X|=1のとき、0になる可能性に気づく、X > M のときは0として投げる、ようやくAC！！！落ち着いて振り返ってみるとひどいね
F - Potion
kを固定して考えてみると、素材をk種類選ぶ選び方で、(魔力の総和) = X (mod k) となるもののうち、魔力の総和が最大になるものを選べばいいことがわかる。これは素材をいくつとったかと、総和 (mod k) を状態に持つDPでいける。全てのkについてDPを行うとO(N4)だが、軽いのでいけそう。総和がXを超えちゃう場合はどうしようかと思ったが、制約でそのパターンはあり得ないことになっているので問題なし。ぱぱっと書いて投げるとWA(8)。DPテーブルの初期値を全て0にしてしまっていた (素材をk種類選ぶという状態が無意味になる) ので直して投げるとWA(9)。-INFから遷移させてるのが怪しいことに気づいて投げ直してAC。ふう......
まとめ
毎度のことだけど焦りすぎ。青上位 perf. で暖まらなくなって今青上位にいるんだなあと実感した。
