2.06.計算量

APG4bの該当ページ

コメント

計算量を知らないとコンテスト中に合っていると思った解法がTLE(実行時間制限)になってしまうことがあります。 コードを書く前に制約をしっかり見て計算量が大丈夫かを見積もりましょう。

今回は演習問題に加えて僕が初めて参加したコンテストでの失敗を見てみたいと思います。

問題¹

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

制約

• $2\le N\le 2\times {10}^5$
• $1\le A_i\le N$
• $1\le K\le {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\le K\le {10}^{18}$

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

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

演習問題

• EX21 - 計算量の見積もり

次回

次回はプログラミングを学ぶ上での一つの鬼門である再帰関数について学びます。理解をするのにかなり苦労すると思いますが、頑張ってください。 リンク

---

1. 問題のリンク D - Teleporter 時間があれば考えてみてください ↩

2. 提出へのリンク https://atcoder.jp/contests/abc167/submissions/13073325 ↩