AHC002参戦記

先月実施されたAHC001が楽しくて、2回目の開催を楽しみに待っていました。

山登り法やビームサーチなどといったマラソンに有効なプログラムは書けませんし、
最適解を求めるアルゴリズムについても、勉強中の身ではありますが、十分楽しめる種類のコンテストだと思い、今回のAHC002にも参加しました。

この記事を書いている私は、AtCoderのアルゴリズム部門のレートは茶色下位から中位くらいで、使用言語はPython3です。

問題概要

大雑把に書くと、会場が50×50のマスで区切られている。
各マスには通過することで得られる得点が書いてある。
会場は大小2種類のタイルで敷き詰められている。
各タイルは2回以上踏むことができない。
この制約下で得点が最大になるような経路を出力してください。

考えたこと1

まずは、得点を伸ばす事よりも、タイルを2回以上踏まないで経路を出力できるプログラムの部品を作ることが重要なことに気づきます。

初期位置が大きいほうのタイルだった場合、端のタイルではなかったとしても、進める方向は3つに絞られてしまいます。

そこで、進める方向をチェックする関数が必要で、そのためには、その方向のタイルが使用されているかを保持しておく配列が必要で、そのタイルがどの位置にあるのかが必要なことがわかります。
この、最後に出てきた、「タイルがどの位置にあるのか」については、問題文中から与えられるので、そこから、タイルが使用されているかを保持しておく配列を記録していきます。
勿論、エリアの端のタイルはそれ以上先には行けないので、それも考慮した関数を作ります。

この関数を作成して、初めて提出した結果がこちらです。(seed0をwebのヴィジュアライザで表示。)

おお、正の得点がちゃんと得られていることに感動しつつも、もっと左、下に行けよ！って思いますよね。

得点は、206679点です。

行動を決定する関数が、上に行けたら上に行く、行けなかったら下に行く、上下に移動できなかったら左に行く。左も行けなかったら右に行く。という関数だったので、当たり前といえば当たり前ですね。

考えたこと2

一回目で提出したプログラムは、行動が今いる場所から上下左右にいけるかを判定しているだけだったので、もうちょっと考えます。
行動を決定する方針は、今いる箇所が半分より右側なら左に、半分より上にいるなら下に行くように書き換えます。

この方針を利用して提出した結果がこちらです。

おおお！先ほどよりも大幅に進む距離が長くなっている！
しかし、中心を進んでしまうので、周りをもっと有効活用したいですよね。

得点は、215720点でした。

考えたこと3

中心に集まってしまうということは、角周辺にあるタイルを踏んだかどうかを判定して、そこにあるタイルが踏まれたら次の角を目指していけばよいかな。と思ったので、
行動を決定する方針を変更しました。
角にあるタイルをsetで管理して、角がTrueになったら次の角を目指すようにします。

そのコードで提出したのはこちらです。

？？？あれ？バグってますね。。。

とりあえず、正の点数が得られそうなので、前回提出したコードと、今回書いたコードを実行して、点数が高かったほうを採用することにしました。

点数は、268515点です。

点数は上がっているので、うまくいくケースもあるみたいです。

[うまくいっているケース(seed6で比較)]

この提出をした段階で残り時間は30分ちょっととなりました。
そろそろコンテスト終了時刻を意識しないとダメな時間帯ですね。

考えたこと4

AHC001の時に、解をいくつか作り、最善の状態を提出するのが重要なことを学びましたので、ここからは行動を決定する要素をランダムとして、行ける方向の中から完全にランダムで選択し、スコアが一番良い状態のものを採用することにします。

ランダムで実施する試行回数ですが、今までの提出はPython3で32msなどだったので、実行回数が早いPyPyなら7000回行けるかな？と思ってコードテストしてみたところ、実行時間は1133msだったので、多分大丈夫だろう。と思って提出したところ、
TLEしました！

Pythonのコードを変えずにCythonでも動くので、Cythonで提出して無事通ることを祈ります。
ちょっと弱気になり、ランダムの試行回数は5000回に減らしました。
Cythonでも無事通ることも分かり、実行時間も1174msと余裕がありそうだったので、7000回に増やして最終提出です。

ランダムなので、ブレ幅はありますが、seed0の単体の得点で8000点くらいの結果が多いです。

無事にACして、ここで今回のAHC002は終了となりました。

最終の得点は、834174点で684位です。

もっと、方針を考えて手直しすれば点数が上がりそうですが、限られた時間で少しずつ改善点を考え、コードにしていくのは非常に楽しかったです。

振り返りをしていて、方針で修正したらもっとよくなりそうな部分が見つかったので、時間を見つけて修正してみてどこまで得点を伸ばすことが出来るか試してみたいと思います。