トヨタ自動車プログラミングコンテスト2024#10（AtCoder Heuristic Contest 038）参加記
はじめに
こんにちは。「AHCを楽しむ人」ことrinrionです。
2024年10月4日から14日にかけて行われたトヨタ自動車プログラミングコンテスト2024#10（AtCoder Heuristic Contest 038）に参加しました。
いつもでしたらAHCコンテストに参加したあとの提出コードの内容や反省はXに投稿しているのですが、今回は書きたいことが多すぎるためこのような形でまとめることにしました。もしこの文章を読んでAHCに興味を持ち、新たに参加する方がいらしたら望外の喜びです。
最終提出コードの内容
各ターンの行動
現在地でアームを回転させて取れるたこ焼きがあれば取り、置けるたこ焼きがあれば置きます。どちらもできない場合は隣接マスに移動します。
移動方向の選び方
「たこ焼きを取りに行く局面」と「指示されたマスに置きに行く局面」を分けました。切り替えは、アームがこれ以上持てなくなった時と手ぶらになった時です。それぞれの局面に応じて、「目的地ではない場所にあるたこ焼き」と「たこ焼きが無い目的地」について、その時点で空いているアームが「取る」または「置く」のいずれかの行動が可能な根の位置のマスに対して評価をプラス1します。この際、アームを回転させる必要がある場合も含めます。
図の例では、ピンクのマスに根がある場合、長さ1のアームがたこ焼きを取ることができます。一方、青のマスに根がある場合は、長さ2のアームがたこ焼きを取ることができます。
そして評価がプラスのマスのうち、現在地から最も近いマスに近づく方向を選びます。同じ距離のマスが複数ある場合は評価が高いマスを選びます。
ロボットアームの設計
問題文を読んですぐに、「コンテスト期間内に関節を作ることは自分には難しい」と判断し、曲がらないアーム作りに専念しました。
テストケースの特徴ごとにアームの長さを変える必要があると考えたものの、入力値から特徴を判断する方法がわかりませんでした。結局、いくつかのパターンを作成し、すべて試してスコアが良いものを選びました。
作ったアームのパターン
- アームの最長の長さ：3パターン（Nの1/2、Nの1/3、Nの1/4）
- アームごとの長さ：5パターン
- すべて最長と同じ
- 最長の2/3から最長まで均等
- 最長の1/2から最長まで均等
- 最長の1/3から最長まで均等
- 長さ1から最長まで均等
これらに加えてスタート地点を中心・角・辺の中間点の9か所に設定し、最長の長さ・アームごとの長さ・スタート地点の組み合わせをすべて試しました。
ビジュアライザで確認したところ、やはりスコアが最も高くなるアームのパターンはテストケースによって異なりました。
コンテスト中に苦しんだこと
私にとって、AHCはとても楽しいコンテストです。難しい問題に対して知恵を振り絞りながら自分だけの解き方を考え、それをコードにして動かせた時や、提出して正の得点を得た時、さらに得点を上げられた時には、他では味わえない楽しさを感じます。
一方で、苦しむことも多々あります。今回は特に苦しみポイントが多かったので、一部をご紹介します。
出力形式が理解できない
出力形式の説明を何度読んでも理解できず、ビジュアライザのOutput欄に数値を入力しながら「アームの数がこれで、ゼロがこの数ならこうなるから…」と何度も試し、やっと理解しました。
枠外のアームの位置の表現方法がわからない
根とアームを操作するために、それぞれの位置（座標）をメモする必要がありましたが、アームが枠外にある場合の位置の表現に悩みました。(追記：座標データをひとつの値に変換して一次元配列で持っていました）
「根から見た四方向と距離を持つ」というアイデアを思いつかなければ、最初の提出までたどり着けなかったかもしれません。
ターンごとの指示の流れがわからない
１ターン内で「根の移動・アームの回転・たこ焼きを取る・たこ焼きを置く」の行動が同時にできるため、どの行動ができるのか、できないのか、できない場合はどうするのかをどのような順番で書けばいいのかで非常に悩みました。
結局、移動せずにアームの回転のみでたこ焼きを取る・置く操作ができるか確認→できるなら回転・操作し次のターンへ進む、できないなら移動→移動後、再度操作可能か確認、という流れにしました。
反省点
効率的なデータの持ち方を書けなかった
アームごとのデータ（たこ焼きを持っているか・根からの距離など）をそれぞれの配列で持っていたため、効率が悪く、データの変更し忘れも多発しました。途中で適当な形式にまとめることを考えましたが、時間が足りずそのままにしてしまいました。
手元と提出の実行時間の差に気づかなかった
アームの数やスタート地点をランダムに試すことも考えましたが、手元での実行時間が不足していたため断念しました。コンテスト後に確認したところ、提出時の実行時間は手元より遥かに短かったことがわかりました。コードテストや提出時にしっかりと確認するべきでした。
とっさの考えにしがみついてしまった
AHCに限らずコンテストへの取り組み方全般に言えることとして、一つの事実からとっさに思いついた考えにしがみついてしまうことが多くあります。
移動先を決める方法を例に挙げます。
すべての未対応マスを評価する方法では計算量がかかりすぎるため、BFSで一番近くにある未対応マスを探し、見つかった時点で探索を打ち切る方法を試したところ、スコアが下がりました。
そのとき、「スコアが下がった」事実だけに注目し、「この案ではダメだ」ととっさに考え、試したアイデアを不採用としました。
しかし、その時点で気づいていなかった事実も多くありました。
・下がったのは複数のテストケースのスコアの平均だった
・テストケースごとのスコアを確認していなかった
・テストケースごとの実行時間の増減を確認していなかった
・ビジュアライザでアームの動き方を確認していなかった
などです。
もし、とっさに考えたことに対して他の事実を探し、それらに基づいた別の考え（スコアが下がったのは一部のテストケースだけかもしれない→テストケースごとにスコアを確認する必要がある、など）を新たに追加していたら、試したアイデアをより正確に評価できたと思います。
コンテスト中で焦っている中では難しいと思いますが、今より少しでも柔軟な考え方ができるように努力していきたいと思います。
最終結果
順位は256位、パフォーマンスは1577、レートは38上がって1397になりました。
最高パフォーマンスを100以上更新できたうれしさもありますが、自分ができるレベルの改善点に気づけなかったことや、あと少しで青パフォに届かなかったことに対する悔しさの方が大きいです。
延長戦で挑戦したいこと
延長戦では以下のことに挑戦したいと思います。
- アーム関連のデータをstructにまとめる
- 移動先の評価を「BFSを使って一番近い未対応マスを探す」方法にする
- スタート地点とアームの長さをランダムに試す
- ビームサーチを書く
おわりに
これからも、少しでもレートを上げていけるように努力していこうと思います。
最後までお読みいただきありがとうございました。
※ブログ内の画像とGIFはAtCoder公式サイトよりお借りしました
