AtCoder Beginner Contest 072 [ D - Derangement ] をPythonで解く（400点🟫茶diff）
AtCoder ProblemsにRecommendationって機能あって、ユーザことにオススメの難易度の問題を勧めてくれるんですよね(Atcoder Problems -> User -> Recommendation)。
🟫茶diffやるべきだろうなと思ってたら、見事に茶の問題ばかり勧められるので、素直にやってきます。
解法
- 数列pを頭から見ていって、Pi == i となってる場所にフラグを立てる
- フラグを頭から見ていって立ってる場所を隣とスワップ。基本はiを見てi + 1とスワップ。最終ループはiとi+1両方見る
- 全部スワップしたかのフラグチェックを二分探索で。TLE対策
書いたPythonコード
参考
公式解説
