blogskol

思わず声に出して読みたくなるブログ

2-回文作問

競技プログラミングにおいて回文の問題はそれなりに考えられているが、 $2$ -回文はそうでも無いだろうなと思ったので思いつくままに書く
解法が分かったら都度追記する

2-回文とは？

「アイアンマン」の様に二つの回文の和で表せる文を2-回文と言う
最も非自明な2-回文は何か
— drogskol (@cureskol) 2021年11月15日

$2$ つの回文の和で表せる文のこと
同様に $k$ -回文が定義出来る
空文字列は回文と見做すことにする（従って $k$ 回文は $k+1$ 回文でもある）

先行研究

$2$ -回文かどうかの判定は Manacher を使えば線形で出来る

arxiv.org $S$ が $k$ -回文であるような最小の $k$ を $O(|S| \log |S|)$ で求めるアルゴリズムが乗ってる
前読んだけどあんまり覚えてない

www.asahi.com 同様の問題を $O(|S|^2)$ で求めるアルゴリズムが誘導を用いて丁寧に問われている

今のところ「小岩井コーヒー」です
— drogskol (@cureskol) 2021年11月15日

小岩井コーヒーは $2$ -回文

問題集

以下文字の種類数を $B$ とし、 $S,T$ を文字列、 $N,M$ をそれらの長さとする
部分文字列と書いたら連続のと非連続のそれぞれ考える

置換距離

$S$ を $2$ -回文にするために置換する必要のある最小文字数
例 : $S$ = "abcded" なら c を a に変更すればいいので答えは $1$

畳み込みで $O(BN\log N)$ と $O(N^{1.5} \log N)$ は思いつくけど多項式の形が特殊なのでもっと早くなりそう
そもそも畳み込みが必須とも思えない
ワードサイズを $W$ として $O(BN^2/W)$ とかも出来て、高速化頑張られると区別が大変そう
この問題に限った話じゃ無いけど、bit 列の時だけ速くなるとかもありそう

合ってるかしら pic.twitter.com/Rckk6kUixu
— drogskol (@cureskol) 2022年4月27日

書いた

$i$ 文字目の変更コストが $A_i$ の場合は？

部分文字列の個数

$S$ の部分文字列のうち $2$ -回文であるものの個数（ multiset のつもり）*1

辞書順 $K$ 番目

$S$ のアナグラムのうち辞書順で $K$ 番目の $2$ -回文
ちゃんと考えてないけどそもそも $S$ のアナグラム $2$ -回文の個数は簡単に求められるのかな直感的には二項係数とかで出来そうだけど
奇数個の文字が $3$ 個以上なら作れなくて、 $2$ 個なら回文の中心 $2$ つが決定するのであとは残りの文字の振り分け
$0,1$ 個の時もほぼ同様に解けそう

連結

文字列集合 $S_1,\dots,S_n$ を好きな順序で連結させて $2$ -回文にすることが出来るか
最小何個連結させる必要があるか
連結で $k$ -回文が作れるような最小の $k$ はいくつか

素な文字列

$S$ が $i_1 , \dots ,i_k$ 文字目のみが与えられている時の何かしらを求めさせる問題

残りの文字が全て # の時 $S$ は $2$ -回文かどうか
残りの文字を自由に決めていい時 $2$ -回文に出来るか
bit列だとして、残りの文字を自由に決めていい時 $2$ -回文の最小 popcount

圧縮文字列

$S$ が文字 $c_i$ が $a_i$ 個の連結で与えられている時の何かしらを求めさせる問題
例えば c4 b2 a5 b2 c7 a5 b2 a5 c3 なら "ccccbbaaaaabbcccccccaaaaabbaaaaaccc" のこと

$2$ -回文か判定（上の例は Yes ）これは多分解ける気がする端と分け目以外は $(c_i,a_i)$ で一文字と見做して良いので

感想

文字列問題 $2$ -回文にすると全部難しくなる

*1:set では流石に難しそう？