Ark's Blog

参加記や備忘録などを書いていきます

ようこそ

第2回 RCO日本橋ハーフマラソン 本戦 参加記

第2回 RCO日本橋ハーフマラソン 本戦 に参加してきました。

rco-contest-2018-final.contest.atcoder.jp

全体の流れ

  • LT
  • コンテスト
  • 懇親会&表彰&解説

ハッシュタグ: #rco_procon

LT

社員さんによる会社紹介や技術紹介のLTがありました。

技術紹介の方では量子コンピュータについての話でとてもおもしろい内容でした。(これ内容喋っちゃダメなんですかね?) 途中、f-algebraとかrecursive schemeとか、圏論の概念が出てきて新鮮でした。最近ちょうど圏論の勉強をしてたので、その圏論を活かせる場面について知れてよかったです。

コンテスト

  • 全2問、4時間のコンテスト
  • 誤提出・再提出のペナルティはなし
  • 再提出には5分以上の間隔を空けないといけない

A ぐるぐる庭園

f:id:ark4rk:20180311174917p:plain:w300

まずはフリップを一切せずに提出。4482点。とりあえず正の得点。

f:id:ark4rk:20180311175057p:plain:w300

遠回りしてくれるように十字つくった。9799点。

f:id:ark4rk:20180311175103p:plain:w300

区分を増やすといいかなと思っていげたをつくった。11246点。 得点は上がったけど、効率的じゃないので別方針を立てることにした。

f:id:ark4rk:20180311175107p:plain:w300

ここで、↑↓↑↓に妖精を誘導できたらいいんじゃないかと閃いてこんな感じに。89677点。一気に上がったので方針良さそう。

f:id:ark4rk:20180311175112p:plain:w300

狭くしてみたり

f:id:ark4rk:20180311175117p:plain:w300

縦・横を切り替えてみたり。このあたりから実際に最短路のシミュレーションをして一番得点が高いものを採用するようにした。134842点。

f:id:ark4rk:20180311175121p:plain:w300

直線じゃなくてぼこぼこさせると、構築時間に影響させない+遠回りできるじゃんと、気づいてやってみた。

f:id:ark4rk:20180311175126p:plain:w300

さらに、ぼこぼこをもっと強化させるともっと遠回りできるじゃんと気づき最終的にこんな感じに。最終スコア353119点。一位の人には遠く及ばないけど、満足した。

B くるくる寿司

問題の概要を理解するのに時間かかってしまった。

とりあえず、D = 1、乱数で文字列Sを生成させて確実に300000点獲得。順位表見ると300000点ばかりだったのでみんなおんなじことしてるなあと思った。

A問題の考察に時間を吸われてしまって、残り時間少ない状態。

  • 乱数で発生した文字列bdcuoac・・・に対し、bbbbddddccccuuuuooooaaaacccc・・・みたいに各文字を連続させる。
  • 例えばdの位置がstart_iだった場合、返ってくるクエリはddcuuuooだったりdddcuoaaだったりと出現するアルファベットの順番は高い確率で保たれる

という考察の元、適当にDの値や連続する文字数を決め打ちした。ただ、これを思いついたのが終了10分前くらいで、焦って提出したらWA。かなり焦った。

バグつぶししててパラメータ調整が不十分なままラストサブミット。338768 点。

300000点を超えることができたものの不完全燃焼。残念。

結果

順位は、A問題11位、B問題26位、総合17位でした。

自分的にはけっこう嬉しい結果。けど、Bでもう少し時間があれば一気に得点が伸びそうだったとか考えたらくやしい。

次回があれば、賞金狙いたいです。

懇親会

コンテスト後は懇親会&表彰&解説でした。

A問題の想定解法が頭良すぎて感動した。

あと、懇親会中のお皿が紙皿でなくて画像のようなものでした。

f:id:ark4rk:20180311184350j:plain:w300

よくある懇親会だと、コップとお皿で両手がふさがったり、机に置かれたコップが誰のかわからなくなったり、みたいなことが起きがちだけど、それを防いでくれて画期的でした。任意の懇親会で採用してほしい。

感想

ラソン形式のコンテスト経験はほぼなかったですが、とても楽しめました。 テスターやビジュアライザがあるおかげで、問題の考察や実装に集中でき、助かりました。

ラソンマッチ、普通の競プロとは違った面白さがあるのでもっとやりたいです。ただ、ドハマリするといろんなものが犠牲になってしまいそうで、困った困った。