ARC227 D - Median of Binary Strings

考え方

目標文字列 $1$ つを作れる必要十分条件について考える。

まず、問題を簡略化して、目標は 000...00 であると仮定してよい。
目標文字列に 1 が含まれている場合、全文字列のその位置の 0 1 を入れ替えればよい。
$S$ 側も含めて全て入れ替えを行うならば、問題としては同等のものとなる。

まず、$2$ 文字の文字列で考えてみる。
仮に、01 10 11 と、目標以外の文字列が全てあったとしよう。
ここから 00 を作れるかというと、作れない。
なぜなら、まず、全て異なる $3$ 個を選んだ場合、できるのは 11 である。
そして、同じものを $2$ つ使った場合にできる文字列はその $2$ つ使った文字列そのものである。
よって、どうやっても 00 になることはない。
したがって、$2$ 文字の場合に 00 を作れる必要十分条件は、それが最初からあることである。

では、次に $3$ 文字の文字列で考えてみる。
この場合、まず「任意の $2$ ヶ所について、同時に $0$ にする方法がある」が必要条件である。
つまり、「任意の $2$ ヶ所について、同時に $0$ になっている文字列が $S$ の中にある」が必要条件。
そして、これは十分条件でもある。

位置 $i$ から $i+1$ までが 00 になっている文字列がある。
位置 $i+1$ から $i+2$ までが 00 になっている文字列がある。
そして、位置 $i$ と $i+2$ が両方 0 になっている文字列がある。
これら $3$ つで合成を行うと、位置 $i$ から $i+2$ までが 000 になっている文字列ができる。

位置 $i$ から $i+2$ までが 000 になっている文字列がある。
位置 $i+1$ から $i+3$ までが 000 になっている文字列がある。
そして、位置 $i$ と $i+3$ が両方 0 になっている文字列がある。
これら $3$ つで合成を行うと、位置 $i$ から $i+3$ までが 0000 になっている文字列ができる。

同様の操作により連続する 0 の個数を伸ばしていけば、最終的に全体が 0 の文字列ができる。
したがって、「任意の $2$ ヶ所について、同時に $0$ になっている文字列が $S$ の中にある」が必要十分条件。

目標は 000...00 であるとした仮定を外しても同様。
したがって、「任意の $2$ ヶ所について、それらが目標と一致する文字列が $S$ の中にある」が必要十分条件。
よって、事前に $i,j$ の組 $\frac{M(M-1)}{2}$ 個それぞれ、00 01 10 11 の組が存在するか確認しておけばよい。

ただし、$M=1$ の場合だけは、この議論を適用できない。
この場合は新しい文字列がどうせ作れないため、「そのものが存在するか」を愚直処理する。

$M \geq 2$ の場合の計算量は $O((N+Q)M^2)$ である。

入力例1での動作

入力を受け取る。

n: 3
m: 3
q: 2
s: {"000", "011", "101"}

まず、各 $2$ 位置の組について、その位置の文字の組が s のどこかに存在するか調べる。

位置 $0,1$ については、それぞれの文字列から 00 01 10 が得られる。
位置 $0,2$ については、00 01 11 が得られる。
位置 $1,2$ については、00 11 01 が得られる。

最初のクエリは 000 である。
各位置の組で必要になるのは全て 00 であり、いずれも s の中に存在する。
よって、Yes を出力する。

次のクエリは 001 である。
必要な文字の組は、位置 $0,1$ では 00、位置 $0,2$ では 01、位置 $1,2$ では 01 である。
これらはいずれも s の中に存在する。
よって、Yes を出力する。

注意点

$M=1$ の場合は、$2$ 位置の組を用いた判定ができない。
この場合は、「そのものが存在するか」を直接確認する。

別解

特になし。