新人競プロerの山田です。
今週から毎大会、振り返り日記をつけることにしました。ほぼ自分用です。
〇 A問題
パッと見た感じ、わからない。
とりあえず動的計画法っぽいなと思いdp[i] (Sのi文字目までで操作を行った場合何通りの文字列ができるか)を計算しようとした。
ここで次のことに気が付く。「違う操作を行っても、同じ文字列が現れることがある」ということ。そして、動的計画法では「ダブった文字列」の処理が難しいこと。
いったん動的計画法はやめ、通り数を直接的に求めることを考え始めた。ここまでで18分くらいだったかな。
文字列を置き換えるときの挙動を考える。「AB」「BA」といったかたまりが消える。「ABABAB」といったかたまりは「ABAB」か「AB」になる。
などとグルグル考えたところ正攻法にたどりついた。AとBが交互に現れる部分がひと固まりになっていて、ここから偶数個減るんだ。かたまりの要素数がゼロになることはありえないから骨格は保たれる。説明むずい。とにかくすぐにACした。
31分44秒。ペナルティなし。
いやむずかしい。山田はたまたま思いつきましたがなんでみんな解けてるんですか。
〇 B問題
いやもうほんとに何から手をつけていいかわからない。
とりあえず転倒数は関係していそう。r-lの小さい順から、入れ替えられるところを貪欲で入れ替えていくのかな。いやそれでいけるとは思えないな。
とりあえずいったんC問題を見てみる。見てみたが普通に意味がわからない。題意の理解に3分ぐらいかかったと思う。こっちのほうがヤバそうなのでBに戻る。
21:50あたりの時点で順位表をながめてみて、2完以上している人間がかなり少なかった記憶がある。250人ぐらいだったかな。今日のARCも1完で終わりそうだーっとほぼ諦めモードに入っていった。考えてはツイッター開いたり、考えてはDiscord開いたりを繰り返していた。順位表もたまにながめていた。
22:30頃、B問題の入力例出力例を使って手元のメモ用紙で実験していた。ここで一個気づいた。出力例だと、差が1の数字を入れ替えている回数がかなり多い。
後で解説を見てみたら、転倒数を思い出したのはいい線行ってた感じだった。ただinverse permutationの扱いに慣れておらずまだ解説を理解しきれていないので後でゆっくり読もうと思う。
〇 大会終了
結局1完のまま23:00大会終了。あーーーやっと無意義な時間が終わったって感じでした。
パフォーマンスは1122。水パフォ欲しかったですね（緑上位パフォの時毎回言ってます）。今の山田の実力では2完以上は不可能とはいえAはもっと早く行けたかもという感じです。
山田は前回のABCでやらかして初冷えを経験したのですが、そこで下がった分はほとんど取り返せました。明日のABCでhighest更新できたらいいです。
〇 最後に
レイアウトのいじり方が分からず全部同じ文字の大きさで書いているのでバカ見にくい記事になってると思いますすいません。
解法を思いつく過程を文章にすることで何かいいことがあるのではないかと思い、このようなことを始めました。部活でいう部誌みたいなものです。
数年後に山田が超つよつよ競プロerになった時、この記事が伝説になっていることを望みます。