AtCoder HTTF2019予選「Python殺し」

　昨日は AtCoder でHTTF(HACK TO THE FUTURE)2019予選なるものがあったので参加した。

狭い盤面の上に500台ロボットを走らせる。
盤面の上にロボットの移動命令に干渉できる命令を書ける。
なるだけ散らばるように盤面を設定せよ。

　よくわからず結局固定盤面をいくつか出してあきらめていたが、ビジュアライザーで試行できる=> javascript で実装できるんだから Python でも実装できるということに気付いて面倒くさーと思いながらとりあえず実装し、小細工を弄するも固定盤面よりもはるかに悪い出来に絶望。あとはたまにサイコロを振りつづけるだけになって87015点で終了。ランキングは226ということで何かを提出できた人の中では中くらい。だが、満点が15万で1位が13万なのでいかにも率は低い。そもそも固定盤面で83000点くらい叩き出していたので、実際にはそこへわずかにプラスできたというにすぎない。(下は固定盤面で83350点出した解答。ちなみにRLTD埋めは全部最初に試した)

beta.atcoder.jp

　しかし後から twitter で情報収集してみると1万回試行したとか高速化が鍵とかいう言葉がボロボロでてくる。どうも今回(というかHTTF)はAtCoderの普段のコンペとは違い、格段に速くなる魔法ロジックがあるわけではなく、地道にサイコロを振りつづけるか、いい初期盤面をみつけてそこから改善しつづけるというアプローチしかなかったようだ。(通信環境条件が悪く、解説放送は今まで一回も聞いたことがないので公式にどうなのかはよくわからない) もちろんそこからの工夫が見せどころなのだが、当然ながら Python3 ではその方向は難しい。たとえば自分のどんくさい実装では試行はせいぜい15回くらいしかできなかった。あとから PyPy3 に投げ直してみるともっとできたがそれでも100回くらいだ。一万回には到底及ばない。最初小細工を弄したとき、一回二回やって大して改善しないので投げだしたのだが、一回二回ではダメでそれを10000回くらい続ける根性がないといけなかったようだ。当然ながら素のPythonでそこまで出せるわけがない。今朝になってみると9万点台に乗せた人が現れたがそれでも9万台だ。ライブラリで高速化できるとはいっても肝心要のロジックは自作するしかないのだから、工夫の余地はあまりないのだろう。

　最近 Python がもてはやされているのはライブラリを操作する便利言語としての側面があるからだ。機械学習がニューロンネットワークの時代に突入し、ロジックでどうこうするというより、どうやって組み合わせて構築するかという方向になってきたとき、つまりやることが既存のライブラリのパラメータを設定するだけになったときには、プログラムとしてはむしろ平易で変なのが書きづらく他のCなどで書かれたライブラリと連携しやすいのが望ましく、Pythonがたまたまそういう位置にあったというだけのことだ。Python 自体が高速なのではない。

　そういう点からすると Python でロジックを組むのは悪手なわけだが、それを今まで敢えてして AtCoder に参加してたのは、もちろん「遅いから」だ。遅いためにロジックの構築に真剣に取り組まざるを得ず、ロジックの差がかなり露骨に実行速度に現れ、学習効果も大きい。平易だから呪文的な面も少ない。ところが今回のように想定が回数勝負の改善アプローチになるとPythonの存在空間はあまりない。しかも自分はその中でももっとPythonに向いてない無脳乱択アプローチを選択したわけだから何が「ロジックの構築」だと自分でも思わざるをえない。まぁ今回のはPythonみたいな言語で平気で重い実装をしてくるふざけた奴を殺しに来たようなもんだろう。

　シミュレータを自分で構築するのがスタート地点で、とりあえずスタート地点には立てたようなのでそこから一歩くらいしか進めなかったにせよそれはそれでよしとする。