AtCoder AGC 032 A - Limited Insertion (400 点)

好き！！！！！でも A 問題としてはかなり難しいね。

問題へのリンク

問題概要

数列 が空の状態から出発して以下の操作を 回行った結果が数列 と一致するようにできるかどうか判定せよ。

• 回目の操作においては 以上 以下の整数 を一つ選んで、数列の 番目に を挿入する

制約

• 

考えたこと

面白そう！！！
とりあえず様子を観察してみる。

操作を (1, 1, 3, 2) とすると

(1)
(1, 1)
(1, 1, 3)
(1, 2, 1, 3)

という風になる。ここで最終状態を見ると、

• 最後に挿入されたのは 1 (1 番目に挿入) か、2 (2 番目に挿入) かのいずれか

であることは直ちにわかる。 が操作された直後には、 となっているからだ。さらに言うと、もしここで (1, 2, 1, 3) に対して直前に操作されたのが だったと仮定すると前回は

• (2, 1, 3)

ということになってしまう。この「先頭の 2」はどう頑張っても決して実現できない。一般に

---

> となることは絶対にありえない

---

ということに注意する。 が挿入された時点ではそれは 番目にあって、その後 番目へと移動していく。

そのことを考えると、

(1, 1, 2, 4, 3, 6, 3, 2, 9, 4)

のような数列では

• 
• 
• 
• 

が直前の操作の候補であるが、9 以外に操作された可能性はありえない。なぜなら、例えば 4 に操作していたとすると直前には

• 
• 

ということになってしまう。これらは決して実現できない。

以上から、

---

• 数列 が与えられたときに、直前の操作は一意に復元できる

• それは となる最大の である

---

ということがわかった。あとは操作を巻き戻しながら、途中で詰まったら「不可能」と判定すればよい。

#include <iostream>
#include <vector>
using namespace std;

int N;
vector<int> a;

void solve() {
    vector<int> res;
    for (int i = 0; i < N; ++i) {
        int pivot = -1;
        for (int j = (int)a.size()-1; j >= 0; --j) {
            if (a[j] == j) {
                pivot = j;
                break;
            }
        }
        if (pivot == -1) {
            cout << -1 << endl;
            return;
        }

        res.push_back(pivot + 1);
        a.erase(a.begin() + pivot);
    }
    reverse(res.begin(), res.end());
    for (auto v : res) cout << v << endl;
}

int main() {
    cin >> N;
    a.resize(N);
    for (int i = 0; i < N; ++i) cin >> a[i] , --a[i];
    solve();
}