メモ

yukicoderでゆるふわgolf

yukicoder No.642 Two Operations No.1

問題はこちら
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