Y箱

同じ数字でできている5組の3乗数をみつける問題。

これも全数アタック





Hashを使って分類する方法を採った。
3乗数を作って、含まれている数をリストにしてソートしたものをキーにして、Hashに入れる。
Hashに入れたときに、5つたまったらそれが答え。





- num 9
  適当なところで9から始めた。 意味は無い。

- res-map
  格納用Hash

- num-key
  キー。 3乗して数字のリストにしてソートしたもの。

あとは、キーのところに望みの数-1個 ( いまのやつがあるから -1) になっているかどうか確認しながら、再帰で回す。

四桁の3～8角数を任意の順に並べて輪を作る問題。

全くいい方法を思いつかなかったので全数アタック。





・ 4桁のX角数を全部リストアップしておく。
・ 3～8の数の順列を全部リストアップしておく。
・ 順列すべてについて、あてはまるものがあるかどうかを探す。
・ 途中でみつかっても中断せず、すべて探す

だいぶ長くなってしまった。



- triangle-num ～ octagonal
- n-digit-xgonal-num
  生成する関数とチェックする関数を両方用意した。
  4桁の数が必要なので、4桁の整数からチェックする関数でフィルターする方法を採った。

- split-into-2digit
  上位と下位の2桁ずつにわけたベクタを生成

- remove-1digit-at-second
  10の位が0の数は、題意に合わないので除外する。

- get-pe61-xgonal-list
  上記の関数をつかって、x角数のリストを作る。
  [[12 34] [56 78] ....]

- get-child
  とある4桁数 [xx yy] に続くx角数のをすべて求める。

- get-pe61-all-path
  3～7の数の全ての順列を返す。
  ※ 8角数から始めることにしたので、8は入っていない。

- search-all-path-depth
  ある順列について、8角数から始めてその順に最後まで並べたときに、
  先頭の2桁と末尾の2桁が同じであればその列を返す。

- pe61
  全ての順列について、上の関数を呼び出して、解だけ出力する。


他にいいロジックがありそうだけど、思いつかない。

どの2つを取ってつないでも素数になる5つの素数の組をさがす問題

解くのにすごく手間どった。なにしろ計算が終らない。ロジックに問題があるのだとばかり思っていたら、そうではなくて、素数判定の考慮漏れだったという情無い落ち。

といっても、解くのに15分以上かかってしまっているので、情無いのには変りない。

全数アタック以外の方法を思いつかないし、出た答えを見ても、うまい枝刈りの方法も思いつかないので、現状ではこれがほぼベスト。8けた以上の数の素数判定が早くなれば、かなり減りそうだけれど、1分にはほど遠い感じ。





方法はこんな感じ。

素数の列を作る。2と5は題意から除外する。

3 7 9 11 13 17 ......

1こずつ取ってきて、組をつくる。
そのときこういうことをする。
a 自分だけの組
b もともとあった組
c もともとあった組すべてに自分を加えた組
できたものを、要素の数の多い順に並べる。

初めは(3)。 これに7を追加するには
a (7)
b (3)
c (3 7)
なので、できるのは、
(3 7) (3) (7)

9を追加すると

a (9)
b (3 7) (3) (7)
c (3 7 9) (3 9) (7 9)
よって、
(3 7 9) (3 7) (3 9) (7 9) (3) (7) (9)

また、追加するとき、その組が題意に沿っているかどうかの確認もする。
たとえば、(3 7 9)は、39が素数でないので除外する。

こうしていくと、ある素数以下の素数でつくられた、題意に沿ったすべての素数の組をつくることができる。 最初に5個になったものが答。

この方式で高速化するなら、下記のやうなことをしてみるかな。
・ 素数判定の高速化
  3の倍数を省くとか、
・ 枝刈りをする
  まったく思いつかない
・ リストの更新処理の高速化
  データの持ち方をちゃんと考えないと

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

Clojure Programmingを予約してあったんだけど、発売日また延期されちゃって、どうやら年内には手に入りそうもない。
そもそも、最初に買ったプログラミングClojureはいい本なのだけれども、対応バージョンが古いのと、もうちょっと真髄みないなものに触れたいと思って、すでに発売中のThe Joy of Clojureと比べて、表紙の絵と新しさでClojure Programmingを選択していたわけだけれども、もう待てません。予約をキャンセルして、The Joy of Clojureを買っちゃいました。

届きました。
うーん。やっぱりこの表紙は怪しい。
まだ、本文は1ページも読んでない。
LOLを返したら読みはじめます。
評価が高い本なので、期待してます。

Clojure Programmingは、来年になって、評価がよかったら買います。
1.3のことが書いてあるならそうでなくても買うかな？

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日間飲める。すでに飲むコーヒーが決っている日はとばす。この「とばす」のをなんとかすればいい。

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

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

先週の週末、娘が図書館で本を借りたいというので、ついていきました。

家から数分のところにある南部図書館という小さな出張所なので、品揃えは貧弱です。これまでも、買い物帰りにぶらっと寄ったことはあったのですが、雑誌を読むくらいのことしかしてなかったのですが、一回りしてみることにしました。コンピューター関連書籍の棚を見てみると、お約束のWordやExelの本に混って、「Let Over Lambda」が置いてあるじゃありませんか。 ちょっとびっくり。借りちゃいました。


今、仕事の行き帰りに読んでいいて、1/3くらいまで来ました。

情報によれば、後半に山場があるそうなので、まだ、感想を言うのは早いのでしょうが、「マクロはこう使え」っていう本ですね。僕にはやっぱりマクロは難しいし、今一つピンとこない。

よくある手法などを定型で効率よく扱えるようにできるのはとても便利です。
そして、ライブラリとしてくくり出すよりも、はるかに自由度が高いのはよくわかります。
新しい考えかたなんかむうまく実現できるし、さらに、DSLという概念を頭に入れてとりかかると方向性を見失わずに済む。

でも、ちょっと、Common Lisp持ちあげ過ぎじゃない？
マクロについては、Clojureくらいの距離の置きかたが僕にはちょうどいい感じかな。