初めてのAtCoderコンテスト中600点正解を目前で逃した話

先週末の天下一プログラマーコンテストのこと。

最初の問題を首尾よく片付けた俺は、2問目に取り掛かっていた。 しかし、600点問題を試験時間内に解いたことは無い。500点でも解けない確率の方が多いので、解けないものと半ば諦めつつ問題文を読んだ。

atcoder.jp

ナップサック問題っぽい。 これは「赤の辺の長さがxのもの」だったら単純なナップサック問題で、動的計画法を使えば解ける。 ……あれ?これは「赤の辺の長さが全体の半分以上のもの」の3倍が三角形を作れない場合の数だから、全体から引けば答えが出るのでは?そして「赤の辺の長さが全体の半分以上のもの」は上と同様の動的計画法で求められるのでは? ……もしかしてこの問題、解けるんじゃないか?

上記で基本方針は正しいが、実はこれだけだとダブルカウントが発生して間違いになる。しかし解いている途中で間違いにも気づき、2つ目のDPテーブルを作れば解決できることを導き出した。

サンプル入出力も無事に通って、満を持して提出！ TLE。Pythonのような遅い言語にはあり得ることだ。 WAは出ていないので、解法は完璧だと思うが、いかんせん計算に時間がかかりすぎている。 その後デバッグを続けてもTLEを脱出できず、時間切れとなった。

やはりPythonで正答を提出するのは不可能なのだろうか。C++とかじゃないと無理なのだろうか。

みんなの回答を見ようとして、言語の一覧を見ていたところ、PyPyを見つけた。 PyPy。確か、Pythonの一般的な処理系よりも処理が高速だ、と聞いたことがある。

試しに最後の回答をPyPyで再提出してみた俺は、脱力した。

すなわちPyPyで提出していれば600点問題がAC（accepted、正答）だったのだ！

この方法に気づかずコードの修正をしていたせいで、 初めての600点ACを逃してしまった。

ひとまず、解法が合っているはずなのにTLEで落ちる場合は、処理系をPyPyに切り替えてもう一度試してみよう。

それでは。