問題を読み、コードを書き、入力例で確認し、全部OKだった。
意気揚々と提出したら 残酷な「TLE」 。
これ通らないの！？ どうしよう・・・。
そんな時の対処法をお伝えします。
なお、この記事は初心者～灰色の方向けに書いていますので、茶色以上の人には当たり前に感じることが多いと思います。
また、難易度が高めの問題で起こりがちなTLEも書きません。
茶色以上の人は勝手に頑張ってくれ。
そもそもTLEとは
TLEはTime Limit Exceeded(実行制限時間超過)の意味です。
問題ページの左上にちっちゃーく実行制限時間2secと書いていますね？
ほとんどの問題は2秒以内に処理を終わらせることができないと正解となりません。
そもそも計算量とは？
ここから計算量がどうだこうだという話をしますので、先に計算量とは何かを説明します。
計算量は要するに計算の回数です。
1+1の計算は1回で済みます。
1~100までの和を求めるなら1+2をして、その結果に3を足して、その結果に4を足して、...とするので100回計算が必要です。
1*1+1*2+1*3+...+1*100+2*1+2*2+2*3+...+2*100+...+100*100を計算するなら100*100=10000回計算が必要です。
競技プログラミングではこの計算量というものをO(なんちゃら)で表します。解説でも「この解法の計算量はO(N)です」というような書き方がされています。
これは「ランダウのO」とか「ランダウの記号」と呼ばれます。きちんと説明するとそこそこややこしいので、ざっくりO(計算回数)だと思ってください。
1+1 → O(1)
1~Nまでの和 → O(N)
1*1+1*2+...+1*N+2*1+2*2+2*3+...+2*N+...+N*N → O(N^2)
となります。(^2は二乗の意味です)
pythonの場合、2秒以内にだいたい10^5回、頑張って10^6回位の計算ができます。(C++だと10^8回位です。つよい)
制約が1≤N≤10^5の問題があったとして、あなたの書いたコードの計算量が
O(N)=最大10^5回→実行制限時間に間に合う
O(N^2)=最大10^10回→間に合わないのでなにか工夫が必要
ということになります。
計算量の確認
そもそも書いたコードの処理が実行制限時間に間に合う計算量になっているか？確認しましょう。
全体の計算量を見積もる
1~Nまでの和を計算します。
以下のコードの場合、計算量はいくらになるでしょうか？
ans=0
for i in range(1,N+1):
ans+=i
print(ans)
i=1,2,3,...,Nまで一個一個足し合わせて最後に値を出力していますね。
これだとN回の足し算があるのでO(N)になります。制約がN≤10^5くらいなら間に合いますが、N≤10^10なら間に合いません。
1~Nまでの和は公式を使うとN(N+1)/2でも表せます。こちらを使うとコードはこうなります。
ans=N*(N+1)//2
print(ans)
これは一回しか計算していませんのでO(1)です。こちらであれば制約がN≤10^10だったとしても間に合いますね。
このように全体の計算量を見積もって、明らかに計算量が多いという場合はコードを工夫しましょう。
慣れて来るとコードを書く前に頭の中で計算量を考えて、この解法なら間に合う、間に合わないというのが判断できます。
1行で書けるのに時間がかかる操作
ここからはコードは1行なのに中身では計算量の大きい操作を説明します。
これがあるだけで計算量が爆増するから気をつけて！
・リストの末尾以外から一個取り出し(pop(x)：O(N))
A=[1,2,3]
x=A.pop(0)
リストの先頭「1」を取り出します。(代入して削除)
これが意外と時間がかかります。具体的にはリストAの長さがNとしてO(N)。
途中の要素を取り出す場合も同じです。何度も要素を取り出しているとTLEしちゃいますね。
ただし末尾から取り出す場合(.pop())だけはO(1)で済みます。
・リストの要素を削除(remove(x)：O(N))
A=[1,2,3]
A.remove(2)
リストの要素「2」を削除します。
これもO(N)です。これができたら楽に解ける問題は多いのですが・・・。
・リストの末尾以外に要素を追加(insert(i,x)：O(N))
A=[1,2,3]
A.insert(1,5)
リストの1番目に「5」を追加します。
これもO(N)です。
ただし末尾への追加(.append)はO(1)でできます。
まとめると
リストの末尾以外に何かするな
となります。
・末尾から取り出し(pop())
・末尾へ追加(append(x))
この二つ以外を使うとだいたいTLEします。
どうしてもリスト先頭に対する操作が必要！という場合はdequeが使えます。
詳細は以下の問題、解説を参考にしてください。
【問題】
【解説】
・ソート(sort()：O(NlogN))
A=[3,1,2]
A.sort()
リストを昇順に並び替えします。
計算量はO(NlogN)です。いきなりlogが出てきた！とビビりますが、Nが大きくてもlogNは大した大きさでないので、O(Nちょっと)と覚えればいいです。
ソートが必要な問題は多いですが、多くても3回くらいにしておきましょう。N回ソートするコードとか書くとだいたいTLEします。
・最大値、最小値を探す(max(A),min(A)：O(N))
A=[3,1,2]
x=max(A)
y=min(A)
リストから最大値、最小値を探します
計算量はO(N)です。リストの要素を一個一個確認しているイメージですね。
これも何回もやっているとTLEします。N≤1000くらいなら何度もできますが、Nが大きめのときは回数を意識しましょう。
・要素が含まれるか確認する(in：O(N))
A=[1,2,3]
if 1 in A:
print("あります")
「in」を使うとリストや文字列の中に指定した要素があるかを確認できます。
便利ですが、これもO(N)です。リストや文字列の長さをよく考えてから使いましょう。
計算量は問題なさそうという場合
計算量見積もりしても計算回数が10^6回以下。なのにやっぱりTLEする！という場合はどうするか説明します。
桁数の大きな計算をしていないか確認
例えば以下の問題。
A^BとA^Cどちらが大きいか比較してください。
2≤A,B,C≤1000
ふむふむ計算しようとコードを書いてみます。
if A**B<A**C:
なんたらかんたら
計算は1回しかしていないからO(1)になりますね。(厳密に言うとA^B,A^Cで2回ですが・・・)
なのにこれはTLEします。 なぜ！
この計算、最大でどれくらいの桁数になるでしょうか。
A,Bがともに最大の1000だった場合、1000^1000になりますね。つまり3001桁になります。参考までに無量大数は69桁です。
いくらコンピューターといえど、ここまで大きな数の計算は時間がかかりますし、CPUが可哀想ですね。
pythonでの計算は頑張っても20桁くらいが限界ですから、それに収まるように工夫しましょう。
この問題であれば単純にBとCの大きさを比べればOKですね。
長い数字を扱うときは文字列としてしまうというテクニックがあります。
他に「答えを1000000007で割った余りを出力せよ」などの問題は答えを出力する直前に余りを取るのではなく、計算の都度余りをとることで計算時の桁数を小さくできます。
無限ループしていないか確認
whileで同じところを延々ぐるぐるしているとか、そういったケースが無いか確認しましょう。
よくあるのは制約の端っこのケースです。例えば1≤N≤10^5であればN=1のケースを確認しましょう。
操作の計算量をググる
コード内で使っている操作の計算量を片っ端からググりましょう。
「pop 計算量」「append 計算量」「dict 計算量」...というような感じです。
その問題を解く時だけでなく、後々他の問題を解くときにも「あーこの操作の計算量、そういえばO(N)だったなー」と考えられるようにもなります。
めんどくさいけど頑張りましょう。
PyPyで提出する
コードは見直した、計算量はギリギリ間に合いそうなくらい、なのにTLEする！という場合。
PyPyで提出する方法があります。
PyPyはプログラミング言語の一種で、pythonとほぼ同じ書き方でpythonより高速に動作します。
pythonは2秒以内にだいたい10^6回位の計算ができますが、PyPyなら10^8回位計算ができます。C++と同程度です。
使い方は簡単で、pythonでコードを書き、提出時に「言語：PyPy3」を選ぶだけです。
じゃあ最初からPyPyで提出すればよくね？ということなのですが・・・まあ99%そのとおりです。
ごく稀にpythonだと動作するけどPyPyだとエラーになる操作とか、PyPyのほうが遅い操作というのがあります。
不安な場合は「コードテスト」画面でPyPyでエラーなどでないか実験してみましょう。
なにをどうしても無理
いやもうこの問題C++しか解けねえだろ！！
まじクソ運営のクソ問題がよ！！！！
はい、落ち着いてください。
コンテストが終わったら「提出」からpythonでACしている人を探してください。
ね？いっぱいいるでしょ？
他の人の書いたコードをしっかり見て、自分のコードと見比べて、何が間違っていたのか確認しましょう。
正解を出すことは大切ですが、何が間違っていたのかを確認することは同じくらい大切です。
皆様も良い競プロライフを！