tokuminiさんのユニークビジョンプログラミングコンテスト2023 新春 (AtCoder Beginner Contest 287)での成績：414位
パフォーマンス：1910相当
レーティング：1891→1893 (+2) :)
https://atcoder.jp/users/tokumini/history/share/abc287?lang=ja
A〜E問題までの5完。WAも出さずいいペースで解けていたのにF問題で封殺されてしまった。
A問題
ひっかかりポイントがありそうで怖い問題。過半数というのをちゃんと考えるのが嫌だったので、「Forの数」 と 「N - (Forの数)」を比較しにいった。
B問題
二重ループが許される制約なのでS,Tを文字列として考えたまま愚直に実装する。Sが長さ6だという制約は見えたけど、なにかが怖くて「後ろから3文字を取る」形の実装にした。
C問題
最初は
- 連結であること
- 次数1の頂点が2つだけであること
の2条件で判定できると思って実装し、提出直前に「端以外でループができている可能性」があることに気づいて
- 次数3以上の頂点がないこと
を追加した。危なかった。
D問題
一瞬難しそうな雰囲気があってやや焦るが、先頭と末尾からしか取らないのでその両端でどの長さまで一致しているかだけ最初に計算しておいて、答えるときに取得する幅とのminを取れば良いと気づいてなんとか処理できた。
E問題
SuffixArrayからどうこうするやつを考えると、ソートして隣とのLCPを調べるだけという解法が思い浮かんで、結構簡単目だなとは思ったし文字列のこのソートって計算量間に合うんだっけとかも自信がなくなったりしはしたけど、出してWAならそのとき考え直す戦略で出したら通った。
F問題
1時間10分以上取り組んで解けなかった。残念。
問題の性質からして、に対して独立に考えても問題が特に簡単にならないと感じたので、1回の木DPで
要素の配列を上手く更新していくのだろうという考えは良かった。
遷移を考えたときに、畳み込み操作だなと思ってatcoder::convolutionで畳み込むものを実装してTLE。logがつくだけだから間に合うんじゃないの？ とか思って、その後も実装のちょっとした変更で通らないかと試行錯誤して5回提出したけど、全然ダメ。
二乗の木DPというもの知らなかったし、知らずに思い付けるようなものかというとちょっと厳しそう。
コンテスト後、現実的に思いつけたかもしれないくらいの工夫として、不要な末尾を削除したら通るのかと思って出してみたけどダメだった→提出
resizeを多用してvectorの長さをなんとかすると通った→提出
G問題以降
読んでいない。
所感
先週のARCも、（そこまで考察が進んでいなかったとはいえ）C++のstd::sortだと比較回数が多すぎてstd::stable_sortだとマージソートベースなので比較回数が少なく済むというものを知らなくて実装ができなかっただろうなという問題だった。今回のF問題でも知らなくて解けないという印象はあり、結構長く競技プログラミングやっているつもりだったけどまだまだ知識足りないなーという感じ。
