YKpages

ロボット分野で勉強したことのまとめ

ハル研究所プログラミングコンテスト2019の参加記録

プロコン

はじめに

ハル研究所が主催するプログラミングコンテスト2019（10/01～10/15）に参加しました。

www.hallab.co.jp

マラソン形式のコンテストへの参加はほぼ初めてでしたが、 最初から最後まで楽しむことができました。

コンテストに取り組んでいた約二週間、 やったことや考えていることなどを定期的にメモしていたので、 この記事ではそのメモをまとめて参加記録を書きたいと思います。

問題

  • 縦30マス × 横60マスのステージがある
  • ステージにはカメが何匹かとニンジンが何本かある
  • 毎ターンそれぞれのカメは上下左右に1マス移動できる
  • カメがニンジンのあるマスに到達するとそのニンジンを食べる
  • すべてのニンジンを食べるとそのステージをクリア
  • クリアするまでにかかったターン数がスコアとなる
  • また、ニンジンには高さがある
  • 例えば高さが3のニンジンは、カメが三匹重なる必要がある

ビューアの様子

公式のビューアは眺めているだけで楽しいです。 緑色がカメ、オレンジ色がニンジンです。

f:id:kato_robotics:20191016002603p:plain
ビューアの様子

結果

  • 総ターン数：76,196
  • 順位：66位

＊ちなみに、チャレンジスコア（77,777）を超えた参加者は全体の48%らしいので、 私はちょうど真ん中らへんということになりそうです。

一日目

コンテスト開始してすぐに問題パッケージをダウンロード。 コンパイル、実行、Viewerの動作を確認。 その後、サンプルコードのまま提出。

  • 総ターン数：232,221
  • 時間：4.2sec

ビューアを眺めてみると、明らかに無駄が多い。とりあえずの改善点を探す。

  • カメたちの動きがかぶっている
  • あっちこっち行き過ぎている

効率よくエサを回る経路を見つけたら良さそう。 貪欲法とか焼きなまし法とか、いろいろあって良く分からないから全部試すくらいの気持ちでやっていく。

二日目

まずは単純に貪欲法を実装。 カメを一か所に集めてから、 カメ全員が近いエサを順番に取っていくようにした。

  • 総ターン数：100,328
  • 時間：2.9sec。

ターン数が半分くらいにはなった。 ここからどれだけ減らしていけるかどうか。

マラソン形式のプロコンの定石とかあるのかなと思って、 取り組み方をちょっと調べてみたらたくさんでてきたので読む。

読んでみて分かったこと

  • 色々アルゴリズムはあるけど最も重要なのは考察
  • とりあえず貪欲法は強い
  • なんでもメモを取っておくといい
  • ランキングから得られる情報も大事だけど見過ぎるのも良くない
  • 根気も大事

三日目

もっと効率良くエサを回ることができる経路を見つけたい。 ということで焼きなまし法を使ってみたい。 正直焼きなまし法がどんなものだったか覚えていないので、 色々資料をあさりながら思い出してみる。

昔、講義で巡回セールスマン問題を焼きなまし法で解く方法を教わったのだけど、 ほとんど覚えていなかった。

以下の記事を参考。

焼きなまし法のコツ Ver. 1.2（→1.3へ改装中） - じじいのプログラミング

四日目

昔書いたプログラムを参考に焼きなまし法を実装して、 エサを回る最適な経路を求めようとしたけど、 自分の環境で17万ターンくらいかかってしまってだめっぽい。 さすがにこれは無理があった。というか最適な経路ってなんだ。

ふと思いついたけど、 貪欲法で近いエサを順々に辿っていく経路を生成してから焼きなますといいかも。 あと、スタート地点はすべてのカメの中心が良さげ。

もしくは最初に書いた単純な貪欲法で、 エサの高さを考慮したアルゴリズムを考える。

コードを提出したらwarning-errorで落ちた。 原因が分からない。 randが原因かな？ random_deviceはエラーになるらしいけどrandは使える？

次に何をやればいいか、電車の中でいろいろ考えていた。

やっぱり貪欲法で近似解ぽいものを作ってから、 焼きなまし法でさらに経路を改善したらスコアが伸びる気がする。 そんなに大きくは変わらないだろうけど。

あとステージを細かく分けて、 その分割した範囲内で効率良くカメを動かしてみる方法はどうか。

五日目

結局のところ乱数生成は何を使えばいいのだろう。 randでいいのかなと思ったけど、調べてみるとなんか遅いらしい。 あと、質もそこまで良くはないらしい。 XorShiftが早いらしいけどなぜかrandと変わらない。 焼きなまし法の実装もあまり良くないのでとりあえず貪欲法でいけるとこまでいきたい。

再び自分の環境では通るのだけど 提出するとなぜかエラーになる。

#include "parameter.hpp"

を消したら通った。 なんかダメだったらしい。

六日目

ステージを四つに分割して一つの区画ごとをすべてのカメで探索。 カメは一番近いエサを食べていく。

  • 総ターン数：97,221
  • 時間：3.5sec

思ったよりもスコアは伸びなかった。 分割数とエサを回る経路を考えればもっと良くなりそう。

ステージを九分割して真ん中の区画から探索開始。 そこからぐるっと渦を描くように区画を移動しながら探索していく。

それぞれのカメは近くのエサから食べていく。 えさの高さ分だけカメは集まる。

  • 総ターン数：88,938
  • 時間：2.5sec

次に考えること

  • エサの総数によって探索方法を変える
  • 探索順路をいろいろ試して一番いいのを選ぶ
  • ごりごりにシミュレートする

一万とか一気にスコアが上がるとは思えない。 どうしようか。

ちょっとした改善でも数千くらいならスコアを減らせることに気が付いた。

何もしないターンを生み出してしまう処理を見つけたので、 数行書き換えたら総ターン数が四千くらい減った。

  • 総ターン数：84,533
  • 時間：2.4sec

また自分の環境では通るのに、提出後に落ちた。 このエラーを取るために時間をかけるのと、 一から書き直すのどっちがいいのか。 というかもっと細かく通るかどうか確認しておくべきだった。

色々変更しながら確認したら制限時間をオーバーしているだけだった。 前にエラーで落ちたのもこれが原因だったのかも。

七日目

スコアが伸び悩んでいたので、 どうしようかなーと考えていて、 ふと思い出した。

今1位の人はコンテスト初日からスコアが高かった。 ということはおそらく複雑なアルゴリズムではなく、 典型的なアルゴリズムを使っているはず。 （最初はみんな典型的な方法を試すはず）

ということでこれからやること

  • 貪欲法で経路生成
  • 焼きなまし法で改善
  • 高さを考慮したカメの移動

やっぱりローカル環境とサーバ環境では実行速度が変わることもあるらしい。 time関数とかで時間を取得すると遅いとかかな。

八日目

ステージを再現してまるごとシミュレート。 焼きなまし法で最善の探索方法を見つけたい（実装中）。

変更部分だけコストを計算し直すということをちゃんとやれば処理を削減できる気がする。

ステージを18分割してぐるっと回るように一区画ずつ回っていく。 今のところ18分割した経路が一番スコアは良い。

経路改善に山登り法を使っているけど、どこかバグっている気がする。 本来なら総ターン数は計算回数を増やすごとに減るか、とどまるはず。 だけどなぜが増えた。 あと、局所解にはまっている気もする。

九日目

高速化の話。 乱数生成でrandは遅いからXorShiftの方がいいという話を聞いたけど、 そんなに変わっている気がしない。 というか乱数生成よりも重い処理があるのかも。

とりあえずvectorのコピーはかなり重いということが分かった。 コピーしているところを二つ改善しただけで、 倍以上早くなった。

ずっとよく分からないバグに悩まされていて、 シミュレータの実装がおかしいのかと思っていたけど、 変数の初期化を忘れていただけだった。

  • 総ターン数：81,954
  • 時間：38sec

シミュレータは重すぎて100回くらいしか回せないけど、 それでも二千くらい総ターン数を減らせた。

今のところ手詰まり。 もっとシミュレータを高速化させたいけど難しい。

ランキングを見ていたら、 実行時間が一桁秒で載っている人もいたので、 もっとスマートに効率の良い経路を探索できるらしい。

前回や前々回のハル研プロコンで提出されたソースコードや、 そのソースコードの解説を読んでいたら、 ビームサーチという単語を見つけた。

以前のコンテストの記事

chokudaiさんのビームサーチの説明

chokudai.hatenablog.com

十日目

他の用事のためなし。

十一日目

チャレンジスコアが発表された。 77,777は達成したい。

ヒントとしてステージには、 エサが高め、低め、バランス良く、 の三種類あるらしい。

あと自分で確認して分かったのが、 エサの個数は40、60、80,100がある。

このへんに着目して改善できたらうれしい。

十二日目

ソースコードを色々書きすぎてファイルが迷子になった。 応募履歴から提出したコードを見れることを初めて知った。 そこから一番良かったものをコピペ。 gitで管理しとくべきだなって何回か思ってる。

ビームサーチとか焼きなましとか色々やってみて分かったことは、 一気にスコア伸ばせたら嬉しいけど、 実際は地道に少しずつ改善していくのが良さそう。

ステージを18分割してぐるっと渦を巻くように分割した区画を一つずつ回っていく。 その流れにあうようにエサをソートしてみた。

  • 総ターン数：78,587
  • 時間：54sec

十三日目

あと少しでチャレンジスコアに届きそうだったので、 山登り法の回数やシミュレートの回数をいじって越えようとしていたけど上手くいかない。 そこで一度山登り法とシミュレートを行わなかったらどうなるかを調べたら、 チャレンジスコアを超えた。

  • 総ターン数：76,950
  • 時間：3.5sec

山登り法の実装がなんかおかしくなっていたらしい。

十四日目

シミュレートを取り入れた。

  • 総ターン数：76,196
  • 時間：58sec

最終日

ランキングを眺めていた。

終わってから

まずはコンテストのアンケートに取り組んだ。 粗品がもらえるらしい。

その後、Twitterでプロコンに参加した方々の解法ツイートを眺めていた。

思っていたよりは自分が考えていた方針は大きく外れていたわけではなさそう。 だけどだからといってもっとスコアが伸ばせたかというとそれは違うんだろうなーとしみじみ思ってる。 もっと精進しないとランキングには載れなさそう。

おわりに

コンテストのはじめの頃はランキングに載れたらいいな～と軽く考えていましたが、 思っていた以上に参加している方々のレベルが高くて驚きました。 そのため途中からはチャレンジスコアを達成できたらいいな～と目標を変えて取り組んでいました。 結果としてチャレンジスコアは超えられたので良かったです。

コンテスト中は公式のビューアの存在がありがたかったです。 自分が書いたプログラムの結果をすぐに確認できるし、 ビューアのカメの動きを眺めているだけでも楽しめました。

ハル研プロコン2019は様々な経験ができた二週間となりました。 最後まで楽しかったので、 また来年も参加したいです。