※ここに書かれた仕様は AtCoder が公式に保証していないものを含むので、告知なしで変わる可能性があります。
AtCoder のコンテストにおける TLE (実行時間制限超過) は、以下の 2 種類に分けることができます。1
- A, 実行時間制限を超えたが、実行打切りは発生していない TLE
- B, 実行時間制限を超え、実行打切りが発生した TLE
ジャッジシステムによる実行打切りは、実行時間制限の約 1.1 倍経過時に行われるため、その提出の実行時間を見ることでどちらであるかを大体判別できます。
例えば実行時間制限が 2 秒の場合は、約 2200 ms で打切られるので、実行時間が「2055 ms」ならば A 、「2204 ms」ならば B の可能性が高いです。
どちらであるかによって優先してとるべき対策が変わると私は考えており、それらについて紹介します。
A の場合: 細かい定数倍高速化
あと 1 割程度実行時間を早めれば確実に間に合います。
判定の内訳が AC と TLE のみならば、AC を取れる可能性が高いです。
この場合は、以下のような細かい定数倍高速化を試すのがおすすめです。
- 不必要な配列などを作成・コピー等していないか見直す
- 多次元配列を 1 次元に圧縮して扱う
- 「(言語名) 競プロ 高速化」で検索して出てくることを試す
- (Python / PyPy の場合) 巨大な整数 ($> {10}^{18}$) の使用を避ける
- (PyPy の場合) Python → PyPy で遅くなるパターン (例: 深めの再帰 DFS 実行) にあたっていないか調べ、修正するか Python3 で提出する
- より速い言語で書き直す
もちろん、これらをしてもギリギリ間に合わない場合もあります。
その場合は、多分時間計算量が想定解よりも悪いので、後述の「計算量の確認とアルゴリズムの再検討」を試すことになります。
B の場合: 計算量の確認とアルゴリズムの再検討
実行時間に関して、制限の約 1.1 倍を超過している以外の情報がありません。
あと数秒で終わるかもしれないし、もしくは何年かかっても終わらないコードであるのかもしれません。
この場合は、コードの時間計算量をもう一度見直して適切か ( $O$ 記法の中の式に代入した結果が ${10}^{8}$ 程度以下に収まっているか) を確認し、不適切な場合はアルゴリズムの再検討を含めた修正をするのがおすすめです。
以下は計算量確認時に間違いがちな点です。
- $O(1)$ の処理だと思っている部分でそうでないこと (例: 巨大な配列の作成・コピー、重めの「$O (\log N)$」の操作) をしていないか
- 一見多重ループだが計算量が軽いアルゴリズム (例: 尺取り法) の実装が適切か
- (PyPy の場合) Python → PyPy で計算量が悪化し得る書き方 (例: 文字列の末尾 1 文字追加の繰り返し2) をしていないか
もちろん、計算量が想定解通りであるにもかかわらず B に該当している場合もあります。
その場合は、高速化できる余地が 1 割以上存在することになるので、前述の「細かい定数倍高速化」を試すことになります。
コードテストの活用
「実行時間が制限の 1.1 倍弱くらいなので、A, B どちらかわからない」「B であるが計算量に問題はないはず」という場合は、時間のかかりそうなケース (全部の変数が制約上限ギリギリなど) を手動で作成し、「コードテスト」タブ3で試すのが有用です。
コードテストでは実行打切りが 10 秒経過時であるため、あとどのくらい早めればよいのかについて、提出の実行時間を見るよりも多くの情報を得られます。
(自分の手元で試して時間を測ることもできますが、AtCoder のジャッジと環境が異なるため単純比較できないことが多いです。)
-
ここではジャッジサーバー上でコードを 1 回だけ実行しているかのように書いていますが、正確には最大 3 回実行しています (https://twitter.com/chokudai/status/1247452767670505474 )。 ↩
-
「コードテスト」タブはコンテストごとに存在します。ここでリンクしたのは ARC164 のものです。 ↩