AGC032A Limited Insertion

くそむず

#include <bits/stdc++.h>

using namespace std;

#define rep(i, n)       For(i, 0, n)

const ll INF = 1LL << 60;

ll n , a, b; 
string S;
//Write From this Line

int main()
{
    cout << setprecision(10);
    cin >> n ;
    vector<int> b(n);
    vector<int> ans(n,-1);
    rep(i,n){
        cin >> b[i];
        if(b[i] > i + 1 ){
            //i番目にi+1 よりも大きいものが入っていたらダメ
            cout << -1 << endl;
            return 0 ;
            //荘じゃなければ作れる。
        }
    }
    //i番目の削除を削除はv.erase(v.begin() + i );
    int num;
    int del ;
    for(int i = n -1 ; i >= 0 ; i --){//
        for(int j =  0; j  < b.size();j++){
            if(b[j] == j+1 ){
                num = j + 1 ;
                del = j;
            }

        }
        ans[i] = num;
        b.erase(b.begin() + del);
    }
    for(auto x : ans){
        cout << x << endl;
    }

}

解法

まずわかる事は、

bの数列のi(1インデックス）番目の値がiより大きかったら無理（-1を出力）

例)

数列b = { 1 3 2 1 1 1}

ここでは、2番目の値(=3)が2より大きいので無理。

3を入れれる操作は3回目で、3番目に挿入するので、

値3は3番目よりも前に入れることはできない。

そうでなければ数列bのように並べることが出来る（らしい）

ヒントは操作を後ろから見る。

僕は天才の考察用紙を見せてもらってＡＣしたので、

自分の理解が深まって、はい、説明できますよ^^ってなったらまた書きに来ます。ちょっと今は自信ない。

使ったもの

vecotr の削除

vectorの名前をVとすると

V.erase(V.begin() + i ) で、i番目（0インデックス）の要素を削除することが出来る。