JOI 本選 2023 A - 碁石ならべ 2 (難易度 6)

どうなっているのかを観察して計算量を減らす系。観察力が問われる！

• 問題へのリンク
• editorials

問題概要

個の碁石を左から順に並べていく。 番目に並べる碁石の色は である ( 以上 以下の数値)。碁石を並べるときの規則は次のようになる。

• 番目の碁石を 番目の碁石の右に置く
• このとき、 番目の碁石の中に、 番目の碁石と同じ色の碁石が存在するならば、そのうちの最も右にある碁石の番号を として、 番目の碁石の色をその色にする

すべての碁石を配置したあとの、各碁石の色を求めよ。

制約

• 

考えたこと

愚直にシミュレーションすると の計算量となる。この手の問題は「どうなっているか」をよく観察することが重要になる。たとえば、

• 

に対して適用してみよう。そうすると、次のようになる。

• 

こうしてみると、先頭要素がかなり重要であることが見て取れる。結局

---

先頭要素と、その先頭要素の色と同じ色である最後の要素との間が、すべてその色になる

---

ということがわかる！

続きはどうなるだろうか。実はこれも単純で、「先頭要素からその色と同じ最後の要素までを除外して、その時点での最左の要素を新たな先頭要素として同じことをする」というふうに考えれば OK。

このように、先頭要素について考察しておくと、その後の要素についても同様に考えれば OK という考察の流れは超頻出！！！

コード

実装上は、「色が であるような最後の碁石が何番目であるか」がパッと分かるようにしておきたい。その情報を予め前処理として求めておけばよい。

その部分に map を用いることにすると、全体の計算量は となる。

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

int main() {
    int N;
    cin >> N;
    vector<int> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    
    // index ベースにする
    map<int, vector<int>> place;
    for (int i = 0; i < N; ++i) place[A[i]].push_back(i);
    
    // 前から順に見ていく
    for (int i = 0; i < N; ++i) {
        // A[i] と同じ値の最後の要素を持って来る
        int last_id = place[A[i]].back();
        
        // i から last_id までは A[i] の値になる
        for (int j = i; j <= last_id; ++j) A[j] = A[i];
        
        // i を last_id にセットする
        i = last_id;
    }
    
    for (auto v : A) cout << v << endl;
}