Y箱

勢いに乗って、予選の問題Cを解いた。
今やらないと、しばらくできないような気がしたので。


この問題、当日は時間が無くて手をつけられなくて、終了後に全数アタックで実装してSmallだけ解いた。
でも、そのやりかただと例題の最後のやつ1つも解けないわけで、全面みなおし。

かかった時間は、70msec弱。 上々かな。



何個か手で解いてみて、数字を並べて眺めていて思った。
もとの数から直接解答の数を作れないかな。
これでほぼできたに等しい。

虫食い算を解くようなもの。下の桁から繰り上がりとかを考えなから条件を詰めていって埋めていく。情報が少ないので、aとbを決定することはできないけれど、1のビットの合計を求めるのに支障はない。

考えかた
- Nのある桁が1だったときと0だったときのaとbの対応する桁がどうなるべきか、下の位からの繰り上がりの有無を加味して考える。

表にしてみる

繰り上がり  N:0    N:1
 なし           A      B
 あり           C      D

・Aの時
繰り上がりがなしで、Nの値が0になるのだから、aとbの対応する桁の数は0と0、1と1の2通り考えられる。1の個数を最大化したいのだから、ここは1と1で決まり。そして上の桁に繰り上がる。

・Bの時
繰り上がりなしで、Nの値が1になるには、aとbの対応する桁の数は1と0、0と1の2通り。どちらの場合も1の個数は同じなので、1と0に決める。上の桁には繰り上がらない。

・Cの時
繰り上がりありで、Nの値が0になるのだから、aとbの対応する桁の数は1と0、0と1の2通り。どちらの場合も1の個数は同じなので、1と0に決める。上の桁に繰り上がる。

・Dの時
繰り上がりありで、Nの値が1になるには、aとbの対応する桁の数は0と0、1と1の2通り考えられる。ここもは1と1で決まり。
というわけにはいかない。もしこれが、Nの最上位ビットだった場合には繰り上でてしまってはいけない。なので、ここは、Nの最上位ビットかどうかで振り分けなければいけない。
最上位ビットの場合は0と0、そうでなければ1と1で上の桁に繰り上がる。

ちなみに、他の場合で最上位ビットであるかどうかの判定はしなくていい。Nの最上位ビットは0でないのでAとCは考慮不要だし、Bの場合は上位に繰り上がらないので、やはり考慮不要。

このロジックで、最下位ビットから順にaとbを決めていけばいい。

あてはめてやってみる。Nが25とすると二進数では、11001。
1の位は1。繰り上がりなし。パターンB。 aとbの1の位は0と1。繰り上がらない。
2の位は0。繰り上がりなし。パターンA。 aとbの2の位は1と1。繰り上がる。
4の位は0。繰り上がりあり。パターンC。 aとbの4の位は0と1。繰り上がる。
8の位は1。繰り上がりあり。パターンD。 最上位ではない。aとbの8の位は1と1。繰り上がる。
16の位は1。繰り上がりあり。パターンD。 最上位。aとbの16の位は0と0。繰り上がらない。

ということで、aとbは

a 01010(2) = 10(10)
b 01111(2) = 15(10)

ということになる。aとbの0/1は入れ替えられるので、別解は、

a 01011(2) = 11(10)
b 01110(2) = 14(10)

当然1の数は同じで6個。


ソースはこれ



・check-one-digit
A、B、C、Dのロジックをそのまま実装したもの。
Nのビット、下位からの繰り上がり、最上位ビットかどうか を受け取って、aとbのビットの合計と、上位への繰り上がりがあるかどうかを返す。

・lsb
nの最下位ビットを返す。

・msb?
nが最上位ビットかどうかを返す。
正しい実装ではない。対象を減らしながらループしているので、nが1だったら最上位まで来たことになるのを利用している。

・gcj-pC
本体
Nの最下位ビットを取りながら再帰で回している。ビットの合計数を加算しながら回しているのでaとbがどんな数なのかは考えていない。


おまけ
Nの二進数表記を得るときに、最初のプログラムではInteger/toBinaryStringを使っていたけれども、Nがintを超えてしまうと使えない(あたりまえ)。二進化を自前で作ろうかと思ったけど、考えてみたら、最下位ビットから順に取り出せればいいだけなので、「2で割った余り」=「最下位ビット」と、右ビットシフトで次に進めるで対応できることに気づいた。よかった。