トヨタ自動車プログラミングコンテスト2024#10（AtCoder Heuristic Contest 038ï¼‰å‚åŠ è¨˜

0.はじめに

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

今回は、 トヨタ自動車プログラミングコンテスト2024#10（AtCoder Heuristic Contest 038）に参加しました。開催期間は2024年10月4日(金)19:00から2024年10月14日(月)19:00までの11日間の長期コンテストです。

この参加記はコンテスト開催中にリアルタイムで書いています。今回はいつにも増して独り言が多くなっているので読みづらいかもしれません。それでもこの参加記を公開するのは、読んだ方に少しでもヒューリスティック・コンテストの楽しさを感じてもらえたらと思っているからです。これを読んで自分もコンテストに参加してみようと思ってくださる方がいれば、とてもうれしく思います。

1.心構え

やりたいこと。

• 日本語コーディングをする
• ビジュアライザを作る

本当に本当に上位に行きたい。

2.問題文

問題文はこちら。

atcoder.jp

• 概要:

  • 高橋社長は、二次元グリッド上でたこ焼きを指定されたマスに移動させるロボットアームを開発している。
  • ロボットアームは関節と指先を頂点とした木構造で表現される。
  • 一度の操作で、ロボットアーム全体の移動、関節の回転、指先でのたこ焼きの掴み・離しを同時に行うことができる。
  • 操作ターン数をできるだけ少なくして、すべてのたこ焼きを目的地に移動させることが目標。

• 具体的な制約:

  • グリッドサイズは $N \times N$（$15 \leq N \leq 30$）。
  • たこ焼きの数は $M$ 個（$N^2/10 \leq M \leq N^2/2$）。
  • ロボットアームの頂点数は $V$ 以下（$5 \leq V \leq 15$）。
  • 辺の長さ $L(u, v)$は $1 \leq L(u, v) \leq N - 1$の整数。
  • 操作は最大 $10^5$ ターン。
  • ロボットアームの初期状態は根の位置と全ての辺が右方向に伸びた状態。
  • 一度の操作で、以下を同時に行える：
    • ロボットアーム全体の上下左右への1マス移動。
    • 関節を軸とした部分木の90度回転。
    • 指先でのたこ焼きの掴み・離し。

• スコアリング:

  • すべてのたこ焼きが目的地に到達した場合、操作ターン数 $K$ が絶対スコア。
  • 一部のたこ焼きが未到達の場合、絶対スコアは $10^5 + 1000 \times (M - M')$（$M'$ は到達したたこ焼きの数）。
  • 絶対スコアが小さいほど良い。

3.コンテスト開始

問題文を読みます。今思っていることです。

• 通常は１マスずつしか動けないけど、回転だと大きく移動できる。
• 一度に複数を動かしたい。ロボットアームを90度、180度、270度動かすことを考える。

コンテストが始まって15分ほどが経過していました。順位表を見ます。5位以下はサンプルコードと思われる得点です。

順位表（2024/10/4 19:15）

4.サンプルコードを動かす

サンプルコードを実行してビジュアライザを見ます。ランダムで動いているけど、何もしていない！

サンプルコードのビジュアライザ　seed0

4.考察（コンテスト1日目）

いつものようにACするコードを書きたくなるけど、ぐっと我慢します。

• １マスずつ動かせば、たこ焼きを１個ずつ動かすことは必ずできる

最低限ACするコードは書けるはずだと思って考察をします。

木全体を上下左右のどれかに１マス動かし、部分木を回転させることで、どんな範囲に移動できるのかを考えます。全部を考えなくてもどれか一方向を考えればよいはず。

考えて気が付いたのは、水平方向、垂直方向は１＋0.5LEN（木の直径）動けて、斜め方向は１＋LEN（木の直径）動けるので斜め方向の移動がお得だということ。

例えば木の直径が１のとき。

移動範囲

3手目

なんか移動を書いてみたけど思ったみたいに動かないのかも。部分木が１以上を動かすとなると赤丸は常に１マスしか動かない様子。

なるほど。

• 部分木を90度回転させるのが大きな動きでそれ以外は小さい。
• 目的地に最初からたこ焼きがあったら動かさないことにしてみようか。
• 一緒に動かすと良くなるときはありそう。seed8を見たら絶対たこ焼きをつかみながら移動した方がよさそう。

ああ、これ、Codingame（Fall Challenge 2024）とちょっと似ている。

seed8のビジュアライザ

M（たこ焼きの数）は22から450。もし半分がたこ焼きだったら、かなりの数が最初から一致していそう。

んー、根の初期位置も決められるんだ。多点スタートを試さないと。

2個運べるのか。2個運ぼう。

やっぱり根で１個ずつ運んでみる？

1. たこ焼きがないポジションを見つける。
2. たこ焼きがある場所を見つける。
3. たこ焼きがある場所に行ってたこ焼きをつかんでたこ焼きがないポジションに行く。

とりあえずこんな木にしようかな。たこ焼きを4個つかめるから

4個持てる木

順位表を再び見ます。

ん、何か貪欲をしているのかな。サンプルコードの相対スコア109,408,603の81倍ほど。後のためにとりあえず記録します。

順位表に同じスコアが並ぶ

5.考察（コンテスト2日目）

2日目の朝です。順位表を見ます。USAさんがダントツトップ。

2024年10月5日6:25現在

んー、問題難しいなー。頭が働きません。

• 関節点（部分木）で動かせるように関数を設計しよう

必要なのは

• 部分木の親の座標
• 部分木の座標グループ
• 回転方向

あれ？書いてみたらそんなに難しくない？

• 部分木のグラフを管理する

変更のないものはグローバルにおいてしまおうかな。毎回引数で全てを渡すのは面倒だから。

• 部分木のグループをうまく管理したい

と思ったものの考察は進みません。

どう考えても180度回転が強いなー

だって離れた場所を2手で入れ替えられるから。

180度回転

V=5 のとき、元の位置から2手で8マス移動できる。

2手で8マス移動

あ、これさ、2手で8マス以外に色々動かせるな。斜め方向、ひし形の右半分は1手で、左半分は2手で行ける（元のたこ焼きの位置が黄色のとき）。

移動

まとめるとこんな感じ。うん、かなり移動を簡単にできそう。180度回転移動をして損している場面がゼロっぽい。

移動まとめ

この考察勝った？

斜めの途中は部分木を回転させているので戻す操作がいるかもなあ。
実装方針がまとまらずにうだうだと過ごしています。

気持ちが萎えてきました。１週間のコンテストなんだからと自分を励まします。

• すぐにわからない問題を出している
• すぐ解けると思うな

呪文のようにとなえて気持ちを落ち着けます。気持ちを落ち着けた後再び考察を進めます。

• 動き方を調べろ

気持ちを鼓舞してビジュアライザを開きます。手動で答えを書くことにしました。

木を作ります。

1. 親と長さを書く。
2. 部分木を回転させる。
3. たこ焼きをつかんで回転。
4. たこ焼きを離す。
5. 部分木を回転。たこ焼きをつかむ。
6. 全体で下に下がったて、たこ焼きを離す。

例を見るのビジュアライザに手で書いた出力を貼ります。

4
0 1
0 1
2 1
1 1
..R..P.P
.LL..P.P
.L...P..
D....P..

例を見るのサンプル盤面を自分で答えを書き直したもの

うん、なるほど。

木の構造体を作ろう。

ここまで来たら動くものを書かないとしょうがない。

長さVの折れ曲がらない木を書こう。

あれ？長さは１以上N-1だった。すごく長い木を一本作ってみる？長さの違う木をV本作ればいいかー。

あれ、何かアルゴの問題思い浮かんだな。

すごく苦手だったやつ

atcoder.jp

この問題のことではないけど何かヒントになるかもしれないからここに問題を貼り付けて次にいきたいと思います。

どうやって動かしたらよいのかを考えます。

• 偶数段を端からお掃除する感じ。

手動でコードを書いてビジュアライザを見ます。こんな感じにしてもいいかな。

こんな感じにお掃除する感じでも良い？

ビジュアライザを動かしていたら面白くなってきたから、早く動くものを作りたいなーという気持ちになりました。

6.最初の提出

必要なのは

• 根の位置（ｘ、ｙ座標）
• 葉の位置（ｘ、ｙ座標）

ほしい関数。

• 回転した後の座標

マンハッタン距離は根（全体）で移動したときのコスト。

移動しながらする回転はコスト０。

• たこ焼きの場所を調べる
• たこ焼きを置きたい場所を調べる
• 葉がたこ焼きに届くから葉がたこ焼きがある場所に届くまでの距離と最短ルートを関数で返す。

TSPにできればよいけどとりあえず貪欲で。

スタートは(0,0)にするけど、

• 最初のたこ焼きに葉が届く場所からスタートすればよいので記録しておく。

もっとルールを単純化しろと頭の中でささやき声が聞こえます。

ただ左右を入れ替えるだけでいい気がする。

たとえば長さ１，２，３，４，５の５個の葉をつくるなら、５列ずつ片付けよう。

うん、できる気がしてきた。

ビジュアライザを見ながらできるかを考えます。

うーん、足りないときにどうするかが難しい。

• たこ焼きがあったらとりあえずつかむ。
• 動かした場所が置きたい場所なら置く、そうでないなら持っている。
• たこ焼きがない場所があったら、手数が少ないところを調べてたこ焼きをもってくる。

初期配置

入出力用の構造体を書いて、回転させる関数を書きました。

うーん、葉を管理する構造体の項目がどんどん増えている。

今こんな感じ。

• 葉のID
• 葉のx座標
• 葉のy座標
• 葉の長さ
• 葉の方向(0: 右, 1: 下, 2: å·¦, 3: 上)
• たこ焼きを持っているかどうか

初期設定

• 葉の長さはIDと同じ長さにする

なるほど。最初の木は水平に並ぶ模様。

ビジュアライザを見ながら、たこ焼きをつかんだり、たこ焼きを置いたりできているかを確認。少しずつ動くようになってきました。

seed0のビジュアライザ

１手先２手先を調べて回転できればかなり良さそう。

やっと面白くなってきた。

木なんて面倒だと思っていたけど、竹串にたこ焼きを刺すだけならまあできそう。

わりと良さそうに見えるなー。

スピード感がある。

どうなんだろう。

一度出してみたくなったので提出をします。無事にACしました。

絶対スコア：6644000

相対スコアはサンプルコード20,296,533よりほんの少し良い得点でした。

相対スコア　213位/421人中

今は180度回転ができていないから全部埋められていません。

seed0のビジュアライザ

伸びしろがたっぷり。

取っ掛かりが難しくてつらかったけど、コードが動き始めたら俄然おもしろくなってきました。難しいことができなくても上位を目指す。心に誓います。

今の絶対スコアが6644000で、このあと自分が簡単に取れる絶対スコアの最大がN*N。50ケースなので50倍すると45000という絶対スコアが計算できます。割り算をすると147倍になります。今の相対スコアを147倍すると4,683,849,765、現在の相対スコアで63位相当。今の感じだとその倍のスコアにはできると思うので40位くらいの順位は狙えるはずだと思います。40位になれば黄パフォになります。

うん、十分やれる。

このわくわくした感じをどうやって伝えたら良いのだろう。

できるかもしれないという希望のような何かが胸を満たすときのうれしさ。

アルゴでひらめいたときにも似ているのだけど、もうちょっと作り上げていく感がある気がしている。

今回AHCのテーマ曲はこれ。かっこいいなぁ。

www.youtube.com

7.ジグザグに見る

根は全てのマスを通ります。（0,0）からスタートして、右端に行ったら下に１マス下がり、その後は左端に進みます。左端に来たらまた１マス下がって右に行きます。そんなふうにジグザグに根を移動しました。コードを提出します。

絶対スコア：6009839

相対スコア　199位/446人中

（0,0）からスタートした根が（N-1,N-1）に到達したら、元来た道を引き返して（0,0）に戻ります。全てのマスを根が４回通るコードにしました。

絶対スコア：2015908

相対スコア　105位/516人中

順位表のトップはc7c7さんに変わっていました。

順位表のトップ　2024年10月5日 23:32

8.コンテスト3日目

翌日の朝です。順位表のトップが突き抜けていました。すごい。（このスコアは相対スコアの満点で、全てのテストケースで1位を取っているということを示しています。）

順位表トップ　2024年10月6日9:48

さて、（N-1,N-1）から始まる横方向のジグザグと（0,0）から始まる縦方向のジグザグを追加して一番良いスコアを提出するコードに修正しました。絶対スコアはだいぶ良くなってきました。ローカルで実行した100テストケース中81ケースでは全て目的の位置にたこ焼きを置くことができています。

絶対スコア：1655161    

相対スコア　128位/567人中

まだ全部置けていないのがseed2。

たこ焼きの串刺しが無駄な動きをしています。ローラーみたいな動きを変えてみようかな。

seed2のビジュアライザ

ぐるぐる渦巻きにしてみました。

うーん、微妙。

却下します。

素直に行ったり来たりしようかな。

• たこ焼きを取りに行く
• たこ焼きを置く

なかなか思ったように動くコードが書けません。何とかそれっぽく動くようになったので提出します。

絶対スコア：1103912

相対スコア　169位/644人中

seed0だけとても良くなり、以前の３分の１くらいのスコアになりました。偶然うまくはまっている感じ。他のseedではこんなふうにうまくいきません。

seed0のビジュアライザ　Score=60

つかんだり離したりするとき以外のポジションをいい感じにすると良いスコアが出るというのがわかってきた。これ、2手先読みと関係があると思っているのだけど、どうしたら良いのかはまだわかりません。

絶対スコア：270586

相対スコア　150位/647人中

とりあえずいろいろなパターンを全部試して一番良いスコアを出すことにしました。マスを通る順を変えたり、葉の向きを変えたりして、全部で6パターンを作っています。

100テストケースのうち、全部97ケースは全部置くことができるようになりました。スコアをN*Nより小さい数にしたいと思っていますが達成できているのは33ケースのみ。

縦横に走査する解法を入れます。100テストケースでは全て並べられるようになりました。絶対スコアは下がりましたが相対スコアはほぼ変わりません。

絶対スコア：170806

相対スコア　152位/652人中

実行時間を何に使えばよいのかなぁ。

静止フラグをつけて180度回転をつけてみよう。

その後は一番良い解の改善を残り時間を使ってしよう。

9.180度回転を入れる

180度回転を入れてみると、たこ焼きがある場所やたこ焼きを置く場所を探す関数がバグっていることに気が付きました。それでもバグっているなりに改善していて、提出をすると絶対スコアが58831になりました。しかし、相対スコアは少し上がっただけでした。

絶対スコア：58831

相対スコア　182位/727人中

10.たこ焼きを探す関数の見直し

探す関数のバグっていた原因がわかりました。根の位置からでなく葉の位置から調べていました。もう一度よく考えて書き直します。そして、ついにデバッグを終えました。

うまく探索できていなかったのは今の葉の向きだけで探索をしていたことが原因でした。だから途中で葉を回転させるとスコアが上下していました。

また、うまく見つからない部分はランダムで移動させることにします。

100テストケースで試した結果は、これまでの半分くらいのスコアになりました。

やったあ！

提出をします。

結果は50ケース中7ケースがTLEしてしまいました。しかし相対スコアは7,139,343,218 になり、139位になりました。ついに暗闇を抜け出した気がしました。

絶対スコアは0

相対スコア　139位/730位

8個試していた解法のうち、ベストがなかった4つの解法を消しました。

時間を計って制限時間内におさまっていることを確認します。

盤面が大きくて、V（葉の数が多い）ときでも2秒以内でした。今回の制限時間は3秒なので、残りの時間はこの解を改善する時間に使いたいと思います。

100テストケース中83ケースでN*N以下のスコアになりました。

11.初期解のベストができあがった

そして満を持して再提出をしました。

あ、またTLEしている。盤面が大きいときは解法を１つに絞ろうかな。先ほどよりは減りましたが50ケース中3ケースでTLEしたので絶対スコアはまたも0です。

TLE

相対スコアは7,709,151,408になり、順位もほんの少し上がり732人中136位になりました。

相対スコア　136位/732人中

うーん、あとちょっと。TLEの原因は良い探索先が見つからなかったとき根をランダムで移動させていたのですが、合法手に限るのを忘れていたからでした。

TLEを解消するため、解法を2個に絞りました。すると実行がすぐに終わるようになりました。また、スコアもほぼ変わらないことがわかりました。

提出制限が30分間隔なので、再提出できるまであと20分間あります。その間休憩することにします。2024年10月7日の23時。コンテスト4日目の夜でした。

seed1のビジュアライザ。いい感じに180度回転が使えている気がします。

seed1のビジュアライザ　スコア140

30分待って提出をしました。一瞬で終わりました。絶対スコアは23616になりました。相対スコアは8,041,815,927になり、133位になりました。すごい下がった！

それでも相対スコアはトップと8倍の開きがあります。

トップの解法はどうなっているんだろう！？

コンテストが終わって解法を聞くのが楽しみになりました。

絶対スコア：23616

相対スコア　133位/735人中

12.初期解の改善を考える（葉の長さを乱択山登り）

今思っているのは葉の長さの組み合わせを変えること。これは簡単にできそう。盤面の大きさに対して葉の長さが長すぎるときは使いづらいように感じていて、盤面の半分くらいまでの長さが良いように感じています。あと試せていなかった同じ長さを複数持つとか。

次は探すときの条件を評価関数にすること。今は距離が一番近い行動をしているけど、トータルで短い方が良いので、プレイアウトをするか、一度にまとめて操作できる回数みたいなものを評価委にするとか、行ったり来たりするときにペナルティをつけたりできないかと考えています。

コンテスト5日目の朝です。

順位表のトップのメンバーが大きく入れ替わっていました。メンバーから何か解法を推論できないかと思いましたが強い人たちなので何でもできそう（わからないということ）

順位表のトップ

さて、私が100位台にいるので私を順位表に見つけた人は考察をがんばろうと思っているはず（実際その通りなのですが）。がんばれ、みんな。自分もがんばります！

まずは時間内にランダムに葉の長さを変えて答えを出してみることにします。

めちゃめちゃ良くなってる！

ローカルで10ケースほど試して出力を確認すると待ちきれずに提出してしまいました。

提出中にローカルの出力を確認します。

seed2のビジュアライザです。659かかっていた手数が266になりました。長い葉の方が良いようです。

seed2のビジュアライザ　スコア266

ああ、またTLEしてしまいました。

絶対スコアは0

相対スコアは提出前の144位、7,888,293,701から113位、10,525,322,748に上がりました。

よっしゃー！

思わずガッツポーズが出ました。ヤバい、楽しい。

相対スコア：113位/752人中

朝はここまで。

今からお仕事です。

お昼休み。実行時間をこまめに計測することにします。時間も2.5秒でやめることにしました。

無事ACしました。絶対スコアはローカルの100テストケースを試して感じていましたが、かなり下がりました。うれしい。

絶対スコア：15570

順位は107位になりました。もう少しで2桁順位です。

がんばるぞ！

相対スコア　107位/758人中

13.たこ焼き探索の評価関数を考えるがうまくいかず、近傍遷移を改善した

• 得をしているのを評価する
  • 一度にたくさん動かしている
  • 遠くのものを動かしている

先に探索後の同評価の移動方向をランダムにします。いまいちでした。

評価関数を書いてみますがうまくいきません。うーん。

はまってきたのでビジュアライザを見よう。

スタート地点を変えてみようか。

葉の長さも１か所だけランダムで変える山登りにしてみよう。

重複も削除していなかったのでしよう。

何か同じ長さが２つある。同じ長さが２こあると何かいいことある？入れ替えが１回でできる？

毎回その場所で手放すと良い？

あー、何かわかりそうな。

操作 3 の中では頂点番号の小さい指先から順に処理が行われる

（問題文中より引用）

これです、これ。どういうことができるのかな。AをBに置いて、Bを持ってCに移動。うーん、持ち替えができるとどんな良いことが？あ、そうか操作順が重要なのか。

あー、やっぱり180度回転が１回でできそう。

これは強そう！

一旦置いておいて、スタート地点を試す

良い候補のスタート地点を試そうかな。

うん、分離しよう。

うまくいかない時間が続きます。

冷静になろう。闇雲に試すのではなく。

これまでは全部の葉の長さを変えていました。今のベストの状態から１個だけ葉の長さを変えることにします。最初からそうするべきでした。

• 葉の長さを１個ずつランダムに変える山登りをします。

100テストケースを試すと、久しぶりにベストを更新しているのがわかりました。提出すると絶対スコアは13895になりました。相対スコアは12,135,490,095になり、778人中109位になりました。2桁順位になりそうでなれない。もどかしい時間が続きます。

絶対スコア：13895    

相対スコア　109位/778人中

seed0ではスコア56が出ました。

seed0のビジュアライザ　スコア56

• 行ったり来たりが無駄なので、端から処理することを考える。
• 今あるルートのswapや繋ぎ変えができないかを考える

14.ビジュアライザの作成

仕事が忙しくて取り組む時間が無く、前回から2日経っています。現在はコンテスト7日目、木曜日の夜です。また、体調が良くないので、ほんの少しだけやって寝たいと思います。

これからは

• 根のルートを改善する

のが目標です。今あるビジュアライザではよくわからいので、ビジュアライザを自分で作成することにしました。

Google Colabを使用してmatplotlibライブラリを使用したコードを作成しました。

seed0の根の移動を描画します。それっぽいものができました。

seed0（スコア48）のビジュアライザです。まだ連続の描画がうまくできませんがそれっぽい感じ。

seed0の根の移動

公式のビジュアライザと並べてみます。

公式ビジュアライザ　seed0

正直結構いい感じの動きをしていて改善箇所がよくわかりません。別のseedを見ることにします。seed1とseed2です。

seed1 score=125

何か無駄そう。

seed2 score=236

まずスタート位置が無駄そう。スタート位置を

• 一番左上（0,0）に近いたこ焼きに置きたい場所に最短でたこ焼きを置ける場所を探し、たこ焼きを置く葉にたこ焼きをつかめる場所

にしたいと思います。

seed2のビジュアライザ

うまくいかないので、スタート地点を完全なランダム（xは全て、yはvを引いた範囲）にして山登りします。最初はたこ焼きがつかめる場所が良いと思っていましたがそうでもない？

→結論、変わりませんでした。

時計回りと反時計回り、両方の選択肢があるときベターな方を選択する

（今は反時計回り、時計回り、180度回転の順に選択している）

時間をのばしたらスコアが伸びたので高速化を考えた

• スコア計算を簡略化（毎回盤面が一致しているか計算していたのを一致した時の数を数えていて省略することにした）
• 葉の長さを2以上(N+1)/2以下とした

絶対スコア：13536

相対スコア　153位/898人中

• 探すときのルートに重みをつけてランダムに選ぶ

絶対スコア：12017

相対スコア　142位/903人中

• 探索範囲を現在の根の位置から±N/2以内とし、マンハッタン距離が1.5N以下とする

NとVの条件別スコア平均

相対スコア　141位/908人中

提出前

Nが23以上のもののときは何もしないコードを提出して得点源の範囲を調べます。
13,008,841,989が6,950,641,389になりました。Nが小さいときの方が得意だと思っていました。Nが小さいときの方が3割くらい良いようです。

Nが22以下の得点

Vが10以下のときは何もしないコードを提出します。4,162,839,502になりました。思っていたのと異なり、Vが小さい方が得意のようです。1.7倍ほどの開きがありました。そうなんだ…

Vが11以上の得点

たこ焼きを置く場所を端から決めていった方が良いのかな。何だか貪欲の良い解法を感じています。これだけ偏った場所に入出力があるのだから、それはそうな気がします。うーん、もっと考えよう。

同じコードを出しなおしたら、絶対スコアが良くなりました。提出ごとに大きくぶれるコードもいやだなあと思いますが、順位はほぼ変わらなかったので問題ないのかもしれません。

絶対スコア：11845

同じコードを出しなおす　143位/918人中

• ビジュアライザを見る

seed99の66ターン目で次に右に進めば葉6のたこ焼きを置くことができます。しかし上へ進んでいます。動かずに回転させるだけでも良い盤面です。探索が間違っているなあと思います。

seed99　66ターン目

葉の上下左右を最初に探索することにしました。スコアが8%ほど良くなりました。seed99のビジュアライザを見ても不自然な動きはなくなったようです。

seed99のビジュアライザ　スコア70

絶対スコア：10788

絶対スコアが1000くらい少なくなりました。おお！

ドキドキしながら順位表を見ます。相対スコアは14,220,973,384になり、順位は128位になりました。結構上がった！うれしい。

相対スコア　128位/918人中

seed6 score=340

seed6 score=292

１ターン目は下ではなく上に行ってほしい。一番多数が行きたい方向を選ぶようにします。

seed6 score=340の１ターン目

1ターン目は別のところからスタートするようになりました。スコアは268になり、だいぶ良くなっています。100テストケースを試し始めて数ケース見て全て良くなっていそうだったのでテストケースが終わるのが待ちきれずに提出をします。

絶対スコアは10220でした。もうすぐで1万を切れる！

絶対スコア：10220

相対スコアも上がりました！やったぁ！

117位/921人中

無駄な探索も削ったので、試行回数も平均800回くらいになり、以前の5倍ほどになりました。

100テストケースの結果

15.コンテスト9日目（初期解の葉の長さの考察）

2024年10月12日土曜日の午後です。今週はずっと体調がすぐれません。熱はないのですが喉が痛くて今も声が出ません。先ほど病院に行って薬をもらってきました。薬を飲んで少し寝て、やっと楽になってきたところです。

残り3日でやりたいことです。

• 同じ長さを2つ持ち、決まったルートを巡回する180度回転を行う解法を試す
• 根の上下左右の移動後に貪欲プレイアウトを行っていちばんよかった行動を選ぶ解法を試す
• できあがった解のルートを変える解法を試す

一番上は書いてみたけど途中でバグったので一旦中止。

そういえば、山登り後の最終的なベストスコア時の葉の長さがどうなっているかを調べることにします。

葉の長さは全体的に長くなっているように思いました。特にVが小さいときに顕著。

絶対スコア：9646

131位/949人中

試行回数が足りていないようで、初期解の影響を強く受けるようです。

100テストケースの条件別平均

16.コンテスト10日目（根の移動についての考察）

2024年10月13日日曜日の朝です。コンテスト残り2日となりました。

seed0のビジュアライザと根のルート、左スコア43、右スコア31

右のほうがスコアが良くなります。20手目では明らかな差がついています。一番左のものは根の移動で、青が左、赤が右になります。ネックになっているのはこれ。(0,5)にあるたこ焼きを左では最後まで残してしまっていました。右では12手目に取っています。

seed0のビジュアライザ

運命の分かれ道は一番左下の(14,2)にたこ焼きを置いた左の8手目だと思うのですが、同じ位置取りでも右はまだ4手目です。

seed0のビジュアライザ

途中に入れ込めないかということを考えていましたが、これは取る順番を指示しない取れなさそうな場所です。また根のポジションは中央寄りの方が好ましいという加点はしても良さそうに思いました。

あ、ビジュアライザを見ながらふと思いました。何でこんな動きをしているのだろうと。

それを考えると、葉はマスの外にいられることを考慮していませんでした。

いや特に問題なさそう。

• 根は中央にいるのが良く、葉は外周にいるのが良い。

何か今さら当たり前なのかもしれませんがそんなことに気がつきました。

そうは思うものの何もできず。

初期の根の座標と探索方法の改善をごにょごにょとやっていました。少しだけ改善。

絶対スコア：9396

相対スコア148位/1002人中

 

相対スコア151位/1010人中

現在のトップ　2024年10月13日20:41

うーん、いろいろとやってみたけどうまくいかない。

何かというと奥から詰めていくみたいなの。

進捗なし。寝ます。

17.コンテスト最終日

2024年10月14日月曜日の朝です。今日は祝日なのでお休みです。

昨日は一日進捗がなく、残念な日でした。

自分のコードで思っているのと違う挙動はわかっていて、斜め方向にたこ焼きを置いていくことです。

seed8のビジュアライザ

一手ずつ順に見ると移動が90度だからかなあという気持ちに。最初から180度回転にしてくれた方がお得なのになあ。

コードを見直します。

あ、もしかして直った？（左端が１列残っているのが気になるけど）探索の優先度で現状を入れるのを忘れていました。（一手先のものしか考慮していなかった）

seed8のビジュアライザ

ところで、葉の長さの考察も、一晩経ったら思考がまとまったので図にしてみました。左右を入れ替えるのに良さそうな葉の長さです。

• (0.5N+V)/2を葉の長さの最大とする

葉の長さのベスト

朝早く起きすぎてしまったので二度寝をしてきました。順位表、朝起きると見るのですが、だいぶ順位が下がっていて悲しい。今は1035人中174位です。今回も2桁順位はダメだったかな。青パフォはなんとか維持できそうなくらいです。順位表のトップでは TopcoderのMarathon Match でおなじみのwleiteさんが2位になっていました！

18.「終わりに」からの悪あがき

もうすぐあと3時間ほどでコンテストが終わります。途中は調子がよかったのに最後はうまくいかないなあと思ったまま終わりを迎えることになりました。今はこれまでの提出で1000テストケースを試しているところです。特に問題がなければこれを最終提出にしたいと思います。

1000テストケースの結果

一番良かったのはseed0のスコア31でした。

seed0のビジュアライザ score=31

さあ終わりにしよう、と思ったのですが、出力がベスト以上の長さになった時点での打ち切りを入れていませんでした。100テストケースを試すと少し良くなっていたので提出をします。お、絶対スコアも相対スコアも少し上がりました。

絶対スコア：9190

相対スコア185位/1063人中

また、100テストケースのスコアを見ていたら、打ち切りを入れても変わらないものがありました。試行回数が1万回以上あるものに関しては、スタート地点を完全なランダムに変更しました（現在はたこ焼きがあるところからスタートしている）。良くなるものと悪くなるものがありましたが、傾向としては良くなっていそうです。30分待ってもう一度提出をします。

絶対スコア：9137

相対スコア　183位/1063人中

18.終わりに

そして、今度こそ本当にコンテストが終了します。最終日に少し改善ができて、悔しかった気持ちが少しだけ落ち着きました。もっとすごい解法を思いつきたかったと思うものの、11日間たくさん考えることができたので、とても楽しい時間を過ごすことができました。

次こそはもっと上位にいきたい！

さて、コンテストが終了した後は、Xのポストや感想会スペース、AHCラジオなどで他の人の解法を聞いたり、自分の解法を振り返ることのできる時間が待っています。とても楽しみな時間であると同時に、しっかりと自分の糧にして次に進みたいと思います。これでコンテストの参加記は終了です。長い文章をここまで読んでくださりありがとうございました。ぜひまた次回のコンテストでお会いしましょう。一緒に競い合えるのを楽しみにしています。

19.最終結果（2024年10月16日更新）

システムテストの結果です。2000テストケースで全てACしていました。2900msになるよう時間管理をしていたので、実行時間の結果もそのままでした。

システムテストの結果と実行時間（2900msに調整していた）

順位は暫定時の194位から少し上がり、1088人中190位になりました。6位のwleiteさんが作ってくださったシステムテストの統計表を引用させてもらつことにします。     予想通りでしたがVが小さいときの順位がよかったです。

統計表はこちらから↓

AtCoder #AHC038 statisticshttps://t.co/fM6xn5Lxdk
Scores are normalized to 100.

— Wladimir Leite (@wleite) 2024年10月15日

システムテストの結果（wleiteさんの統計表より）

結果としては過去4番目に高い1717というパフォーマンスを出すことができました。

とはいうものの、他の方の解法や感想会スペースでの話を聞くと、自分の考察がまだまだだなあと反省する気持ちがわきあがっているところです。

パフォーマンス1717

明日2024年10月17日の夜20時からはAHCラジオがあるのでしっかり復習に取り組みたいと思います。

www.youtube.com

ヒューリスティックのRatingは19上がり1701になりました。ここ1年間で100くらい上がっているので、あと3年で黄色にいけたらいいなぁと思います。

ヒューリスティックRating