競プロ始めました-kaede2020-

競技プログラミング初心者向けのブログです

RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜参加記

0.はじめに

初めまして。もしくはお久しぶりです。競技プログラミング歴1年半のかえでです。

今回参加した「RECRUIT 日本橋ハーフマラソン 2021〜増刊号」は、2021年9月5日18時から、9月12日18時までの期間に開催されていました。ヒューリスティックコンテストと呼ばれるコンテストの特徴は、期間が長いことと、最適解がなく、できるだけ良い解に近づけていくことを競うコンテストだということです。

初心者が参加するのはなかなかハードルが高いと思うのですが、じっくりと考える時間があることや、何回もコードを書き直す時間があるところなどは、初心者にとっても取り組みやすいと思います。ヒューリスティックコンテストは、いろいろな方法を試してスコアが良くなっていくところがとても楽しいので、ぜひまだ参加したことのない方にもチャレンジしてみてもらいたいなと思っています。

私はまだアルゴリズムやデータ構造を少しずつ勉強しているところで、知っている知識はたいしたものではありません。実装力はまだまだ足りていない状態なのですが、それでもこんなことを考えて、こんなことをやって、こんな得点が出ましたとお伝えすることで、その楽しさが少しでも伝われば良いと思っています。

長くなりますが、よろしければどうぞ最後までお付き合いください。

その前に一つだけ。この記事を公開する前に、結果が出ましたのでお伝えしたいと思います。結果は168位/519人中でした。これはうれしい結果でした。

f:id:kaede_2020:20210915200208p:plain

AtCoderヒューリスティックコンテストのレーティング(β)も1320に上がりました。
1.問題の概要

・16×16区画の農場がある。

・1000日間の間、16×16区画の農場に野菜が生え、枯れていく。

・野菜の数は5000個で、一定期間生えた後に、枯れるか、収穫することで消える。

・野菜の収穫には収穫機を使い、野菜のある区画に収穫期を置くことで収穫できる。

・野菜を収穫すると、「(野菜の価値)×(収穫機と連結している収穫機の数)」の資金を得る。

・目的は1000日後の資金を最大に増やすこと。

・入力ケースが与えられるので、1000日間の間に取る行動を、「収穫機を買う」、「収穫機を移動する」、「パスする」の3種類から選んで、行動する区画の位置を出力する。

・移動は、収穫機1台を選んで、収穫期の置いていない区画であれば盤面上のどの区画にも移動することができる。

・資金は1からスタートする。

・収穫機の購入に必要な資金は、最初は1だが、2台目以降は、「(持っている収穫機の台数+1)の3乗」の資金が必要となる。

f:id:kaede_2020:20210913090628p:plain

16×16区画の初日の農場。数字がある区画は野菜が出現中(数字は初日の野菜の価値)。オレンジの四角は現在位置を表しています。

2.最初の提出

さて、正の得点を得る、一番簡単な答えは何でしょうか。

1000日間何もしないことです。最初の所持金が1なので、これを提出すると、テストケースが50ケースあるので、スコアが50になります。

しかし、私が最初に提出したスコアは、23万9841でした。一体何をしたのでしょうか。

AtCoderの問題文より引用します。

f:id:kaede_2020:20210913084315p:plain

そうです。配布物の中にサンプルコードがあったのです。

「テスター類」からダウンロードしたzipファイルを開くとこんな感じです。

f:id:kaede_2020:20210913084915p:plain

最初にAというフォルダが出てきます

f:id:kaede_2020:20210913084945p:plain

Aを開くと、testerとvisualizerという2つのフォルダが入っています

f:id:kaede_2020:20210913085252p:plain

testerフォルダを開くと、sample_submisshion.cppとsample_submissino.pyの2つのサンプルコードが見つかります

このサンプルコードを私は提出したのでした。このサンプルコードはとても親切に書かれていて、初心者に優しいコンテストだと思いました。

さて、問題を読んだ最初の印象を書きたいと思います。

まず考えたのは、アメーバみたいに広がるか、へびみたいに動くような収穫機の動きです。また、最初は野菜の価値が低く、終わりに近づくほど高くなるので、終盤に向けて、できるだけ早く収穫機を増やし、野菜を多く収穫でき、かつ高額の資金を得ることのできる状況を作ると良さそうだと思いました。何となく、ゲームのキャラクターのレベル上げが頭に思い浮かびます。最初は自分も弱く、敵も弱いところから始まり、自分が強くなると、強い敵も倒せるようになるといったイメージです。収穫機の資金が、1、8、27、…とだんだん高くなっていくので、できるだけ効率よく次の野菜を収穫できるようにしたいと思いました。しかし、最初からこれを実装する力はないので、サンプルコードから少しずつ改良することにしました。

ここでサンプルコードの中身がどうなっているのかを見てみましょう。先ほどのtesterフォルダ内のREADME_ja.htmlを開きます。

f:id:kaede_2020:20210913142446p:plain

サンプルコードの内容

サンプルコードでは、資金があれば収穫機を買えるだけ買ってくれるようになっていました。区画のその日から最終日までの、野菜の価値の合計を計算して、一番資金を多く得られるところを選んで、収穫機を購入します。しかし、収穫期の移動はしません。

テストケース(input_0.txt)の最終日の資金(money)は7187でした。これを提出し、23万9841のスコアを得ました。

f:id:kaede_2020:20210913142750p:plain

サンプルコードで出力したinput_0.txtの最終日をビジュアライザで見たところ

テストケース(input_0.txt)に生える野菜の各区画の価値の合計を計算してみました。

f:id:kaede_2020:20210913163134p:plain

input_0.txtの区画ごとの野菜の価値を合計した表

合計してみると一番多い区画で3150、一番少ない区画で60でした。また、サンプルコードでは、収穫機が連結することがほぼなかったので、倍率は1倍で資金が増えていました。サンプルコードで出力した結果をビジュアライザで見ることで、どのように資金が増え、いつ収穫機を購入したといったことがわかり、考察する際にとても便利でした。
全区画の野菜価値の合計は221250で、5000個のうち約1000個の野菜を収穫するとして単純に5で割ると、たったの44250にしかなりません。一番価値の高い野菜を1区画ずつ収穫するよりも、収穫機を連結して収穫することの方が大事そうだということがここでも想像できました。

サンプルコードでは最終の資金が7187でしたが、20の収穫機を購入しています。その購入代金として44100を使っているので、この想像とも合致しそうです。

3.サンプルコードに移動を追加

提出したサンプルコードが無事ACしたので、サンプルコードで「パス」という行動を選んでいた日に、収穫機の移動を追加してみました。野菜が生えなかったら、その日生えている一番高い野菜のある区画に移動します。

テストケース(input_0.txt)の最終日の資金(money)は64064になりました。そして提出したスコアは214万2504になりました。移動がなかった最初のスコアに比べて、約10倍になりました。

f:id:kaede_2020:20210913170206p:plain

サンプルコードに移動を追加した最終日のビジュアライザ
4.序盤の改善を試みるが失敗

次に行ったのは、序盤の改善です。序盤の資金を効率よく増やせないかと考えました。収穫機の2機目を購入出来たら、取りに行きたい野菜の隣に収穫機を置いて、その後に野菜のあるところに収穫機を置くと、得ることのできる資金が2倍になります。

これは実装してみましたが、良くなるどころか同等以下な感じでした。2倍にできても2手かかっているので、差し引き0といった感じでしょうか。

では3機で3倍にしたらどうかと思いましたが、「3日分それぞれ最大の野菜を収穫してまわる」のと、「3倍して価値がそれを上回る野菜があるか」を比較してみても、やっぱり3手かかるので、序盤の野菜の低い価値では、そんなに得をしなさそうだと思いました。ここで序盤の改善はやめることにしました。

5.終盤に収穫機を並べてみる

今度は終盤の改善に移ります。終盤に生える高い野菜を調べて、それを高額で収穫できるように収穫機を移動して並べてみました。

テストケース(input_0.txt)の最終日の資金(money)は271020、提出したスコアは1264万5234になりました。収穫機を連結する前に比べて、約6倍になりました。

f:id:kaede_2020:20210913171740p:plain

終盤に収穫機を並べてみました
6.収穫機をへびのように連結したまま動かす

連結した方が良いというのがわかっていたので、収穫機で野菜を得る際は、収穫機をつなげたまま移動したいと思いました。終盤になったら、野菜を収穫した後、次の目標に向かって、収穫機を連結したまま移動するようにしました。うまく実装できなくて、随分と時間がかかりました。
テストケース(input_0.txt)の最終日の資金(money)は380165になりました。提出したスコアは1623万5659になりました。終盤に収穫機を並べた提出と比べると約1.3倍になりました。

ここで、あれ、思ったほどよくならないなと思います。あらためてビジュアライザを眺めます(下の動画1)。かわいい動きにしばし心がなごみます。どう見ても最短距離ではなく動いていて、思っていた挙動とは違います。じゃんけん列車が頭に思い浮かびました。この結果を見て、これを改善していってもスコアを上げるのは難しいだろうと思いました。それは、自分自身、次にどこに行くかの計算が大変で、実装が追いついていなかったからです。

9月5日から始まったコンテストは10日の朝を迎えていました。コンテストの終了は12日18時です。ここで考えていた案を全てをあきらめることにしました。

f:id:kaede_2020:20210915224006g:plain

動画1:収穫機を連結した状態で動かす
7.収穫機を固定する

ここまでがんばってきましたが、自分にとって難しかった点がいくつかあります。

・収穫機を連結した状態に保つこと。

・連結した収穫機のどれが、どこにある野菜を収穫するのかを決めること。

・収穫までに日にちが空くと、その日収穫できる野菜の盤面が変わってしまうこと。

すなわち、「収穫機を連結したまま、次に取りに行く野菜のことを考え、どの収穫機を動かすか」を考えて、コンテスト終了までに実装を完了するということに、現実味がなくなっていました。

あらためて別の方法を一から考えます。方眼ノートを出してきて、16×16のマスを作りました。下図が、実際にコンテスト中に書いていた手書きメモです。うまく収穫機を配置すれば、少ない動きで、連結したまま野菜を取れるのではないかと考えました。

f:id:kaede_2020:20210914070746p:plain

考察メモ

まず、最終的には全面に動けるようにしたいと思いましたが、目標は3手までの範囲の野菜を収穫に行くことにしました。最初に1手で行ける範囲の野菜を収穫にいくように実装します。収穫機は固定が19機、フリーが1機といった盤面を考えました。800日までは収穫機を買うことにしたので、まだ買えそうなら適当に連結して並べることにしました。

テストケース(input_0.txt)の最終日の資金(money)は554863になりました。提出したスコアは2818万8517になりました。

f:id:kaede_2020:20210915223714g:plain

動画2:収穫機を固定する
8.固定した収穫機で最終提出を行う

思った以上に良いスコアが出て、テンションが上がります。

ここまで、シンプルな実装にしたことで、やっと、固定した収穫機のまわりに隣接する価値が高くなる野菜を収穫できるようになりました(下図1:1手で取りに行けるところ)。

黄色の野菜を収穫すると、13×9(連結した収穫機の数)=117の資金を得ることができます。これは1区画で収穫する野菜の20よりも価値が高くなります。

f:id:kaede_2020:20210916054850p:plain

図1:最大価値のある野菜よりも連結して価値が高くなった野菜を収穫できた

ここからは、固定する収穫機の位置を変えてみたり、2手で行けるところまで野菜を収穫できるようにしました。また、何日目まで収穫機を購入するかとか、収穫機を何台購入するかといったことを試してみたりしました。

最終的に800日まで収穫機を購入することにし、約39台まで収穫機を購入していました。

f:id:kaede_2020:20210916055728p:plain

楽しくなってきて、改善しては提出を続けているところ

最後の提出でのテストケース(input_0.txt)の最終日の資金(money)は263万9920になりました。提出したスコアは1億3024万4779になりました。

f:id:kaede_2020:20210916060647g:plain

最終提出(input_0.txtでのビジュアライザ)
9.スコアまとめ

初日スタートからの提出スコアを下に書きました。最初の提出に比べると、最後の提出ではかなりスコアを上げることができました。

  • 23万9841(最初の提出:サンプルコード)
  • 214万2504
  • 1264万5234
  • 1623万5659(最初の案を捨てたポイント)
  • 2818万8517

   (中略)

  • 1億3024万4779(最終提出)
10.最後に

コンテスト終了後は、様々な方法でこの問題に取り組んだことをTwitterで知ることができました。また、上位の方が50機近く収穫機を購入しているのを目にして、トップ層の収穫機はLv50、自分はLv39だったなと考えたりしていました。キャラクターのレベルに置き換えると、そのスコア差を素直に納得できたのでした。

相変わらず、マラソンらしいことは何一つできていない自分です。それでも、テストケースを100個生成したり、改善した後に提出をする前には、毎回100個のテストケースを試したりするようになりました。インプット、アウトプットをテキストファイルで行うといったこともできるようになりました。(それでもシステムテストで1000ケースを実行したら、10REしたので、もっと試さないといけないということを今回学びました。)

前回、2021年8月28日の14時から18時に行われた「RECRUIT 日本橋ハーフマラソン 2021」に参加したときには、思うような結果が出せませんでした(結果は422位/478人中)。出力がおかしいと気づいたものの、間違えた箇所を見つけられず、自分のしたいことを全然書けないまま終わってしまいました。コンテスト終了後には、本当に悔しくて情けなくて、涙があふれて止まりませんでした。そのことで、自分がどれだけヒューリスティックコンテストのことを大好きで、もっと自分はやれるはずだと思っていることに気づかされたのです。

これからもマラソンと呼ばれるヒューリスティックコンテストにはどんどん参加して、もっともっと強くなって、その楽しさを伝えていけたらいいなと思っています。泣くほどつらい思いをするならやめた方がよいのではないかと思う人もいるかもしれませんが、元々感情の起伏が激しくて泣き虫なタイプなので、問題ありません。そして、ものすごく負けず嫌いなので、泣いたまま去っていくということはまずないと思います。

これで、今回の「RECRUIT 日本橋ハーフマラソン 2021〜増刊号〜」の振り返りは終わります。長くなりましたが、ここまで読んでくださった方、本当にありがとうございました。そして、もしこれを読んで興味を持ってくれた方がいらしたら、ぜひ私と一緒にコンテストに参加してみませんか。

f:id:kaede_2020:20210913185518p:plain

コンテスト中の考察メモ(左上から右下に向けて改善を行っている)