ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）参加記【最終71位】
こんにちは、notkamonohasiと申します。
ALGO ARTIS プログラミングコンテスト2023冬（AHC028）に参加しました。スコア1.077Mで最終順位71位でした。
コンテスト中の流れをぼんやり書きたいと思います。
解法概要
- 焼きなましで単語の順番を決める。焼きなましの遷移は「文字aで始まって文字bで終わる2つの部分文字列をswap」
- キーの順番は毎回DPで最適解を計算
前提知識
- DP（1000Diff程度）
コンテスト中の流れ
0:00[0.000M] ～問題を見た直後の考察～
頻出の「最適化したい対象が2種類ある」問題。前回のAA社コンもそうで、この時は選択を間違えていたので、どちらを重視するかよく考えたい。
0:36[0.950M] ～DPでキーの順番の最適化～
単語の順番を決めた時の、キーの順番の最適解はDPで出せる。単語の順番は入力と同じ順番にして、とりあえずDPだけを実装する*1。短期コンだと後で書き直すことはできないので、関数・クラスは最初から真面目に実装します。
提出すると0.950Mで15位、同じ点数の人が他に3人いて安心。
1:00[1.032M] ～しりとりで総文字数を減らす～
次は単語の順番を決める。総文字数は少ない方が有利なので、しりとりになるようにします。欲しい最初の文字を持つ単語がないときは、適当に選ぶ（←後で真面目に考える必要あり！）
提出すると1.032Mで21位
1:20[1.068M] ～山登りで単語の順番を改善～
現時点での計算時間が4msなので山登りで解を改善します。「単語の順番」と「キーの順番」の2つのどちらをメインにするか考えるが、「キーの順番」は最適解を出せるので「単語の順番」をメインに決定。
山登りの遷移のみが唯一自分の解法の非自明な箇所、遷移は「文字aで始まって文字bで終わる2つの部分文字列をswap」としました。思いついた経緯は以下の2つ
- シンプルに「適当な2つの単語をswapする」だけだと、総文字数が増えてしまうので、遷移が受理される確率が低くなる。iterが十分回るならそれで良いが、DPが重いため回数を稼げない
- この遷移だと、遷移に関係ない単語への影響が小さいので、遷移が受理される確率が十分高そう
（蛇足）少し考えると、単語の順番を変えるとキーの順番が大きく変わってしまうので、良くないのでは？となる。しかし、AtCoder11周年記念コンテスト（AA社とTHIRD社とFuture社の対抗戦）で似たような話があって、「文脈がある問題でも、良い解の形は保存される」（？）という議論になっていたので、「まあ良いでしょ」の気持ちで実装を始めた。
提出すると1.068M
1:51[1.070M] ～DPを高速化～
山登りのiterが5000回程度しか回っておらず、計算時間を増やして実行すると多少スコアが上がったので、遷移のボトルネックになっているDPを高速化します。
今のDPテーブルは、文字列をSとして
としています。しかし、各文字が存在する場所は決まっているので、ほとんどの箇所は到達不可能となっており無駄が多いです。各文字について、存在する場所に番号を与えると、DPテーブルを約
に圧縮することができて、計算量を減らすことができます。今回はiter回数が2倍になりました*2。
圧縮と復元の実装でバグらせて、30分かかったのは反省。
提出すると1.070M、思ったより伸びず
2:12[1.075M] ～焼きなまし～
山登りを適当に焼きなましに変えます。iter回数が少ないので期待していなかったのですが、思ったより上がりました。
提出すると1.075M
4:00[1.077M] ～無～
遷移を増やしたり、初期解を複数生成したりしたが、大きなスコアアップには繋がらず。悪あがきで乱数シードガチャをしていました。。。
反省
chokudaiさんやhenoさん、公式解説がおっしゃっていたをスコアとする方法が、自分の初期解に対する違和感を綺麗に定式化していて、なるほど～となりました。
適当に考えた初期解の生成方法を改善せず、安易に「山登り・焼きなましを改善すればスコアを上げられるはずだ！」と思ってしまったのが今回の敗因でした。
最後に
AtCoderの皆様、writerのterryさん、スポンサーのALGO ARTISさん、コンテストを開催してくださり、ありがとうございました！
