Educational Codeforces Round 94 F. x-prime Substrings

Problem - F - Codeforces

自分の解法が非想定解っぽいので書き残しておきます。

問題概要

$x$ を正整数とする。 $1, 2, ..., 9$ の数字からなる文字列が $x$ -primeであることを、以下の2つをともに満たすことと定義する。

全ての数字の和が $x$ である。
任意の連続部分列について、その数字の和は $x$ より小さい $x$ の約数ではない。

$1, 2, ..., 9$ の数字からなる文字列 $s$ が与えられる。この $s$ からいくつかの文字を取り除くことで、 $s$ のどの連続部分列も $x$ -primeでないようにしたい。そのために取り除く文字数の最小値を求めよ。

制約

$1 \le |s| \le 1000$
$s$ は $1, 2, ..., 9$ からなる
$1 \le x \le 20$

解法

$n = |s|$ とし、文字列ではなく整数の数列 $a_{0}, a_{1}, ..., a_{n-1}$ として解説します。

ある要素を右端とする連続部分列の和として登場する値の集合を考えます。これは以下の図のように列挙することができます。便宜上 $0$ も含めておきます。

f:id:betrue12:20200826200930p:plain

これらの値のうち考えるべきは $x$ 以下の値だけです。この登場する値の集合を、値 $k$ を含んでいたら $2^{k}$ のビットが立つようなビット列で表現します。こうすると、この範囲内に存在する連続部分列の和としてあり得るものは、ビット列において立っている2つのビット同士の距離と見なすことができます。

このようなビット列は $2^{x+1}$ 通り考えられますが、その中で、「 $x$ -primeになるので登場してはいけないNGパターン」がいくつかあります。具体的には $x$ ビット目が立っていて、立っているどの2つのビット同士の距離も $x$ より小さい $x$ の約数ではない場合、そのビット列に対応する連続部分列は $x$ -primeなので登場してはいけません。逆に全ての要素について、その要素を右端としたときのビット列がNGパターンではない場合、そのような数列は $x$ -primeな連続部分列を持ちません。

ということで、このビット列をキーとしたDPをします。

$dp\lbrack i\rbrack\lbrack s\rbrack =$ 数列を $a_{i-1}$ まで見て、最後に採用した要素を右端とする連続部分列の和として登場する値の集合（ビット列）が $s$ であるときの、これまでに削除した文字数の最小値

$dp\lbrack i\rbrack\lbrack s\rbrack$ からの遷移は2通りあります。もし $a_{i}$ を削除する場合、 $dp\lbrack i\rbrack\lbrack s\rbrack + 1$ が $dp\lbrack i+1\rbrack\lbrack s\rbrack$ の候補になります。もし $a_{i}$ を削除せずに繋げる場合、 $s$ は「左に $a_{i}$ 桁だけビットシフトして、 $1$ を足して、 $2^{x+1}$ で割った余りを取る」という操作をした値に変化します。この変化後の値を $s^{\prime}$ として、もしこれがNGパターンでなければ $dp\lbrack i\rbrack\lbrack s\rbrack$ が $dp\lbrack i+1\rbrack\lbrack s^{\prime}\rbrack$ の候補になります。

このDPを回すと答えが求められる…と言いたいところですが、全体計算量 $O(n2^{x})$ はちょっと間に合いません。状態を削減する必要があります。

ここで注目するのが $1$ という要素の存在です。 $1$ という要素を含んだ連続部分列は、 $x=1$ である場合を除いて絶対に $x$ -primeになりません。そのため与えられた数列を $1$ で分割してパーツごとに独立に解き、それぞれの削除すべき最小文字数を全て足したものを答えとしても良いです。

このときDPの対象となる数列は $1$ を含まない前提で考えることができるので、 $2^{x+1}$ 通りのビット列のうち多くのものは絶対に登場しません。具体的には隣り合うビットが1組でも同時に立っているものは登場しないと考えることができます。この条件を踏まえると、考えるべきビット列は $x=20$ のときでも $28657$ 通りです。これらの状態だけを扱うDPをすると間に合います。