見出し画像

水コーダーの私がAtCoderで史上最高点を取った話

にゃにゃん(山名琢翔)

水色タッチコーダーと申します

こんにちは、にゃにゃんです。私はものづくり以外にも「競技プログラミング」という競技を嗜んでいます。競技プログラミングは、コンテストに参加してアルゴリズムや数学の問題をプログラミングで解き、得られる点数を競う競技です。

コンテストでの成績に応じてレートがつき、レートには段階的に色が決まっています。

私の腕前はレートで「水色タッチ」程度です。これは競技プログラミング界隈で超有名なchokudaiさんいわく「水色はかなり優秀です。普通に企業とかで超優秀って言ってるプログラマが居た時に、半分くらいはこのランクになると思います。」というレベルです。

私のレート推移です。あれあれ？最近レートが下がっていますね。。。。

画像2

さて、この記事を書いている時点では未来の2020年11月7日に「HACK TO THE FUTURE 2021 予選」という名前のコンテストがあります。私は今このコンテストで上位に入るべく猛特訓をしています。そんな中とてもびっくりなことが起きたので記事にしておこうと思います。

マラソンとは

HACK TO THE FUTUREというコンテストは俗に「マラソン形式」と呼ばれる形式のコンテストです。普通のコンテストは100分くらいが一般的なのですが、このコンテストはなんと8時間ぶっ通しでやります！！

そして、普通のコンテストは「最適解が見つかる」ことが保証されていますが、マラソンでは最適解が見つかるとは限らない問題を解きます。例えば「～～をできるだけ小さくせよ」という問題だったら、「これがあり得る最小値です！」と断定できないような問題が出るということです。

今回挑戦した問題

私は今回HACK TO THE FUTURE 2018 本選の過去問を解きました。こんな問題です(抜粋)。

高橋君は、新たな惑星を発見しました。この惑星では、植物「ツカモ」がよく育つことが分かっています。ツカモを出来るだけ多く育てましょう！


とは言っても実際の植物を育てるのではありません。擬似的な植物「ツカモ」はかなり単純にモデル化された架空の植物です。

植物「ツカモ」の育つ特性(こんな規則で繁殖する、など)と、主人公高橋君のできる行動(ツカモを植えたり収穫したり)が与えられるので、高橋君の行動をなるべく最適に近づけて植物「ツカモ」をいっぱい収穫することを目指します。

難しそうですね。はい。難しかったです。

解いた。

この問題を実際に8時間かけて解いた結果がこちらです。

画像3

何やらごちゃごちゃ書いてありますが、重要なのは得点です。9728845点でした。これは過去問が実際に行われたコンテストで取ればなんと9位に入れる点数です。頑張りました。私の競技プログラミングの実力は「優秀」程度で、「超優秀」ではありません。そんな私が9位という順位を叩き出せたのです。本当に嬉しかったです。

翌日にも解いた。

8時間かけて問題を解いた翌日、スッキリした頭でもう一度問題を解いてみました。その結果がこちらです。

画像4

前日の倍以上の点、20478919点を取れました。これは本番なら4位に入れる点数です！！自分でも信じられません。

何が勝因だったのか

まず最初に考えられることは、私は普通のコンテストよりもマラソンが得意そうだということです。実は先程お見せしたレートグラフにはマラソンの結果が反映されません。普通のコンテストでのレートなのです。

次に考えられるのは問題が自分に合っていたことです。私は正解が一意に定まらない難しい問題について、「こうなったら嬉しいよね」というような方針を立てるのが比較的得意です。今回の問題はその感覚が大いに役立つものでした。

2020年11月追記

この記事を書いたあともこの問題に挑戦し続け、ついに人類最高点を更新しました。提出結果はこちらです。最終的な得点は94337656点となりました。実際にプログラムが動いている様子は以下のツイートでご覧いただけます。


問題を解く方針(4位相当の点数のもの)

方針の解説です。時系列に沿って思いついたことを列挙します。ここからは問題の解説なので、問題文を読んでいることを前提とします。まだの方はこちらから

https://atcoder.jp/contests/future-contest-2018-final-open/tasks/future_contest_2018_final_a

・ツカモは育ててしばらくすると岩になってしまい面倒なので、とりあえず最初からツカモを育てるのは控える

・最初は労働力を増やすと良い(一度に収穫できるツカモが増えるので)

・ツカモの収穫にはワープ口の周りに十字の形で道を作ると収穫にかかる労働力が減らせそう

・最初労働力を効率よく貯めるためにお金を増やす必要がある。道で区画を作って狭い区間でツカモを完全にコントロールして栽培するとお金がいっぱい貯まる

以上です。全部を実践するとこんな感じで盤面が進みます。

序盤。狭い区間でツカモをコントロールしながら栽培・収穫してお金を貯めつつ労働力を増やす

画像5


中盤。ツカモを全範囲に解き放ち、お金を貯めてワープ口、及び十字の道を作る

画像6


終盤。一部のツカモが岩になってしまうが、ワープ口周辺のツカモは岩にならない。収穫量がどんどん増える。

画像7

まとめ

ここまで読んでくださった方は稀だと思います。ありがとうございました。HACK TO THE FUTURE 2021 予選の本番でも頑張ります。

この記事が気に入ったらサポートをしてみませんか？