2.06.計算量

APG4bの該当ページ

高橋王国には \(N\) 個の町があります。町は \(1\) から \(N\) まで番号が振られています。
それぞれの町にはテレポーターが \(1\)台ずつ設置されています。町 \(i\) (\(1 \leq i \leq N\)) のテレポーターの転送先は町 \(A_i\) です。
高橋王は正の整数 \(K\) が好きです。わがままな高橋王は、町 \(1\) から出発してテレポーターをちょうど \(K\) 回使うと、どの町に到着するかが知りたいです。
高橋王のために、これを求めるプログラムを作成してください。

制約

\(2 \leq N \leq 2 \times 10^5\)
\(1 \leq A_i \leq N\)
\(1 \leq K \leq 10^{18}\)

下のコードが僕が提出したものです。(分かりやすいように一部変えています)

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

int main {
    int N, K;
    cin >> N >> K;
    vector<int> tel(N); // 次に移動する場所
    for (int i = 0; i < N; i++) {
        cin >> tel[i];
    }
    int count = 0; // 今何回テレポーターを使ったか
    int now = 1; // 今どこにいるか
    while (count < K) { // countがK未満の時ずっと繰り返す
        now -= 1;
      now = tel[now];
      count++;
    }
    cout << now << endl;
}

さて、僕がこのコードを提出したところ TLE (実行時間制限超過) になってしまいました²。何故でしょう？

答え

上のコードだと while 文のループが \(K\) 回行われているので、計算量は \(O(K)\) であると分かります。しかし、制約を見てみると

\(1 \leq K \leq 10^{18}\)

であり、 \(O(K)\) は最悪で \(10^{18}\) 回の計算をすることになってしまうので、到底間に合いません。もう少し効率の良いプログラムを書く必要があります。

このように計算量を意識しないと実行時間制限に引っかかってしまい問題を正解することができないことがあるので、問題を解くときには必ず計算量を意識しましょう。

演習問題

EX21 - 計算量の見積もり

次回

今回で第2章は終わりです。お疲れさまでした！！！かなり発展的な内容も多かったので1度では理解しきれないかもしれません。
記事を何度も見返したり、問題を解いたりして知識を定着させましょう。

さて、次は 3.00.第3章についてを見てください。

問題のリンク: D - Teleporter 時間があれば考えてみてください。 ↩
提出へのリンク: https://atcoder.jp/contests/abc167/submissions/13073325 ↩

2.06.計算量

コメント

問題¹

制約

演習問題

次回

2.06.計算量

コメント

問題1

制約

演習問題

次回

問題¹