AtCoder Beginner Contest 197

思い込みが思わぬ失敗を招くことは多い―――

「ABC197で起きた話だ。ある男がD問題にせっせと取り組んでいた。残り時間はもう30分もない。男は解法をすんなり閃いたことに安堵しながら、キーボードを叩き始めた。何のことはない、回転行列を使った座標の変換だ。回転中心が原点じゃない時はどうするんだったか…そんなことを考えながら男は忙しなくサイトを巡り、数式の羅列に目を走らせた」

『あった！』

「首尾よくお目当ての数式を見つけた男は、浮き立つ心を必死に抑えつつコーディングを進めた。サンプルケースも問題なくAC。いける、そう確信しながら提出ボタンを押下した」

『え、嘘』

『WA』

「非情にも不正解を告げる画面が表示される。20のテストケースの内ACが8個、WAが12個。あぁそうか、問題文に想定解答との絶対誤差または相対誤差が$10^5$以下でないと不正解って書いてたっけ、浮動小数点演算は極力避けろって教訓もあったよな…合点した男はコードを修正し、計算に使用される数値を予め$10^5$倍して最後に$10^5$で除算することで帳尻を合わせようとした」

『WA』

『なんで！？』

「結果は先刻と全く変わらない。$10^5$じゃ駄目だったか？$10^{10}$にしてみようか、待てよ回転角を求める時にangle = math.radians(360//N)で計算しているけど、これもDecimalで有効桁数を増やさないと駄目だった？残り時間はもう10分もない。正解はすぐそこのはずなのに、答えにたどり着けない。焦燥感に駆られながら、コードの提出を繰り返す男。結果はやはり変わらない。コンテストが終わってみると、男の前には夥しい数のWAが積み重なっていた」

「―――それで、結局何が間違いだったんですか？」

「男は角度をangle = math.radians(360//N)で算出していたが、360/Nにしないといけなかった。N角形の内角は整数とは限らないからな」

「なるほど、間違いが有効桁数にあると思い込んだ男は本当の間違いに気づかなかったんですね」

「そう、思い込みを捨ててコードを一歩引いた目線から見ることができたなら、結果は違ったかもしれない。入茶も夢じゃなかったろうな」

「勉強代は高く付いたようですね」