ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

ABC138 F - Coincidence

桁DP

問題
 提出コード

解法

$(x,y)$ が問題の条件を満たすには、これらを2進数に直した時に、

最上位桁が一致している
それぞれの桁について、 $x$ の $i$ 桁目と $y$ の $i$ 桁目が一致している、もしくは $x$ のみ0で $y$ のみ1になっている

という条件を満たす必要があります。
ということで、最上位桁が下から $d$ 桁目の際の $(x,y)$ のペアを求めるために、桁DPを行います。あとはこれを全ての桁について行えばよいです。
$dp[i][j][k]$ を用意し、

$i$ :上から何桁目を見ているか(ただし最上位桁は確定しているのでないものとします)
$j$ : $x$ が $max(L, 2^{d-1})$ 以上であることが確定しているか
$i$ : $y$ が $min(R,2^{d} - 1)$ 以下であることが確定しているか

とします。
あとは、下の表をもとに遷移をひたすら書いていけばよいです… f:id:emtubasa:20190820173515p:plain

感想

$L$ の存在が邪魔で、うまい処理方法を思いつきませんでしたが、よくよく考えれば $R$ 同様フラグを立てれば処理できますね…ただ桁DPの実装は丁寧にやらないといつもバグらせるので悲しいです(コンテスト中にラスト10分で書き直したものはもちろんバグだらけでした)