[解析アルゴリズムプール]BOJ 2858の原状回復

久々のやり直しアルゴリズム!簡単な実装問題BOJ 22858原状回復を解答しました!

BOJ 22858原状回復

番号はP 1、P 2、...、PNP_1, P_2, ..., P_NP1​,P2​,...,PN NNN個のカードがあります.
D1、D2、……Di,...DND_1, D_2, ... , D_i , ... D_ND1​,D2​,...,Di​,...DNがあります.このとき、DID iDIは、3番目のPDIP{D i}PDI値を意味する.この仕事をシャッフルと呼ぶ.トランプの仕事は同時に行われた.
例えば、P 1、P 2、…、PNP_1, P_2, ..., P_NP1​,P2​,...,PNは、1、4、5、3、2、D 1、D 2、…、DND_1, D_2, ..., D_ND1​,D2​,...,DNが4 3 1 2 5であると仮定するこのカードは打つと三五一四二です.次の図では、SSSはカードを1回混合した後を意味します.

上記のようにKKが混ざったカードの情報とDDDの情報が分かれば、元のカードがどのように置かれているかを見てみましょう.

にゅうしゅつりょく

[入力]
1行目は、カード数NNNとカードの混合回数KKKをスペースで区切ります.
2行目では,KK番号カードを混合すると,カードの配置を示すSiS iSiがスペースで区切られ,NNN個である.
3行目には、N個のDID iDIがスペースで区切られています.
[出力]
オリジナルカードのレイアウトをP 1 P 1 P 1からPNPNまでの値をスペースで区切って出力します.
[制限]
1≤N≤1041\le N\le 10^41≤N≤104 
1≤K≤1031\le K\le 10^31≤K≤103 
1≤Di≤N1\le D_i\le N1≤Di​≤N 
1≤Pi,Si≤1061\le P_i, S_i\le 10^61≤Pi​,Si​≤106 

私の答え

アルゴリズム自体は簡単です.銀3段階の問題なので特に難しくはありません.与えられた方式を逆方向に実行することにより、S[i]値が元のD[i]位置に存在するべきであることが容易にわかる!
入力したSをk回並べて、最後の結果を出力すればよい.
入力値が大きい場合は、余分な配列を書くことを考慮するかもしれませんが、それほど大きくはありませんので、毎回新しい配列に含まれる置換形式で行います.

コード#コード#

#include <iostream>
#include <vector>

// boj 22858 원상 복구, 실버 3, 구현
using namespace std;

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int N, K;
    cin>>N>>K;

    vector<int> S(N+1,0);
    vector<int> D(N+1, 0);

    for (int i = 1; i <= N; ++i) cin>>S[i];
    for (int i = 1; i <= N ; ++i) cin>>D[i];

    vector<int> rewind(N+1, 0);
    while (K>0){
        K--;
        for (int i = 1; i <= N; ++i) {
            int origin_index = D[i];
            int num = S[i];
            rewind[origin_index] = num;
        }

        S = rewind;
    }

    rewind.clear();

    for (int i = 1; i <= N; ++i) {
        cout<<S[i]<<' ';
    }
    cout<<'\n';

   return 0;
}