たこし++の備忘録

競技プログラミングの備忘録

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

はじめに

3年前から参加し始めたハル研究所プログラミングコンテストに今年も参加しました。 マラソン形式のコンテストに久々に参加できたのと、1年以上ブログを更新しないのは如何なものかと思ったので参加記を残します。 最終結果はまだですが、暫定順位は16位でした。(最終順位はきっともう少し上がってくれると信じてる)

問題

ここから問題の詳細とパッケージをダウンロードできます。 www.hallab.co.jp 前までは2年前の問題は見れなかった記憶があるけど、普通にアクセスできたので 焦ってパッケージをダウンロードしなくていいのかも。

以下問題のざっくりした紹介

  • UFOを操作してみかんを農場から各家にできるだけ少ないターン数で運びたい
  • UFOは二種類存在し
    • 大UFO　みかんを最大40個まで運べる　移動速度が遅い　2機
    • 小UFO　みかんを最大5個まで運べる　移動速度が速い　8機
  • 出来る操作は以下の4種類
    • 農場からみかんを最大まで補給する(農場とUFOが接していないとこの操作は出来ない)
    • UFO間で荷物をやりとりする(中途半端な受け渡しはできず、受け取る側がパンパンになるまでみかんを渡さなければならない。UFO同士が接していないとこの操作は出来ない)
    • 家に配達する(家とUFOが接していないと出来ない)
    • 移動する
      • 移動以外は1ターンに何度でも行うことができ、移動は各UFO1ターンに1回までしか出来ない

この参加記を書くまで、UFOはずっとただの荷物を運んでいると思っていた(ソースコードの変数名もmOfficeだったので)

提出したものはこんな感じで動きます。

f:id:t-pro-6q:20171028224427g:plain

アルゴリズム

提出したコードのアルゴリズムは最終的に多点スタート貪欲に収まりました(正式名称を知らない)

  • 家を適当な大きさにグループ分けする
  • UFO10機を、大UFO１機+小UFO１機の2グループ、そのほかは小UFO１機だけからなる計8グループに分割
  • いい感じに配達する
  • というのを時間が許す限り様々なグループ分けに対して行い、一番よさそうな行動をする

家をグループ分けする

問題文には書いてありませんが、ステージ生成するコードを読むと各ステージに2~3つの街があり、各街は乱数で決めた座標を中心として、半径hogeメートル以内に20軒以上の家を生成するようになっている。 大UFOは大容量なことを考えると、直感的に街に大UFOを送った方が良さそうなので、まずは街の中心座標を推定する。 街の中心座標は大雑把に推定できればいいので、計算時間を考慮して嘘推定した。

  • 各家から半径hoge以内に家が20軒以上あれば、その家の座標を街の中心座標とする

街の中心からhoge以内でない家についても、街に属している家から十分に近い家は同じ街に属しているとしても大きな問題に ならない(どころか大UFOで処理しやすくなる)ので、そういった家も街の一部としてグループ分けを行う。

街のグループ分けが済んだら、残った家を「適当な大きさ」のグループに「適当に分ける」。 「適当な大きさ」のパラメータ値は多点スタートするときに指定。 「適当にわける」は、距離が近いものは同じグループになりやすいように分けました。(もっといい感じに分ける方法がありそう)

いい感じに配達する

どのUFOがどのグループを配達するかを決める。街に対しては大UFOのグループを割り当て、それ以外はグループに属している家の数を考慮して小UFOを割り当てる。 どの家から配って行くかは巡回セールスマン的なものをした方が良くなりそうだが、計算時間をあまり使いたくないというのがあったので、純粋に近いところから 配って行くという貪欲アルゴリズムをしました(絶対良くない)

時間の許す限り繰り返し実行する

変えるパラメータは

  • 街に属している家から十分近い家も街の家とみなすための具体的数値
  • 1つのグループに所属させる家の最大軒数
  • 同じグループに属している家の距離の許容値(離れすぎている家を同じグループとするのは直感的に良くなさそうなので)

の３つ。 これをいろんなパターン生成・実行した結果一番よかったものを出力する

日記

期間中、どの時期に何考えてたかはこんな感じになってます

問題発表日

問題・ソースコードを読む。ソースコードは問題文には書かれていないこととか、曖昧な部分が良くわかるのでとても大事だなと改めて実感。 問題文から、巡回セールスマン問題の雰囲気を察知する。そして二年前も巡回セールスマン問題を題材にした問題で、結構いい順位を取れたことを思い出し、 もしや優勝ワンチャンあるな賞金で何を買おうかといったいつもの妄想を始める。

問題発表日 ~ 1.5週くらい

ビームサーチや焼きなましやその他なんやらといった王道アルゴリズムを試そうとするも、 何を近傍に設定していいのかさっぱりわからず、無駄なコードを大量に生成する。そして全く方針が立たないまま時間だけが過ぎていき、とても辛かった。

1.5週〜最後

とりあえず方針がぶれぶれで全く良くなさそう、最低でもどんぶり欲しい、ということでここに書いた多点スタート貪欲で行こうと決心する。締め切り前5日前に初Submitし、そこからちょくちょくコードを修正したりしてfinish

反省

最初の1.5週間、問題についてきちんと考察せず闇雲にアルゴリズムで殴ろうとしてたのは悪手で時間を無駄にしかしてなかったので、ただのあんぽんたんだった。きちんと考察してからコードを書き始めないと事故ることを学びました(それはそう)。

感想

久々のマラソンマッチだったので、長期間コンテスト特有の楽しさ・辛さとか、マラソン中心の生活になっていくあの感じとかも感じれたのでよかった。マラソンはいいぞ。