先日のAHC032でHeuristc橙を達成した記念の記事です。 この記事では自分がAHCに参加するときに心がけていることを記します。参考になれば幸いです。
問題文をよく確認する
条件を読み間違えたまま考察し始めると悲惨なので、問題文は入念に読むことを心がけています。
また、アルゴのコンテストより時間に余裕があるので、それ以外の要素もしっかり確認します。
- ストーリー
問題のイメージを把握するために重要です。
- 制約
制約を確認しないと部分的に全探索するような解法を見逃す可能性があります。
- スコア計算方法
スコアの計算式から最適なパラメータが計算できることがあります。
- 入力生成方法
テストケースの特徴が解法の本質的な部分に関係していることもあります。
ビジュアライザを活用する
解を出力するプログラムが書けたら、とりあえずビジュアライザに突っ込んでみるのが良いです。
利点の1つとして、まずバグが発見しやすくなります。「山登り法を実装したはずなのに解が悪化している」「そもそも制約に反した解を出力している」といったことにすぐ気づけます。
もう1つの大きい利点が、「自分の解法の悪い部分・改善すべき部分を見つけやすくする」という点です。
例えばビジュアライザが明らかに無駄な動きをしている場合、そのような無駄が生まれない美しい解法に到れるのが理想ですが、次善策として強引に無駄を無くす処理を最後に加えたり、ペナルティを重めに課すようにするだけでもスコアが良くなります。
「最終的な解の理想形」をイメージする
これは結構重要で、ここを正確にイメージできるかどうかが最終的な順位にかなり関わってきます。 ヒューリスティックコンテストは多くの場合最適解を求めるのが困難ですが、「最適解はどうなっているか」を雰囲気だけでもイメージできると、そこから使用するアルゴリズムを逆算できます。
例えばAHC032の場合、最適解は「全てのマスで高得点(90%~95%以上？)」が1つのイメージとなります。 その場合、例えば山登り法や焼きなまし法で、「最適解に近い解」から「より良い解」への遷移を具体的に求めたり、乱択で発見することが困難であるという予想が立てられるでしょう。 一方で「1マスだけ最適な値になるスタンプを押して、そこはもう変化させない」という戦略をとれば、少なくとも81マスのうち49マスについては高得点をとれそうです。
また、スコアの上界を求めるのも1つの有効な戦略です。
例えばAHC027では、各マスを訪れる回数を√dに比例させ、かつ等間隔で訪れるものが理論上最適な解であることがわかります。これに近いものを貪欲的に求めたものを初期解として焼きなましなどで改善する手法が有効でした。
なお、この戦略は「理想的な解」のイメージを間違えてしまった場合の修正が難しいというデメリットがあり、特に操作の自由度が高い長期コンの場合に起こりがちです。
私はAHC025で、「最適解では全てのアイテムに対する重さの比がほぼ完全に求まるはずだ」という思い込みから抜け出せず、最後まで良いスコアをとれませんでした。
解を決め打って解く
具体的な解法に近いテクニックですが、「ランダムに最終形を決め打ってそれを達成する手順を求める」を時間の許す限りひたすら繰り返す、という解法が有効なことがあります。(例：AHC011)
アルゴが得意な人が手を付けやすい解法であると思います。
解法を決め打たない、考察の幅を狭めすぎない
例えば「問題文では3種類の操作が与えられているが、効果が薄そうだから操作3は使わなくてよい」などと決めつけて一度考察を始めてしまうと、実際は操作3が必要であってもなかなか原点に立ち返って一から考察することが難しくなります。
とはいえ実践するのは難しく、十分注意していないとコンテスト中の焦りも相まって楽で単純な解法に固執してしまいがちです。
また、アルゴコンでもそうですが、問題を考察する時には「何のアルゴリズムを使うか」から考えてはいけません。 問題に向き合い確実・着実なアルゴリズムを考え、それを改良するという手順で考察するべきです。
パラメータ調整は最後までとっておく
正直これは正しいのかどうかわかりません。適当すぎるパラメータではアルゴリズムの良さも判定できないような気もします。
ただ、パラメータ調整で簡単にスコアが上がるのが楽しいあまりそれに時間を使ってしまうのは当然注意が必要です。
あとがき
とりあえず短期コン1桁順位、長期コン1ページ目を目標としてこれからも頑張ります。
