AtCoder失敗リスト

MLE

• 与えられたH×W=10^6の文字列からグラフを構築してTLEやMLE PAST5H TLE
• 全探索の 「次に訪問する頂点」をリストで持ってTLE 集合に変えたらAC ABC184E
• ダイクストラの実装でvisitedをつけ忘れ PAST4J
• 前処理をして高速化、2つ前処理するものがあるのに片方しかしておらずTLE、計算量オーダーを勘違いして場当たり的な定数倍高速化してしまう PAST4K
• 最大スコアを計算するためのmaxが一つループの内側に入ってた(TLE) ABC175D
• 前処理で累乗テーブル作成: a ** xにしてて余りを取る前に桁が爆発 / pow(a, x, MOD)にしてTLE / これは対数オーダーなのでテーブルを作るときは前の値の再利用で定数オーダーにすべきだった ARC106D
• 定数オーダーだが、その定数が10^9 ABC164D
• 素因数分解TLE 4)) でするに置き換えたらAC
• 深さ優先探索で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のメモリを確保する
  • RE: MemoryError AtCoderのPythonでMemoryErrorを出すとREになる
    • 「DPでやっても間に合わない」と気づくべきだった AGC048B
  • AC: 累積和で最内ループを潰しAC ABC179D
• 深さが10 ** 5の木をPythonで深さ優先探索したらSegFaultでRE AOJ GRL_5_C
  • AOJと僕の手元のPythonではダメで、AtCoderのコードテストだと10^6でもOKなので多分処理系のコンパイルオプションによる

WA

• 連結成分のサイズが2以上になるのは一つだけだと思い込んでたこと。実際には複数ある ARC107C
• 複数のものの関係を問う問題でN=1がコーナーケース ARC106C
• INFを10**10にしてて、超える値がある AGC044A
• 座標圧縮したのに元の座標でアクセスしてた PAST2N
• 負の辺を入れてはいけない最小費用流ライブラリに負の辺を入れた　PAST3O
  • ダイクストラ法にも負の辺を入れてはいけない
• 頂点を塗るのか辺を塗るのかを勘違いしていて、1ズレるバグ PAST4M
• for文なのにポインタをインクリメントした時にcontinue ABC178F
• 一部の頂点が到達可能かが知りたいのにダイクストラの結果に対してINFが含まれるかチェックして「すべての頂点が到達可能か」を調べてしまっていた　ABC190E
• 二分探索でrightの初期値が条件を満たしてる ABC192D
• WAになって、バグを直して2回目の提出をする時に「バグを直して、軽く高速化」ってやって、その高速化でバグを入れてる。バグが直ってないと勘違いして混乱 ABC192F
• 数学的にO(1)の解法があるが浮動小数点数の誤差がある、O(1)の解法にこだわってしまったが、整数にして二分探索でO(logN)が正解　ABC191D