Quiz
https://atcoder.jp/contests/agc032/tasks/agc032_a
Submit
https://atcoder.jp/contests/agc032/submissions/4676797
解法
- テストケース3を見ると、最終状態から過去に1手づつ遡るのがよさそう
- 最後に行える操作は、j番目にjを挿入
- A[j] == j の箇所に最後に挿入した可能性がある
- それを取り除き、N-1の長さになった配列に同じく遡りを行う
- dfsで書いた
- TLE... (あと少し足りない)
- 計算量はO(N * N-1 * N-2 * ...) = O(N!)
Submit TLE
- https://atcoder.jp/contests/agc032/submissions/4671026
- 最初に提出したもの
- TLEのみなので方針は合っている
何が足りない?
7 1 2 2 1 2 3 2
- を考えてみると、先頭とその次がそれぞれ遡りの対象になる
- 前者の遡り後(1を取り除く)
6 2 2 1 2 3 2
- 詰み
- 一方、後者(2を取り除く)
6 1 2 1 2 3 2
- 継続可能
- ということで、A[i]==iが複数あった場合は最後尾のもので遡らないと詰む
- これを導入すると計算量が落ちてAC
- https://atcoder.jp/contests/agc032/submissions/4676797
- O(N2)という確信は得られていない..