Mister雑記

競プロやります。

TSG LIVE! 2 競技プログラミング反省

この記事はTSG Advent Calendar 2018の10日目に書かれたものです。

先日はdaiさんによる「キーボード盗聴の話?」でした。


初めましての方は初めまして、Misterと申します。

私は東京大学のTSG(理論科学グループ)というサークルに所属しているのですが、TSGは今年の駒場祭1で「TSG LIVE! 2」という企画を3日に渡って開催しました。

TSGの部員達が「競プロ」「AI実装」「コードゴルフ」「CTF」を実際にやる様子をYouTubeniconicoの生放送で実況するというもので、私はそのうち「競プロ」「AI実装」でプレイヤーとして参加しました。本記事ではそのうち「競プロ」の方について語ります。

なお一口に競プロと言いましたが、今回行われたのは「アルゴリズム」ではなく「マラソン」でした。とはいえ時間が75分なのでマラソンの中ではとても短い部類ではありました2

目次

問題概要

イワシの収穫祭」

壁がまばらに配置されている H \times Wのグリッドがある。

グリッド上にいるfiordくんは、毎ターンいずれかの方向へ1マスずつ移動する(あるいは移動しない)ことで、 Tターンに渡って N匹の「イワシ」を収穫する。

イワシは特定のターンにグリッド上に生えてくる。そして毎ターン、fiordくんか他のイワシの中で、自分に最も近いものに近づくように移動する(細かい動き方は割愛)。なおイワシは複数匹が同一のマス上に存在することができる。これを「群れ」と呼ぶことにする。

fiordくんはイワシの群れに接触することでイワシを回収できる。しかしイワシは集団になると凶暴になる性質がある。fiordくんは6体以上のイワシの群れに接触すると、回収できない上に怪我をして5ターン行動不能になる。

最初にグリッドの配置と各イワシの出現するターン及び位置が与えられる。このとき、fiordくんの動きを出力せよ。

制約と点数

  • 全ケース共通

    •  H = W = 22
  • tiny (1ケース)

    •  N = 50
    •  T = 150
    • 壁は全体の 15\%
  • little (6ケース)

    •  N = 250
    •  T = 1000
    • 壁は全体の 25\%
  • much (6ケース)

    •  N = 3000
    •  T = 1000
    • 壁は全体の 25\%
  • challenge (3ケース)

    •  N = 1000
    •  T = 1000
    • 壁は全体の 47.5\%、作為的に生成

challengeのケースは以下のようになっており、盤面が実質直線になっている。

f:id:misteer:20181209220631p:plain:w400

各ケースごとにイワシの収穫率がそのままスコアとなり、その合計が最終スコアとなる。

本番の流れ

事前にfiordさんから聞いていたので覚悟はしていましたが、まぁまぁ問題文が長い。特にイワシの動きの部分が曲者なのですが、「一番近いfiordくんとイワシに近づく」ということだけ頭に入れて読み流しました。実はサンプルコードに動きをシミュレートするコードが入っているので、イワシの動きが細かく分からなくてもなんとかなります。

乱択厳選

ラソンということで、最初にしたのが乱択です。ランダムに方向を決めて、実際にシミュレートします。

しかしここで競プロerにあるまじきミス。fiordくんの移動は自身でシミュレートするのですが、その際に壁判定と場外判定を両方飛ばしまいました。結果として範囲外参照が出たり出なかったりすることになり、しばらく唸っていました。

それに気づいてバグを修正したのが大体25分頃。そこから少しだけ工夫をして、この生成を7回繰り返して最適なやつを選択するコードを提出したのが35分頃でした。

しかしこのスコアが4.99点とあまり芳しくありませんでした。なぜか前に出したバグ有り乱択の方が5.29点とスコアが高いという有様。この時点で対戦相手のdaiさんは5.73点を出しており、内心焦っていました。

中心へ

ここで初めてビジュアライザを起動。すると、想像していた以上にイワシがfiordくんへ吸い寄せられていることが分かりました。

「これ下手に動かない方が良いのでは?」と勘付き、試しに一度も動かないコードを提出してみると5.56点と最高記録が出ました3

そして特にスコアが高かったやつ(これ)をビジュアライザで眺めていると、「グリッドの中心に近いほどイワシが効率的に吸い寄せられるのではないか」と思い始めました。以降それを実装することになります。

逆辺張りBFS

後は中心へ移動するプログラムを組むだけです。具体的には「逆辺張りBFS」をします。

まずfiordくんの初期位置を始点としてBFS(幅優先探索)をします。このとき、「どの方向の移動によってそのマスへ移動したか」を同時に記録します。

f:id:misteer:20181209220713j:plain

次に目的地を決めます。今回は到達可能な中で (H / 2, W / 2)とのマンハッタン距離が一番小さい場所を目的地にしました。

最後に経路を求めます。今度は目的地を始点として、先程の遷移を逆走するようにします。すると最終的にはfiordくんの初期位置へたどり着きます。その際通った文字を反転させれば、これが目的地へ移動するような文字列になるわけです。以下の例ではNEENNがそれに当たります。

f:id:misteer:20181209220731j:plain

このアルゴリズムを思いつくのは秒なのですが、実装に地味に時間がかかりました。その根底のミスが「queueへのpushし忘れ」というしょうもないもので、これに気づかないまま終わっていたら競プロ引退案件でした。

それでもなんとかそれに気づいて終了2分前に提出。これが無事バグ0で真ん中へ移動してくれて、6.38点という最高得点を叩き出しました。

結果

終結果は私のスコアが最終提出の6.38点、daiさんのスコアが最初の提出の5.73点でなんとか勝つことができました。

後でコードを読んだところ、daiさんは「10手先読み」を実装していたようです。具体的には、「あと n手ある状態で各方向へ移動した場合の最高スコア」を再帰的に求めて、一番いい方向へ動くというものです。

ただし今回の問題はシミュレーションにとても時間がかかるため、TLE(15sec超過)になっていたことに気づかなかったそうです。それにしてもあれだけの量を75分で実装していたのは驚嘆という他ありません。

想定解法

ライブ終了後、fiordさんに想定解法を訊いたところ「影響マップ」という単語が出てきました。

fiordくんはできるだけイワシを収穫したいので、当然ながらイワシに近づきたいことになります。一方で6匹以上のイワシの群れには当たると怪我してしまうため、できるだけ近づきたくありません。

そこで、5匹以下のイワシの群れからは「正のオーラ」、6匹以上の群れからは「負のオーラ」が周り全体へ広がっていると考えます。これらのオーラは発信源から遠くへ行くほど小さくなり、重ね合わせると互いに打ち消し合います。そして全てのオーラを重ね合わせたとき、一番正のオーラが強い方に移動すると得ということになるわけです。

これが「影響マップ」という考え方だそうで、「なるほど確かに実装も楽そうだなぁ」と思いました。マラソンと言えば「焼きなまし法」と「ビームサーチ」しか知らなかったので、良い知見が得られました。

反省

ラソンと言っておきながら最終的には「真ん中に移動するだけ」になりましたが、それはそれで競プロらしくて良いんじゃないかなと思います。

ただ範囲外参照やBFSのバグについては要反省ですね。緊張して大分焦ってコードを生んでいたので、もう少し落ち着きを持てるようになりたいです。

ラソンも楽しいのですが、次にTSG LIVEがあれば作問に挑戦してアルゴリズムも開きたいなぁと思いました。今回のCTFの点数形式がアルゴに近い感じで、アルゴ勢はTSGにもそれなりにいるので楽しそうです。まぁ作問ができればの話ですが。


本記事は以上になります。最後まで読んでいただきありがとうございました。

明日の記事はmoratoriumさんの「駒場祭AIコンテストで作ったゲーム」です。冒頭に述べた通り、私はAIコンテストの方にもプレイヤーとして参加したので楽しみです。ちなみにAIの方の反省記事は20日目に書く予定ですので、そちらも読んでいただけると幸いです。





  1. 東京大学には年に2回学校祭が開かれていて、そのうち秋に開かれる方が「駒場祭」です。ちなみにもう1つは春に開かれる「五月祭」。

  2. 作問者のfiordさん曰く、「400m走」的な感覚だそうで。実際75分間に渡って、アルゴリズム並のスピードで考察、実装することが求められました。

  3. 後から分かったことですが、バグ有り乱択はバグが起きたときに何も出力されず、それが「何も動かない」と解釈された結果それなりの点数が出たわけです。daiさんが最初に出したコードもサンプルコードそのままで、これが何も出力しないものだったので5.73点という点数が出ていたようです。