ALGO ARTIS プログラミングコンテスト2023 冬（AtCoder Heuristic Contest 028） 参加記
問題ページ
考えたこと
問題の性質上、単語に関係ないキータイプをするメリットがないことから、「文字列を作る問題」というよりは「全単語の順番を決める問題、ただし前後2単語の関係によってボーナスあり」と解釈したほうが考えやすい気がします。
そのうえで、この問題は各種事前計算をして操作をショートカットすることが有効な問題だと思いました。
その中でも、1単語を完成させるまでの手順をショートカットすることを中心に考えました。
「今の単語」「1個前の単語との重複文字数」「1個前の単語のキーボード上での終了位置」「今の単語のキーボード上での終了位置」の4つが決まれば、今の単語を完成させる最適なキーのたたき方は一意に定まります。その最適なたたき方は一回計算しておけば使いまわしが可能です。
どう使うかはともかく、この事前計算をしてテーブルを作っておいて損をすることはないはずと考え、私としては珍しく足回りから実装を始めました。
事前計算テーブルの構築と解の持ち方
以下のようなDPを事前計算します（以降、キーボード上の位置は1次元化して扱います）。
dp[w][filled][now][end] = (単語wがfilled文字埋まっていて指が位置nowにあり、単語wを完成させるとき最後の指の位置がendであるとき、単語wを完成させるまでの最小コスト）
DPの次元数は 200 * 6 * 15^2 * 15^2 ≒ 6.1*10^7 ということでちょうどいい感じになります[1] 。
また、2単語ペアでの重複文字数もM*M 通りを事前に全列挙しておきます。
common[Wa][Wb] = (単語Waの後ろに単語Wbが続く時の重複文字数)
このDPテーブルと重複文字数テーブル使うと決めてしまえば、解の持ち方も (単語W, 単語終了位置E) の列にすることが自然に定まります。
すなわち
と解をもつとき [2]、以下のように全体コストが計算できます。
この全体コストの形を見ると、(W,E)を2個連続した単位ごとに独立に計算できるものであるとわかります。一部を変更したときも変更したところだけ再計算をすればよい、差分計算が効きやすい形です。
焼きなまし
ということで (単語W, 単語終了位置E) の列としてなるべく良いものを選ぶ問題になったのですが、私は単純な焼きなましで解きました。利用した遷移は無作為な(単語W, 終了位置E) を1個選んで別の場所に移す、という遷移だけです。
ただし、(単語W, 終了位置E)の移動先は無作為に選ぶわけではなく、全探索をして貪欲に選びます。すなわち、移動先としてありうる全ての場所から元の位置を除いたM-1箇所を全探索し、さらに終了位置Eは単語Wの最後の文字に一致するキーボード上の位置を全探索します。
よって、一回の遷移でおよそ 199 * 15^2 / 26 パターンを試行し、全てのパターンでスコアの差分計算を行い、最もスコアの高い移動先・終了位置を選んで遷移とします。
個人的には焼きなましの遷移として「1変数だけ乱数にして、それ以外は貪欲に選ぶ」というパターンをよく利用します。このパターンの利点として2つ考えています。
- 全く見込みのない遷移をする可能性が減らせる (気がする)
- ボトルネックが貪欲の内側に局所化されるため、定数倍高速化がやりやすい
差分計算について
以下のような遷移を考えます。 (Wx,Ex) のペアを移動させ、かつ Ex を Eyに変更します。
遷移前： ...,(Wa,Ea),(Wx,Ex),(Wb,Eb),...,(Wc,Ec),(Wd,Ed),...
遷移後： ...,(Wa,Ea),(Wb,Eb),...,(Wc,Ec),(Wx,Ey),(Wd,Ed),...
差分計算としては 遷移前では「(Wa,Ea),(Wx,Ex)」「(Wx,Ex),(Wb,Eb)」「(Wc,Ec),(Wd,Ed)」の部分を計算し、遷移後では「(Wa,Ea),(Wb,Eb)」「(Wc,Ec),(Wx,Ey)」「(Wx,Ey),(Wd,Ed)」の部分だけ計算すれば十分です。
先述の通り、(W,E)を2個連続した単位ごとにDPテーブルとcommonテーブルを用いてスコアの部分的な計算ができます。
提出コード
コンテスト中の提出コード https://atcoder.jp/contests/ahc028/submissions/49255252
- 1095650点 16位
- 手元で6万回程度遷移が回った。 スコア計算は1億回程度？
定数倍高速化をしたバージョン https://atcoder.jp/contests/ahc028/submissions/49266866
- 1099617点 本番8位相当
- コンテスト中のコードより5倍くらい速くなってしまった。これが本番でできていれば...
Discussion