はじめに
短期AHCの場合は、深い考察をしている時間がないためとにかく筋の良い貪欲解を目指していきます
あわよくば橙パフォとれたら良いなと思っています
1.問題
N×Nのキーボードがあり、M個の縁起の良い文字列を入力したい
できるだけキーの移動量が少ない操作を求めよ。という問題でした
2.開始直後の考察
M=200という制約と縁起の良い文字列は長さ5であるということから、最大でも1000文字の入力で足りることが分かります
つまり、操作回数の上限5000回は無視できます
→出力回数や操作回数の上限の余裕度を理解しておくことは大事
前の文字列と後ろの文字列で重ねられる所は、重ねていく方が良さそう
M=200の文字列の全組み合わせは、200!=10**375なので全探索は不可能
→文字列を連結しておけば可能になる？
3.最終解法(DP+貪欲)
いきなりですが、最終解法の解説になります
解説放送(0:26~くらい)にあった、DP+貪欲とほぼ同じ解法になります
ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028）解説 - YouTube
・前処理
全文字列を比較して、4,3,2文字の重なりがあれば適宜合体させます
strMap[i][j][s] i行j列から見て、文字sについての (移動コスト, 座標) のリストを作成
・次に打ち込む文字列の全探索
現在位置(cy, cx) から文字列seachStr を入力するときの最短経路をdpで計算します
dpは、遷移先座標をキーにして、(最小コスト, 遷移元座標)を値として入れていますが、もっと良い方法があると思います
文字列seachStrについて、直前の文字入力と被る文字は省くようにしています
・打ち込む文字のdp経路復元
上で作ったdp[-1]の最小コストとなる座標から、遷移元座標を辿って経路復元します
i文字目のdp[i]内の最小コストを辿ろうとすると、正しい遷移が出来なかったため座標もメモしておいて辿る処理にしました
以上の処理を文字列分繰り返しています
4.細かい工夫
次に打ち込む文字列の全探索の際に、文字列長さと5の差の絶対値でコストを割った値を使っています
普通の文字列より、合体した文字列や直近1文字と重なっている文字を使った方が良いのでは。という気持ちで入れ、スコア向上しました
5.最終提出
pypy3で書いています
6.終わりに
短期コン難しい。という感想です
文字列のDPで最適経路までは思いつきましたが、実装が悪く遅すぎたため焼きなましには持って行けなかったと思います
長期コンの予定もいくつか決まっていて、今からわくわくしています
次も楽しめるように引き続き頑張ります
