AGC032 A - Limited Insertion (400)

A - Limited Insertion

概要

空の数列aに下記の操作をN回繰り返す。

• i番目の操作では、1≦j≦iを選び、数列aの先頭からj番目にjを挿入する

N項の数列bが与えられる。上記操作でbを作成できるかを判定し、できれば挿入する数字を順番にN行出力し、できなければ-1を出力せよ。

制約

1 ≦ N ≦ 100

方針

この操作では先頭からi番目の項にiより大きい数字を挿入することはできない。
そのため、bについてi番目の項がiより大きい箇所が1箇所でもあれば作成できない。
実は、それ以外の場合はすべて数列を作成することができる。

まずは試行錯誤で与えられたサンプルについて、実際に数値を挿入する操作を繰り返して作成方法を考えてみる。
そのあと、最終状態(数列b)から操作を逆にみていく。すると、挿入されている項は当然その時点で先頭からi番目にiの数字が挿入されていることになる。

よって数列bについて、先頭からi番目にiの数字がある箇所を一つずつ消去してゆき、消去した数値を覚えてゆくことでその操作を再現できる。
このような箇所が複数個ある場合は、もっとも大きな数字の場所を消去すればよい。
例えば、b[i] = i+1かつb[j] = j+1かつi < jの場合は、数字j+1を消去すればよい。
これは先にi+1を消去してしまうと、次はb[j-1] = j+1となってしまい、j+1の挿入がもれてしまうためである。
逆にj+1を消去してもb[i] = i+1のままであるため、i+1の挿入がもれることはない。

下記は自分で解いたときに書いたメモです。（汚いですが。。）
サンプルは112431224（自作）です。
左側はbからスタートして消去すべき数値に○をつけています。
右側は消去した数字を逆にたどり、サンプルが再現できるかを確認しています。

解答

Submission #4672216 - AtCoder Grand Contest 032

#include <bits/stdc++.h>
#define rep(i,n) for(int i=(0);i<(n);i++)
 
using namespace std;
 
typedef long long ll;
 
int main()
{
	cin.tie(0);
	ios::sync_with_stdio(false);
 
	int N;
	cin >> N;
 
	vector<int> v(N);
	for(int i = 0; i < N; i++) cin >> v[i];
 
	for(int i = 0; i < N; i++){
		if(v[i] > i+1){
			cout << -1 << endl;
			return 0;
		}
	}
 
	vector<int> ans(N);
	for(int k = 0; k < N; k++){
		int t = 0;
		for(int i = 0; i < N - k; i++){
			if(v[i] == i+1) t = i+1;
		}
 
		ans[N-1-k] = t;
		v.erase(v.begin() + t-1);
	}
 
	rep(i, N) cout << ans[i] << endl;
}