執筆時レート：水色

問題文→https://atcoder.jp/contests/abc301/tasks/abc301_d
公式解説→https://atcoder.jp/contests/abc301/tasks/abc301_d/editorial

問題

0, 1, ?からなる文字列 $S$ および整数 $N$ が与えられる．
$S$ に含まれる?をそれぞれ0または1に置き換えて2進数と見なしたとき， $N$ 以下で最大のものを(10進数として)出力せよ．
ただし，そのような $N$ 以下の値が存在しなければ，-1を出力せよ．

制約

$S$ は0, 1, ?からなる文字列
$1 \leq |S| \leq 60$
$1 \leq N \leq {10}^{18}$
$N$ は整数

解説

$S$ にある?の個数を $K$ とすると，作られる2進数は ${2}^{K}$ 種類になる．
このうち $N$ 以下で最大のものを見つけたい．
サンプルケース1で樹形図を書いてみる．

ここで $N$ がどこにあるか書き込むと，

$N$ 以下をOKとすると単調性が見えてきた．二分探索っぽい．

?を上の桁から見ていって，1にしてもOKのものが存在するなら1にしたら良い．存在しなければ0にする．
「OKのものが存在するか」というのは，単調性により，その桁を1にしたときの最小値がOKかどうかを見れば良い．
つまり，その桁以降の?をすべて0にした数がN以下かどうかを見れば良い．

?ではない桁はどう扱うか．
$S$ では1で $N$ では0だとその時点で必ず $S$ が上回ってしまう．
その時点で答えが-1であることは確定する．
他の1と0の組のパターンはN以下であることが保たれるので問題ない．
下の実装では途中で処理を打ち切らずに，最終的な答えが $N$ 以下であるか，後で評価している．

実装

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0; i<n; i++)
using ll = long long;

int main() {
  string s;
  ll n;
  cin>>s>>n;

  int len=s.size();

  // よく使うので2のべき乗を前計算
  // p2[i]=2のlen-i-1乗の値
  vector<ll> p2(len);
  p2[len-1]=1;
  for(int i=len-2;i>=0;i--) p2[i]=p2[i+1]*2;

  ll res=0;
  rep(i,len) {
    // 上からi桁目を見る

    if(s[i]=='?') {
      // この桁を1にして，それ以降の?を0にした値がn以下か？
      ll val=res;
      val+=p2[i];
      for(int j=i+1;j<len;j++) {
        if(s[j]=='1') val+=p2[i];
      }

      if(val<=n) {
        // この桁を1として良い
        res+=p2[i];
      }

    }else{
      if(s[i]=='1') {
        res+=p2[i];
      }
    }
  }

  // 最後にn以下かチェック
  if(res<=n) cout<< res <<'\n';
  else cout<< -1 <<'\n';

  return 0;
}

楽な実装

公式解説(楽な実装)では，最初に $S$ のすべての?を0に変えた値が $N$ 以下かをチェックしている．

$S$ から作られる数の最小値が $N$ を上回っていれば，どう作っても $N$ 以下になるはずが無いので答えは-1に確定．
そうでないならば，少なくともその最小値が $N$ 以下であるから，上の桁から見ていくアルゴリズムで必ず答えが得られることが保証される．
上の実装でのresが，よくやる二分探索の実装(okとかngとか使うやつ)でのokのように常に $N$ 以下の値を保持しているイメージがする．

なぜ上の桁から決めることが二分探索なのか？

上の桁から決めることで，表現されうる数の範囲が半分ずつに絞られていくからだ．

ちなみに

今回のABC301では初めて配点が問題に応じて調整された．
今まで：100-200-300-400-500-500-600-600
今回　：100-200-300-400-475-500-600-625

配点と言えば，過去に@kyopro_friendsさんが触れていた．

サーバル「私が配点を決めていいなら 1-2-4-8-16-32-64-128 がいいかなー」
— 競技プログラミングをするフレンズ (@kyopro_friends) 2022年12月21日

2進数表記だと
1-10-100-1000-10000-100000-1000000-10000000

ここでQuestion.
コンテスト終了後の得点が2進数表記で10110101だったら，その人は全体でどの辺りに位置しているだろうか？
二分探索で考えてみてね．

アジの開きを閉じる。

競プロ(AtCoder)中心のブログ

【解説】ABC301 D - Bitmask

問題

制約

解説

実装

楽な実装

なぜ上の桁から決めることが二分探索なのか？

ちなみに