RCO presents 日本橋ハーフマラソン 参加記

プロコン参加記 マラソン

ハーフマラソン（走らない）

予選

A19位,B9位で総合8位でした。


やったことが解説の想定とほぼ同じだった。
www.rco.recruit.co.jp

本戦

RCO presents 日本橋ハーフマラソン 本戦 - RCO presents 日本橋ハーフマラソン 本戦 | AtCoder

A45位,B39位で総合46位でした😇
めちゃくちゃ冷えてます

学生10位まで賞金出るって聞いたとき狙えると思ったんですが本戦全然ダメでしたね・・・
さすがに悔しかったので時間をかけて復習していましたが、本戦1位のmamekinさんのスコアが抜けません

A問題

本戦中

クエリあたりの効率が大事な気がしたので、来た客に対して何手で渡せるか求めようとした。
ここで幅優先探索でなぜかいい感じなると思って実装してしまった。
実際の所、いい客には沢山のタンクを使う必要があるので3手程度しか読めない探索では何も出来ない。これは本番後に気づいた。
ここに2時間半費やして、最終的に下から2番目の点数だったので大事故となった。

練習

まず、来た客にたいしてfillとsellだけで売れたら売る、売れないならskipという貪欲を書いた。
これだけで本戦のスコアの1.5倍が出た。(3.4M点)

その後、
・Dの低い客を無視して小さいタンクにchangeを繰り返す(5.0M点)
・客が来る前に大きいタンクにfillしておく(6.2M点)
でスコアが上がった。

今の手持ちで、Dが一定以上の客が来た場合の稼げる期待値のようなものをスコアにして、fillとchangeを使った1手先のスコアの期待値を最大化するようにしたら、点数が7.3M程度に激増した。
1手読みのような凝ったことをしている人はあまり居なくて、changeやfillのルールとしきい値をうまく調整すると同程度の得点が取れる模様。

B問題

本戦中

実際の道路を参考に一方通行とか交差点を駆使すればいけるんじゃないかと思い、一部のマスでは移動できる方向を制限するようなことを考えた。
Aで時間を食っていたこともあって、結局まともな実装ができずほとんど点が取れなかった。

練習

目的地に向かう動きとランダムに動く動きをうまく混ぜるといい感じになるらしい。

・できるだけ目的地に向かっていくが、停止するのを禁止する。
・同じ距離になる場合はランダムに向きを選ぶ
・行動順はランダムに決める
でかなりいい感じに動くことが分かった。

終盤になったら停止を許可してできるだけ近づくといい感じになる。(6.7K点)

ここで引っかかって抜けられなくなってるやつがまだ残ってるので、5ターン中2ターンランダムに動かすと点数が伸びた。(388K点)

それでもまだ引っかかってるやつが残るので、これをスコアを下げずにいい感じにしたかったが面倒そうなので諦めた。

他の方針として、片側に詰めて並べていって最後にバッと戻す方針というのもあって、それも実装してみた。(497K点)

市松模様に並べて動かしていくという方針もあるが、これはめちゃくちゃ難しそう。

この問題の設定、見覚えがあると思って調べた所、Asymmetric Simple Exclusion Processと呼ばれているらしい。

反省や感想

今回は最初に間違った方針で、しかも重い実装に取り掛かってしまったので取り返しのつかないことになった。
まず最初に貪欲を考えるという方針が良いような気がする。
しかし、CODE RUNNERの2回目の予選A(交わらないように直線を引くやつ)のように、貪欲よりも頭の良い解法が圧倒的に良い場合もあるのでそのあたりは難しいなあと思った。
短時間マラソンでは、自信のない重い実装はやめたほうがよさそう。

その他：
・東京駅から徒歩2分、乗り継ぎもなかったのでめちゃくちゃ楽だった
・企業紹介と文章要約アルゴリズムについてのスライド？はどちらも面白かった。（途中で置いていかれた）
・懇親会は主にピザ🍕とフライドチキン🍗