RCO presents 日本橋ハーフマラソン本戦の感想

参加しました。オンサイトコンテストに参加するのは初めてでした。
結果は28位と微妙なポジションでした。Aは10位となかなかよかったのですが、Bが自明解を超えられず43位とほぼビリだったのが痛かったです。
初のオンサイトコンテストということで緊張し、またとても疲れました。けど楽しかったです。

会場入り～コンテスト開始前

コンテストはグラントウキョウサウスタワー 41F スカイルームCという場所で行われました。
ビルに入るとガラス張りのエレベータが何基もあって「オシャレなとこだなあ」と感動しました。
それで受付に行って会場に入ると既に席がほとんど埋まっていました。13時までに来いって言われて、13時ちょっと過ぎについたので妥当ですね。
正直言うともうちょっとゆったりしてるのかなと思ったら割とギッチリした感じでした。でもお菓子と飲み物がいっぱいあったのはよかったですね。
後太っ腹なことに参加者全員にパーカーがプレゼントされました。XLとちょっと大き目なサイズしか残ってなかったですが。

少しするとRCOの人のLTが始まりました。何か業務が競プロの問題に似てて面白いので競プロ強い人は是非入ってください！　みたいな感じでした。
内容は正直あまり理解できていないです。（何かセッティングでわたわたしててあんまり集中して聴ける感じでは無かったのもあります）

なんかコンセントが上手く刺せなくて隣の人に代わりに刺してもらいました。あのときはありがとうございました。

コンテスト開始～終了

14時からコンテストが始まりました。
私はとりあえず問題Aの問題文を読むことから始めました。

A: 石油王Xの憂鬱 - RCO presents 日本橋ハーフマラソン本戦 | AtCoder

前もって告知されていたリアクティブ形式の問題ですね。
fill, move, change, pass, sellなど１ターンあたりに出来る行動が多くてややこしいのと利益が二乗で増加していくことがポイントですかね。
二乗で増加するので小さい容量の客は相手にせず、その時間は空のタンクを埋めるなり、小さいタンクをchangeしたりするのに使ったほうがよさそうです。
そして出来るだけ大きい容量の客に対応できるようにするほうがいいんじゃないかなーという感じです。
あとmoveは使いにくいのでmoveは使わない方針にしました。上手く使えば対応幅が広がっていい感じになったりしそうですけど。

ただ方針があまりちゃんと固まってなかったのと結構めんどくさそうなので、実装は後にして次にB問題を読むことにしました。

B: 日本橋大渋滞 - RCO presents 日本橋ハーフマラソン本戦 | AtCoder

こっちはとりあえず「動かさずに終わる」という自明解があるので、とりあえずそれを提出しました（L = 0にできるのを見落として、L = 1にしてしまっていますが）
ここで初submitになって、とりあえず順位表を見てみると20位くらいになってました。まだ提出していない人が多かったですね。Aは既に600万点台が何人かいた気がします。

それでB問題は自明解は簡単に出せるけど、本格的に解くのは難しそうだなあ、と認識したところでA問題の実装に戻ることにしました。
実際に書いて提出したコードがこちらですね。

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

これを提出したのがコンテスト開始から1:30経った頃ですね。
ソースコードのコメントにあるように、

小さいバケツは規定値以上になるまでチェンジしてから本処理に入る
Dが規定値(cl)未満であれば、その客は無視して空のタンクをfillする時間に使う、全部fillされたらpassする
Dが規定値(dl)以上であれば、2^8の総当たりでそれを作れるか確かめる、作れるなら出来るだけ短い時間で作れるものを選んで作って売る、作れないならその客はpassする

という感じです。「Dが規定値以上だけど作れないならpass」は「fillする時間に使う、全部fillされたらpass」に変えたほうがいいみたいですね。
Aは実はこれでほぼ終わりで、後はdl, clのパラメータをチマチマ変えて出したりしてました。

それで残りの2時間半ぐらいほぼBに使ってたわけですけど、それでも自明解を超えられなかったですね。
初めは何か一斉に動かすとめんどくさそうなので１台ずつ適当にゴールに近づけていって動けなくなったら終わりみたいな方法でやってたんですが、これだと手数ばかり伸びてP_Dがほとんど減らないので
スコアがどんどん落ちて行っちゃうんですよね……

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

「１台ずつ動かす」っていうのがやっぱりダメなんでしょうね……効率が悪すぎなんだと思います。

それで'-RLUD'をK個並べる全ての通りを試して一番スコアが伸びるやつを採用していくっていうやり方を思いつきました。
ただこれは5^K通りあるので１回動かすことすらままなりません、どう考えても無理ゲーです。なのに5K通りだと勘違いして必死に実装してました。
それで動かす段階になって「終わんないな……」ってなったところで計算量の見積もりの間違いに気づいてもうダメだってなって終わりました。
「計算量O(N^K)をO(NK)だと勘違いする」ってなかなか酷いですね……

まあ何か間違いに気づいてからもいろいろやってたんですが、案の定同時に動かすとぶつかったりするバグが出てダメでした。私には無理です。

コンテストの様子は、皆結構４時間座りっぱなしで集中してたようです。
私は集中力が無いので、しばしばトイレに行ったりお菓子を食べに行ったりしてました。
あと、割とギッチリしてて筆記したりするスペースがあんまり無かったので、バインダーを持って行ったのは正解だったと思います。
バインダーがあるとメモが取りやすくてよかったです。手書きメモ派の皆さんは、オンサイトコンテストにはバインダーを持っていくといいと思います。

コンテスト終了～懇親会

コンテストが終わると懇親会がありました。
懇親会中に解説もあって、Aはだいたい私のような方針でやるのが正当っぽかったです。他にも工夫のしどころはあるようですが。
Bは何か貪欲に目的地に向かわせようとすると真ん中で固まっちゃってダメなので確率的にあえて目的地から離すように動かすといい感じになるとのことでした。
後は市松模様を作ってから車を目的地にぴったりつくようにするとできるとか、左端に寄せてから一気に全ての車を目的地に動かすとか、様々な解法があるようでした。
実際にビジュアライザを見せてくれて面白かったです。ビジュアライザで分かりやすく目に見えるとやっぱり面白いですね。

後は何か適当にピザとフライドチキンをたくさん食べて帰りました。
初のオンサイトコンテストとのことで不安もありましたが、楽しかったです。
主催のRCOさんありがとうございました。次回があれば、またよろしくお願いします。