0Pricing
Competitive Programming Academy · レッスン

TLE が起きる理由と見つけ方

予算を使い果たす隠れたループを見つけます

「TLE が起きる理由と見つけ方」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン4/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。

TLE 判定を知る

TLE は Time Limit Exceeded の略で、コードは正しいものの遅すぎることを意味します。コンテストで初心者が最もよくぶつかる壁です。⏰

よくある原因

TLE のほとんどは、n に対して計算量が高すぎることが原因です。n = 10^6 で O(n^2) の方針を使えば、毎回必ず時間予算を超えてしまいます。

隠れた内側のループ

最も気付きにくい TLE の原因は、見落としていたループです。ループ内のメソッド呼び出し自体がループしていると、O(n) が O(n^2) になることがあります。

for x in arr:
    if x in seen_list:
        ...

リストでの所属判定

リストで x in を確認する処理は、1回あたり O(n) です。ループ内で行うと二次時間になります。所属判定には set を使って O(1) にしてください。

seen = set()
if x in seen:
    ...

ループ内で文字列を構築する

ループ内で plus を使って連結すると、毎回文字列全体がコピーされます。この隠れたコストは O(n^2) になるため、断片を集めて最後に1回だけ join してください。

parts = []
parts.append(s)
result = "".join(parts)

入力の遅さも影響する

大量の入力を通常の input() で読み込むと、それだけで TLE になることがあります。大きなテストでは、sys.stdin を使ってデータ全体を素早く読み込んでください。

import sys
data = sys.stdin.read().split()

再計算とキャッシュ

同じ値を何度も再計算すると時間を無駄にします。累積和のような結果をキャッシュすれば、繰り返していた O(n) の処理を O(1) にできます。

提出前に見積もる

判定される前に TLE を見抜きましょう。計算量を n に適用し、10^8 と比較してください。超えるなら、提出前に設計を見直します。

ボトルネックを見つける

TLE になったら、最も深い入れ子のループを見つけ、実際に何回実行されるのかを考えてください。ほとんどの場合、そこから処理時間が漏れています。

計算量を下げる

TLE の解決には、細かな調整ではなく、通常はよりよいアルゴリズムが必要です。入れ子の走査を、ソート、ハッシュマップ、または尺取り法に置き換えてください。

定数倍の調整は最後にする

制限時間を少し超える程度なら、高速な I/O などの小さな定数倍の改善で救える場合があります。ただし、まず Big-O 自体が適切かを確認してください。

確認問題

この隠れた処理速度低下の原因を診断してみましょう。

復習

TLE は正しいものの遅すぎることを意味します。隠れたループを探し、リストを set に置き換え、文字列は最後に1回だけ結合し、Big-O を下げましょう。まず見積もってから提出してください。🛠️

よくある質問

「TLE が起きる理由と見つけ方」レッスンは無料ですか？

はい。「TLE が起きる理由と見つけ方」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。

「TLE が起きる理由と見つけ方」で何を学びますか？

予算を使い果たす隠れたループを見つけます ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Competitive Programming Academyを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン4/4です。

「TLE が起きる理由と見つけ方」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCompetitive Programming Academyレッスンでコードを書いて実行できますか？

はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. Big-O で演算回数を数える
  2. 10^8 の経験則
  3. 制約を読み、計算量を選ぶ
  4. TLE が起きる理由と見つけ方
← Competitive Programming Academyに戻る