競プロ日記

新ABCを制覇し、コツコツと旧ABCを埋めている。
ABC124～ABC120の水色レベルの問題全てを解説なしで解けて、今までで一番の成長を感じている。
緑以下からでも色々吸収できてニコニコだったのだが、環境の違いにかなり困惑してしまった。

問題はABC120D Lazy Faith。
ACコード
WAコード

解説PDFと少し解き方は違う。
①神社siに東西それぞれに最も近い寺tj、寺tiに東西それぞれに最も近い神社sjをあらかじめ求める。
②クエリ地点に東西それぞれに最も近い神社2箇所寺2箇所と、既に求めたそれらの神社・寺から東西に行く8通りを見る。
結局やっていることはPDFと同じく8通りを見ているだけである。
書いていて思ったが、最初の神社/寺に近い寺/神社を求める部分は、東西方向それぞれじゃなくてどちらか近い方だけでよかったな。

本題の環境の違いについて。
まず、WAコードの間違えた部分について説明しておく。
①である神社/寺より西側あるいは東側に寺/神社ない場合、INFを与えている。
その判別に使ったのが、lower_boundしたインデックスが0なら西側にはない、配列サイズと同じなら東側にはない、というものである。
この配列サイズのsとtを間違えて逆にしてしまった。
間違いなく間違えているのだが、なんとWAコードでもローカル環境では正しい答えが出ている。
間違えている部分は37,44行目。ifの中身のaとbが逆。
どうして・・・。


AtCoderのコードテストではしっかり間違えている。



色々考えてコードを追ってみると、配列外アクセスをしている可能性があることに気付いた。
そう思って少し調べてみた。

サンプル1だと、sのインデックスの判別がうまく行かず、sのサイズは2なのにs[2]にアクセスしてしまう。
そこでローカル環境とAtCoderのテストコードでs[2]の値を出力して値を確かめた。
ローカル環境: 4294967295(unsigned intの最大値)
コードテスト: 0
結果はこのようになっており、1が並んでいるか0が並んでいるかの違いがあった。
これを見るとなるほど納得が行く。
最終的にminを取っているので、ローカル環境ならINF-xの値が保存されるので、正しい答えが出る可能性は十分ある。
逆にテストコードでは0-xの値が保存されるので、minを取ると明らかに正しい答えが出ない。

正直これをデバッグするのは至難の業だと思う。
しっかり解法を立ててサンプルケースが合っている時点で、実装ミスよりは細かい条件分岐にミスを疑ってしまう。
今回はローカル環境でサンプルケースが合っているにも関わらず、提出結果を見るとサンプルケースが間違っていたので、コードテストを試すことで気づけた。
最初は全く分からず、サンプルケースは間違えているわけないし、提出をミスったのかと全く同じコードで2度提出して2度WAをもらった。
本番ならかなり痛い。

今回はサンプルケースが違っていたので分かったが、運悪くサンプルケースは正解で非公開のテストケースが間違えていたらどうしようもない。
どうしようもないが、こういう事態も起こり得るというのは肝に銘じておく必要がある。
ローカル環境だけではなく、コードテストを試すという選択肢を持っていくのも大事だ。