Atcoder Heuristic Constest 002の解き直し
自分のマラソン力向上のために，Atcoder Heuristic Constest 002(AHC002)を解き直した．
そのついでに解説を書きます．
当時参加したときの順位は位でパフォーマンスは
でした．
解き直して，自力で到達できたスコアは
m点で本番順位換算で
位相当，パフォーマンスは
ぐらい？になった．
本番の制限時間である4時間で，ここまでたどり着ける気がしない…
AHC002問題概要
マスの空間に
or
，
の大きさのタイルが敷き詰められている．
- 各マスには点数（
–
）がつけられている．
- 上下左右，隣り合うマスに移動しながら，同じタイルを2度踏むことなく，なるべく多くの点数を集めよ．
- ちゃんとした問題文
解法
初期解を作って，それを焼きなまし．
初期解の作り方
初期解はスタート地点からランダムに進める方向に進んで，進めなくなったら数手巻き戻し，また進める方向に進むという方法を取った． このままだと，局所解から抜け出せないことが多かったので，評価値がしばらく改善されなかったら，スタート地点から計算をやり直しさせた．
初期解の評価関数は（踏んだマスの点数の和） （経路の長さ）
とした．
には特に意味はなく，最終的なスコアが良かったから採用した．
評価関数に経路の長さを加えたのは，後で焼きなますことを考えると，現状のスコアよりも，経路の長さのほうが大切じゃない？とおもったから．
経路長だけで評価することも試してみたが，スコアを含めたほうがスコアは良かった．
この計算をms行って，評価値が一番高いものを初期解とした．
ちなみに，この時点でのスコアはおおよそ
点で，制限時間いっぱい回すと，おおよそ
点になった．
焼きなまし
近傍（遷移先の候補）は現在の経路の一部（長さ –
程度）を壊して，その部分をつなぎ直すことで作った．
経路を壊す長さは時間とともに短くなるようにした．
つなぎ直し方は，壊した長さ分適当に動いて，その後，つなぎ先がある場所へ向けて進む方法を取った．
なので，つなぎ直せることもあれば，つなぎ直せないこともある．
経路を壊して，つなぎ直したときにスコアが改善したら，次はその付近を壊すことにした．
例えば，周りがすでに踏んだタイルによって囲まれていると，壊した部分のつなぎ方が通りしかなく，改善の余地ない．
スコアが改善できなかった場所は行き詰まっている可能性があるので，なるべく他の場所を選びたい．
スコアが改善できた場所はまだ，改善の余地がある可能性が高いので，その付近を壊すことにした．
近傍に遷移するかしないかは，序盤は経路の長さかスコアのどちらかを見て決め，終盤は最終的なスコアのほうが大切なので，スコアのみを見て決めた．
焼きなましの初期温度は，経路をつなぎ直せたときに，遷移する確率が程度になるように決めた．
冷却は実行時間とともに線形に減らした．
非線形な冷却も試してみたが，線形に減らすのが一番スコアが高かった．焼きなまし難しい．
また，しばらく遷移が起きないとき，前回遷移があった温度付近まで加熱するというのを採用した．
これを制限時間いっぱいまでやった．
改善の余地
焼きなましをもう少し高速化したら初期解をパターン用意して，焼きなましできそう．
初期解によっては，焼きなまししてもスコアが伸びないことがあったから，初期解のパターンを増やすと，スコアが安定するはず．
現状で
パターン実行すると，焼きなましの時間が足りないように見える．
焼きなましのときに，経路の端（スタートと反対側の点）は固定したけど，動かしたほうがいい気がする． 気が向いたら実装しようかな？
感想
思ったよりもいいスコアが出たが，やはり時間で実装はできるきがしない．
改めて，上位陣の凄さを感じた．
スコアが安定しない．同じ入力であっても，上振れると
点，下振れると
点になる．
辛い．なんか安定させる方法ないかな？
やはり焼きなまし
回走らせたいな．
焼きなまし技術が高ければスコアが伸びるのかな？
これまでのマラソンコンテストでは気にならなかったけど，ローカルとジャッジサーバーで速度差が意外とあり，なかなか面倒だった．
理由はわからないけど，ローカルではms程度回さないとジャッジサーバーの点数に追いつけない．
m1 macbook airなので，そこまで遅いことはないと思うんだけどな…
Optunaを使ってパラメタを探したけど，なんか微妙． 使い方悪かったのかな？
実行例
余談
記事タイトルの改行のしかたがわからない．"し"が気になる
HACK TO THE FUTURE 2022 予選に参加しました
HACK TO THE FUTURE 2022 予選に参加しました． 結果は暫定テスト40位，システムテスト39位でした． 個人的に良い順位が取れて，気分がいいので，解説を書きます． やったことは，公式の解説放送で解説されていることがほとんどなので，解説放送を見た人向けに書きます． 参考になるかわかりませんが，個性を出した部分はアンダーラインを引いています．
ちなみに，最終提出版のseed=0のビジュアライザーはこんなかんじになりました．
問題概要
- メンバー数20人のチームがあり，完了すべきタスクが1000個ある．メンバーにタスクを割り振って，なるべく早くすべてのタスクを終わらせよう．
- タスクには依存関係がある．
- 例） タスク
はタスク
とタスク
を終わらせないと始めることができない．
- 例） タスク
- あるタスクが完了するまでの日数は，タスクを割り振られたメンバーの技能レベルとタスクが必要とする技能レベルによって決まる．
- メンバーの技能レベルは与えられないので，推定する必要がある．
立てた方針
問題を大雑把に以下の3つに分けて考えた．
- メンバーの技能レベルの推定
- タスクの優先順位の決定
- タスクの割り振り
2番目，3番目の問題は1番目の問題に依存している． メンバーの技能レベルの推定値が変わることで，タスクの優先順位は変わるはずだし，各メンバーがタスク完了までにかかる推定日数も変わる． よって，計算の流れは以下のようにした．
- いくつかタスクを実行
- 実行したタスクからメンバーの技能レベルを推定
- タスクの優先順位を更新
- タスクを割り振り，実行
- 2に戻る
これを全タスクが完了するまで繰り返した．
やったことの解説
メンバーの技能レベル推定
- 各メンバーが完了したタスクとかかった日数を記録しておく．
- （タスク完了までにかかった日数）と（技能レベルから予想される日数）の差の２乗の和が小さくなるような技能レベルを推定した．
- 推定には遺伝的アルゴリズムに似た方法を使って最適化した．
- 技能レベルの推定は，前回の推定からこなしたタスクの数が30個を超えるたびに行った．
- あまり高い頻度で推定しても意味がない気がしたから設定した．
タスクの優先順位の計算
- 技能レベルが更新されるたびに，着手されていないタスクについて，各メンバーの実行時間を計算．
- 優先順位の決め方は公式解説と同じで，パスの重みを少し工夫した．
- パスの重みはタスク実行にかかる時間の短い5人の実行時間の平均（総和）
- 5人いたら1人ぐらいは手が開いてるんじゃない？という想定
タスクの割り振り方
- 大きく分けて２つの段階に別れている．
- 一番早くタスクを終わらせることができる人にタスクを与える段階
- タスクを持っていない人へ強制的にタスクを与える段階
一番早くタスクを終わらせる事ができる人にタスクを与える段階
- 着手可能なタスクを優先順位の高い順に見る．
- 一番早く，そのタスクを終わらせることのできる人を選ぶ．
- （かかる日数）
（現在処理中のタスクが終わるまでの日数）
（新たに着手するタスクにかかる日数）
- 現在処理中のタスクがある人は，かかる日数に3日加える．
- 実際にかかる時間は（能力から決まる日数）
なので，3日程度早くならないと美味しくない気がしたから加えた．
- 実際にかかる時間は（能力から決まる日数）
- （かかる日数）
- 一番早く，そのタスクを終わらせることができる人の手が空いていたら，そのタスク与える．
- 手が空いていない場合は，そのタスクを実行しない．
タスクを持っていない人へ強制的にタスクを与える段階
- 上記の方法だけだと，能力の低い人に仕事が回らないので，強制的にタスクを与えた．
- 上記と同様に着手可能なタスクを優先順位の高い順に見る．
そのタスクをこなす早さが，早い人達と大差がないときは，そのタスクを与える．
- 優先順位の計算のときに使った，タスク実行時間の短い人5人の実行時間の総和
と比較した．
- 優先順位の計算のときに使った，タスク実行時間の短い人5人の実行時間の総和
最終盤では，強制的にタスクを与えない．
- 最終盤で技能レベルの低い人にタスクを与えるとスコアが悪くなることが多いため．
時間があったらやりたかったこと
タスクの割り振り方に幅をもたせる
- ビームサーチ的なことがしたかったけど，実装が重くて諦めた．
タスクの依存関係の数でパラメタや方法を変える
- タスクの依存関係の数とスコアに関係があることはコンテスト中にわかっていたが，なにかする時間と気力がなかった．
解説はここまでで，あとは日記と感想です．
コンテスト中の日記
1 – 4日目
- 技能レベルをを推定しながらタスクの優先順位を決めていくという方針はすぐに立った．
- 技能レベル推定は面倒なので，とりあえず，優先順位をいい感じに決めていく方針で，プログラムを書き始めた．
- タスクの優先順位の決め方は解説部分とほぼ同じで，パスの重みはタスクの必要技能レベルの合計にした．
- なんかバグってるような気がしつつも，人並みに点数が取れていたので，気にしなかった．
- 実際に優先順位計算部分にバグがあり，番号の若い順番にタスクが実行されていた．
- 番号の若い順番に実行するのはそれなりに強いので，人並みに点数が取れていた．
6 – 7日目
- 能力推定を始めた．
- 思ったよりもスコアが伸びないので，あれこれ考え始めた．
- なんか初期化する値やパラメタを変えたらスコアが伸びた．
- スコアが伸びると気分がいいので，パラメタ調整に執心する．
- 明らかに適切でないパラメタを入れてもスコアが伸びたので，バグがあることを確信し，デバッグ開始．
8 – 9日目
- 野球を見ていたので，あまり作業が進まなかった．
- オリックス・バファローズのファンで，7年ぶりのCSだったので，どうしても見たかったので仕方ない．
- この解説的なものも日本シリーズを見ながら，書いてます．
最終日
- 00:00ごろに，デバッグが終わったものを提出すると，96kだった．
- 朝起きてからは，適当に思いついたアイデアを実装&人力でパラメタ調整．
- 100k点に乗せたかったが数百点足りなかった．
- 暫定テストのテストケースに偏りがあることに気づいていたので，最終提出はseed=0–149で実行したときに，スコアが一番高いものを提出し，コンテスト終了．
感想
最初に立てた方針がよかったようで，公式解説と同じような事はできていたが，デバッグに時間がかかり，つらかった． デバッグをもうちょっと早く終わらせたら，色々できた気がする． 暫定順位が40位で，3000円がもらえるかと思ったけど，システムテストで1つ順位があがって39位になった． 順位があがったのは嬉しいけど，3000円ほしかったな…
上位の人はMCMCを使っているようなので，ベイズ統計学の勉強をして，ベイジアンになりたい． なんかいい本ないかな？PRMLは一度挫折したからなぁ…
良かった点として，長期コンテストで2桁順位になれたこと． 短期コンテストではAHC004で一度だけ2桁順位になったけど，運でなった感じがしていた． 今回のコンテストは運ではなく実力で取った感じがして，すごく気分がいい．
もう一つ良かったのは，Golangでコンテストに出るのに慣れてきたこと． Pypy3やPython3 + Numba + Numpyでやっていたときより，やりやすい気がする． コードを書く量はGolangのほうが長くなってしまうけど，実行速度を気にしないでかけるのは楽だ． Pythonだと，書き方によって実行速度が変わったりして，よくわからないところに気を使わなければいけなかった． アルゴリズムのコンテストもGolangに乗り換えたいけど，乗り換える労力が大きいので，Python3のままかな.
あと京セラプログラミングコンテスト（AtCoder Heuristic Contest 006）のレート増加と合わせて，Heuristicのレートが2000を超えました．アルゴリズムのレートの倍近くになってしまった．
余談
技能レベルの推定に遺伝的アルゴリズムを使ったのは，chokudaiさんが「遺伝的アルゴリズムがコンテストで勝ったのを見たことない」的なことをtwitterでつぶやいていたのを見て，使いたい気分になったからです． 変な遊び心を出さずに普通に焼きなましすべきだったかな？
