tokuminiさんのToyota Programming Contest 2023 Spring Qual A(AtCoder Beginner Contest 288)での成績:302位
パフォーマンス:2172相当
レーティング:1807→1849 (+42) :)
https://atcoder.jp/users/tokumini/history/share/abc288?lang=ja
A~Eまでの5完。ペナルティを出さなかったのが良かった(というか単純にサンプルが充実気味だったのかもしれない)。前回の反省を活かし、D問題で詰まった際に一旦飛ばしてE問題を先にACし、気持ちに余裕を作ってからD問題に戻ってAC出来たのは良かった。
A - Many A+B Problems
もうA問題でループ使うのも当たり前になってきたな。
B - Qualification Contest
謎にstd::set
に詰める方針でやってしまった。
C - Don’t be cycle
Union-Findでやればいいんだろーってあまり厳密に考えずにやった。
D - Range Add Query
なんとなく差分に注目したくなる問題設定だなとは思ったし、そうするとK間隔で2箇所に同じ値をプラスとマイナスする操作だとは理解したが、そこから厳密に詰めていくのが難しかった。30分経過してしまったので一旦飛ばした。
戻ってきて考え直すと、先頭と末尾は切り出しているので、両端に0をくっつける感じでやらないといけないということに気づいた。これもサンプル2がちゃんとそういうケースを入れていたのでわかったが、なかったら難易度さらに上がっていたのでは?
E - Wish List
まともにやっていくと解ける問題設定じゃないのでDPなんだろうなと思った。取った数を持っていれば、次に取るものをどれだけスライドしたタイミングで取るかはその範囲内で自由に選べそう。
Cの区間minを求めるのにセグメント木を使ったので実行時間が最大879msecでちょっと怖かった。
F - Integer Division
まずN(N-1)/2くらいかかるDP解は書いてみて、でもこれは高速化できる見た目じゃないなぁ〜と思って寄与ごとに分解するとかいろいろ考えていたけどダメだった。このDP高速化できるのか……。1桁目だけ扱いが違うとか難しい。