2018の10日目に書かれたものです。先日はdaiさんによる「キーボード盗聴の話?」でした。初めましての方は初めまして、Misterと申します。2」という企画を3日に渡って開催しました。TSGの部員達が「競プロ」「AI実装」「コードゴルフ」「CTF」を実際にやる様子をYouTube、niconicoの生放送で実況するというもので、私はそのうち「競プロ」「AI実装」でプレイヤーとして参加しました。本記事ではそのうち「競プロ」の方について語ります。一口に競プロと言いましたが、今回行われたのは「アルゴリズム」ではなく「マラソン」でした。匹の「イワシ」を収穫する。各イワシは特定のターンにグリッド上に生えてくる。毎ターン、fiordくんか他のイワシの中で、自分に最も近いものに近づくように移動する(細かい動き方は割愛)。イワシは複数匹が同一のマス上に存在することができる。これを「群れ」と呼ぶことにする。fiordくんはイワシの群れに接触することでイワシを回収できる。イワシは集団になると凶暴になる性質がある。fiordくんは6体以上のイワシの群れに接触すると、回収できない上に怪我をして5ターン行動不能になる。最初にグリッドの配置と各イワシの出現するターン及び位置が与えられる。このとき、fiordくんの動きを出力せよ。作為的に生成challengeのケースは以下のようになっており、盤面が実質直線になっている。各ケースごとにイワシの収穫率がそのままスコアとなり、その合計が最終スコアとなる。本番の流れ事前にfiordさんから聞いていたので覚悟はしていましたが、まぁまぁ問題文が長い。イワシの動きの部分が曲者なのですが、「一番近いfiordくんとイワシに近づく」ということだけ頭に入れて読み流しました。実はサンプルコードに動きをシミュレートするコードが入っているので、イワシの動きが細かく分からなくてもなんとかなります。乱択厳選マラソンということで、最初にしたのが乱択です。ランダムに方向を決めて、実際にシミュレートします。ここで競プロerにあるまじきミス。fiordくんの移動は自身でシミュレートするのですが、その際に壁判定と場外判定を両方飛ばしまいました。結果として範囲外参照が出たり出なかったりすることになり、しばらく唸っていました。それに気づいてバグを修正したのが大体25分頃。そこから少しだけ工夫をして、この生成を7回繰り返して最適なやつを選択するコードを提出したのが35分頃でした。このスコアが4.99点とあまり芳しくありませんでした。前に出したバグ有り乱択の方が5.29点とスコアが高いという有様。この時点で対戦相手のdaiさんは5.73点を出しており、内心焦っていました。中心へここで初めてビジュアライザを起動。すると、想像していた以上にイワシがfiordくんへ吸い寄せられていることが分かりました。「これ下手に動かない方が良いのでは?」と勘付き、試しに一度も動かないコードを提出してみると5.56点と最高記録が出ました3。スコアが高かったやつ(これ)をビジュアライザで眺めていると、「グリッドの中心に近いほどイワシが効率的に吸い寄せられるのではないか」と思い始めました。以降それを実装することになります。逆辺張りBFS後は中心へ移動するプログラムを組むだけです。具体的には「逆辺張りBFS」をします。fiordくんの初期位置を始点としてBFS(幅優先探索)をします。このとき、「どの方向の移動によってそのマスへ移動したか」を同時に記録します。次に目的地を決めます。マンハッタン距離が一番小さい場所を目的地にしました。最後に経路を求めます。今度は目的地を始点として、先程の遷移を逆走するようにします。すると最終的にはfiordくんの初期位置へたどり着きます。その際通った文字を反転させれば、これが目的地へ移動するような文字列になるわけです。以下の例ではNEENNがそれに当たります。このアルゴリズムを思いつくのは秒なのですが、実装に地味に時間がかかりました。その根底のミスが「queueへのpushし忘れ」というしょうもないもので、これに気づかないまま終わっていたら競プロ引退案件でした。それでもなんとかそれに気づいて終了2分前に提出。これが無事バグ0で真ん中へ移動してくれて、6.38点という最高得点を叩き出しました。最終結果は私のスコアが最終提出の6.38点、daiさんのスコアが最初の提出の5.73点でなんとか勝つことができました。後でコードを読んだところ、daiさんは「10手先読み」を実装していたようです。手ある状態で各方向へ移動した場合の最高スコア」を再帰的に求めて、一番いい方向へ動くというものです。今回の問題はシミュレーションにとても時間がかかるため、TLE(15sec超過)になっていたことに気づかなかったそうです。それにしてもあれだけの量を75分で実装していたのは驚嘆という他ありません。想定解法ライブ終了後、fiordさんに想定解法を訊いたところ「影響マップ」という単語が出てきました。fiordくんはできるだけイワシを収穫したいので、当然ながらイワシに近づきたいことになります。一方で6匹以上のイワシの群れには当たると怪我してしまうため、できるだけ近づきたくありません。そこで、5匹以下のイワシの群れからは「正のオーラ」、6匹以上の群れからは「負のオーラ」が周り全体へ広がっていると考えます。これらのオーラは発信源から遠くへ行くほど小さくなり、重ね合わせると互いに打ち消し合います。全てのオーラを重ね合わせたとき、一番正のオーラが強い方に移動すると得ということになるわけです。これが「影響マップ」という考え方だそうで、「なるほど確かに実装も楽そうだなぁ」と思いました。マラソンと言えば「焼きなまし法」と「ビームサーチ」しか知らなかったので、良い知見が得られました。反省マラソンと言っておきながら最終的には「真ん中に移動するだけ」になりましたが、それはそれで競プロらしくて良いんじゃないかなと思います。範囲外参照やBFSのバグについては要反省ですね。緊張して大分焦ってコードを生んでいたので、もう少し落ち着きを持てるようになりたいです。LIVEがあれば作問に挑戦してアルゴリズムも開きたいなぁと思いました。今回のCTFの点数形式がアルゴに近い感じで、アルゴ勢はTSGにもそれなりにいるので楽しそうです。作問ができればの話ですが。本記事は以上になります。最後まで読んでいただきありがとうございました。明日の記事はmoratoriumさんの「駒場祭AIコンテストで作ったゲーム」です。冒頭に述べた通り、私はAIコンテストの方にもプレイヤーとして参加したので楽しみです。ちなみにAIの方の反省記事は20日目に書く予定ですので、そちらも読んでいただけると幸いです。東京大学には年に2回学校祭が開かれていて、そのうち秋に開かれる方が「駒場祭」です。fiordさん曰く、「400m走」的な感覚だそうで。実際75分間に渡って、アルゴリズム並のスピードで考察、実装することが求められました。後から分かったことですが、バグ有り乱択はバグが起きたときに何も出力されず、それが「何も動かない」と解釈された結果それなりの点数が出たわけです。daiさんが最初に出したコードもサンプルコードそのままで、これが何も出力しないものだったので5.73点という点数が出ていたようです。※各問題名は表記ミスではありません。2018の本戦へ行ってきました。「Candles」の解説。公式はてなブログをはじめよう!misteerさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。