Rustコトハジメ

プログラミング言語Rustと競プロに関する情報をお届けします。

【Codeforces 1238 (Div 2) E - Keyboard Purchase】ビットDP

Problem - E - Codeforces

問題

文字列が与えられ、ここにm種類の文字が入っているとする。

あなたは一本の指でキーボードを使う。キーボードには、m種類の文字を横に並べる。

文字列を打つ。この時のコストは指の移動距離の総和である。コストの最小値は?

制約: m=20, n=105

方針

エディトリを途中まで読み解く。最後の式変形は正しさはわからない。

見た目明らかにビットDPである。

DPでは、何かしら状態を決めて、それに対して計算を行ったら、それをあとの計算で使うことが出来るという、局所解が部分解になっているという性質を利用する。そのように状態を決める。

例えば、TSPでは、それまでに訪れたノードの集合 + 最後に訪れたノードの2つで状態を決める。こうすることで、この範疇だったら間違いなく最善だよねという値を求めることが出来る。こうではなく、それまでに訪れたノードの集合だけで状態を作ってしまうと、新しいノードを足した時に、必ずしもその集合において最善である場合の一番最後のノードから移動するわけではないから、破棄する可能性が出てくる。だから、2つの値で状態を構成する必要がある。

この問題では、キーボードの状態を使ったキーの集合で表して、さらに、キーボードの状態を(使ったキー)(使ってないキーの昇順)で決め打ちする。値は、使っているキーが絡むものだけで計算することとする。求めるものは、(使ったキー)(無)である。

こうすると、使ってないキーの昇順が固定されているのだから、使ったキーの集合がこれらである場合には、最善が決定出来る。例えば、aからeのキーがあるとして、cdを使ってるとすると、cdabeとdcabeなら、どちらかが最善かわかるし、2つのキーを使った場合のすべての状態に対する最善値がわかれば、3つのキーを使った場合も、それらのどれかを採用して遷移出来る。

ある集合に対して新しいキーを追加する場合、(すでに使ってるキー)(新しいキー)(使ってないキー)という順序になるが、この時、新しく追加される値は、エディトリに書いてあるようになる。(以下略)