はじめに
今回のAHCの期間は春休みという事でたくさんの時間を使ってやるつもりなので参加記を書こうと思います
いつもは緑パフォ～青パフォですが黄パフォとか出すつもりで頑張ります
思ったことや方針を書きなぐっているので少々見ずらいと思いますが見てくれると嬉しいです
要約
さすがに10日分の考察は長いので自分がやった戦法をまとめます
食いちぎ戻りを活用した貪欲
まず自分が作った言葉である食いちぎ戻りについて解説します
下の動画のように胴体を食いちぎった後、しっぽのところまでさかのぼることです
これを使うと蛇の色は変わらずに位置だけ変えることができます
次にとるべき色を見つけてその餌に向かう。
普通にやると探索できる範囲が狭いが食いちぎ戻りをすることで範囲が結構広がる
この戦法は密度が小さい盤面で少ない手数だけで全揃えすることができる
だが、密度が高いと目当ての餌をとれず泣く泣く他の餌をとらないといけないことがよくある
そういう時は食いちぎ戻りしてる最中に間違った餌直前で遡るのをやめる
そしてそこからまた違う餌を食べていくこれによって誤差をなくす確率を高めていく
速くて見づらいが下の動画の感じのことをやっている
食いちぎ戻りをする胴体の場所をランダムにすることによって可能性を広げている
これって山登りというより乱択なのかな？
順置き
順置きは餌を食べる順に並べて整理する戦法
この動画の動きをすれば右端以外の場所に餌を置くことができる
BFSの方を改良していくうちにこっちはあまりいいスコアを出せなくなってくる
色々注意しないとバグだらけになる
この二つで頑張りました
あとは日記を見てください
日記
1日目
まず、問題を理解する
・蛇ゲームで胴体を食べると餌になる
・食べた餌の色がしっぽの色になる
・体色を好きな色にする
この時点での考察
ターン数めっちゃ多くて焼きなましできなさそうで悲しい
得点の式を見ると指示の回数と好みの誤差の寄与が極端に離れてないから偏りなくやんなきゃなさそう。とはいえ、すべての餌を誤差なく食べるのを先にやりたい
食いちぎるのをやらずに貪欲のDFSで全探索みたいなのをやればちょっとはいい点数でそう計算量はわからん
とりあえず正の得点を出したい
蛇行してすべての餌を食べるプログラムを作る
こんな感じ
https://atcoder.jp/contests/ahc063/submissions/74618313
得点 24447131 8桁
ちなみに得点低い方が良い成績という事です
次はDFSして目当ての餌以外取らずに全探索しようとしたが計算量的に間に合わなさそう
向きを指定すればいい感じにシミュレーションしてくれる関数と構造体を作る
ランダムな向き(合法手ではあるやつ)で頑張ってみる
得点 48069273 ８桁
2日目
今日の考察
食いちぎるのをなしにして蛇でのBFSむずそう移動すると移動できる場所が変わる計算量やばそう
蛇の座標と時間かな？O(N^2T)Tは蛇の長さくらいだから全体の計算量はO(N^6)くらいになりそう1e7できるかな？向きもある
一回蛇の動きを考慮しないBFSをする
https://atcoder.jp/contests/ahc063/submissions/74628749
得点 47533430 ８桁
ほぼランダムと同じ
食いちぎ戻りという技を編み出す
胴体のどこかを食べて餌になった胴体を食べるとまた同じ色になって場所だけ変わる技
しっぽの場所に頭、頭の場所にしっぽが来て位置が反転する
これを加えて他にもいろいろ工夫をしてバグ取りをするとseed0ではすべての餌を誤差なく食べられるようになりましたhttps://atcoder.jp/contests/ahc063/submissions/74634631
得点7278406 7桁やったね！！
3日目
今日はBFSの改善をするいまのBFSは蛇の胴体としっぽがあるところはずっと壁として扱っているが実際は動いてる間にしっぽが動くのでそれをBFSにいれたい
胴体のidx+BFSのdist<=蛇のサイズになると壁になる
その時以外は通過できるようにする
成功したときのgifを置こうとしたがいろいろあって置けなかった...
提出！
得点6078118 更に減っていい感じ！
考察
一旦BFSで思いつくことやったのでBFS軸でさらにできることを考察
今の問題点
意味ないところで食いちぎ戻をしているところ。これは実装がめんどくさいから後でやるビームサーチするときにまとめて直すかな
下の写真のようにほかの餌を食べる以外のことができない袋小路になったとき食べざるを得ない
色3を食べたいときにこういう感じで他の色の餌に阻まれて取れなくなってしまう事、現状のプログラムでは一回食べた餌はおんなじ所に残り続けるのでこういう盤面では誤差が残り続ける
この2つを何とかしたい
思いついた方法を上げてみる
・逃げ場がなくなる餌は取りにいかない
これだと計算量が結構増えそうだし、狙いの色で取れる餌が少なくなって結局スコア減りそう
・一回すべての餌を食べて根元で食いちぎって新しい盤面を作る
これ良さそう 新しい盤面だと餌をとりやすい位置に配置できそう。でも密度が高いと結局上2つみたいなことが起きるか？
・何個か違う餌食べて、食べたところをちょん切る
実装むずそ～でもやれそうではあるな
・狙いの餌でとれる候補が沢山あった場合、隣接する頂点が少ない方に行く
これもできそう 将来的にはどっちも行くのを試すビームサーチができそう
とりあえず実装していく盤面リセットが一番楽そうだからそれからやる
実装中止！
実装してみてわかったがあんまりよくない。食いちぎってリセットするから結局連結して餌が密集する。しかも、Uターンしないようにするのが難しい。こっちが実装やめる理由
もう完成したときに一回りする方がいいと思う
次は間違った餌を食べたところをちょん切るプログラムを作る
よく考えれば間違ったところを狙ってピンポイントに切るんじゃなくて食いちぎ戻りをしてる際中で違うところに行けばいいんだ
一回普通にやったバージョンとちょん切っていくバージョン2つを作る
実装完了したので提出する
得点 3111686 すごすぎる！！
そのあと試す時間を増やしたり、盤面をちょっと変えてからスタートするやつなどちょこっと工夫して
得点 2653628！
ただこの方針はもう煮詰まってきたあと7日間なにする？
4日目
今日はビームサーチをしていこうと思う
まず狙いの餌をBFSで探す
もし狙いの餌を見つけたら
狙いの餌全ての経路をpriority_queue(これからはqueと呼ぶ)に入れる
狙いの餌が無かったら
取れる餌全ての経路をqueに入れる
こんな感じでやっていく大幅な改修をしていく
食いちぎ戻りを使わずにビームサーチをしてみる
食いちぎ戻りしないといける場所がなくなってREになりそう...
食いちぎ戻りを実装する食いちぎ戻りをした後の違う餌を食べない奴は実装できなさそう
提出！
得点 44537003 8桁
桁違いに低い今までの5時間は何だったんだ うわああ
ビームサーチやめよ
5日目
4日目にかくの忘れてたのでこっちに5日目と合わせて書いていく
一回方針を転換する
色々蛇で遊んでみる 遊ぶ中で面白い解き方ができる方法を見つけた
餌を一つ取ってこういう置き方を使っていけば全て並べることができるのを発見した
全部並べてみた 3000ターンくらいでできた
これをコンピューターでやりたい
この置き方のことを詳しく解説していく
上の動画の餌を置くときの一連の操作を順置きと呼ぶ
順置きのいいところは置く場所の左と下に干渉しないこと。これのおかげでひとつずつ順番に置くことができる
しかし右端、左端はスペースが無くて順置きができないなので折り返し置きを発明した
下の動画のように置けば一番端は置けないがその次のマスにはおけるこれで餌を選ぶときのスペースが増える
とりあえずやりたいことをめっちゃ雑に書いた
これから実装していく
餌を置くために最初、すべての餌を奥に詰める
餌を見つけて食いに行くBFSと餌を持ち帰って順置きや折り返し置きの所定の開始位置にいくBFSをつくる
そして順置きして次に置く場所に切り替える
これを繰り返していく端に着いたら折り返し置きして反転した操作をする
しかしこれには問題点がある
目当ての餌が他の餌に囲まれていて取れないとき仕方なく他の餌を突っ切って取りに行くそうすると目当ての色じゃない餌を置いてしまう
これが起きてしまったら一回根元で食いちぎってもう一回BFSすることで解決
その他多くのバグに見舞われるがちょっとづつ直していき、最終的には一回変なこと起きたときは強制的にプログラムを終了させる臭い物に蓋をする作戦で実装終了
これを提出！
得点 3837293 なかなかいい点数
https://atcoder.jp/contests/ahc063/submissions/74747981
順置きのいいところは盤面がでかいほど集めやすいところ
盤面がでかいほど餌を置くときのスペースが広くなりいい感じになる
前作ったBFSの奴は食いちぎ戻りを何回もやって試行回数を増やしたいから小さい盤面のほうが得意
順置きと今まで作ってたBFSを合わせれば最強なんじゃないか？！
二つやってみてスコアが低い方を採用する
提出！
得点 790924 やったあ！！！！！
過去最低の点数！桁が違う！うれしい！
だが相対スコアを見ると三日目とかと同じで萎える
僕がスコア上げる間に他の人スコア上げないでほしい
BFSのほうでこうなるときがある
こういう時どうすればいいんだろう
6日目
もう得点これ以上下げられないよ
順置きを逆からやってもいいな一番最初の餌から置き始めるのではなく一番最後の餌から置き始るパターンを増やせば少しはスコア良くなるかも
得点 779307 まぁ誤差
このゲームの本質に気づいてない気がする
左端からじゃなくて右端からも行ける？
これ普通のやつは回収するとき右下からだから無理だけど、反転させた奴は回収もできるんじゃないか？言葉で説明することが難しい
実装できた。無駄はあるがこれがやりたかったもの
これだと密度が高くても昨日のよりもスペースができて順置きの成功確率が上がる
提出！
得点259044 昨日の1/3くらいになってる！
相対スコアちょっとしか上がらないんだけどマジで意味わからない
そのあといろいろ工夫して
得点188839
きょうはこのくらいで
7日目
もうやることがないから蛇で遊んでみる
色分けしてみた特に何も起きなかった
今の食いちぎ戻りBFSは狙っている胴体の色じゃない餌食べた後に食いちぎるとその間違えた餌直前までさかのぼりその後は捨てるようにしているが、これがうまくいってないっぽい
という事でバグ取りをする
ついでにランダム要素がちょびっとあるから時間いっぱい何回も試すようにする
提出
得点 135409まぁまぁいいんじゃない？
8日目
何もせず
なんか日時ずれた気がする
9日目
もう新しいことは思いつかなそうだから1%改善みたいなことをやっていく
時間いっぱい何回も試すところにバグがあったので直す
提出 87116 え！？こんな点数低くなるの？バグ直すの大事だな
この提出したコード順置きを一回も使っていないかもしれない
食いちぎ戻りのほうのやつでBFSして目当ての餌が取れないときなんでもいいから近くの餌一つ食べるようにしていたが目当ての餌まで他の餌関係なく突っ込むようにしてみた
得点 89552 誤差だな
10日目
もう何も思いつかないよ！
プログラムの制限時間を1900msにしてみる
おわりに
今回長期AHCをやり切った感想は思いつくこと全部やった達成感がありますね
ですが、暫定テストで青パフォギリギリしか出なくて黄パフォを目的にしていたのでとても悔しいです。
AHCの勉強していきたいな
