tsukammoの収穫記

上下左右の更地にアルゴリズムを

第4回 RECRUIT 日本橋ハーフマラソン に参加しました。

下記の日時に開かれた競技プログラミングコンテスト、AtCoder「第4回 RECRUIT 日本橋ハーフマラソン」の備忘録です。

  • 予選：2020/02/15(土) 19:00 ~ 23:00 (240分)
  • 本戦：2020/03/07(土) 14:00 ~ 18:00 (240分)

f:id:tsukammo:20200326210327j:plain
第四回ハーフマラソン景品

結果

予選：1/525位、本戦：57/76位でした。※有効回答者のみカウント。
予選は生まれて初の優勝 & 初の本戦進出となり、嬉しかったので記念に参加記を書きます。

予選：考えたこと・やったこと

前日の2/14(金)にDevSumiに登壇したため睡眠不足状態でした。睡眠を補給すべくお昼寝を計画。コンテスト中のガソリンとしてチョコレート・クッキー・グミ・オレンジジュースを買い込んだ後、紅茶を飲みカフェインによる90分後の覚醒期待してベッドへ。

案の定寝過ごして、起きたら19:00時ジャスト。焦った状態でスタート。

A問題に取り組む(19:00～20:00)

眠気覚ましにオレンジジュースを一気に飲み、A問題を開く。寝起きで目の焦点が合わない。 ルールを読んで、ブロックを積み重ねていく問題だと理解したので、とりあえずビームを打っておけば良いと理解。大きく詰まらずに実装ができ、pythonのtesterで動作確認してsubmit。

A問題では3位、最高の滑り出し。初の本戦出場か？と期待が止まらない。

B問題に取り組む(20:00～22:30)

ひとまずA問題は正の点数が得られたのでB問題を見る。これは重そう。。。 全マス目と塗れるマス目が同数なので、無駄塗りができないと気付く。また、小さな塊は塗るマス目が足りないことが見えたので、どれだけ効率的に塊に色を伸ばすかの問題だと理解。

f:id:tsukammo:20200326213621p:plain
B問題sample1のvisualizer

ここまでで1時間経過、少々焦ってくる。 できるだけ早く各色の塊に到達するために、最短経路を考える。グリッドの最短経路といえばDijkstra法。だが、5マスずつ進む特殊な移動のため、めちゃくちゃバグる。 B問題0点という未来が見えながら、比較的落ち着いて実直にデバッグ。1時間かけてなんとか解消。コンテスト終了まであと1時間。

時間が無いので到達後の色塗りは貪欲で適当にやる。testerで点数が得られたのを確認してsubmit。心臓がバクバク。

上位に食い込んだことを喜んでいたが、順位表を間違えて見ており、この時点で1位なことに気付いていない。

A問題を詰める(22:30～23:00)

A問題の順位がかなり落ちていたので、詰める余地があると考えて残り時間を割く方針に。

  • ブロックを敷き詰めていった最後に行が揃ってないと点数が入らないのでピッタリ入るよう改善。
  • ブロックの落下先は行しか点数影響がなく、列は関係が無かったので左詰めにして状態数を減らすよう改善。
  • 実行時間に余裕があったので、ビーム幅を調整。

そしてコンテスト終了。

B問題が1位を維持したのと、A問題を詰めたのが効いて1位。A問題を詰めて無かったら1位を確実に逃していた接戦でした。対戦ありがとうございました！ f:id:tsukammo:20200326220437p:plain

本戦：考えたこと・やったこと

コロナ影響でオンサイトイベントが消失。おのれ。

B問題に取り組む(14:00～17:00)

寝坊しなかったので、まずはAとBをそれぞれ確認。Aは軽そうだったのでBに取り組む方針に。同一文字を連続でできるだけ取るのが重要だと理解したので、格子状に連結する最大の文字を見つけ、任意のマスに壁を置いて回収していくことに。バグを取りつつそれなりに実装していったが、どうやっても時間的に十分な点数が取れる実装に届かないことが見える。

submitは義務(17:00～18:00)

諦めてB問題をsubmit。正の点数を取る。

A問題も、とりあえず時間内に取れる自明解をsubmit。対戦ありがとうございました。。。

f:id:tsukammo:20200326221146p:plain

振り返り

AtCoder定期コンテスト(アルゴ)力が大きく劣る私は実装速度が弱点で、過去のハーフマラソンでも全く結果を残せていませんでした。 直近1年間はコンテスト出場頻度も落ち、特にマラソン系コンテストはtopcoder MMのプラットフォーム変更以降全く出ていません。 そのような中で今回の良い結果を得られたのは、現在マラソンを仕事にできているからではないかと思っています。

「仕事 = 精進」

最後になりましたが、このようなコンテストを開いてくださったリクルートと中の方々、本当にありがとうございました。来年以降も可能な限り参加し続けます。