ARC042 A:掲示板

競技プログラミング

https://atcoder.jp/contests/arc042/tasks/arc042_a

最初は1〜Nまで昇順に整列されている。
この数列に格納されている数字を、次のM行に入力される順に次々と頭の方に持っていく。
もちろん、これをプログラムで愚直にシミュレートしようとしたらメモリアクセス違反起こしそうだわそもそもTLEに引っかかりそうだわとえらい目にあうのは確定的。
そこで、あらかじめN+Mのサイズの配列を用意しておく（こういう発想がちゃっちゃとできるようになりたい）。前のN-1番目までは普通にN〜1までの数値を格納し、続くN〜M-1番目に入力される数値を格納する。
あとはすでに出力された数値かに気をつけながら配列をケツから走査すれば、結果的に浮上したスレッド番号 + 昇順番号の数列を出力できる。

int main() {
    int n, m; cin >> n >> m;
    vector<int> v(n+m,0);
    for (int i = 0; i < n; i++) {
        v[i] = n - i;
    }
 
    // 浮上したスレッド番号をケツにつけていく
    for (int i = n; i < n + m; i++) {
        int a; cin >> a;
        v[i] = a;
    }
 
    vector<bool> used(n+10, false);
    // ケツから
    for (int i = n + m - 1; i >= 0; i--) {
        int a = v[i];
        // すでに登場しているスレッド番号は無視
        if (!used[a]) {
            cout << a << endl;
            used[a] = true;
        }
    }
}

まあ最初は見事にTLE散らかしたわけだが。

int main() {
    int n, m; cin >> n >> m;
    vector<int> input(m);
    for (int i = 0; i < m; i++) {
        cin >> input[i];
    }
    reverse(input.begin(), input.end());
    vector<int> v;
    for (auto a : input) {
        auto iter = find(v.begin(), v.end(), a);
        if (iter == v.end()) {
            v.push_back(a);
        }
    }
 
    for (int i = 1; i <= n; i++) {
        auto iter = find(v.begin(), v.end(), i);
        if (iter == v.end()) {
            v.push_back(i);
        }
    }
 
    for (auto a : v) {
        cout << a << endl;
    }
}

100%間違った表現だろうけど、雑に計算してみても O(2n^2logN) ぐらいのオーダーになってる。そりゃ間に合わんわな。