お疲れさまでした~
20分3完でした、setは重複が自動削除されることを知らなかったのが敗因です……
敗因とか書いてるんですけど冷えてはないんですよね、灰diff早解きで緑パフォが出るの不思議ですね。
- A - Rearranging ABC
- B - Avoid Rook Attack
- C Prepare Another Box
- D - Many Segments 2
- E - Permute K times 2
A - Rearranging ABC
方針
ソートしてABCと等しいことを判定すればOK,。ちなみにBACとかだったら両方ソートしましょう。
B - Avoid Rook Attack
方針
飛車に取られないマスは何マスあるか、なので実際にシミュすれば良いです。
C Prepare Another Box
方針
基本的にはBと同様にシミュすれば良いですが、N^2マスととても大きいのでvectorでは管理できません。よって、mapを使って動けるマスを管理しましょう。駒があるところ自体もアウトなのと、実装の際にはN^2から置けないマスを引くのが良いと思います。
D - Many Segments 2
方針
色々やり方はありますが、自分が取った方針は、左端の固定です。左端をlとしたとき、l<=L[i]を満たす集合Rのうち、minR-iが答えとなります。これを左端からシミュレーションしていけば良くて、集合Rを削除して、その都度最小値を更新すればOKです。
余談
冒頭にも書いた通り、setは重複が削除されることを知らずにWAの原因が分からなくて通せませんでした......
ちなみにこの方針でも各値において要素数を管理してあげて、要素数が0になったらsetから削除してあげればOKです。
E - Permute K times 2
考えたこと
ダブリングの拡張パターンだと思いましたが、普通のダブリングすら怪しいので分かりませんでした......
解説見たらグラフ理論の話してて???ってなりましたね。
ちなみに青diffらしいです。直近のEで青diffは351だったので、相当珍しいですね。(352~376においては黄diffが2回でそれ以外は緑か水diff)