AtCoder ABC 370 B - Binary Alchemy (5Q, 灰色, 200 点)

こういう値を順次更新していくようなシミュレーションは慣れておきたい！

• 問題へのリンク

問題概要

元素 がある。

元素 を合成すると、 のときは元素 になり、 のときは元素 になる。

元素 に対して、元素 を順に合成していったとき、最終的にできあがる元素はなんであるか？

制約

• 
• のいずれか

考えたこと

0-indexed で考える。このとき、合成されていく元素の番号を res とすると、初期状態では res = 0 である。

これに対して、 に対して、

---

res を、元素 res と元素 i を合成させてできる元素の番号に置き換える

---

という処理を繰り返していけば良い。具体的には

• res >= i のとき：res = A[res][i]
• そうでないとき：res = A[i][res]

というように書ける。

コード

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

int main() {
    // 入力受け取り（正方データで取得する）
    int N;
    cin >> N;
    vector A(N, vector(N, 0));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < i+1; j++) cin >> A[i][j], A[i][j]--;
    }

    // シミュレーション
    int res = 0;
    for (int i = 0; i < N; i++) {
        if (res >= i) res = A[res][i];
        else res = A[i][res];
    }
    cout << res+1 << endl;
}