CSA FII Code Final Round Online Mirror F - Flawed Olympiad

https://csacademy.com/contest/fii-code-2019-final-round-online-mirror/task/flawed-olympiad/statement/

問題概要

要素数 $N$ の非負整数列 $A_{1}, ..., A_{N}$ と非負整数 $x$ が与えられる。数列 $A_{1}, ..., A_{N}$ の要素間に | （ビットOR）または & （ビットAND）を入れて出来る式であって、計算結果が $x$ となるものを1つ求めよ。そのような式が存在しない場合は impossible を出力せよ。

ここでORとANDの演算に優先順位はなく、左から順に処理されるものとする。

制約

$1\le N \le 10^{5}$
$0 \le x, A_{i} \lt 2^{30}$

解法

この記事では値同士の関係を、ビットが立っているところを要素とする集合の記号で表現することがあります。例えば $A \supseteq B$ は $B$ が $A$ の部分集合であること、つまり、 $B$ で立っている桁のビットは全て $A$ でも立っているという意味になります。

後ろから考える

最終的な計算結果に近いのは後ろの方の値なので、後ろから考えていきます。

一番後ろの要素である $A_{N}$ の直前に置く演算子としてANDを採用できる条件は、 $A_{N} \supseteq x$ であることです。

そして「ここにANDを採用したとき、 $A_{1}, ..., A_{N-1}$ の演算結果がどのような条件を満たすべきか」を考えることができて、具体的には

$A_{N}, x$ ともに0であるような桁については、どちらでもよい。
$A_{N}$ で1、 $x$ で0であるような桁については、0である必要がある。
$A_{N}, x$ ともに1であるような桁については、1である必要がある。

と判断することができます。

f:id:betrue12:20190414154527p:plain

一番後ろの要素である $A_{N}$ の直前に置く演算子としてORを採用できる条件は、逆に $A_{N} \subseteq x$ であることです。

そして同様に「ここにORを採用したとき、 $A_{1}, ..., A_{N-1}$ の演算結果がどのような条件を満たすべきか」については

$A_{N}, x$ ともに0であるような桁については、0である必要がある。
$A_{N}$ で0、 $x$ で1であるような桁については、1である必要がある。
$A_{N}, x$ ともに1であるような桁については、どちらでもよい。

と判断することができます。

f:id:betrue12:20190414155657p:plain

1つずつ決めていく

このように、OR/ANDそれぞれについて「その演算子を採用できる条件」と「その演算子を採用した場合、それ以前までの計算結果はどのような条件を満たすべきか」を求めることができます。これを繰り返していくことで後ろから順番に演算子を決めていくことができそうです。

後の説明のために定式化しておきましょう。 $dp\lbrack i \rbrack\lbrack d \rbrack$ を「 $A_{i}$ より後ろの演算子を決めた時、 $A_{1}, ..., A_{i}$ までの演算結果の $d$ 桁目はどのような状態になっているべきか」を表現する値とします。この値は「0である必要がある」「1である必要がある」「どちらでもよい」の3通りです。

遷移については、 $dp\lbrack i \rbrack$ と $A_{i}$ の値から $dp\lbrack i-1 \rbrack$ を更新します。一度「どちらでもよい」という扱いになった桁は無視することにして、先ほどと同じように考えて $A_{i}$ の直前の演算子を決定します。

OR/ANDのうちどちらかしか採用できない場合は単純にそちらを選び、どちらも採用できない場合はその時点で impossible と出力して終了します。問題なのはどちらも採用できる場合で、これを両方とも調べようとするとパターン数が爆発します。

OR/AND両方採用できる場合を考える

では、OR/AND両方採用できる場合というものが具体的にどうなっているか考えます。これは「どちらでもよい」桁を除いて $x$ と $dp\lbrack i \rbrack$ が一致している場合です。

このときもし $A_{i}$ の直前にANDを採用すれば、図で示すように $dp\lbrack i-1 \rbrack$ は「1である必要がある」桁と「どちらでもよい」桁だけになります。であれば、 $A_{i-1}$ までの値のビットはとにかく立てたほうが得なので、それ以前は全てORを採用するのが最善です。つまり $A_{0}, ..., A_{i-1}$ のORを計算してしまって「1である必要がある」ビットが全て立っていればそれが答えになりますし、そうでなければ $A_{i}$ の直前にANDを採用してはいけないことになります。

f:id:betrue12:20190414161224p:plain

同様に、もし $A_{i}$ の直前にORを採用すれば、 $dp\lbrack i-1 \rbrack$ は「0である必要がある」桁と「どちらでもよい」桁だけになります。そのため $A_{i-1}$ 以前は全てANDを採用するのが最善となり、それを計算することによって答えが得られるか $A_{i}$ の直前にORを採用してはいけないことが分かります。

f:id:betrue12:20190414162207p:plain