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で割った余り」=「最下位ビット」と、右ビットシフトで次に進めるで対応できることに気づいた。よかった。

Code Jam Japan予選のB問題。 ふと思い出したときにちょこっと考えていたりしたんだけど、やりかた思いついたので、やってみた。 解けた。

もうちょっと効率を上げたりできそうだけど、500msちょっとで解けたんだからまあこれでいいでしょう。




予選当日に考えた方式は以下の通り。結果としてこの方式で解いた。

戦略

- 今日何を飲むかではなくて、このコーヒーはいつ飲むのかを考える。
- 満足度の高いコーヒーから飲む日を決めていく。
- 飲む日はどうやって決めるのか？

たとえば
 - 期間が5日
 - 満足度(S)10 賞味期限(T)が3日のコーヒーAが2杯(C)
 - 満足度1 賞味期限が5日のコーヒーBが5杯
の場合、
   3日目にコーヒーAが残っていたら飲むのはA
   3日目にAを飲む場合、2日目にAが残っていたら飲むのはA
このように、賞味期限の日からさかのぼって埋めていけばむだなく割り当てることができる。

- 他のコーヒーの予定がすでにが入っているときはそこをとばす。

上記のAのコーヒーは、Tが3でCが2なので、3日目と2日目に飲む。
Bのコーヒーは、Tが5でCが5なので、5日目、4日目、3日目と2日目は埋まっているからとばして、あとは1日目に飲む。

当日のアルゴリズム

当日は、これを実現するために、全体の日程を配列にして埋めていく方法を採った。
上記の場合ならこんな感じ。
 ooooo
 oAAoo
 BAABB
実際は、配列の要素には、決定したコーヒーの満足度を入れておいて、最後に全部足して答えとしていました。

でも、この方式でLargeが解けないのは明白。
日数が1兆を超えるような条件では、どんなに小さくしても配列が作れない。


改良版のアルゴリズム

- 日程の情報を持てないので、選んだコーヒーがどれだけ飲めるかを決定するロジックできないかどうか考えることにした。

- あるコーヒーは、T日目からさかのぼってC日間飲める。すでに飲むコーヒーが決っている日はとばす。この「とばす」のをなんとかすればいい。

で、無くしてしまえないかと考えた。

とばすのではなくて、決った日を取りのぞいてしまう。
そして、その分期間を減らす。 あと、残っているコーヒーの賞味期限も変更しないといけない。
その方法はこんな感じ。

GCJJ運営からメールが来て、予選の問題の解説が掲載されたらしい。

でも、くやしいから自分で納得できる解答ができるまで見ないよ。
見ないみない。

Code Jam Japan予選のA問題。当日終ってから考えたロジックを実装してみた。
結果は上でき。 ということで、解説です。




その方法は、逆順でのトレース。
知りたい場所のカードが初めにどこにあったのかを考えるわけ。
図を書いたので、貼りつけ。


ソースはこれ



なんと、1秒以下で答がでた。

今日は環境を調えて、6時間みっちり Code Jam やりました。

結局 AとBのSmallだけしか時間内にできなかった。
Cの問題はそれほど時間がかからなそうだったけど、順番に解くのにこだわりたくて、でも、結局だめだったけど。
時間切れ後に、いちおう、CのSmallも解いてみた。

次回は、1つぐらいLargeが解けるようになっていたい。


問題が公開されているんで、一応僕の書いたコードを。



あら。 Gistって修正すると、貼ったやつも変っちゃうんだね。便利なような不便なような。
Gistベースで修正してるので、随時更新されます。
前のを見たい人は、下の方のリンクからGistに直接アクセスしてくださいです(10/7)


問題Aです。
最初は書いてあるとおりに解いた。Smallだと数秒で解ける。
修正版は、Largeでも250ms程度で解けた。 完了。




問題Bです。
最初からいちおうしらみつぶしでないやりかたを模索した。
現在修正中。


問題 C。
時間切れ後に解いた。 問題のとおり。でも、Small解くのに1分半くらいかかってしまう。
そのうち修正。