AGC032_A Limited Insertionをコンテスト中に解いた話

AGC032はA問題から400点という事で、初心者の方には難しく結果として０完や、未提出となった方も多いと思います。公式の解説pdfではA問題にとてもわかりやすい解法が書いてありますが、今回は解説の解法が思いつくような天才にはなれなかった私がコンテスト中にACした方法を書いていこうと思います。ちょっと面倒な解法ですが、解説のような手法が思いつかない場合に強引になんとか解く方法は有用です。私は前回のAGC031でもO(1)数学解法が思いつかずに再帰を用いた、速度が愚直にやる場合よりはやや改善されたbit全探索で実行時間ギリギリでACをしました。毎回最もスマートな解法を思いつけるとは限りませんので、様々な解法を知っておくとよいことがあるかもしれません。
というわけで、AGC032のA問題である、Limited Insertionのコンテストの解き方です。

まずこの問題で考えたいのは、無理な条件がどのような場合かという点です。この問題では、自明に無理なケースとしてサンプル２があります。
Sample2 2 2 2
これは問題中にある通り、数列の先頭に２を追加する事が出来ません。このように、任意の数字Ｎに対してその数字が数列bでのＮ番目より前にある場合は不可能であることがわかります。では、これ以外でダメなケースはあるのでしょうか？
実はありません。これが何故なのかは解法を説明してからの方がわかりやすいため、解法から先に説明します。
というわけで解法です。
空文字列から１文字ずつ追加する各クエリでaに追加するのは、最終形であるｂの数列の中にある任意のまだ取っていない数字で、(それより前に位置する要素の中で既に追加されている要素の数+1)以上のものの中で最も後ろにあるものです。相変わらず日本語は難しいので、具体例で説明します。

Sample3 9 1 1 1 2 2 1 2 3 2
これは、まず最初に追加するのはどの１でしょうか？
正解は5番目(0-index)です。最初はどの要素もとっていないため、それより前で既に追加した数は次のようになっています。
0 0 0 0 0 0 0 0 0
実際には+1なので、配列の全要素を+1しておきましょう。
1 1 1 1 1 1 1 1 1
というわけで、最初に追加するのはｂの中で最も後ろにある1で５番目です。次にこの５番目の1を追加したことでこのそれより前で既に追加した数配列(以降配列ｃとします)は、
1 1 1 1 1 2 2 2 2となります。
すると、次に追加するのはbでの8番目の2となり、これを追加すると
1 1 1 1 1 2 2 2 3
というふうになります。これを繰り返すと、
6番目の2を追加する
1 1 1 1 1 2 3 3 4
7番目の3を追加する
1 1 1 1 1 2 3 4 5
2番目の1を追加する
1 1 2 2 2 3 4 5 6
4番目の2を追加する
1 1 2 2 3 4 5 6 7
3番目の2を追加する
1 1 2 3 4 5 6 7 8
1番目の1を追加する
1 2 3 4 5 6 7 8 9
0番目の1を追加する
2 3 4 5 6 7 8 9 10
となりうまくいきました！ここで重要なのは、複数候補が存在する場合は最も後ろから追加していくことです。これの理由は、前の要素を追加する場合は当然それより後ろの要素を追加する場合にも影響を及ぼしますが、一番後ろの要素を追加することで少なくともそれより前の要素に影響を及ぼすことはないからです。また、要素を前から追加する場合、これは実験をすると簡単にわかるのですが明らかに答えがおかしくなります。また、なぜこの解法が上手く行くのかの説明や証明は難しいです。恐らく私のレベルだと公式のpdf解説を用いてこう解けるからこの解法も正しいみたいな事になると思います……
この解法はある程度実験でそれっぽい事をしないと導くのは難しいかもしれません。やはり実験は偉大ですのでみなさんもしましょう。
最後に、これだと何故sample２のようなケース以外で上手く行くかの説明です。これはもう簡単で、上の解法のようにやると少なくとも一番前の１が追加でき、するとその次の２も追加でき…と順順に前から条件を満たすからです。
ちなみにO(N^3)で想定解より遅いので制約が甘くて良かったです。
最後になりましたが、コードを張り付けて終わりにしたいと思います。

taskA.gcc

int b[101010];
int c[101010];
int N;
int main() {
    cin>>N;
    for(int i=0;i<N,++i){
        cin>>b[i];
        if(b[i]>i+1){
            cout<<-1<<endl;
            return 0;
        }
    }
    for(int i=0;i<N,++i){//i回目の文字の追加
        for(int j=N-1;j>=0;--j){//後ろから追加できる条件を満たすものを探す
            if(b[j]<=a[j]+1){
                cout<<b[j]<<endl;
                b[j]=1000;//一回使った値を二回使わないように大きい値で上書きする
                for(int k=j,k<N;++k){
                    c[k]++;
                }
                break;
            }
        }
    }
	return 0;
}

また、何か疑問点等ありましたらTwitterまでお聞きください。
始めてQiitaを書いたのですが、とても難しかったです。文章力も精進しますね。