【AtCoder】ABC301 D - Bitmask を二分探索問題と勘違いしていた
異端な解き方をしたようなのでメモ。
問題
考えたこと
Sの長さは最大60。
?の個数も最大60。
→単調増加の世界にできたら二分探索ができそう。
二分探索できるか検討してみる
例えばN=184、S="10?1??0?"の場合を考えてみる。
※図における「AC」と「WA」は公式解説動画の二分探索でよく使われている「正解ゾーン」と「不正解ゾーン」の意味。
?部分だけをbitとして持った64bit整数型で二分探索できそう。
ではどこから開始するか。
二分探索するためには絶対に正解であるACゾーンと、絶対に不正解であるWAゾーンを指定しなければならない。
ACゾーンの決定
?が全て0だったら最小値なのでACとなり得るか？
→ NO。前述の例の場合、Nが143などであればACではない。しかし全ての?が0でN以下にできないならばこの時点で-1を出力して終了すれば良い。この前提を踏まえた上であれば、ACゾーンを0から開始して良い。
WAゾーンの決定
これはシンプルに?を全て1にした場合の数+1と言える。前述の例で言えば190。この値は実現不可能なので正解になり得ない。
実装
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
auto solve(string S, ll N) -> ll {
vll indicies;
for (ll i = S.size() - 1; i >= 0; --i) {
if (S[i] == '?') {
indicies.push_back(i);
}
}
auto to_ll = [&](ll m) {
string s(S);
for (ll i = 0; i < indicies.size(); ++i) {
s[indicies[i]] = (m >> i) & 1 ? '1' : '0';
}
ll n = 0;
ll v = 1;
for (ll i = s.size() - 1; i >= 0; --i) {
n += v * (s[i] - '0');
v *= 2;
}
return n;
};
if (N < to_ll(0)) {
return -1;
}
ll ac = 0;
ll wa = 1LL << indicies.size();
while (wa - ac > 1) {
ll wj = (wa + ac) / 2;
if (N >= to_ll(wj))
ac = wj;
else
wa = wj;
}
return to_ll(ac);
}
int main() {
string S;
cin >> S;
ll N;
cin >> N;
cout << solve(S, N) << endl;
return 0;
}