仮想インデックスで脳を破壊されないために

引っ越す代わりにラベルを変える

　ABC395 がありました。

　この D 問題で脳を破壊された人がちらほらいるように見受けられます。

　要点を述べると、ハトが巣に入ったり、巣をまるごと交換したりというのを繰り返す、という問題ですが「巣をまるごと交換する」というのが難点で、実際にこれをシミュレーションしたら時間がかかります。

　そこで、「実際に移動するのではなく、ラベルが入れ替わったと考える」ことによって、事実上の引越を高速でシミュレーションする、というのが問題のポイントになります。

　……という考察を思いついた人は多いと思いますが、実装の段階で混乱してしまった人も多いのではないでしょうか。

• 箱→ラベルの配列
• ラベル→箱の配列

　をふたつもって、同時にそれらを更新する必要がありますが、特に「ラベル→箱」のスワップが難しいです。

　これをスマートに理解する方法はないか？

　色々考えたけど、ない という結論に至りました。ここに私は次の解決策を考えます。

解決策（根性）

• A_to_B といった変数名で、とにかく 「何から何の変換か」を明示する
• now_A といった変数名で、とにかく 「対象が何であるか」を明示する
• スワップはとにかく 変換の次元を合わせる

例

　上の問題だと、変数名は以下になります。

• pigeon_to_box
• box_to_label
• label_to_box
• now_pigeon
• next_label
• a_label
• b_label

　ここでのコツは、問題名で与えられる変数名（多くはアルファベット一文字であっても）も、意地でも「何が対象か？」を明記することです。

　コードは以下のようになります。ほとんど解説と同じですが……。

int main() {
    int n, q;
    cin >> n >> q;
    vector<int> pigeon_to_box(n);
    vector<int> label_to_box(n);
    vector<int> box_to_label(n);
    iota(all(pigeon_to_box), 0);
    iota(all(label_to_box), 0);
    iota(all(box_to_label), 0);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int now_pigeon, next_label;
            cin >> now_pigeon >> next_label;
            now_pigeon--;
            next_label--;
            pigeon_to_box[now_pigeon] = label_to_box[next_label];
        }
        if (t == 2) {
            int a_label, b_label;
            cin >> a_label >> b_label;
            a_label--;
            b_label--;
            int a_box = label_to_box[a_label];
            int b_box = label_to_box[b_label];
            swap(label_to_box[a_label], label_to_box[b_label]);
            swap(box_to_label[a_box], box_to_label[b_box]);
        }
        if (t == 3) {
            int now_pigeon;
            cin >> now_pigeon;
            now_pigeon--;
            cout << box_to_label[pigeon_to_box[now_pigeon]] + 1 << endl;
        }
    }
}

　とにかく、「スワップと代入は次元を合わせる」ことを意識しましょう。

練習問題

　$N$ が小さいのでシミュレーションでも解けますが、練習です。

使用する変数

• box_to_cd
• cd_to_box
• now_cd
• next_cd
• now_box
• next_box

int main(){
    int n,m;
    cin >> n >> m;
    vector<int> cd_to_box(n+1);
    vector<int> box_to_cd(n+1);
    iota(all(cd_to_box),0);
    iota(all(box_to_cd),0);
    while(m--){
        int next_cd;
        cin >> next_cd;
        int next_box = cd_to_box[next_cd];
        int now_box = 0;
        int now_cd = box_to_cd[now_box];
        swap(box_to_cd[now_box],box_to_cd[next_box]);
        swap(cd_to_box[now_cd],cd_to_box[next_cd]);
    }
    rep(i,n){
        cout << box_to_cd[i+1] << endl;
    }
}

　now_box は $0$ 固定なので定義する必要はありませんが、あえて now_box と名付けた方が脳に優しいです。

練習問題2

　マージテクを使う問題です。

　使用する変数

• box_to_label
• label_to_box
• box_to_colors
• color
• now_box
• next_box
• now_label
• next_label

int main(){
    int n,q;
    cin >> n >> q;
    vector<set<int>> box_to_colors(n);
    vector<int> box_to_label(n);
    vector<int> label_to_box(n);
    iota(all(box_to_label),0);
    iota(all(label_to_box),0);
    rep(i,n){
        int c;
        cin >> c;
        box_to_colors[i].insert(c);
    }
    while(q--){
        int now_label, next_label;
        cin >> now_label >> next_label;
        now_label--;
        next_label--;
        int now_box = label_to_box[now_label];
        int next_box = label_to_box[next_label];
        if(box_to_colors[now_box].size() > box_to_colors[next_box].size()){
            swap(box_to_label[now_box],box_to_label[next_box]);
            swap(label_to_box[now_label],label_to_box[next_label]);
            swap(now_box,next_box);
        }
        for(int color:box_to_colors[now_box]){
            box_to_colors[next_box].insert(color);
        }
        box_to_colors[now_box].clear();
        cout << box_to_colors[next_box].size() << endl;
    }
}

　実はこれ、box_to_label は必要ないのですが、そういうこを考えずにとりあえず定義しといた方がたぶん実装しやすいです。

　とにかく、泥臭くても、丁寧に名前をつけて、次元が合っているか確認しましょう。

練習問題3

　想定解は文字（たかだか $26$ 種類）の対応関係だけをシミュレートするものですが、マージテクを用いて計算量を抑えることもできます。

　使用する変数

• box_to_idxs（indices だと長いので、あえて idxs にしています）
• box_to_label
• label_to_box
• now_label
• next_label
• now_box
• next_box

int main(){
    int n;
    string s;
    int q;
    cin >> n >> s >> q;
    vector<vector<int>> box_to_idxs(26);
    rep(i,n){
        box_to_idxs[s[i]-'a'].push_back(i);
    }
    vector<int> box_to_label(26);
    vector<int> label_to_box(26);
    iota(all(box_to_label),0);
    iota(all(label_to_box),0);
    while(q--){
        char now_label,next_label;
        cin >> now_label >> next_label;
        if(now_label == next_label){
            continue;
        }
        int now_box = label_to_box[now_label-'a'];
        int next_box = label_to_box[next_label-'a'];
        if(box_to_idxs[now_box].size()>box_to_idxs[next_box].size()){
            swap(box_to_label[now_box],box_to_label[next_box]);
            swap(label_to_box[now_label-'a'],label_to_box[next_label-'a']);
            swap(now_box,next_box);
        }
        for(int idx:box_to_idxs[now_box]){
            box_to_idxs[next_box].push_back(idx);
        }
        box_to_idxs[now_box].clear();
    }
    vector<char> ans(n);
    rep(box,26){
        for(int idx:box_to_idxs[box]){
            ans[idx] = box_to_label[box]+'a';
        }
    }
    rep(i,n){
        cout << ans[i];
    }
    cout << endl;
}

　余談ですが、次元を合わせればなんでもいいという発想から、最後の ans への記入は以下のように書くこともできます。

（変更前）

    rep(box,26){
       for(int idx:box_to_idxs[box]){
           ans[idx] = box_to_label[box]+'a';
       }
   }

（変更後）

    rep(label,26){
        int box = label_to_box[label];
        for(int idx:box_to_idxs[box]){
            ans[idx] = label+'a';
        }
    }