Anything Goes to Makura
https://youtu.be/-iPh3Vuhp80?si=LFi7mcAijUoMQgHp&t=66
「すべてがまくらになっていく」と聴こえること、また
「えにしんぐごーずとぅまくら」と音数が同じことから。
…というわけで、ここからはAnything Goes to Zeroの解き方について解説していく。
問題概要
非負整数$ nについて、関数$ \mathrm{popcount}(n)を
$ nを二進数表記したときの$ 1の個数。
例えば、$ \mathrm{popcount}(3)=2,~ \mathrm{popcount}(7)=3,~ \mathrm{popcount}(0)=0。
と定義する。また、非負整数$ nについて、関数$ f(n)を
「$ nを$ \mathrm{popcount}(n)で割った余りに置き換える」という操作を繰り返した際に$ nが$ 0になるまでの操作回数
と定義する。例えば、$ f(7)は、以下のように$ 2回の操作で$ n=0となるため、$ f(7)=2となる。
$ \mathrm{popcount}(7)=3なので、$ 7を$ 3で割った余りである$ 1に置き換える。
$ \mathrm{popcount}(1)=1なので、$ 1を$ 1で割った余りである$ 0に置き換える。
二進数表記で$ N桁の整数$ Xが与えられる。また、$ 1 \leq i \leq Nを満たす整数$ iに対して、$ Xの上から$ i桁目が$ 0なら$ 1に、$ 1なら$ 0に変更した整数と$ X_iと定義する。
$ f(X_1),f(X_2),...,f(X_N)をそれぞれ求めよ。
制約
- $ 1 \leq N \leq 2 \times 10^5
- $ Xは先頭の桁が$ 0とは限らない$ N桁の整数
考察
まず、$ X_iについて考えてみよう。$ Xの上から$ i桁目の数字を$ d_iと定義すると、$ X_iの定義より、
$ d_i = 0の時は$ X_i=X+2^{N-i}
$ d_i = 1の時は$ X_i=X-2^{N-i}
となる。
これらについて、$ f(X_i)をそれぞれ求めるために、$ \mathrm{popcount}(X_i)の値を知りたいが、全ての$ iについて計算していると、$ X_iが全部で$ N個あり、それぞれについて1桁ずつ確認するのでそれぞれ$ N回かかり、計算量が$ O(N^2)($ O(A)は大体$ A回くらいの計算回数ということを表す)となってしまい、実行時間制限に間に合わない。
ところが、$ X_iは$ Xから一桁だけ変更したものであるから、実は$ \mathrm{popcount}(X)の結果を使いまわすことで、$ d_iを見れば$ \mathrm{popcount}(X_i)はすぐにわかる。
具体的には、
$ d_i=0の場合は$ \mathrm{popcount}(X_i)=\mathrm{popcount}(X)+1
$ d_i=1の場合は$ \mathrm{popcount}(X_i)=\mathrm{popcount}(X)-1
となる。
さて、$ \mathrm{popcount}(X_i)の値がわかったので、$ f(X_i)の計算をしよう。
$ A ~ \% Bを、$ Aを$ Bで割った余りと定義することにすると、 ここまでの議論で、最初の計算として、
$ d_i=0の場合は$ (X+2^{N-i}) ~\% ~(\mathrm{popcount}(X) + 1)で$ X_iを置き換える
$ d_i=1の場合は$ (X-2^{N-i}) ~\% ~(\mathrm{popcount}(X) - 1)で$ X_iを置き換える
が必要なことがわかる。
$ d_i=0のときについて考えてみる。
あまりの性質より、
$ (X+2^{N-i}) ~\% ~(\mathrm{popcount}(X) + 1)
$ \equiv (X ~\% ~(\mathrm{popcount}(X) + 1))+(2^{N-i} ~\% ~(\mathrm{popcount}(X) + 1)) \pmod{(\mathrm{popcount}(X) + 1)} )
とわかる。
まず、$ (2^{N-i} ~\% ~(\mathrm{popcount}(X) + 1))について計算しよう。
実は、$ n \geq 0, m \geq 1を満たす整数$ n,mについて、任意の整数$ aのべき乗$ a^n ~\mathrm{mod}~{m}は、繰り返し二乗法という手法を用いて、$ O(log N)で計算可能である。 続いて、$ (X ~\% ~(\mathrm{popcount}(X) + 1))についても計算しよう。
$ d_i=1となるような$ iそれぞれに対して、$ (2^{N-i} ~\% ~(\mathrm{popcount}(X) + 1)))の和をとって$ (\mathrm{popcount}(X) + 1)で割った余りを見ればいいので、結局、$ 0 \leq i \leq N - 1を満たす整数において、$ (2^i ~\% ~(\mathrm{popcount}(X) + 1)))を高速に求める問題に帰着される。
これは、先ほど紹介した方法で$ i一つあたり$ O(log N)で計算でき、それが最大で$ N回繰り返されるから$ (X ~\% ~(\mathrm{popcount}(X) + 1))の計算全体として$ O(N~log~N)で可能だ。
しかも、この計算は一度だけでよい。
以上を考えれば、最初の置き換えを全体$ O(N~log~N)で実行できる。
2回目以降の置き換えについて、置き換えた後の$ X_iは$ \mathrm{popcount}(X) + 1未満であることから、大雑把に見積もっても二進数で20桁以下の数となるので、愚直にシミュレーションしても十分時間制限に間に合う。
このペースでいけば、すぐに$ n=0になりそうと予想もたつ。
正確には、およそ$ O(\mathrm{log}~N)で$ 0になることが説明できる。
以上より、$ d_i=0となる$ f(X_i)について、全体で計算回数$ O(N~log~N)回で答えることができる。
また、これは$ d_i=1の時も同様の議論が適用できる。
よって、この問題を計算量$ O(N~log~N)で解くことができた。
解答例(C++)
$ \mathrm{popcount}(X)=1のときがコーナーケース。
$ d_i=1となる唯一の桁において$ \mathrm{popcount}(X_i) = 0となり、余りを取ることができない(そもそも操作をする必要がない)ことに注意しよう。
上記解説とは異なり、0-indexed(0から数え始めること)で実装した。
code: answer.cpp
#define rep(i, a, b) for(long long i = (a); i < (b); i++) using namespace std;
using namespace atcoder;
int main() {
long long n;
string x;
cin >> n >> x;
long long pcX = 0;
rep(i, 0, n) pcX += (xi == '1'); long long pcPlus = pcX + 1, pcMinus = pcX - 1;
long long modXPlus = 0, modXMinus = 0;
rep(i, 0, n) {
modXPlus += pow_mod(2, n - 1 - i, pcPlus);
if(pcMinus != 0) {
modXMinus += pow_mod(2, n - 1 - i, pcMinus);
}
}
}
modXPlus %= pcPlus;
if(pcMinus != 0) modXMinus %= pcMinus;
rep(i, 0, n) {
long long ans = 0;
long long num = 0;
num = (modXPlus + pow_mod(2, n - 1 - i, pcPlus)) % pcPlus;
ans++;
}
else {
if(pcMinus != 0) {
num = ((modXMinus - pow_mod(2, n - 1 - i, pcMinus)) + pcMinus) % pcMinus;
ans++;
}
}
while(num > 0) {
num = num % __builtin_popcountll(num);
ans++;
}
cout << ans << endl;
}
}