CodeChef May Challenge 2020 - Chef and Bitwise Product

• 問題
• AC

いったん$L$と$R$を無視して考えると、$X$と$Y$の少なくとも一方が立っているビットは$Z$も1にしたほうがよいし、そうでないビットは0にするべきである。

$L$と$R$を導入する場合にもこの考え方が使える。桁DPのように「$L$にはりついている」フラグと「$R$にはりついている」フラグを持ちながら、上位の桁から$Z$を全探索することを考える。両フラグがオフになった枝は残りをどう選んでも$L$より大きく$R$より小さいことが確定するので、残りの桁は上の考え方によって一通りに決めることができる。探索する枝は桁数に対して高々線形になる。