E - Divide and Divide Editorial
by 
MMNMM
\(f(N)=\lceil\log _ 2N\rceil\) とします。
答えは \(N(f(N)+1)-2 ^ {f(N)}\) です。
証明
帰納法で証明します。
\(N=1\) のとき、\(f(N)=0\) なので、\(N(f(N)+1)-2 ^ {f(N)}=1\times1-1=0\) となり、正しいです。
\(1\leq N\lt n\) で成り立っていると仮定し、\(N=n\) で成り立っていることを示します。
\(1\lt n\) なので、まずコスト \(n\) をかけて \(l=\left\lfloor\dfrac n2\right\rfloor,r=\left\lceil\dfrac n2\right\rceil\) を黒板に書きます。 それぞれがすべて \(1\) になるまで操作を行うので、全体でかかるコストは、帰納法の仮定より \(n+l(f(l)+1)+r(f( r)+1)-2 ^ {f(l)}-2 ^ {f( r)}\) です。
\(f(l)=\begin{cases}f(n)-2&(n=2 ^ {f(n)-1}+1)\\f(n)-1&(\text{otherwise})\end{cases}\) および \(f( r)=f(n)-1\) が成り立ちます。
証明
\(f(n)\) の定義より、\(2 ^ {f(n)-1}\lt n\leq2 ^ {f(n)}\) です。
両辺 \(2\) で割ると \(2 ^ {f(n)-2}\lt n/2\leq2 ^ {f(n)-1}\) です。
\(2 ^ {f(n)-1}\) は整数なので \(2 ^ {f(n)-2}\lt n/2\leq\lceil n/2\rceil\leq2 ^ {f(n)-1}\) が成り立ち、\(f( r)=f(n)-1\) です。
\(2 ^ {f(n)-1}+2\leq n\) なら、\(2 ^ {f(n)-2}+1\leq\lfloor n/2\rfloor\leq n/2\leq2 ^ {f(n)-1}\) が成り立つので \(f(l)=f(n)-1\) です。
\(2 ^ {f(n)-1}+1=n\) なら、\(l=2 ^ {f(n)-2}\) なので \(f(l)=f(n)-2\) です。
\(n=2 ^ {f(n)-1}+1\) かどうかによって場合分けを行います。
- \(n=2 ^ {f(n)-1}+1\) のとき、\(l=2 ^ {f(n)-2}=2 ^ {f(l)}\) です。 よって、 \[ \begin{aligned} &\phantom{=}n+l(f(l)+1)+r(f( r)+1)-2 ^ {f(l)}-2 ^ {f( r)}\\ &=n+l(f(n)-1)+rf(n)-2 ^ {f(l)}-2 ^ {f( r)}\\ &=n+(l+r)f(n)-2 ^ {f(n)-2}-2 ^ {f(n)-2}-2 ^ {f(n)-1}\\ &=n+nf(n)-2 ^ {f(n)}(2 ^ {-2}+2 ^ {-2}+2 ^ {-1})\\ &=n(f(n)+1)-2 ^ {f(n)} \end{aligned}\] となります。
- \(n\neq2 ^ {f(n)-1}+1\) のとき、 \[ \begin{aligned} &\phantom{=}n+l(f(l)+1)+r(f( r)+1)-2 ^ {f(l)}-2 ^ {f( r)}\\ &=n+lf(n)+rf(n)-2 ^ {f(l)}-2 ^ {f( r)}\\ &=n+(l+r)f(n)-2 ^ {f(n)-1}-2 ^ {f(n)-1}\\ &=n+nf(n)-2 ^ {f(n)}(2 ^ {-1}+2 ^ {-1})\\ &=n(f(n)+1)-2 ^ {f(n)} \end{aligned}\] となります。
以上より、\(N=n\) でも成立することが示されました。
ワードサイズを \(w\ (1\leq N\lt 2 ^ w)\) として \(f(N)\) を求めるのは \(O(\log w)\) 時間などで可能です（たとえば、\(N-1\) の最上位ビットから下の部分を \(1\) で埋め、popcount を計算することなどで求められます）。
これを実装することで、高速にこの問題を解くことができます。
#include <iostream>
int main() {
using namespace std;
unsigned long N;
cin >> N;
unsigned long fN = N - 1;
fN |= fN >> 1;
fN |= fN >> 2;
fN |= fN >> 4;
fN |= fN >> 8;
fN |= fN >> 16;
fN |= fN >> 32;
fN = (fN & 0x5555555555555555) + (fN & 0xAAAAAAAAAAAAAAAA) / 2;
fN = (fN & 0x3333333333333333) + (fN & 0xCCCCCCCCCCCCCCCC) / 4;
fN = (fN & 0x0F0F0F0F0F0F0F0F) + (fN & 0xF0F0F0F0F0F0F0F0) / 16;
fN = (fN & 0x00FF00FF00FF00FF) + (fN & 0xFF00FF00FF00FF00) / 256;
fN = (fN & 0x0000FFFF0000FFFF) + (fN & 0xFFFF0000FFFF0000) / 65536;
fN = (fN & 0x00000000FFFFFFFF) + (fN & 0xFFFFFFFF00000000) / 4294967296;
cout << N * (fN + 1) - (1UL << fN) << endl;
return 0;
}
posted:
last update: