エイシング プログラミング コンテスト 2020 D - Anything Goes to Zero
昨日のD問題，このレベルは本番で出ても難しい． 解答だけ見ると真新しい知識はないんだがビット系の問題はどこから取っ掛かりをつければ良いか勘がつかめていない．
回答時の方針
本番中に提出したのが以下のコード．
Submission #15177835 - AIsing Programming Contest 2020
問題を見てとりあえずビット演算するかという発想になった．まずこれが良くなくて与えられた制約のもとでどの程度の計算量になるか見積もるべきだった．bitsetを初めて使ったわけだがbitsetのcount()の計算量が普通に考えればO(N)なんだけど，本番中は希望的観測でO(1)でいけるのではという発想になってしまってbitsetのcountを使う実装でゴリ押ししてしまった．コード提出した結果やっぱり無理かと思ってビットカウントを高速化する課題だということに気づいたが時既にお寿司でした．
正答
上述の通りでビットカウントを高速にするのが今回のお題．愚直にやるとカウントするのにO(N)かかってしまうのでこれを高速化する必要がある．私的には今回の問題を解くために必要な発想は以下の通り．
i桁目をビット反転してもビットカウントは
+-1にしかならないi桁目をビット反転したものの値は
+=2^(i-1)になる合同式の性質の利用
2回目以降の処理については高速化の必要がない
入力例1で考えてみると
3 011
もとの値は3でビットカウントは2
3桁目を反転することを考えると0->1だからビットカウントは2+1になり，そのときの値は3+2^(3-1) = 7
各桁反転するとき0か1かでビットカウントをプラスするかマイナスするかが決まり，そのときの値は0であればその桁のぶんだけもとの値に+ 2^(i-1)すればよく1のときは逆に- 2^(i-1)すれば良いことがわかる．
Xi % popcount(Xi) を考えるときにXiは最大200000桁でありオーバーフローする可能性があるため各桁2^iについてpopcount(Xi)の剰余を逐一取りつつ計算する．
元の値とそのビットカウントとをorg_v,org_bとすると各桁を反転したときの値は 0 -> ビットカウント-> org_b+1 値-> (org_v+2^(i-1)) % (org_b+1) 1 -> ビットカウント-> org_b-1 値-> (org_v-2^(i-1)) % (org_b-1)
Submission #15197488 - AIsing Programming Contest 2020
※ポップカウントの計算は高速化の余地あり
いじょー．
