AHC短期メモ
解説記事を読んだ上での改善含むので自力ではない
■AtCoder Heuristic Contest 002
時間：004:00
概要：フィールド上を与えられた初期位置移動してポイント稼ぎ
perf：3512(1位)
やったこと：焼きなまし
初期解をdfsをすることで発見する
初期解をベースにし、初期解の中間地点の２箇所を選択する
選んだ２点を始点、終点としdfsを再度行う
これによって新たな解を生成し焼きなましを行う。
■AtCoder Heuristic Contest 004
時間：006:00
概要：文字列が大量に与えられる。その文字列を多く含む行列を作成する。
perf：2976(6位)
やったこと：山登り法
ひとまとめに出来る文字列は纏めたほうが効率良さそう。
しかし、高々１文字とかのために結合すると自由度が減るだけなのでルールを設ける必要がある。
最低4文字とか。
文字列の連結は乱数を使用し、山登りのたびに行う。
■AtCoder Heuristic Contest 005
時間：004:00
概要：グリッドが与えられる、全ての移動可能マスが見えるような最短コストの経路を作れ
perf：3578(1位)
やったこと：kick+山登り
まず、交差点と道を全列挙する
すべての道に一度は訪れる必要があり、道から道に移動するためには
交差点から交差点に移動する。
経路はvector
1.山登り
経路を１つ消して、適当に挿入する
2.kick
経路から複数消して、適当に挿入する
1だけだと局所解にすぐハマるので、2で大幅な変更を定期的に行う。
■AtCoder Heuristic Contest 006
時間：004:00
概要：配達をしろ
perf：2996(4位)
やったこと：焼きなまし
貪欲で初期解を生成する
経路を１つ消して、適当に挿入する。挿入する候補は5つ程度試す。
これだけだと局所解にハマる可能性があるので2-optもたまに行う。
■AtCoder Heuristic Contest 007
時間：004:00
概要：オンラインで最小全域木を作れ
perf：2817(8位)
やったこと：モンテカルロ法
採用するか、採用しないか
採用しないならどの長さのものをかわりに採用することになり
コストがどれぐらいかかるかをかをシミュレーションする
■AtCoder Heuristic Contest 009
時間：004:00
概要：確率DPぽいもの
perf：3025(4位)
やったこと：焼きなまし
ランダム初期解を適当に作って、焼きなまし
■AtCoder Heuristic Contest 010
時間：004:00
概要：閉路を２つ作る
perf：2922(4位)
やったこと：焼きなまし
基本的にはAHC002とほぼ同じ。
実装がHard
■AtCoder Heuristic Contest 012
時間：004:00
概要：ケーキを切り刻んで分ける
perf：2998(4位)
やったこと：焼きなまし
初期解は縦横均等に切るところから始める。
差分計算をアルゴで培ったテクで頑張る
■AtCoder Heuristic Contest 015
時間：004:00
概要：果物を塊にしろ
perf：3043(4位)
やったこと：モンテカルロ法
ルールベースモンテカルロというらしい
■AtCoder Heuristic Contest 020
時間：004:00
概要：放送局を選択して全ての住民に配信しろ
perf：2921(6位)
やったこと：やきなまし
初期状態を各頂点に最も近い頂点におまかせした状態にする
そこから10頂点の出力を0にして同じことを繰り返す。
部分グラフの最小全域木みたいなのは頂点数が少ないので毎回やってもしれてる
■AtCoder Heuristic Contest 021
時間：004:00
概要：ピラミットをきれいにしろ
perf：3513(1位)
やったこと：
eijirouさんの提出を全部読みました
二重連鎖木の上でビームサーチをする
■AtCoder Heuristic Contest 024
時間：004:00
概要：地図をグラフとして同型にする
perf：2506(18位)
やったこと：
行を削って、適当に書き換えてコピーして消しての山登り
■AtCoder Heuristic Contest 026
時間：004:00
概要：ダンボールを運び出す
perf：3001(3位)
やったこと：
賢い貪欲をして、ビームサーチをする
ビームサーチがほとんど回らないが十分に効果がある
■AtCoder Heuristic Contest 028
時間：004:00
概要：部分文字列をいい感じに
perf：2873(8位)
やったこと：
toamさんの提出を全部読みました
ビームサーチをする
■AtCoder Heuristic Contest 032
時間：004:00
概要：Mod Stamp
perf：2660(18位)
やったこと：
貪欲が強いので、それをビームサーチにする
最後は時間の限り全探索をする
asi1024さんの実装をパクリ
■TOYOTA Programming Contest 2023 Summer final
時間：003:50
概要：コンテナを詰めて運び出す
perf：2834(5位)
モンテカルロシュミレーションをする
