AtCoder ABC 306 C - Centers (灰色, 250 点)

バケットを使ってもいいし、set や map を使ってもいいかもしれない

• 問題へのリンク

問題概要

が 3 回ずつ表れる長さ の数列 が与えられる。

を「数列 において 2 回目にその値が登場する index」が小さい順にソートせよ。

制約

• 

考察：まず問題を掴む

最初の注意点として、配列 A の添字は 0 始まりで考えることにする。

まずは問題をつかもう。たとえば のとき、

• が 2 回目に登場するのは A[1]
• が 2 回目に登場するのは A[6]
• が 2 回目に登場するのは A[4]

ということで、これが小さい順に を並べると、答えは となる。

解法 (1)：2 回目に登場する index を求めて、キーにしてソート

一つ目の方法として、次の方法が考えられる。まず、次のような配列 ind を求める。

---

ind[v] ← A[i] = v となる添字 i は 3 個あるが、そのうち 2 番目の値

---

とする。この配列は for 文を回すことで求められる。たとえば、次のようにすればよい。

vector<int> cnt(N+1, 0);  // cnt[i] は i が何回登場したかを表す
for (int i = 0; i < N * 3; ++i) {
    ++cnt[A[i]];
    if (cnt[A[i]] == 2) {
        ind[A[i]] = i;
    }
}

このようにして配列 ind を求めれば、その値をキーとして、 をソートすればよい。

計算量はソートの部分が最も時間がかかるため、 となる。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> cnt(N+1, 0), ind(N+1);
    for (int i = 0; i < N * 3; ++i) {
        int A;  cin >> A;
        ++cnt[A];
        if (cnt[A] == 2) ind[A] = i;
    }
    
    // 1, 2, ..., N を ind が小さい順に並び替える
    vector<int> res(N);
    for (int i = 0; i < N; ++i) res[i] = i+1;  // 配列 {1, 2, ..., N} を作る
    sort(res.begin(), res.end(), [&](int i, int j){return ind[i] < ind[j];});
    for (int i = 0; i < N; ++i) cout << res[i] << " ";
    cout << endl;
}

解法 (2)：2 番目に見つけるたびに res に push

もう少し楽に実装することもできる。

そもそも、配列 A を順に見ていく過程で、「2 回目に登場した値」を検出した順に、答えを表す配列 res にその値を push していけばよい。

それを出力するだけで OK。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> cnt(N+1, 0), res;
    for (int i = 0; i < N * 3; ++i) {
        int A;  cin >> A;
        ++cnt[A];
        if (cnt[A] == 2) res.push_back(A);
    }
    
    for (auto v : res) cout << v << " ";
    cout << endl;
}