問題はこちら
No.642 Two Operations No.1 - yukicoder
逆にやる。即ち問題を次のように読み替える
「X=Nから始めて次の操作でX=1に出来るか? 出来るならば最小操作回数を答えよ
操作1:Xを1増やす
操作2:Xが偶数のとき2で割る」
まず、Xが偶数なら操作2によりX/2に、Xが奇数なら操作1+操作2により(X+1)/2に変換することができるので、X≧2に対しては、Xを小さくすることができる。
つまりどのようなXから始めても必ず1にすることができる。
次に最小回数を考える。
Xが奇数のときは操作1をするしかない。
Xが偶数のときは操作2をするのが最適である。
なぜならもし操作1をした場合、再び操作1をするしか無く、(値が小さくなるのは操作2を行った時のみなので)それ以降のある時点で操作2を行うことになる。
つまりあるK≧1が存在して「操作1を2K回行う→操作2を行う」という流れになるが、これは「操作2を行う→操作1をK回行う」と同じであり、こちらのほうが操作回数が少ないので、そのようなものは考慮しなくてよい。
editorialにある次の主張を証明する。
主張:N−1 を2進数にしたときの桁数と 0 の個数の和が答えとなる
「K-1 を2進数にしたときの桁数と 0 の個数の和」をf(K)とし、先ほど同様、元とは逆の問題を考える。
f(1)=0なので、操作を1回行う毎にf(X)の値が1小さくなることを言えば良い。示すべきは次の2つ
その1:Kが奇数のときf(K+1)=f(K)-1
その2:f(K)=f(2K)-1
・その1について
K-1は偶数なので、K-1の最下位を0から1に変更するとKになる。
これにより桁数は変わらず、0の個数が1減るのでf(K+1)=f(K)-1となる。
・その2について
2K-1=2(K-1)+1なので、2K-1の最下位の1を削除することでK-1になる。
これにより桁数が1減り、0の個数は変わらないのでf(K)=f(2K)-1となる。
以上より示せた。
s; main(n){ scanf("%d",&n); while(n>1){ s+; if(n%2)n++; else n/=2; } printf("%d",s); }
やるだけ
s; main(n){ for(scanf("%d",&n);n>1;s++)n+=n%2?:-n/2; printf("%d",s); }
66B