けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder AGC 032 A - Limited Insertion (400 点)

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

問題へのリンク

問題概要

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

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

制約

  •  1 \le N \le 100

考えたこと

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

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

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

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

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

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

  • (2, 1, 3)

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


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


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

そのことを考えると、

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

のような数列では

  •  a_1 = 1
  •  a_4 = 4
  •  a_6 = 6
  •  a_9 = 9

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

  •  a_5 = 6
  •  a_8 = 9

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

以上から、


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

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


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

#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();
}