Code Weekend#1 36th write up

The English translation follows the Japanese.

はじめに

はじめに

2024年6月8日午前6時から48時間行われたコンテスト、Code Weekendに、自分とshim0さんとssaattooさんでチームを組んで参加していました。面白いコンテスト、面白い問題の提供本当にありがとうございます！！

この文章は、Code Weekendの振り返りです。ゆるく参加していたため、アルゴリズム的な話はほとんど書けません。

Code Weekend

Code WeekendはRGBteam(qwerty787788, Romka and tourist)がホストをしてくれて実施が試みられた、新しいヒューリスティックコンテストです。touristによるcodeforcesへの告知にあるように、ICFPCやGoogle HashCodeに似た形式でした。つまり、kaggleのsantaコンペに近く、Atcoder Heulistic Contestからは遠い形式です。

team up

recruitment

Xで多くの人がざわついていたことからイベントの存在を知りました。

おもしろそうだったため、RTして参加者を募るも、誰からも反応がありませんでした。悲しんでいても仕方がないので、同じように募集していたshim0さんに「組んでくれ～」とリプライを送りチームを組みました。

shim0さんがししゃも(shishamo)が好きらしいことと、自分がコダック(psyduck)が好きらしいことから、後ろの方を取ってチームshamockの結成です。

entry

Code Weekのトップページから登録ができます。本名が求められ、shim0さんに本名を聞くのが面倒だったため、自分の本名を言ってshim0さんに登録してもらいました。この時点ではチーム名: shamock、チームメンバー:(shim0さんの本名)(自分の本名)でした。

recruitment2

登録が終わったぐらいのタイミングでssaattooさんから「チームに混ぜて～」というリプライをもらいました。kaggle santa2023に共に参加したつよつよプログラマーを断る理由もなく、3人のチームが結成されました。

preparation

コード共有なり通話なり、目的別に会話できたほうが嬉しいだろうということで、3人のdiscordを用意しました。githubにコンテスト用のレポジトリをつくろうかと一瞬思いましたが、santa2023では特に有意義ではなかったため、つくりませんでした。（大した量にならないしコード直貼りのほうがはやい。）

contest day1

wake up

コンテスト開始は土曜日の朝6時です。当然自分は寝ていました。discordを見るとssaattooさんが10時ごろから問題を見ていたようです。ssaattooさんの初動が毎度毎度ありがたくて、json形式の入力をAHCの形式(空白、改行区切りのテキストファイル）に変換して入力ファイルを用意してくれました。さらにそれに加えて、AHC形式の出力(今回であればmove 10 20のようなものが複数行続く）を提出用のjson形式に変換するコードも用意してくれました。これによりAHCと同じ感覚で問題に参加することができます。

shim0さんがtest1を手で解いて1000点を獲得しました。しっかりとれるところを取るのえらい。

12時ごろに自分が起きました。問題文や順位表、test1の動いている様子などを見て、問題を理解しました。順位表を見ると、（特に日本人で）本名ではなくハンドルネームを使っている人がちらほらいたことから、順位表の名前をatcoderと同じものに変更しました。またssaattooさんがいることを踏まえて、チーム名をShamockからSShamockkに変更しました。（は？）

problem day1

問題はラミィの大冒険に似ていて、ラミィの動きを最適化してねというものでした。

...ラミィの大冒険、しってる？

day1ではフィールドの縦横、ラミィの初期位置、移動速度、攻撃力、攻撃可能範囲、レベルアップ時のステータス上昇率、また複数のモンスターの位置、体力、獲得経験値、獲得ゴールドが入力で与えられます。ラミィは攻撃可能範囲内のモンスターに攻撃することで、そのモンスターの体力を攻撃力分減らすことができます。モンスターの体力を0以下にすると経験値とゴールドが手に入ります。経験値が貯まるとレベルが上がり、それによりステータスが上がります。最終的に得られるゴールドを最大化するのがゲームの目的です。

solution1 test1-25

とりあえず正の点数が欲しかったため、最低限の読みやすさを意識しつつコードを書きました。

以下の貪欲をやることで、それなりのスコアを得ることができます。(大体最上位の半分のスコアが得られます。)

• 攻撃可能範囲内にモンスターがいる場合は、その中で最もidが低いモンスターに攻撃する
• 攻撃可能範囲内にモンスターがいない場合は、現在位置から最も近いモンスターの位置まで、min(speed, distance)で移動する

solution2 test1-25

多分ssaattooさんがおそらく次のようなコードを書いて得点率を50%から80%ぐらいまで改善してくれました。

• モンスターを倒す順番を、2点swapによる焼きなましで決定する
• 倒すモンスターが攻撃可能範囲内にくるように移動する
• 攻撃する

contest day2

wake up

初日と同じように、追加された問題についてAHC形式にしてくれた入力があったので、それを見ながらコードを書きました。

problem day2

day1の設定に加えて、ラミィにfatigueというパラメータが追加されます。また各モンスターにも攻撃範囲と攻撃力が追加されました。ラミィがモンスターの攻撃範囲に入るとモンスターから攻撃されて、fatigueがそのモンスターの攻撃力分増加します。モンスターを倒した時に得られるゴールドはmonster.gold×1000/(1000+fatigue)となるため、fatigueは小さければ小さいほど嬉しいです。

solution3 test26

test26(2日目のセットの中で最も行動ターン数、モンスター数が少ない問題)は手で解けそうな感じがしたため、問題理解も兼ねて手で解くことにしました。自分の絶対スコアと相対スコアから満点(相対スコアが1000点のチームの絶対スコア)が見積もれます。その値を実現するモンスターの倒し方(の組み合わせ)が1通りに定まるので、あとはそれらのモンスターを倒せるように既定ターン数でしっかりラミィを移動させてあげればいいです。jsonを直接書いてdashboardから提出を繰り返し、1時間弱で満点を獲得しました。

solution4 test18-21

day2の問題をしっかり解くためにはある程度の実装が必要で大変そうだったため、先にday1の問題について振り返りました。test18-22は入力が特徴的だったため、solution1を、この特徴に合わせて少し変更しました。具体的には、倒しておいしいモンスターのみを狙うようにしました。(モンスターの体力にはほとんど差がないものの、(exp,gold)=(1,1)の倒してもあまり嬉しくないモンスターと、(exp,gold)=(1000,1000)のおいしいモンスターの2種類が存在していた。)
これだけでもだいぶスコアがあがり、さらにそこからsolution2のコードでもおいしいモンスターのみを狙うことでらトップスコアの90％以上を獲得していたようです(気づいたら上がっていたのであまり分かっていない)

solution5 test22-25

test18-21と同様に、test22-25も特徴的な入力だったため、それに合わせてsolution1を変更しました。これらのテストケースには以下の特徴があります。

• プレイヤーのspeed(移動可能範囲)がlevel0の時点で十分に大きく、フィールドを端から端へ瞬間移動することが可能
• モンスターが複数の円周上に配置されている

この特徴から、円の中心にワープして周りをぐるっと攻撃して次の円に移動すると強そうな感じがします。
これを踏まえて、以下の貪欲をやるだけで、結構いいスコアが得られます。(大体最上位のスコアの99%が得られます。)

• 攻撃可能範囲内にモンスターがいる場合は、その中で評価値が最も大きいモンスターを攻撃する
• 攻撃可能範囲内にモンスターがいない場合は、移動後に攻撃可能範囲内にいる全モンスターの評価値の和が最も大きい位置に移動する
• 評価値はmonster.exp+monster.gold×turnとする。(気持ちとしては、序盤はexpをとってレベルアップを狙いつつ、終盤になるにつれてgoldをたくさんとっていけるようにしている。)

solution6 test26-50

そろそろtest1-25よりtest26-50のほうが簡単に改善できそうになってきたため、day2の問題に取り掛かります。solution5をもとに、monsterのstructや獲得ゴールドの処理を少し変更し、ターン進行時の処理にモンスターからの攻撃を加えるだけで、まあまあのスコアが取れるようになります。(ケースによって0%〜80%)
実際には以下の貪欲をやりました。

• 攻撃可能範囲内にモンスターがいる場合は、その中で評価値1が最も大きいモンスターを攻撃する
• 攻撃可能範囲内にモンスターがいない場合は、移動後に評価値2が最も大きい位置に移動する
• 評価値1はmonster.exp+monster.gold×turnとする。
• 評価値2は(攻撃可能範囲内にいるモンスターの評価値1の和)/(1+そのマスに移動したときに増加するfatigue)とする。(気持ちとしては、モンスターからあまり攻撃をもらわないところでたくさん攻撃できるようにしている。)

solution ? test ?

solution6を書いたのが18時ごろで、そこからチームメイトが頑張ってくれていたようです(あまり分かっていない)。
特にtest36-37は、絶対に倒せず近づいただけでスコアが0になる激ヤバ化け物が壁になっており、コードを書いて正のスコアを獲得するのが難しかったのですが、明示的にチェックポイントを設けるような形で、正のスコアをとってくれていました。

おわりに

2日間楽しい時間を過ごせました。〜3時間のコンテストのような高い集中力を求められず、1週間〜のコンテストのように中弛みすることもなく、適度な難易度の問題にストレスなく取り組めました。

順位も36位となかなかの数字で、チームメイトにおんぶにだっこされた甲斐があったなぁという感じです。今後ともよろしくお願いします！！