コンテストページ: パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder
コンテスト中AC: A〜C
コンテスト後にD,Eを自力AC

D - Bitmask

以下の説明で、 $N$ の最大値を十分に超えるため、最上位ビットを63としておきます。 $S$ がこれより小さい場合はサイズが63になるように0を追加しておきます。

上位のビットから?のビットを決定していくことを考えます。上位ビットをできるだけ大きくした方が、値として大きくできるため、優先します。

この時、 $N$ より小さい数にするために、?を使うのは高々1箇所であると言えます。なぜなら、一度 $N$ 未満となれば、その後の下位ビットをどのようにしたとしても、 $N$ 以上となることはありえないからです。

仮に $i$ 番目のビットで $S$ が $N$ 未満であることが確定した場合に最適解であったとします。この時、最上位ビットから $i+1$ 番目までのビットは $N$ と $S$ で一致していることが言えます。

もし一致していなければ、 $i$ 番目より上位のビットで $S$ が $N$ 未満であるか、 $N$ より大きいかのいずれかとなってしまいます。

また、 $i-1$ 番目以降の?は全て1にするのが最適です。

$S$ を $N$ 未満にするというのは、 $N$ の $i$ ビット目が1であり、かつ、 $S$ の $i$ ビット目が?である状況で、?を0にすることと言えます。

そこで、 $S$ の?を1つずつ0にした場合について、その時の $S$ の最大値を全探索します。この時、

$L_i:=$ $S$ の最上位ビットから $i$ ビット目までについて、?の箇所を全て $N$ と同一にし、 $i-1$ 以降は0であるような値

$R_i:=$ $S$ の0ビット目から $i$ ビット目までについて、?の箇所を全て1とし、 $i+1$ ビット目以降は0であるような値

となるように配列 $L,R$ を作っておくと、 $i$ ビット目で $N$ 未満となった時の値を $L_{i+1}+R_{i-1}$ で計算できます。但し、便宜上、 $L_{64}=R_{-1}=0$ とします。(ビットを1オリジンで実装すれば-1が0になって実装しやすくなります。)
解の最大値の更新は、この値が $N$ 以下である場合のみ行えばよいです。