AtCoder Beginner Contest 371

　Eまで。

コンテストへのリンク

コンテスト後のツイート

AtCoder Beginner Contest 371 Eまで。最初に手をつけたCに20分かかった。
A 高い方に+1低い方に-1して、合計が0のもの。
B どの家で太郎とつけたか記録しておく。
C 対応する点をどうするか全部試す。
D 座標圧縮して累積和
E ある数字をこの前つかったのがいつだったかを覚えていれば計算できる。

— titia (@titia_til) September 14, 2024

F - Takahashi in Narrow Road

　解説放送を見てAC。SortedSetを使った。

　解説放送を見て衝撃だったのは、$X_i-i$、$G_i-T_i$と座標変換して良いというところだった。これは思いつけない。

　これを思い付いていればそれ以降の部分は自力で解けた気がするので、ここが本質だと思う。しかし、言われてもかなり長いこと正当性が分からなかった。

　こういう変換ができることもあると覚えておきたい。

　

G - Lexicographically Smallest Permutation 

　大体自力でACだけど、中国剰余定理などという単語はツイッターで見た。

　順列を、どう巡回するかで分けるのはよくある方法。一つ決めるとその巡回部分は全て決まるので、それを使って最初の数字から決めていく。辻褄を合わせることができるか？　とい部分で中国剰余定理を使えばOK。

　Fでなくこっちを解いていればコンテスト中に解けた気もする。

　ただ、コンテスト中は、Gの「辞書順」という単語を見て避けてしまったんだよね。もうちょっとちゃんと問題を把握してから解くか避けるか決めた方が良いね。