脳log[20220731]

2022年07月31日 (日) [AtCoder] 今日は ABC262 があった。最近頭の中に蜘蛛の巣が張っていて ARC でも ABC でもいいことがない。時間内には解けなかったけど手応えがあった F 問題「Erase and Rotate」について書いて気持ちを良くする。■操作を繰り返して辞書順最小の数列を作る。制約から数列は空にはならない。■１．まずどの要素を先頭にするか決める。これは操作回数の制約の中で先頭に持って来られる要素のうち最小のもの。■２．次は２通り考える。先頭の要素をどのようにして先頭に持ってきたか。前にある要素を削除したか、ローテートして後ろのものを前に持ってきたか。■２-Ａ．簡単なのは前にある要素を削除して先頭を先頭に持ってきた場合。残りの操作回数で隣接２項が減少している場所を見つけて一方を取り除く。前の方から数列が昇順になるように整形するということ。それでも操作回数が余ったら末尾の要素を取り除いて数列を短くする。並びが同じなら短い方が良い。他の人の提出を見ていたら、ステップ１を飛ばしてこの操作をしても自動的に先頭になるべき要素が先頭に出てきて同じ結果になるらしい。■２-Ｂ．ローテートして先頭を先頭に持ってきた場合は数列を２つに分ける。ローテートした部分と、それ以外の部分。それ以外の部分は２-Ａと同じ処理をして答えの数列の後半部分とする。先頭を先頭に持ってくるためにローテートした部分というのは、実はローテートする代わりに削除したとしても構わない。どちらが得か。答えの数列の後半の先頭の要素より小さくて昇順になっている限りにおいて削除せずに保存する。■TLE、TLE、AC。■難しくてわからんという問題ではなくて、実装が大変、見落としが怖いという問題だったと思う。門前払いにせず手を動かしただけ達成感を与えてくれる問題で好き。黄 diff なのは６問目で時間がなかったか細部を詰め切れなかったかだと思う。