A - Limited Insertion agc032_a

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

何が足りない?

7
1 2 2 1 2 3 2
  • を考えてみると、先頭とその次がそれぞれ遡りの対象になる
  • 前者の遡り後(1を取り除く)
6
2 2 1 2 3 2
  • 詰み
  • 一方、後者(2を取り除く)
6
1 2 1 2 3 2