おはようございます。しほみんです。
今日は前回に引き続きエイシングコンテストのD問題を振り返ります。最近、競プロからはちょっと離れていますが、まあ基本役に立ちそうなことがなさそうなのが悲しいところです。ただ、一問一問をしっかり理解することでできることが増えているので確実に復習はして精進したいところです。
D問題
popcount(n)を「nの2進数表記の1の個数」とします。
例えば、popcount(3)=2,popcount(7)=3,popcount(0)=0です。
f(n)を「nをpopcount(n)で割ったあまりを置き換える」という操作を繰り返した際、nが0になるまで繰り返した数とします。
2進数表記でN桁の整数が与えられます。1<=i<=Nを満たすiについて、i桁目のビットを反転した整数をXiとします。
f(X1),f(X2),....,f(Xn)を求めなさい。
2進数とあまりに関する問題です。何言ってるかわからないですが、道筋さえ立てば素直に実装して解ける問題です。
といっても最初道筋を立てることができないですよね....30分ぐらいうんうんうなってました。
最初に考えたことは以下の3つです。
・最初は数が大きくてlong型でも処理できないが、1回行えば、次の数は200000以下になるなあ。
・2回目以降、2進数にすると桁はせいぜい20もないぐらい。つまり、1回やるとあまりは急速に減るので4,5回やればなんか終わりそう。
・処理をN回やるから、一回の桁での動作はlogNが限界。つまり、2回目以降の操作は実直に計算できそう。
となると、1回目の操作を高速化することをさらに突き詰めないとなあとなります。
1回目の操作で注目すべきことは各iにおいて、ビット反転するのでpopcountは高々１回しか変わらないってことです。つまり、最初に与えられたビットの配列に対しての数Xのpopcount(X)は高々1しか変わらないです。よって、それぞれ与えられたXiはpopcount(X)±1での余りしかないはず....
ということで、各桁は2の(N-i)乗を示しているので、それをpopcount(X)±1で割った数をもとめて、足しておきます（これは繰り返し二乗法を用いてlogNで求められます）。
あとは、各桁において、0から1になったら2の(N-i)乗のpopcount(X)+1で割ったあまりを出し、1から0になったら2の(N-i)乗のpopcount(X)-1で割ったあまりを引けばよいです。
これによって、最初の一回の操作はo(1)で処理可能です。
あとは、一回操作後は素直にlong型でその数を2進数表現して、1の数を数え、割っていき、0になるまでの回数を求めればよいです。これはo(logN)程度です。
よって、最初の準備を合わせてo(NlogN+NlogN)で十分間に合います。
ここまでくると、0で割ることを気にしないとならないです。
つまりpopcount(X)-1=0のときです。この例外は、別で処理しないとエラー起こります。
このケースですが、全部0のときか、1つだけ1のときのみがあり得ます。
よって、最初のpopcount(X)=0か1のときだけ例外処理します。
・popcount(X)=0のとき
全部、1回の処理で0になるので、全部1を出力します。
・popcount(X)=1のとき
まず、ビットが1のところは処理しないで済むので0で出力します。
ビットが0のところは1のところが2つあるのですが、popcount(X) = 2なので、次は1か0です。これは一番最後の桁が1かどうかで決まります。
最初の1の位置が、一番最後の桁の場合...それ以外の場所は一回の操作で1になるので、2回の操作で完結します。2を出力します。
最初の1の位置が、一番最後の桁ではなく、一番最後の桁以外も場合....すべて、一回の動作で0になるので。0を出力します。
最初の1の位置が、一番最後の桁ではなく、一番最後の桁も場合....1回で1になるので2回目の操作で完結します。よって、2を出力します。
これさえやっておけば、一回動作をすることは必ず保証されます。なので、この処理をして、そのあとは適当にやらせればどうにかなります。
まとめると、
1. まず、ビット配列を把握。popcount(X)を求める。
2. popcount(X)=0か1のときは例外処理を行う。
3. 最初のビット配列からpopcount(X)±1のとき、1回目操作後の数を求めておく（Aとする）
4.i番目のビット反転をして、0から1のときはAから2の(N-i)乗のpopcount(X)+1で割ったあまりを足す。1から0のときはAから2の(N-i)乗のpopcount(X)-1で割ったあまりを引く。これを、1回目の操作後の数にする（Bとする）。
5. Bに対して、2進数表記をして1の数を求めて、popcount(X)を出し、あまりを出す。
6. 0になるまで5を繰り返す。その回数を記録する。
7. 4-6を各桁でおこなう。
8. 全部出力する。
2-4の工程をきちんと気が付いて解けるかが勝負で、D問題としてはかなり難しい部類かなと感じました。例外処理と高速化はE問題でも十分でそうです。
最後に....
まずはできることから考えてみて、肉付けしていくと気が付きやすいです。例外処理は具体的に考えてからだと意外と気が付けます。
とはいえ、これは精進の結果かなと思います。今までさんざんこういう問題気が付けなかったので。
どっちかというと知識の問題より数学パズル的な感じだったので楽しかったなあと思います（解ければ楽しいというバイアス）。
ではでは。
