AtCoderの065 B – Trained?をC++で解いてみた

こんにちは！ mnbd（@mnbbbbbd）です。

AtCoder Beginner Contest 065 B Trained?

問題文

筋力をつけたい高橋君は、AtCoder 社のトレーニング設備で、トレーニングをすることにしました。
AtCoder 社のトレーニング設備には N 個のボタンがついており、ちょうど 1 個のボタンが光っています。
ボタンには、1 から N までの番号がついています。
ボタン i が光っているときにそのボタンを押すと、ボタン i の明かりが消え、その後ボタン ai が光ります。
i=ai であることもあります。
光っていないボタンを押しても、何も起こりません。
最初、ボタン 1 が光っています。
高橋君は、ボタン 2 が光っている状態で、トレーニングをやめたいと思っています。
そのようなことは可能かどうか判定し、もし可能なら最低で何回ボタンを押す必要があるかを求めてください。

https://atcoder.jp/contests/abc065/tasks/abc065_b

解説

例によって問題文でわかりにくい印象ですね。

• N個の配列に番号が入っています。
• 番号は、配列の番号です。
• 最初の配列の参照は、1です。
• その番号の配列を参照します。
• 2が出た段階で終了です。
• 参照のために移動した回数を表示します。
• 2が出なかった場合は、-1を表示します。

入力例の解説

3
3
1
2

• 1行目 ボタンが3つあることを表しています。
• 2行目 ボタン1が3になってますので、ボタン3に行きます。
• 4行目 ボタン3が2なので終了。3行目には行きません。

出力例の解説

2

• 最初のボタン1の参照で1回。
• 次のボタン3の参照で２回になります。

私の回答

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

int main() {
    int N;
    cin >> N;
   
    vector<int> vec(N);

    for (int i = 0; i < N; i++) {
        cin >> vec.at(i);
    }

    int count = 0;
    int i = 1;

    while (1) {
        if (i == 2) {
            cout << count << endl;
            return 0;
        }

        i = vec.at(i - 1);
        count++;
 
        if (count >= N) {
            break;
        }
    }

    cout << -1 << endl;
}

配列は、通常0から始まることを教えられますが、この問題では1始まりで表示するので、実際のコードの中で間違わないようにしなければなりませんでした。

学んだこと

繰り返しで配列を順次参照する方法はわかっていましたが、今回のように飛び飛びで配列を参照をする方法がわかりませんでした。

まとめ

AtCoder Beginner Contest 065 B Trained?の問題を解いてみた解説と回答でした。

プログラミングは、知れば知るほど難しさを感じます。

以上です。
読んでいただきありがとうございました！