ABC126 F - XOR Matching - ツバサの備忘録

問題
 提出コード

解法

$M=1$ の場合
$K=0$ ならば $0 \ 0 \ 1 \ 1$ もしくは $0 \ 1 \ 1 \ 0$ もしくは $1 \ 0 \ 0 \ 1$ を出力すればよく、それ以外ならば $-1$ を出力します。
それ以外の場合
$K \geqq 2^{M}$ の場合、数列に含まれる数字は $2^{M}-1$ までの関係で、どう頑張っても $K$ を作成することができないので答えは $-1$ になります。
そうでない場合、
$0, 1, 2, ... K-1, K+1, ... 2^{M}-1, K, 2^{M}-1, ... K+1, K-1, ... 2, 1, 0, K$
という数列を作成することで問題の条件を満たします。
まず、挟み込んでいる2つの数字 $a_{i},a_{j}$ については、それらでxorを取った時点で打ち消しあって0になるので、考えなくてよいです。
$0$ から $2^{M}-1$ の全ての数字についてのxorを取ると、全ての桁について、立っているビットは全体の半分で偶数であり、結局は0になります。
そこからある数 $X$ についてのxorだけを取らないことを考えると、これは $0$ と $X$ についてのxorを取ることと変わらないため、結局 $X$ になります。
ということは、2つの $K$ で挟み込まれている部分のxorが $K$ となるには、 $K$ 以外の $[0,2^{M})$ についてのxorを取っていればよく、逆に $K$ 以外の数字で挟みこまれている部分のxorが $K$ になるには、 $K$ を1つだけ用意しておいて、それ以外の数字についてのxorが0になっていればよいので、上のような数列を用意してあげればよいことになります。

感想

せっかく考察がはやく終わったのに、デバッグに1時間ぐらいかかったうえ、結局バグはサンプルケース( $M = 1$ の部分)だったということに気づいたのが終了数分前でした。
ACできる考察を用意する前では、コーナーケースとして処理していたのですが、ACできる考察のコードに、その処理を記述し忘れていました…
この手のバグ取りに時間をかけてしまう(+サンプルを通さない)のはよくない気がしているので気を付けたいですね。

解法

感想