AtCoder失敗リスト
MLE
与えられたH×W=10^6の文字列からグラフを構築してTLEやMLE PAST5H TLE
全探索の 「次に訪問する頂点」をリストで持ってTLE 集合に変えたらAC ABC184E 前処理をして高速化、2つ前処理するものがあるのに片方しかしておらずTLE、計算量オーダーを勘違いして場当たり的な定数倍高速化してしまう PAST4K 最大スコアを計算するためのmaxが一つループの内側に入ってた(TLE) ABC175D 前処理で累乗テーブル作成: a ** xにしてて余りを取る前に桁が爆発 / pow(a, x, MOD)にしてTLE / これは対数オーダーなのでテーブルを作るときは前の値の再利用で定数オーダーにすべきだった ARC106D 深さ優先探索でvisit(next)とすべきところをvisit(pos)している(手元テストすれば気づいたはず)
深さ優先探索を関数の再帰呼び出しで実装したがPyPyは関数呼び出しが遅い、回数が10^6オーダーだと厳しい、whileループに書き換え PAST5H 文字列をループの中で結合してTLE、リストにappendしておき、最後にjoinする PAST5H 小さな行列の掛け算を繰り返す場合、Numpyを使ってもオーバーヘッドが大きくてメリット少ない ABC189E すべての辺のコストが1なのにダイクストラを使ってTLE、BFSに変えたらAC ABC190E 桁DPにおいて「既に出てきた数字が何か」を覚えておこうとして2^16のテーブルを作ってTLE、桁DPのlessでは必ず全種類の数字が出てくるので「いくつが既出か」だけでよい ABC194F RE
Nが10^5の区間DP, 10^10のメモリを確保する
「DPでやっても間に合わない」と気づくべきだった AGC048B AOJと僕の手元のPythonではダメで、AtCoderのコードテストだと10^6でもOKなので多分処理系のコンパイルオプションによる
WA
連結成分のサイズが2以上になるのは一つだけだと思い込んでたこと。実際には複数ある ARC107C 複数のものの関係を問う問題でN=1がコーナーケース ARC106C 負の辺を入れてはいけない最小費用流ライブラリに負の辺を入れた PAST3O ダイクストラ法にも負の辺を入れてはいけない
for文なのにポインタをインクリメントした時にcontinue ABC178F 一部の頂点が到達可能かが知りたいのにダイクストラの結果に対してINFが含まれるかチェックして「すべての頂点が到達可能か」を調べてしまっていた ABC190E 二分探索でrightの初期値が条件を満たしてる ABC192D WAになって、バグを直して2回目の提出をする時に「バグを直して、軽く高速化」ってやって、その高速化でバグを入れてる。バグが直ってないと勘違いして混乱 ABC192F 数学的にO(1)の解法があるが浮動小数点数の誤差がある、O(1)の解法にこだわってしまったが、整数にして二分探索でO(logN)が正解 ABC191D