RCO presents 日本橋ハーフマラソンに参加しました

3/20にRCO presents 日本橋ハーフマラソンに参加しました。競プロをやりだしたのが学生じゃなくなってからなので、予選付きコンテストでオンサイトに出ることは半ばあきらめていたんですが、予選でギリギリ引っかかって上げてもらいました。感謝です。

予選

A問題 Multiple Pieces

最初山登り的なものを実装しようとするが、実装が難しく最初の提出まで1時間かかった上に点数が泡を吹くほど低い。ただ低すぎたおかげで逆にそこまでの方針を捨てる踏ん切りがついて、ごくごく単純な貪欲で書き直したら点数が10倍くらい上がってそこそこの順位に。具体的には「全マスを大きい順のpriority queueに突っ込む→順に取り出して周りの大きいマスと貪欲にくっつけていく」という感じ。単純すぎて制限時間10sのところ6msで終わってしまう。このあたりで3時間中の1時間半くらいが経っていたので一旦よしとしてB問題へ行くことにする。

B問題 Food Collector

今度は時間をかけすぎたら終わりなのでA問題の教訓を活かしてとにかくまずは単純な方針からやっていこうと考える。ということで「初期解として完全ランダムにターン数分の移動命令を生成 → 何ターン分かの移動をランダムに変えてシミュレート → よくなるならその解に乗り換える」という山登りを10秒いっぱい回す。割とまともな点数が出て一安心し、残りの時間はこの方針をベースにして逐次改善していこうとしたが大して変わらず終了。

結果

A問題50位＋B問題73位で、全体49位。だいぶ微妙でしたが上位にオンサイト不参加者も何名かいたようで、「学生の上位40名を抜いたあとの上位10名枠」の9番目につけてギリギリ本戦に通してもらえました。

本戦

開始前

開始までは後ろの方に座ってぼやぼやしながらオンサイトの雰囲気を味わった。あと参加賞ということでパーカーをもらった。競技プログラミングで衣服をもらうのがひそかな目標だったのでとても嬉しかったです。あと気がつくと真後ろの席にAtCoderの社長が座っていてヒョエ〜〜〜〜となった。あと業務の説明を聞いてたのしそ〜〜〜となった。

A問題 石油王Xの憂鬱

問題文を読んだだけで変な汗が出た。めちゃくちゃ苦手な算数パズル（天秤をn回使って偽物の金貨を特定してくださいみたいな類のやつ）っぽかったからである。ちょっと考えるけど取れる行動も多いし方針すらまったく立たないのでさっさとB問題へ。

B問題 日本橋大渋滞

こっちはA問題と比べるとだいぶ素直な印象を受けた。まず何も考えず全車を目的地に向かわせる貪欲解を書いたところ、0だけの自明解(3331点)をちょっとだけ超える(4613点)。ここでビジュアライザを見てみると、どうやら車が多すぎてほとんどの車がまともに動けてないことがわかった。要するにこれをどうにかする問題なんだな〜〜〜とやっとこの段階で気づく。とにかくどこかで回り道させないといけないので、ある車が目的地に近づけない場合はランダムな移動を行うようにするとちょっと上がる(6513点)。たしかこの時点でB問題だと2位か3位を取れていてかなりウキウキしたが、1位の人を見ると60万点とかいう異次元のスコアを出していて最初真剣にバグか？？？？？と思った。さすがにここまでスコア差がつくということは根本的にもっといいやり方がなんかあると思ってスコアの計算式をよく読んでみると、かかったターン数で割り算が発生しており桁違いの差が付くならこの辺が鍵かなあなどと考える。自分の解を省みると制限ターンいっぱい使っていたのでこれは明らかにダメだろうと思い、解を得た段階でスコアの動きをシミュレートし一番よいターンで打ちきって出力とすることしてみる(12478点)。数十万のオーダーには全然届かないが順位的にはかなりよかったのでB問題はここで一旦やめにしてA問題へ。

A問題ふたたび

相変わらずアイデアは一切なかったが、ここで予選A問題の教訓（そんなんでいいの？という単純な方針でも割と点数取れることがある）を思い出し、めちゃくちゃ単純なやり方が何かないか考え始める。そこで「自分が持ってるどれかの容器1個とまったく同じ容量の注文を出してきた客には売る、そうでなければパス」というやり方で出してみたところ、とりあえず正の点数を得ることができた(154272点)。上位陣は700万とかで争っているので順位的にはアレだけどこれでだいぶ落ち着いた。ちょっとB問題で試したいことが浮かんでもう一回戻る。

B問題ふたたび

これまでの解答だと各ターンで車の移動を考えるとき与えられたインデックス順に動かしていたのをランダムな順番にするよう変更したらスコアが4倍くらいになった(52297点)。同じ順番で動かしているとデッドロックがとれづらいとかそういう理由だろうか？ともかく今度こそA問題にちゃんと向き合うことにする。

A問題みたび

さっきの超単純貪欲からもう一歩進んで、「自分の持ってる容器を足して作れる数字の注文が来たときは売る、そうでなれけばパス」という方針にすることを考えてみる。手持ちの数列から作れる和を求めるのはDPでよくあるやつだからこれならできる！と思い実装を始める。バグを仕込みまくって泣きそうになりながら3, 40分くらいかけてやっと書き上げて提出(5576164点)。これでA問題もオーダー的にはまともなスコアが出たので、あとはここからの改善だけを考えることにした。で思ったのが同じ和に対して組み合わせが複数通りあるときどの容器を売っぱらうかは大事だなということで、dpつくるとき保存しておく組み合わせの条件をいじったりしてたら結構よかった。いろいろあって最終的には100万点底上げできた(6657203点)

結果

A問題が11位、B問題が7位の合計18で全体6位（提出者48名）でした。まさかこんな順位を取れると思ってなかったのでマジか〜〜〜ウレシ〜〜〜〜〜と思いました。いい大人だったのでお金はもらえませんでした。（事前に学生以外賞金出ませんという連絡があってそのときは自分には関係のないことだと思って気にも留めていなかったということを思い起こすと、それが関係ある順位に入れたということでむしろもらえないことが嬉しくもあった（複雑な心の動き））

まとめ

正直今後オンサイトに出れる機会があるかと考えると自分の実力だとなかなか難しいところがあると思うので、今回は本当に良い経験になりました。このような機会を与えてくださったみなさまに感謝します。あといまぜんぜんプログラミングとか関係ない仕事してるので転職してコード書く人になりたいです。PythonとC++とD言語をよく書いています。何とは言いませんがよろしくお願いします。