COMPETITIVE DEBUG STUDIO

TLEの原因を調査する方法

TLEは「Time Limit Exceeded」の略で、プログラムの実行時間が制限時間を超えた状態です。答えの考え方が合っていても、処理が重すぎるとTLEになります。

Competitive Debug Studioでは、タイムアウトしたケース、重い行、実行時間分析、ベンチマークを確認しながら、 TLEの原因を探せます。

まずTLE判定を確認する

実行・判定を行うと、右側の実行結果にAC・WA・TLE・REなどの判定が表示されます。 TLEと表示された場合は、プログラムの実行時間が設定された制限時間を超えています。

TLEでは、出力が間違っているというよりも、処理が終わらないことが問題になります。まずは、どの入力で時間がかかっているのかを確認します。

TLEが発生したケースは、失敗ケースとして保存されます。ケース詳細を開くと、入力やタイムアウト秒を確認できます。

小さい入力では通るのに、大きい入力でTLEになる場合は、ループ回数や探索範囲が大きすぎる可能性があります。

コードヒートマップでは、実行回数が多い行や時間がかかっている行を色で確認できます。 TLEの調査では、まず色が強く表示されている行を確認します。

特に、ループの内側で何度も実行されている処理は要注意です。二重ループ、三重ループ、全探索、リストの線形探索などがTLEの原因になりやすいです。

実行時間分析では、どの関数に時間がかかっているのかを確認できます。関数ごとの実行時間や割合を見ることで、 TLEの原因になっている処理を絞り込みやすくなります。

特に上位に表示されている関数は、実行時間の大部分を使っている可能性があります。その関数の中にあるループ、再帰、探索、重い計算を確認すると、改善すべき場所を見つけやすくなります。

例えば、特定の関数が実行時間のほとんどを占めている場合は、その関数の処理内容や呼び出し回数を見直すことで、 TLEを改善できる可能性があります。

ベンチマークでは、入力サイズを変えたときに実行時間がどのように伸びるかを確認できます。入力が少し増えただけで急激に時間が増える場合は、計算量が大きい可能性があります。

例えば、Nが2倍になったときに実行時間が約4倍になるなら、O(N²)に近い処理の可能性があります。 Nが2倍で8倍になるなら、O(N³)に近い処理を疑います。

TLEは、処理の回数が多すぎると発生します。まずは次のような原因を確認してください。

原因	確認すること
二重ループ・三重ループ	全探索している範囲が大きすぎないか確認する
毎回リストを探索している	`in list` や `list.index()` を何度も使っていないか確認する
ソートを何度もしている	ループの中で `sort()` や `sorted()` を呼んでいないか確認する
同じ計算を繰り返している	メモ化、累積和、前計算で減らせないか確認する
標準入力・出力が遅い	`input()` を大量に使っていないか、出力を1行ずつしすぎていないか確認する