ALGO ARTIS プログラミングコンテスト2023 冬（AHC028）に参加して、93位/918人 でした。
解法や所感について書いていきます。
解法
大筋
一単語ずつ選んでいくビームサーチをしました。
遷移は、
- 暫定解の末尾との重複度合いの大きさ
- 現マスからの近さ
の順で単語に優先度を振って、その上位5個くらいを選んで打鍵、としました。
ノードの評価は通算コストにしました。
提出コード
Submission #49255662 - ALGO ARTIS Programming Contest 2023 Winter（AtCoder Heuristic Contest 028）
解法内でよく分からなかったところ
選んだ単語の打鍵の経路の出し方について、最適経路でない方が良いスコアが出ました。
最初はビームサーチで経路を求めていたのを、後からDP手法(厳密解を出せる(はず))に気付いて書き換える、という流れを経たんですが、DP手法にした方がスコアが悪くなってしまいました。
単純にDPの実装をミスっただけなのか、あるいは、ここの計算が適度に悪い方がビームサーチがむしろ良い塩梅に進む みたいな感じだったのかもしれません。
雑感
- 「貪欲法をした後、それを使ってビームサーチをする」というテンプレパターンをやった回だった。
- 最近では珍しく(?)シンプルに考察できる回だった気がする*1。順位とレートの相関の高い回だったんじゃないかなという気がする（確認はしてないですが）。
- コンテスト後に考えてみたけど、このビームサーチだと利益の先食いみたいなことが起きるだけであんまり嬉しく無さそうな気がした。打鍵コストの低い単語が序盤に当てがわれるだけで、全体を通した効率改善みたいなものに利するわけでは無いように感じる。TLの雰囲気からも感じたが、やっぱりローカルサーチ回だったのだろうか。
*1:ビームサーチや焼きなましに落としやすいというか
