トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)

　Fまで六完。コンテスト後50秒でGが通った。また、Fはafter contestのcaseで落ちた。

コンテストへのリンク

コンテスト後のツイート

トヨタ自動車プログラミングコンテスト2023#2(AtCoder Beginner Contest 302)
C 順列全探索
D 尺取り
E setで愚直
F うまくBFSする
G SA=sorted(A)として、(A[i],SA[i])の組を考える。(x,x)は無視、(x,y)と(y,x)があれば交換してOK。それ以外のとき、適切に（なんでも良い？　よく分かっていない）交換

— titia (@titia_til) May 20, 2023

F - Merge Set

　見直したら解法自体はあっていてほっとした。

　初期状態で1を含む集合がたくさんあったとき、それらの要素を全て初期状態に放り込み、重複をなくすことを忘れていたのがafter contestで落ちた原因だった。

　コンテスト中でTLEが返ってきたらどうだったろうか。解法自体はあっているので気付けばすぐ修正できただろうが、すぐ気付けたかは分からない。

　

Ex - Ball Collector 

　解説放送を見てAC。

　こういう問題でグラフへ帰着するのはよくあるのに、思いつかなかったのは反省。

　Roll-back付きUnion-findが思ったより簡単に書けることは勉強になった。

　なお、再帰で書いたらTLEしたため非再帰に書き直した。

　こういうdfsで帰りがけに処理をするのを非再帰でどう書けばいいか分からない部分があったのだが、その書き方が分かったのも良かった。