手に汗握る高校生アスリートの戦い。日本最大の高校eスポーツの祭典「STAGE:0」で競技プログラミング 高校生大会を初開催、大会優勝者＆主催者インタビュー

【ストーリー】
高橋市警では警察官の人手不足解消のために、自動運転の無人パトカーによる自動パトロールが実施されることになった。 無人パトカーには屋根の上に高性能な全方位カメラが取り付けられており、現在位置からの直線上にある道路全体を一度に見渡すことが出来、画像処理技術を用いて異変が無いかを自動検出する。市民の安全で安心な暮らしを守るため、市内の隅から隅まで少なくとも一度は見渡すことが出来るような巡回ルートを設定したい。 そのような巡回ルートの中で出来るだけ短いものを求めてほしい。

【問題概要】
N×N(Nは60くらい)の地図が与えられる。上下左右に視界が通る。スタート地点から上下左右に移動し、全ての地点を見て返ってくるルートのうち、出来るだけ短いものを求める(各マスの数字はそのマスに移動するためにかかる時間)。

開始10分に提出のあった全ての参加者が同スコアを提出。その後、今いるマスから、最も近いものを選ぶことを繰り返す「貪欲法」と、最短経路を求めるアルゴリズム「ダイクストラ法」の合わせ技による改善で77分、渋渋(渋谷教育学園幕張高等学校)チームが15,928,627点までスコアを伸ばした。「絶対に通るマス」を最初にいくつか決め、見えていないマスの数が最も減るよう、マスを1つずつ選ぶ。これを繰り返し、数十個のマスを通るだけで、全ての道路が視界に収まるようにする。

なお、全てのマスを見ることが出来ない巡回ルートでも、見えたマス数の分だけ点数が貰えるが、全てのマスを見るルートよりも当然点数が低い。

【問題の概要補足】
この問題は「巡回セールスマン問題」と呼ばれる問題に近い性質を持つ問題である。

巡回セールスマン問題とは「全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで、移動時間が最も短くなる巡回路を求める」という問題であり、これは非常に難しいことが知られている。今回の問題は、その問題を発展させたものである。巡回セールスマン問題においては「どの都市にたどり着くべきか」ということが決まっている。だが、今回は「全てのマスを通る」ではなく「全てのマスが視界に入る」というのが条件であるため、各マスの条件を満たすために通るべきマスが必ずしも1つではない。そのため「どのマスを通り、どのマスを通らないか」という選択が生まれる分、巡回セールスマン問題よりも複雑な問題であると言える。この問題に4時間で取り組む必要がある。

【観戦記】

開始10分に提出のあった全ての参加者が同スコアを提出。その後、今いるマスから、最も近いものを選ぶことを繰り返す「貪欲法」と、最短経路を求めるアルゴリズム「ダイクストラ法」の合わせ技による改善で、77分、渋々チームが15,928,627点までスコアを伸ばした。

「絶対に通るマス」を最初にいくつか決め、見えていないマスの数が最も減るよう、マスを1つずつ選ぶ。これを繰り返し、数十個のマスを通るだけで、全ての道路が視界に収まるようにする。

次に、それらのマスについて、訪れる順番を決めていく。巡回セールスマン問題は、2-optと呼ばれる改善方法を繰り返すことで、最適解にかなり近づくことが出来ることが知られていて、灘高チームもこの2-optを採用していた。渋渋チームと同様、距離を求める際にはダイクストラ法を使っている。

https://www.dropbox.com/s/wedwcg4ibtquofk/KoD_85.gif?dl=0

開始150分、Nachiaさんの最初の提出で、一気に1位が入れ替わる。提出コードは444行と、他チームより倍以上長い。最初からこのコードを書き始めていたようだ。基本的には灘高チームと同じ方針のようだが、絶対に通るマスを選ぶ際、交差点のみを考慮して選んでいることや、巡回路を求める2-optを使う際、焼きなまし法と呼ばれる高度なアルゴリズムを利用している。これらの差が、結果的に大きな要因になったと思われる。

残り25分。上位3チームが1,800万点台で並ぶ中、ついにNachiaさん(Perisitence)が2000万点に到達した。絶対に選ぶマスの選び方にランダム要素を入れ、何度も実行するように変更したようだ。

最後の10分、凄まじい勢いで結果が入れ替わった。そして、最終結果はこちら。