競技プログラミングで正解にならないときの対処法

Question

実現したいこと

私は最近AtCoderを始めました。
提出してみると、ほとんどのテストケースに対してはACになるのですが、1つや2つWAやTLEとなってしまい、ACにならないことがあります。
その場合、皆さんはどのようにして原因を探っていますか？
私は極端な例を入力してみたり、それでだめならいろいろなパターンの入力をひたすら繰り返して試す作業をしているのですが、ほかに良い方法があればご教授お願いします。

Answer 1

一般の開発で言うと、「書いたプログラムが単体テストを通らない。いくつかの入力データでは期待通りの結果が出るが、いくつかの入力データでは期待通りでない結果になったり、とんでもなく長時間かかったりする」ということで、日常的にあり得る話かと思います。詳細情報が書いてないので、一般論での質問ですよね？

コーディングスキルに問題が無いという前提を置いていい場合は、
テストケースの違いが入力データの違いなのであれば、
・どういう入力データがあり得るのかの検討が足りない
・仕様にない制約を自分で勝手に追加してしまっている
などでしょうか。

後者の例は、最近他の人の質問であったのは、「数値の上限の記述が無いのに、4バイト整数の範囲の計算で収まると勝手に考えてしまった」というものですね。
これは広い意味では前者の場合の一部で、例えば「桁数の大きい入力データがあると思っていなかった」ということになるかと思います。あるいは「数値の桁数など全く意識してなかった」とか。

「半角文字だけだと思っていたが、漢字や絵文字もあり得た」とか、「自分の書いたコードでは明示的に制約は付けてないが、使っているライブラリーに制約があった（＝ライブラリの調査不足）」とか。

原因の可能性のリストアップ能力も問題解決スキルの一部です。
「どういう入力データがあり得るのかの検討が足りない」を疑うなら、
「自分はどういう入力データパターンがあり得ると想定してこのプログラムを書いたのか」を明文化すれば、質問文と見比べて、「どういう入力パターンの想定が漏れているか」が分かるはずなので、そのパターンも考慮に入れてプログラムを書き直せば良いです。

あるいは、「入力パターンの想定は間違っていなかったが、プログラムが間違っていた（プログラムバグ）」という可能性もありますね。これはさらに、
・単純なタイプミスの類い（変数名、演算子、括弧の位置など）・・・プログラムを数回音読すると見つかるはず
・そもそもこの問題を解くだけのプログラミングスキルに達していない
などに分かれるかと思います。

あと、過去の質問だと、「プログラムを修正したのに、修正前のプログラムを実行していた」というパターンも、多くはないけど珍しくはないです。

色々な可能性があるので、あとは状況により何の可能性から順番にチェックするかですね。
「入力データは単純で誤解の余地が無い」
「タイプミスは生まれてから一度もしたことない。もししてたらその場で腹を切る」
「自分は操作ミスが多いことを自覚している」
など。

Answer 2

手元にコンパイル環境は整えてください。 導入するツールをある程度自由にできるならクラウド環境でもかまいません。

コンパイラの警告をなるべく多くだすようなオプション指定をしましょう。 アドレスサニタイザなどを導入して不正なメモリアクセスなどを検出する仕組みを整えましょう。 自動で出来ることは自動でやるべきです。

GCC などではいくつかのマクロを定義すると標準ライブラリが受け取った値がおかしくないかをチェックする仕組みが有効になったりもします。

テストケースの作成についてはテスト技法の考え方を取り入れるのがよいのではないかと思います。 たとえば境界値分析などは単純ながら有効でしょう。

そして大事なのはプログラムを整理することです。 競技プログラミングでは手っ取り早さのために全部を main に詰め込んでごちゃごちゃしているようなことはとても多いです。 競技という性質上、早く完成させることも必要ではありますが、結果が間違っているようではそんなことも言ってられません。

デカルトが言ったという「困難は分割せよ」という格言はプログラミング業界でもよく知られています。 問題はより小さな問題に分割できます。 プログラムはそれを構成する小さなプログラムに分割できます。 分割された小さなプログラムごとにテストを作って検証するほうがどこに間違いがあるのか見つけやすいです。

Answer 3

自分はコアに競技プログラミングに向き合えていませんが、
経験からいえば1つや2つの場合アルゴリズムの問題ではない場合が多いですよね笑
考えても無駄なことが多いと思ってます。

とりあえずチェックリストでも作ってみるのが妥当な解決策では？

問題文と自分の考えが合っている、変数名が合っている、入力を受け取れている、型が合っている、etc...

もっとレベルの高い質問だとは思うのですが、天才では無いので1個1個チェックするのがいいかもしれないです。

※質問者さんのレベルを示すといい回答が得やすいかもしれないです、自分も興味あります

Answer 4

私はその手のやつに興じている人ではないのですが……

TLE

というのは，要は，そのアルゴリズムでは｛データ量がある程度多い場合，データがそのアルゴリズムにとって都合が悪い形である場合，etc｝には制限時間内に終わらないという話なのでしょうから，多くの場合，根本的にアルゴリズムを変えるしかないのではないでしょうか．
（偏見ですが，この手のプログラミングパズルみたいなやつって，愚直なアルゴリズムだとそうなるように意図的に制約してあるのではないかと）

あるいは，バグで「無限ループになるパターン」みたいなのがそのコードに存在していないのかを確認するとか．

WA

こっちは単純に「不正解」なので，実装のバグか，あるいは「その方法では何かが足りてない」って話ですよね．多分．
いくつかの入力に対しては「正解」になるという場合，「あり得る入力の全てを網羅できていない」っていう話でしょうから，いろんな入力でデバッグしてみることになるのでは．

• 入力値に Min <= x <= Max みたいな範囲が設けられているなら，Min とか Max なる値に対しても適切に処理できるのか？
• 入力が複数個あるとき，同じ値が複数入っているとか，値がすごく偏っているだとか，順番がトリッキー(?)だとか，そういうパターンに対してはどうか？

等々，「その問題文が提示している条件に違反していない入力であって，且つ，相当にいじわるなもの」みたいなのを想定して考えてみる感じ…でしょうか？

私は最近AtCoderを始めました

冒頭で述べたように，私自身はこれ系のやつのことを良くは知らないのですが，
「これ系のやつによくある罠」みたいなのが存在しているのではないかと思うので，そういうのを踏まえて考えるべきなのかもしれません．
（ #define int long long とか言い出すような，すごく独特な世界みたいですし？）

あと，変なマクロみたいなのを使っているような場合，一旦，ふつうの書き方に書き変えてみるとか．
（これ系の質問で稀に見かける気がします．何故か for のループすら謎マクロにしていて→そのマクロを使うところが間違っているという本末転倒みたいなの）
そうでなくとも，これ系に特有のコーディングスタイル（…なのか？ main の中に全部書く，変数名が謎の一文字，みたいな）でコードを書いてあるなら，それを一旦「ふつうの」スタイルに書き変えてみるとか．（…っていう書換え作業の途中で「あれ？　ここって…」とか気づくこともあるんじゃないのかな的な．「強制的な実装の見直し/確認」とでも言うか，そのように働く感じ）

Answer 5

検索すれば、その手の記事が色々見つかるので、いくつか読んでみてはいかがでしょうか。

デバッグ力を高める！　～5 年間の経験から学んだ、競プロ・アルゴリズム実装におけるバグ取りの戦略～
【Python版】AtCoderのコンテスト中に「問題が解けない！」となった時に読む記事
【AtCoder】WAが出た時の対処法(灰色コーダー向け)【競技プログラミング】