競技プログラミング初心者がやらかした凡ミスを紹介

2019年8月からAtCoderで競技プログラミングデビューしました。エンジニアとしての基礎力向上に役立つかなと思って始めたんですが、単純に面白くてハマっています。

よくネットの記事は玉石混交(石多め)なんて言われますが、競技プログラミングに関する記事は宝の山です。本格的に勉強したい方はちょっと探せば素晴らしい記事がすぐにたくさん見つかるので、いろいろ参考にしてみて下さい。偉大な先人達に感謝です！！

そんな宝の山に石を紛れ込ませるのは申し訳ないのですが、自分への戒め＋初心者さんへの共有ということで、私がこれまで参加したコンテストでやらかした凡ミスを紹介したいと思います。

出力文字に注意！！

AtCoderの問題の中に、入力値に対して、その値が特定の条件を満たすならYes、満たさないならNoと出力させるような問題があります。

さて、以下は私が初参加したABC136 Cの問題文一部抜粋と、私が提出したコードの出力部分です。

（問題文一部抜粋）マスの高さを左から右に向かって単調非減少にできるなら Yes、そうでないなら No を出力せよ。

# 以下が最後の出力部分
if ans == True:
    print('yes')
else:
    print('No')

お気づきになった方が多いかと思いますが、問題文の指示はYesなのに対し、上記の私のコードではyesになっています。そして、当然ですがこれでは不正解になってしまいます。（ちなみに私はこの間違いにコンテストが終わるまで気づけませんでした・・・・）

問題文によってYES, Yes, yesのように色々パターンがありますので、最後の最後で油断しないように注意しましょう。

AtCoderの問題では、答えがとても大きい数値になることがあります。そうした問題の中で割り算を実施する際の注意点です。

pythonの場合、割り算の商が欲しい時は // を、小数点も含めて割り算の答えが欲しい時は / を使うと思います。（他の言語でも似たようなことをやってると思います？）

さて、明らかに割り切れる場合の割り算で / と // はどちらを使っても同じ結果が得られるように思いますが、ここに罠が潜んでいます。

以下は第一回日本最強プログラマー学生選手権予選の問題と私が提出したコードの一部分です。

第一回日本最強プログラマー学生選手権予選 B https://atcoder.jp/contests/jsc2019-qual/tasks/jsc2019_qual_b

# 以下が最後の出力部分　こちらは不正解になる
R = sum(R_down) * k * (k+1) / 2
L = sum(L_down) * (k-1) * k / 2
ans = (R + L) % mod
print(int(ans))

# 以下が最後の出力部分　こちらだと正解
R = sum(R_down) * k * (k+1) // 2
L = sum(L_down) * (k-1) * k // 2
ans = (R + L) % mod
print(int(ans))

２つのコードの違いは、割り算を / でやっているか // でやっているかのみですが、上のコードは不正解になり、下のコードでは正解になりました。（その他の実装部分は同じです）

難しい話ができるほど勉強できていないので、詳細は以下のリンクを参考にしていただきたいのですが、どうも桁数の大きい数値をfloat型で取り扱うと誤差が出てしまうようです。（bitとか2進数が関係する話）

実はこの記事を書く直前に開催されたABC139でも // を使わないと、誤差が出て不正解になってしまう問題が出題されています。必死に考えたアルゴリズムが正しいのに、こうした細かいミスのせいでACが取れないのはとても悔しいので皆さん気をつけましょう。