問題の概要

数列(1,2,...,n)があります．その後， $i=1,2,\dots ,m$ の順で， $e_i$ を数列の先頭に出します．最終的な数列を出力してください．

例えばsample1では，
1,2,3,4,5
4,1,2,3,5
2,4,1,3,5
5,2,4,1,3
となって，答えを得ます．

解法

まず， $e_i$ の最後にある値ほど先頭に来ることが分かります．よって，最終的な数列は， $e_i$ を逆順にしたものが先頭に来て，それから残りを単に昇順にしたものが後ろにくっついたものになりそうです．sample1では，4,2,5の順で前に出しているので，最終的な数列はその逆順の5,2,4が先頭に来て，残りの1,3が後ろにくっついたものになります．

でも一つだけ罠があって，同じ値が何度も前に出されることがあります．一見ややこしそうに見えますが，2回目以降に前に出された値は，それ以前の位置は気にする必要はありません．とにかく，最後に先頭に出された値ほど，最終的な数列でも先頭にくるということが重要で，値が何回前に出されたかは気にする必要がありません．

このことは， $e_i$ を逆順に出力するときに，初めて出現した値だけを出力することで実現できます．実装としては，「既に出力したか？」を表すフラグ用配列を作っておくことが考えられます．

また， $e_i$ に出現しなかった残りの値の出力方法については，1,2,...,nの値を，フラグ用配列と照らしながら順番に出力するようなことが考えられます．

#include <iostream>
#icnlude <vector>
using namespace std;
int main(){
    int n,m; cin>>n>>m;
    vector<int> e(m);
    // e_iの入力
    rep(i,0,m){
        cin>>e[i];
    }
    // 既に出力したか？を管理するフラグ用配列
    vector<int> outed(n, 0);
    // e_iは後ろから見て
    for(int i=e.size()-1;i>=0;i--){
        // フラグが0なら出力
        if(outed[e[i]-1] == 0){
            cout<<e[i]<<endl;
            // フラグを1に
            outed[e[i]-1] = 1;
        }
    }
    // 残りを出力．1~nまで回して，フラグが0なら出力
    for(int i=1;i<=n;i++){
        if(outed[i-1] == 0){
            cout<<i<<endl;
            outed[i-1] = 1;
        }
    }
}

gotutiyan’s blog

ICPC アジア地区予選2016-A Rearranging a Sequence 解説

問題の概要

解法