yukicoder No.429 CupShuffle

問題

問題概要

数列をswapしていく。k回swapするが、k-1回文のswapの処理は与えられるが、どこか一か所のswapの処理がわからないようになっている。一番初めの数列の状態と、最後の数列の状態が与えられるので、途中一か所わからないswapの処理がどのようなものを判定する問題。

解法

まず、はじめの状態から処理がわからない箇所まで順方向にswapの処理をして、どのような数列になるかを求める。つぎ、最後の状態から、処理がわからない箇所まで逆方向にswapの処理をしてどのような数列なるかを求める。それら2つの数列を見比べて、値が異なっている場所が、処理がわからない箇所でswapした場所である。

ミス

逆方向から考える問題は多いよね。

コード

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstdio>
#include <set>
#include <string>
#include <cmath>
using namespace std;
typedef long long ll;
#define rep(i,n) for(int i=0;i<(n);i++)
const int INF = 1e9;

int a[100010], b[100010];
int main(void){
    int n, k, x; cin >> n >> k >> x;
    int idx;
    rep(i, k){
        string ta, tb; cin >> ta >> tb;
        if(ta == "?" && tb == "?"){
            idx = i;
            a[i] = 0, b[i] = 0;
        }else{
            a[i] = stoi(ta); b[i] = stoi(tb);
        }
    }
    vector<int> rv(n);
    rep(i, n){
        cin >> rv[i];
    }
    vector<int> v(n);
    rep(i, n){
        v[i] = i + 1;
    }

    //順方向
    for (int i = 0; i < idx; ++i){
        swap(v[a[i] - 1], v[b[i] - 1]);
    }
    //逆方向
    for (int i = k - 1; i > idx; --i){
        swap(rv[a[i] - 1], rv[b[i] - 1]);
    }

    vector<int> ans;
    rep(i, n){
        if(v[i] != rv[i]) ans.push_back(i);
    }
    rep(i, ans.size()){
        printf("%d ", ans[i] + 1);
    }
    printf("\n");
    return 0;
}