この記事は、競プロ Advent Calendar 2021 3 日目の記事です。
飛ばしていい雑談
現在水色コーダーのH20と申します。
2020年の5月よりAtcoderのコンテストに参加してから、競技プログラミングという沼にハマり続け、参加回数はすでに80回を超えました。
沼にハマり続けるのは何も競技プログラミングだけに限りません。WA(不正解)とTLE (実行時間超過)の沼にもハマり続けました。
何度「解法は合ってた、解けてたはずなのに！」という後悔と、「ぎりぎりバグを見つけて通せた！」という喜びがあったでしょうか1。
実装ミスは特にこの半年の上がっては下がりを繰り返す気にくわないほど横ばいなレート推移となる一因です2。
とにかく今悩んでいる問題の AC (正解)を目指す。
解法は合ってるはずなのに何故か提出するとWAになってしまう状況や、ペナの数はもう気にしないとにかくこの一問を解きたいという切羽つまった状況で、その問題を解ききるやるべき対策を自戒の意味を込めてまとめます。
0.まずは深呼吸しましょう
落ち着くことで急に閃くものがあるかもしれないです。
15秒使って5回くらい大きく息を吸って吐いてみて落ち着きましょう。
今がコンテスト中でなかったり、時間に余裕があるのであれば、e869120さんの以下の記事を読みましょう。
デバッグ力を高める！ ～5 年間の経験から学んだ、競プロ・アルゴリズム実装におけるバグ取りの戦略～
これからの記事はe869120さんの記事と内容が重複しています。またe869120さんの記事にあるような細かな戦略については記載していません。
コンテスト中に問題が解けず悩んでいる際に、短い時間でチェックする一覧として利用できる形式でまとめまています。
じっくり読むような余裕がなく、（Pythonに特化した内容を多く含むので）特にPythonを使用して提出している方はそのまま下に進んでみていください。
1.目次
起きている現象について内容を分割しています。
※あくまで私の経験則による主観的な対策で、内容の正確性が欠けることはご了承ください。
人によっては間違っていると感じる部分もあることと思います。
合わないと思った箇所は、書かれていることを無視してください。
- サンプルが通らない
- 提出するとサンプル含めて全てでWAが出た
- 最大ケースがサンプルなどで判明している状態で、最大ケースだとTLEするか微妙なライン
- 提出するとサンプル以外の大半でWAが出た
- 解法を思いついたが提出するとTLEしそう
- 想定解であるはずだが、PythonなのでTLEしてしまった
- 提出するとTLEが起きた
- 提出すると1つか2つWAとなる
- 提出すると1つか2つTLEする
- 提出するとRE(ランタイムエラー)が起きた
- 提出するとMLE（メモリオーバー）が起きた
- 提出するとWAもREもTLEも起きた
- 実行するとエラーが発生したり無限ループして正常に終わらない
- 他人のライブラリを流用したがうまくいかない
- 過去にその問題の類題を見つけた気がする
- 思いついた解法が制約よりもかなり余裕があり、提出するとWA
- 思いついた解法が複雑すぎて違う気がする
- 問題文の意味が分からない
- 解き方が分からない
- 通らないかもしれない
- 分かんないからTwitterを眺めたい書き込みたい
- もう諦めちゃった
- 終わりに
【サンプルが通らない】
問題文や制約の誤読をしていないかもう一度問題文と制約を一文逃さず読み直す
処理の順序を間違えてないかコードと見比べてチェック
記号関連は誤読しやすい
切り捨てとなる$\lfloor x \rfloor$や同じ意味をもつガウス記号$[x]$と、切り上げ$\lceil x \rceil$ の見た目は凄く似てるので注意条件を満たす回答が複数ありそのどれを出力してもよい場合で、サンプルと合っていないだけではないか
グラフ問題については サンプルをグラフのビジュアライザでチェックしてみてもよい
文中に記載された有向グラフか無向グラフであるかの情報の読み飛ばし、読み誤りはよくある数列が入力にある場合について、ソートされた数列と勘違いしているが、実際はランダムな順序だということはないか
サンプルの2個目以降から合わなくなる原因の一種、ソートしようサンプルが通ってない状況で提出してもいいが、だいたいの場合において無意味にWAを重ねるだけ
自身の開発環境がおかしいせいからWAになってるだけで提出するとACするかも、なんて期待は提出する前に捨てた方がよい提出するとサンプル以外の大半でWAが出たの内容をチェック
【提出するとサンプル含めて全てでWAが出た】
コードのコピペミスではないか
提出する言語を誤っていないか
デバッグ文字を埋め込んだままにしていないか
答えとなる値を出力する前に
YesやNoを出力する必要はないか配列の出力である場合に、その要素数を先頭に出力する必要があったりはしないか
まずこれらの場合についてはAtCoder Easy Testを導入し、次回から『Test & Submit』による提出を一般的な提出とした方がよい、無駄なWAが減らせる
条件を満たす回答が複数ある場合などで、正しい解答に対して誤っていると表示されるケースを許容しないといけないが、それが一切苦にならないほど有用なツール
【提出するとサンプル以外の大半でWAが出た】
制約の誤読により、最大値や最小値に対する考慮漏れはないか
以上、以下、未満、より大きいの条件を誤っていないか
ifとelseのネストは正しいか、elseを書いていないせいで余計な処理が行われていないか小さいテストケースを自分で作ってみて、おかしくなるパターンがないかチェックしてみる
開発環境でデバッグを行い、くさいところで1行1行動作を確認する
まだデバッグ環境を作っていない場合はVsCodeのデバッグは構築が楽だし無料なのでお勧め
（方法については、競技プログラミングを始めたばかりの人に伝えたいことの5日目の記事がちょうどよさそうなので、それにリンクを張る予定です）イテレーターの範囲や変数名に誤りはないか
リストのアクセスを1行で複雑に書いているなら処理を2行に分割してみる、誤った参照や抜け漏れも見つかりやすくなる
変数を別の用途の変数で上書きしていないか
forのイテレーターや、入力要素などの上書きはやりがちだし気づきにくい
Pythonだとエラーとして出にくいので、本当にやりがち制約として同じ値が複数存在することがある場合、その考慮がなされたコードになっているか
bisectやdeque関連のleft,rightの違いには気を付ける
max,minの制御は正しいか
inf(無限大)扱いした値よりも大きな値が結果となることはないか
Answerとする値の初期値としての値は正しいか、もっと大きくしたり小さくしてみる必要はないか二分探索であれば、上限と下限を想定よりも大きくとってみる
下限についてマイナスな値にしてみるとかmodをとった上で提出しているか、modの値を手打ちしてタイポしていないか
abs(絶対値)を考えないといけない箇所で漏れはないか
制限時間に余裕がある場合は全体的な要素や処理を大き目にとってみてもよい
小数が絡む問題は小数点誤差でWAとなる可能性が高い
decimalを使ったり、整数に出来る部分があれば整数に変換して処理したりする
小数点を切り捨ててよい場合は切り捨て除算を使用する（切り上げも同様に切り捨て除算を応用して切り上げる）
小数点の入力をfloatで受け取った段階でWAとなる問題も過去にあるので文字列で受け取る必要があればそうすること小数点誤差が発生する処理を作った場合について、誤差許容範囲を狭めるのとは逆に、許容範囲を広くとることでWAがとれることもある
解決できてないまま同じ内容のコードを二度投げるのは無駄
狂気とは即ち、同じことを繰り返し行い、違う結果を期待すること （アインシュタインの言葉ではないらしい）
【最大ケースがサンプルなどで判明している状態で、最大ケースだとTLEするか微妙なライン】
手元の環境で結果が出力されるまでに時間があり、TLEするかもと不安な時は、Atcoderにあるコードテストで実行してみる
時間がないときは、勢いで提出してみるのも吉
【解法を思いついたが、提出するとTLEしそう】
実行時間制限: 2 secかチェック
2secじゃない時に強調表示してくれるTime Limit Emphasizerを導入するのはよい対策どこかに省略できる処理や打ち切ってよい処理がないかチェック
気づいたアイデアは脳の片隅に溜めておいて、後で試しに提出してみるのもあり
解法が二分探索の場合について、想像よりもに早く実行が終わることはしばしば、そのまま提出してみてもいいかも
$O(N!)$ の処理もそこそこ早い
上限が小さい制約があればその制約をオーダーを中心に処理を考えてみる
【想定解であるはずだが、PythonなのでTLEしてしまった】
まずは、本当にPythonなので起きており、C++だったら解けたはずの解法であるか切り分け
DPでは累積和でまとめられる処理をまとめていないせいでTLEしている可能性がある無駄に重い処理を作り上げていないかチェックする
多次元の配列によるアクセスは遅いため、二次元リスト、三次元リストは一次元リストのに書き直す
LIST[y][x]としている箇所について配列のサイズが分かっている場合はLIST[y*W+x]といったように1次元に落としてしまうPypyで提出していて、Pythonによる提出を試していない場合、Pythonの提出なら間に合うことも稀にある
dfsやdecimal、文字列操作の多いコードで起きるdfsの場合、dequeを使った処理に置き換えてみる
置き換えは結構に簡単にできるため、焦らず行う
それでも間に合わないならメモ化再帰する問題かもしれないfloat('inf')は関数呼び出しなので処理は結構重い、比較処理もちょっと重いことに気を付ける
float('inf')はループする処理で毎回呼び出さずinf = float('inf')や10**18とかにして実行する別の言語で解くのも一つの手だが、いきなり競プロに慣れていない言語で取り掛かってもうまくいく可能性は低い
アルゴ式とかで最低限の慣れと実行環境の準備は必要
【提出するとRE(ランタイムエラー)が起きた】
0除算、配列の要素外にアクセス、
Noneの考慮漏れがないかチェック縦横の$W, H$ について逆に処理していないかチェック
バグの原因が不明で
Yes/No回答の場合try catchで例外をキャッチしてNoと出力するのも一つの手dfsの場合、
おまじないのsys.setrecursionlimit(10 ** 9)はちゃんと書いているかチェック
【提出するとTLEが起きた】
TLEが起きた場合、最終的な結果が出るのは数十秒先とか、実行の途中結果を眺めているのは時間の無駄
制約を再チェック
制約で $ 1 \le M \le 10^{9} $ に対してL = [[0]*2 for _ in range(M)]みたいな感じのことをすると、MLEではなく、TLEする何か無駄なループや無駄な配列を作ったりはしていないかチェック
TLEしたテストケースが多いときに、処理を半分の時間へ改善するような中途半端な改善方法は徒労に終わる可能性が高い
想定解は大抵短くスマートなので、中途半端な改善でACできることはC++ならまだしもPythonでは起きにくい
$O(N^3)$を$O(N^2)$に、$O(N^2)$の処理を$O(NlogN)$や$O(N)$に改善する方法はないか検討するリストの足し算や文字列の変換処理は遅いのでそういった処理がないかチェック
累積和やいもす法、セグ木、平衡二分探索木で省略できる処理はないか考える
メモ化再帰に置き換えたり、優先度付きキューが使える部分はないか
なんらかのライブラリを使っている場合は、そのライブラリ内の処理をチェック
$O(1)$と思っていた処理が$O(N)$ や$O(N^2)$なんて時もある
【提出すると1つか2つWAとなる】
疑うべきはコーナーケース、問題文や制約などを見直す
特に$0$とか$1$を含むパターンはちゃんと試す
小さいパターンの結果が頭の検算と合うか試してみる最大ケースの漏れはないか
複数パターンの提出を試してWAとなる数が異なる場合、その二つの処理を順次実行するコードにしてもよいかも
ですが、うまくいく可能性は低め...嘘解法で頑張ってみるのも手だし、また改めて考え直すのも手
小さなテストケースの場合は愚直解をする処理に飛ぶようにしてみるというテクニックもある
【提出すると1つか2つTLEする】
テストケースをエスパーして回答を埋め込みをするのもあり
実行時間が最悪となるパターンを思いついてみる
制約上で最大となる典型的なテストケースは基本含まれている
約数を使う解法なら高度合成数の$735,134,400$で出来上がる解を埋め込んでみるとか特定条件で無限ループに陥ることがないかチェック
試したことはないが、時間を図って1.8secになったら処理を抜けるなんてのもありかも実は想定解からかけ離れてる場合がある
半分全列挙を必要とする問題でやられたことがある、意地悪いテストケースの罠に注意
閃きを必要としないABC E以降の問題で、なんらかの高等アルゴリズムや高等技術を使わないで解ける問題が今までにあったか考えてみるギリギリでTLEしているなら、同じコードをそのまま何度か提出したら、一回は通ることはある（参考提出1、参考提出2）
あんまりやらない方がいいけどあるにはある、本当にギリギリで終わっているなら試す価値はある
【提出するとMLE（メモリオーバー）が起きた】
制約を再チェック
制約で $ 1 \le M \le 10^{9} $ に対してL = [0]*Mみたいな感じのことをするとMLEする
やりたいことに応じて、座標圧縮したり、setやdefaultdictを使用するメモリ制限: 1024MBフルで使う問題はそうない
メモリ制限: 256MBの時に、制限フルに使うCheckerがあったが1024MBフルで使うような問題は記憶にはない
何か無駄なことをやっているためどうにかしてメモリを節約しよう
【提出するとWAもREもTLEも起きた】
ある意味レア
一つずつ解決していく
ものによっては小さなミス一つ直すだけで一気に解決する可能性もある
無駄な処理が紛れ込んでいないかチェックコンテスト後、クラスのみんなに自慢しよう
【実行するとエラーが発生したり無限ループして正常に終わらない】
基本的にはケアレスミスなので落ち着いて対処
入力処理が誤っていないか
無限ループなら条件を見直す、再帰関数を使っている場合についてreturnの漏れはないか
変数を上書きしていないか
型の誤りではないか
特に整数型と文字列型はしっかり変換する
【他人のライブラリを流用したがうまくいかない】
流用は上から下まで正確にコピーしているかチェックする
流用したライブラリや処理が完全に誤っているということはめったにないが、短いケースで確認してみてもよい
誤っていればかなり不運、外れくじを引いたと思って別の流用先を探す他人のライブラリの使い方が誤っているパターンがある
セグメントツリーは基本的には半開区間だったりするので注意
転倒数は$0 ～ N-1 $でなく、$1～N$番目の転倒数を数えるライブラリが多い
使い方の問題で誤ることはよくあるため、流用元の情報はよく読む
変数の上書きをしてしまっている可能性もあるかも
流用元の関数の戻り値が複数である場合もあるのでその場合は複数の変数に分けて受け取る
返却されるデータの型が想定している型と異なることもあるので、内容が理解しきれない場合は、デバッグ実行で型をチェックする他人のライブラリが誤ってはいるわけではないが、処理に改善できる余地があり、TLEしてしまうパターンがある
呼び出す処理のオーダーに着目して、重い処理がないかチェック
ワンライナーの転倒数のコードを流用した結果、処理が$O(N^2)$でTLEしたという経験がある、短いコードはちょっと注意
使い方を新たに検討してみる、流用したライブラリの処理をいじるなんて方法もあるが、諦めて他のライブラリを探すのも無難な対策
【過去にその問題の類題を見つけた気がする】
問題の内容が完全一致するパターンはあるにはあるが、かなり稀（約数の偶奇とOdd vs Even）
どちらの問題もちゃんと読み、違いがないかをちゃんと見つける
特に、最近出たyukicoderやICPC、コドフォの問題との類似問題は 何かしらの違いがあるはず
例：風船配りとProject Planning
（過去に直近のコンテストで類似問題が出たために予定されていたコンテストが取り消しになった例がある）似た問題を解いたことがあったので喜び勇んで同様の方法で解いてみた結果、WAとなることはある
いくつかの解法があるのでまずは類題の解説を読んで別解を確認してみる
今回の問題に活かせる部分があるかもしれないAtCoder上でいかにも類題な問題は、別の方法をとらないといけないか、その前の問題を応用して解く問題であるので、全く同じ解法で解けることはなさげ
別の方法をとらないといけない例：><と>< again
応用して解く例：LampとLamps
【問題文の意味が分からない】
ゆっくり落ち着いて読むこと、誤読や書いてないことを勝手に付け加えてしまっている可能性はないか
まず問題文が数学的な言い回しで分かりにくいだけで実際言っていることは簡単だったりする
$\sum$はfor文に置き換えて考えてみる
「任意の整数について」など言いまわしは分かりにくいけど、たいていの場合で「どんな整数についても」という意味に置き換えてよい3文字の掛かっている言葉が何かに注目する
対象の問題について質問が来てないかチェックする
集中してる時は全体公開の質問があることに気づかないことも
順位表を見て全体的に誤っている人が多ければ、質問を投げてみるべき、その解答がヒントになるかも
【解き方が分からない】
誤読していないかチェック
ひとまず愚直解を作ってみる
小さい値の入力をいくつか試して規則性を見つけてみたりできるDPの可能性はないか疑ってみる
気づいたところで解けないことは多いけれど…お気に入りやライバルにしている人が解いているならその人の得意な分野がなんであるか考えるという手がある
順位表を見てAC数が感覚よりも多いようなら、それは愚直答や、貪欲解、比較的簡単なアルゴリズムの応用である可能性が高い
ただやるだけのコードを作ったり、全探索、端から順に貪欲、二分探索、逆順、UnionFindなどよくあるパターンで当てはまるものはないか試してみる構築問題などで存在なしない場合は
-1を出力してくださいと書かれているけど、サンプルに-1の出力がない場合は、必ず存在する（-1を出力することがない）ことが多い
必ず存在すると仮定した場合で検討してみる
ひとまず作って提出してみる
そこから1WAとかなら、WAになったものが-1になるようなコーナーケースである可能性が高いあり得そうなアルゴリズムを口に出してみる
あのアルゴリズムはどこ？の内容をパラ読みしたり、上から順に目次を音読してみるとか最大値の最小化問題であれば、二分探索を試してみる
【思いついた解法が制約よりもかなり余裕があり、提出するとWA】
-
ABCの問題で、やたらと小さな制約が存在し、その制約を注目しないような解法は基本的には誤りと思った方がよい
競技プログラミングで解法を思いつくための典型的な考え方が参考になるはず
【思いついた解法が複雑すぎて違う気がする】
-
それ以外に思いつかなかったり、別の方法で試したものが通らない場合は試してみるべき
コードが長くなるようなものであれば回答になりにくいと考えてしまうが、その一部に典型となるアルゴリズムが混じるなら想定解の可能性は高い
【出しても通らないかもしれない】
-
解法のストックには溜めておくこと、どうしても解けないときは一旦その方法で出してみる
うまくいく可能性が少なからず存在するし、結果から絞れるものがあるかも
【分かんないからTwitterを眺めたい書き込みたい】
ルール上、Twitterに有益な情報が流れてくることはないので避ける
ランキングを眺めてた方が有用諦めていない状況で書き込むのは厳禁
書き込んでいる時間にコード書いてたらぎりぎり解けたのに、と悔やむ経験はするものではない
【もう諦めちゃった】
次の問題が解けたりしないかはチェックすること
一問飛ばして次の問題に取り掛かっていたなら、一つ前の問題を悪あがきでもいいのでチャレンジするのもあり
やり残したことはないか、諦めるならすっぱり諦める
レートが下がれば残念だけれど、気持ちを切り替えるしかない
解けなかった問題の解説はちゃんと読み、今回の敗因を分析する
きっと次につながる、はず…洗濯物とかまだ回していい時間なら回した方がよい
遅い時間に回すのは近所迷惑となるので回す場合はお早めに手持ち無沙汰に感じたら、私のおすすめフリーRPGゲームざくざくアクターズをプレイ！
【終わりに】
自戒としてまとめてみました。
いつも脳内の反省会で終わらせていることについて、文字にしてアウトプットしてみると、忘れていた反省も思い出すいい体験になったと感じます。
記事を書いたおかげでレートが上がってくれれば申し分ないのですが、どうなることやら…
この記事が出来たせいでメタを張る問題が出てくる、ということはないと思います。あったらごめんなさい。
誤字脱字の指摘や、内容について追記した方がよいもの、訂正した方がよいものがあれば、コメントやDMしていただけると幸いです。
これをコンテスト中に読んでいる方がいましたら、AC できることを祈っています。頑張ってください！