ARMERIA

Rubyと競技プログラミングの話 AtCoderやCodeforcesの問題解説記事が多め。

Educational Codeforces Round 74 E. Keyboard Purchase

お題箱より。ただ、この問題は元々書こうと思っていました。

Problem - E - Codeforces

問題概要

 m 文字のアルファベットからなる長さ  n の文字列  S が与えられる。アルファベット  m 個を並べる順列  P を1つ決めた時、「 S の隣り合う2文字のペアそれぞれについて、そのアルファベット2つの  P での距離を求め、合計したもの」を合計コストとする。この合計コストの最小値を求めよ。

制約

  •  1 \le n \le 10^{5}
  •  1 \le m \le 20

解法

まず異なるアルファベットのペア  \frac{m(m-1)}{2} 通りについて、そのペアが  S において何回隣り合っているかを前もって集計しておきます。こうすれば以降の計算で文字列の長さ  n は関係なくなります。アルファベットのペア  (x, y) に対するペアの登場回数を  c(x, y) と書くことにします。これは隣り合っている順番を区別せず両方含むことにします、すなわち  c(x, y) = c(y, x) です。

また順列  P 上での  (x, y) の距離を  d(x, y) と書くことにします。そうすると合計コストは  c(x, y) \times d(x, y) を全てのペアについて合計したものです。

順列  P に並べるアルファベットを順に1つずつ決めていくようなDPを考えてみます。このとき単純に考えると、アルファベットを足したことによるコストの増加量を「新しく追加したアルファベット  y と既に追加済みのアルファベット  x たちについて、  c(x, y) \times d(x, y) を足す」と計算したくなります。ただし  d(x, y) を計算するには既に追加したアルファベットの順番を覚えておく必要があり、状態数が爆発します。

f:id:betrue12:20191012024502p:plain

何とかして順番を覚えなくても良いようにしたいです。順番を忘れることができれば、これは集合に対するDP、つまり状態数が  2^{m} になるようなbit DPとして解けそうです。

ここで発想を変えましょう。「アルファベットを1つ足そうとして、 P の置き場所の境目を1つまたぐときに、追加済みのアルファベットと未追加のアルファベットのペア全部について距離が1増える」と考えます。言わんとすることは図を見てください。

f:id:betrue12:20191012025028p:plain

こうするとペア数自体は多くなってしまうのですが、「追加済みのアルファベット」を一括りにできるので順番を覚えておく必要がなくなります。

こうやって計算されるコストの増加量は、アルファベットの集合  S に対する「 S に含まれる要素  x と含まれない要素  y を組み合わせた全てのペアについての、 c(x, y) の合計値」です。この値を  C(S) と書くことにすると、DPの遷移は

  • 集合  S を遷移元として、 S 含まれていない要素  y それぞれについて、 dp\lbrack S \cup \lbrace y \rbrace \rbrack \leftarrow dp\lbrack S \rbrack + C(S) と更新(より小さかったら採用)する

と行うことが出来ます。ここでDPテーブルの定義は、「集合  S に含まれている要素を既に並べていて、既に通り過ぎた境目について、アルファベットのペアがそこをまたぐ時のコスト増加量を合計したものの最小値」です。

遷移の合計回数が  O(m2^{m}) なので、あとは  C(S) を良い感じに前計算できれば間に合いそうです。

 C(S) の前計算は、こちらも  S の状態数が  2^{m} なので1個あたり  O(m) くらいで計算できれば勝ちです。これもDPで計算できます。

ある集合  S について既に  C(S) が求まっているとします。ここで  S に含まれていない要素  y を新しく  S に足すと、  C(S) に対する変化量は

  •  S に含まれている要素  x について、 (x, y) が新たに同じ集合に入るので  c(x, y) が減算される。
  •  S に含まれていない  y 以外の要素  z について、 (y, z) が違う集合に分かれるので  c(z, y) が加算される。

として計算できるので、 C(S) から  C(S\cup \lbrace y \rbrace) を差分計算できます。これは  O(m) でできます。

f:id:betrue12:20191012024928p:plain

これで前計算も  O(m2^{m}) で出来たので、間に合います。

ACコード

Submission #62145546 - Codeforces

数え上げ問題で、よく「全てのAについてのBの合計を求めよ」という問題を「Bの加算要素それぞれについて、それが含まれるAの個数を掛けたものの合計を求めよ」と言い換えるものがあります。今回も「アルファベットのペア」と「 P における置き場所の境目」について同じことをしている、と考えることが出来ますね。