Code Weekend #1参加記 - 競プロ始めました-kaede2020-

0.はじめに
1.参加登録をする
2.コンテスト開始
3.順位表
4.問題の概要
5.最初の提出
6.正の得点を得る
7.25個のテストケースで正解する
8.追加のテストケース
9.評価関数の改善
10.テストケースの特徴
11.途中経過
12.追加のテストケース用のコードを書く
13.TEST1で満点を取る
14.ビジュアライザを見ながら改善する
15.終わりに
16.最終結果

0.はじめに

はじめまして、もしくはお久しぶりです。競プロ歴約4年半のかえでです。

今回は2024年6月8日午前6時から始まった48時間コンテスト、Code Weekend #1に参加しました。Code Weekend は今回新しく始まったヒューリスティック・コンテストです。ICFPCもしくはGoogle Hashcodeに似たコンテストになるとcodeforcesでtouristが告知をしていました。

Code Weekend #1 - Codeforces

アナウンス等はDiscordで行うとのことだったので、Code Weekendのサーバーに入ります。800名ほどが入室していて、discussionsでは運営が参加者の質問等に答えてくれていました。

1.参加登録をする

Code Weekendのトップページです。

codeweekend.dev

コンテストは1名から4名で参加できるチーム戦とのことでした。新規でアカウントを作成します。コンテストに出題される問題の難易度も、私自身がコンテストにどのくらいの時間を使えるかもわからなかったので、1人で参加することにします。

チーム名：kaede2020、チームメンバー：kaede2020（フォームには本名と書いてありました）で登録します。

2.コンテスト開始

コンテストが開始しました。開始時刻は朝の6時でしたが普段から起きている時間だったので問題文を見ます。前者のhereをクリックすると、問題文のPDFが開き、後者のhereをクリックするとheropath_inputs_day1.zipがダウンロードされました。zipファイルの中身は25個のテストケースでした。ファイル形式はJSONです。24時間後には今よりも難しいテストケースが追加されると事前にアナウンスされています。

問題文の概要は後から書きますが、問題名は「HeroPath」。ヒーローを動かしてモンスターを倒し、ゴールドを得るという内容でした。CodinGameっぽくて、好みの題材です。

入出力の形式はJSONでした。JSONは業務で少し使うくらいで競プロで使うのは初めてです。C++でどう扱えばよいのかわからなかったので調べてみると、専用のライブラリがあるということがわかりました。nlohmann/jsonかRapidJSONのどちらかを使ってみたいと思います。

上のメニューバーにあるDashboardを見ます。各テストケースを提出するフォームがありました。またVisualizeというリンクがありました。

テスト1のVisualizeをクリックします。自分の出力を見ることができるようです。ビジュアライザを自作する必要があると思っていてので、うれしく思います。出力ファイルを指定していないので、初期の入力のみ表示されているようです。

問題文を日本語に訳して目を通します。眠くなってきたので、ここで二度寝することにしました。週末は無理をしないつもりです。

3.順位表

さて、時刻は土曜の午後1時を過ぎています。Scoreboardを見ると、すでに100チーム以上の提出がありました。スコアは各テストごとに一番良いスコアを1000とした相対スコアのようです。

トップはPsyhoさん、3位にwataさんがいました。

Scoreboardをキャプチャして貼り付けてみたのですが、これでは小さくてスコアが読めませんね…。もう1回貼り直すことにします。その短時間の間に1位と2位の順位が入れ替わっていました。接戦です。

このブログはちょこちょこと書き足しているので、前の行から数時間経過しています。

午後3時過ぎ、Discordにadminがメッセージを書き込んでいました。それを読んで、思わず微笑んでしまいました。48時間コンテストではさすがにずっと起きてはいられないですよね。もちろん私も夜になったら寝ます。

参加者の皆様へ

adminは数時間睡眠をとります。これまで通りすべてが順調に進むことを願っていますが、もし何か問題が発生しても心配せずに休息を取ってください。すぐに戻ってきますので、よろしくお願いいたします。

（adminのメッセージを日本語に翻訳したもの）

4.問題の概要

やっと問題に取り組む時間ができました。JSONのテスト1と照らし合わせながら読むと理解しやすそうです。下の概要では問題文やJSONの内容を適当に並べ替えて書いています。

2次元グリッドの大きさ（weight×hight）：テスト1では100×100
ターン数：テスト1では12
ヒーローの持っている情報
- 初期位置（x,y）：テスト1では(62,53)
- スピードとスピードレベル：テスト1では(10.50)
- パワーとパワーレベル：テスト1では(50,50）
- 攻撃範囲と攻撃範囲レベル：テスト1では(10,50)
モンスターの持っている情報（テスト1では7体あったので数値は省略）
- 位置(x,y)
- HP
- ゴールド
- 経験値
ヒーローの行動
- move：距離の2乗がスピードの2乗以下の範囲を移動できる
- attack：攻撃範囲内のモンスターのHPを攻撃力分減らす。0以下にするとゴールドを経験値を獲得できる
ヒーローの能力
- ヒーローのスピード（レベルLのとき）
  - base_speed×(1+L×level_speed_coeff/100)

- ヒーローのパワー（レベルLのとき）
  - base_power×(1+L×level_power_coeff/100)

- ヒーローの攻撃範囲（レベルLのとき）
  - base_range×(1+L×level_range_coeff/100)
レベルアップに必要な経験値
- レベル0からスタートする。
- レベル1になるために必要な経験値：1000
- レベル2：1100、レベル3：1300、レベル4：1600…
- 1000＋L×(L-1)×50
目的：ターン内にできるだけ多くのゴールドを集めること

5.最初の提出

出力例があるのでそれに沿って出力ファイル（JSON）を作成します。

結構シンプルそう。

{
"moves": [ {
"type": "move",
"target_x": 15,
"target_y": 18
},{
"type": "attack",
"target_id": 5
},{

(問題文より引用)

さて、入力を受け取り、一番近いモンスターに移動し、攻撃範囲内なら攻撃し、それ以外ならモンスターに移動するという行動をするようなコードを書きます。

何とかそれらしい出力ファイルができました。Visualizeボタンを押しても初期画面のままです。提出しないとダメなのかなと思い、提出をしてみることにしました。

テスト1で出力ファイルを選択します。

しかし、submitボタンがどこにあるのかわかりません。しばらく悩んだ後、あっとひらめいて下にスクロールしてみます。一番下の左下にsubmitボタンがありました。

よかった。submitボタンを押すと、すぐに結果が返ってきました。無事提出はできたようです。こんなコメントが出ていました。

そして、順位表の一番下に自分がいました。

これが最初の提出でした。

6.正の得点を得る

自分のスピードよりも遠くに移動していたので修正します。

テスト1の出力ファイルを再度提出をします。コメントにOKが出ました。絶対スコアは494点のようです。

順位表を見ると、705.71という相対スコアが出ていました。

わーい！

とりあえず残りの24テストケースも出力ファイルを作成して提出をしたいと思います。

提出しました。ほとんどが不正解のようです。正解だったtest2のビジュアライザを見ます。イメージ通りの動きをしていたので、計算を間違っていそうです。

7.25個のテストケースで正解する

提出したときのコメントとビジュアライザと自分の出力を比較しながらデバッグをします。レベルアップのときの余りの経験値を足し忘れていたり、レベルアップに必要な経験値を間違えていたりしました。

少しずつ修正を重ね、ついに25個のテストケースでOKを得ました。相対スコアの得点は14125.26で平均スコアは565くらいでした。順位は161人中105位でした。

順位表のトップを見ると、相変わらず接戦のようです。4位にShun_PIさんがいました。

テストケースのモンスターの配置がそれぞれ特徴があるので一つひとつ見ていくことにします。

8.追加のテストケース

翌日の朝です。新たに25ケースが追加されていました。追加のテストケースではモンスターが攻撃してくるようです。新しいテストケースに対応する前に、ひとまず昨日の簡単なテストケースの改良を考えます。

9.評価関数の改善

ゴールドを移動とモンスターのHPを0以下にするためにかかるターン数で割ったものを評価関数にしました。途中でJSONの書き出しがうまくいかなくなって悪戦苦闘しました。

10.テストケースの特徴

ビジュアライザで書くケースを見ます。ビジュアライザにはコメントもつけることができました。色分けはheroが青、モンスターのHPによって高いものは緑、低いものは赤でグラデーションがつけられています。

テストケース15が相対スコアでいまひとつでした。ゴールドを優先すると経験値が貯まらずにレベルアップできません。経験値を優先するようにしたら、倍以上のスコアになりました。

なるほど、全てOKなコードを書くというよりは、テストケースに合ったコードに修正する必要がありそうです。

おもしろいな、と思った瞬間でした。

左のモンスターを倒す方が経験値が貯まります。その後右に移動してモンスターを倒すとスコアが上がります。

最初に貪欲に倒せるモンスターを近場で探していたときは左に行かずに右に行っていました。

テスト16ではテスト15よりさらに経験値の評価を重くします。また、攻撃力を余らせないことを高く評価するようにしました。

中央左半分で経験値を貯め、右側ではHPの高いモンスターを攻撃できています。

11.途中経過

現在のスコアは19737.40、193人中113位です。相対スコアの平均は790くらいです(1000点がベスト)。

順位表のトップです。Psyhoさんとwataさんが接戦です。4位にsimanさんがいました。

12.追加のテストケース用のコードを書く

追加25テストケースでOKが出るコードを何とか書くことができました。50テストケースの相対スコアは23458.50、順位は193人中83位になりました。

しかし新しく追加されたモンスターの攻撃がヒーローのfatigueというパラメータに疲れとして累積されていくのですが、この部分がまだ評価しきれていません。TEST36、TEST37では絶対スコアが0点でした。難しい。

13.TEST1で満点を取る

さて、最初の目標に戻ってきました。TEST0で満点を取りたいと思います。

ビジュアライザを自分で作成しました。Pythonのmatplotlibを使います。現在は移動がターゲットのモンスターを決めてモンスターに向かって移動しています。TEST0を見ると、モンスターの間に移動すると、良さそうに見えたから、手動で位置を調整してみたいと思います。
1手余るようになりましたが、得点は変わりません。数字は現在のヒーローと各モンスターの距離で、10以下であれば攻撃できます。

座標を見ているうちに気がつきました。ここだ！

最初にモンスター3を倒さずに4つのモンスターの中央に行きます。こうすれば12ターンでモンスター4体を倒せて、近くにいたモンスター3を倒すよりも高得点が取れます。

手入力でJSONを書きかえて提出します。絶対スコアが635から700になり、ついに相対スコアでベストの1000点が出ました。

わーい、うれしい。

出力ファイルのみを提出するコンテストというのは、ビジュアライザを見ながら手で書いて答えを出しても良いところがおもしろいなあと思いました。

コードが書けなくても大丈夫なのかー。大変だったけど。

14.ビジュアライザを見ながら改善する

TEST14は前半は経験値優先、後半はゴールド優先に評価関数を調整します。

TEST18は一定方向に進むようにモンスターを決めます。

TEST19は、ん、おもしろいなー。絵が出てきた。

というわけで前半25個はテストに合った評価関数に変えて、絶対スコアが下記のようになりました。

TEST1 700
TEST2 2188
TEST3 222897
TEST4 118454
TEST5 6089042
TEST6 11097815
TEST7 2380613
TEST8 321070
TEST9 428609
TEST10 1649737
TEST11 1503871
TEST12 2341
TEST13 3311
TEST14 669596
TEST15 1813840
TEST16 926470
TEST17 17380000
TEST18 1140076
TEST19 956000
TEST20 775001
TEST21 658001
TEST22 22834
TEST23 36811
TEST24 14730
TEST25 13856