Euler : Problem 66

Posted by TAKAIY On 2011年11月30日水曜日 0 コメント

ペル方程式の問題です。

って言ってますけど、わからないので、情報を調べていてこの方程式がペル方程式という物だということを知ったんですけどね。

解く方法はわかったんですが、残念なことに、どうしてこうすれば答が出るのか理解できてません。
そういうの多いんですけど、ちょっと悔しいね。





もとのペル方程式は、
  x^2 - Dy^2 = ±1
の形をしています。

これの最小解を求めるには、二次体(Q√D)がなんたらかんたらで、結局は連分数√Dの連分数展開の結果を使ってごにょごにょであるとのこと。詳しくはペル方程式でググってください。

やりかただけ書くと、まずは√Dの連分数展開を求めます。平方根の連分数展開は、小数点以下が必ずループするので、こんな形になります。
{a0: a1, a2, ... an, ,a1, ...}
で、この、n-1番目までの結果を分数にしたものの分子と分母がそれぞれxとyの最小解になっているんだそうな。

連分数展開は前の問題で作ったのがあるけど、ちょっと改変が必要。

あと、結果は場合によっては、x^2 - Dy^2 = -1 の解が先に出る。
ペル方程式の解は無数にあって、n番目のもの xn,ynはここでもとめた最小解x0,y0と
xn - √Dyn = (x0 - √Dy0)^n
という関係があって、しかも、-1 の次は +1 であるとのことなので、2番目を求めればよい。

さて、よくわかってませんが、これを実装しました。


式の中では
 √3 + 5
----------
    4
のような形が基本データになるので、これを、
 √X + M
----------
    N
として、基本形としています。




- int-floor
引数nを超えない最大の整数を返します。

- inverse-rationalize
基本形の分数の逆数を求めます。ただの逆にするのではなく、分母を有理化します。有理化すると形は基本形になり、平方根の中身Xは変らないので、更新したMとNの組を返します。

- make-proper
基本形の分数を帯分数化します。括り出した整数と新しいMを返します。

- get-cf-list-loop
引数Xの連分数展開の結果を返します。ただし、ループの終端までで返ります。

- calc-cf-partial-fraction
連分数展開のリストをもらって、分数に戻します。

- check-norm
x^2-Dy^2が1になっているかどうかを返します。
名前のつけかたを間違えていますね、norm-is-1? だったな。

- my-numerator
- my-denominator
Clojureは分数表記を扱えて、分子と分母を求める関数がある(
numerator,denominator)のですが、引数に整数を渡すと例外を出してしまうので、整数でも動くようにしたもの。マルチメソッドにすべきだったかな。

- solv-pell-eq
問題を解くメイン関数。
Dの値を引数に取って、√Dを連分数展開。
ループの直前までの分数の値を計算。
分母と分子をペル方程式にあてはめて、1ならそれ、-1なら2番目を返す。返るのは、 x,y,D。

- square?
平方数かどうか

- pe-66
1からlimitまでの平方数以外の数について、ペル方程式が1になる解を求めて、xの値が最大になるものを返します。

READ MORE

Euler : Problem 68

Posted by TAKAIY On 0 コメント

魔方陣系の問題です。

条件を見つけるためにちょっと試していたら、その場で答が出ちゃったという初めての経験をしました。
ですけど、勉強のために、コードは書いてみました。





魔方陣のセオリー通り、穴は図のA(外周)とB(内周)の様に2種類に分けられます。

一列に並んだ数の合計を同じにするということは、
 A1 + B1 + B2
 A2 + B2 + B3
 A3 + B3 + B4
 A4 + B4 + B5
 A5 + B5 + B1
この5つが同じになるということです。これをXとすると全部の合計は、5X ということになります。
次に、上の式から全部の合計は、
  (A1 + B1 + B2) +  (A2 + B2 + B3) + (A3 + B3 + B4) + (A4 + B4 + B5) + (A5 + B5 + B1)
= (Aの合計) + (Bの合計)×2
ということが分ります。
ということで、
 5X = (Aの合計) + (Bの合計)×2
 X = ((Aの合計) + (Bの合計)×2) ÷ 5

ということになり、Aの組に入れる数を決めれば、1列の合計を求めることができます。

たとえば、Aに 1,2,3,4,5 を入れたとします。Bには、残りの6,7,8,9,10が入ることになります。
(Aの合計) + (Bの合計)×2 = 95
5X= 95
X= 19
1列の合計はすべて19になるということです。

さて、この問題は、Aのグループのなかで一番小さい数から時計回りに数字を並べたときに、最も大きくなるものを求めるのですから、外周に最も大きな数字を並べればよさそうです。
ということで、上の例とは逆に、Aに6,7,8,9,10、Bに1,2,3,4,5を入れます。
 5X = 40 + 15 × 2 = 70
 X = 14
1列が14になります。

ここからごにょごにょやって、手で答えを出しちゃったわけですが、それは最後の方で


さて、答えがでちゃったわけですがやっぱりプログラムで解きたいのでちょっと考えました。
- A1が6で、A2~A5 が 7 8 9 10 のどれか
- 1列の合計を求めて、全ての列がそれになっているかどうか
という計算をしました。
もうちょっと頭のいいやりかたがありそうですけどね。





- check-pe68
  各列の合計が14であるかどうか確認して、そうであれば、
  順番に並べたものを返し、そうでなければFalseを返す。
  a1は6で固定。

- pe68
  外周用に7-10の全順列(6の位置は決っているから)、内周用に1-5の全順列を作って、
  それぞれの全ての組み合わせをcheckに喰わせてfalse以外の
  ものを取得


-----------------------------------------------------
この先は答え入りの手計算解説。 注意
-----------------------------------------------------



1から10の数字を組みあわせて合計が14になるものはそれほど多くありません。
10 3 1
 9 4 1
 9 3 2
 8 5 1
 8 4 2
 7 6 1
 7 5 2
 7 4 3
 6 5 3
たとえば、10を採とるとすると、のこりは4。1から9で足して4になるのは1と3だけ、という具合です。また、5以降はすでに表われているはずなので考える必要はありません。

さて、結果をみると、10と6は1通りしかありませんので、列の作りはそれぞれ2通りしかありません。
 10 3 1、 10 1 3
  6 5 3、  6 3 5

ここで、問題に立ち帰ると、Aで最も小さい6が先頭にきて、数字を大きくしなければならないわけですから、6の列は 6 5 3 に決ります。
もう一方の10の列は、10 3 1 に決ります。これは、3が6の列の最後に来ているため、10 1 3の並びが作れないためです。
また、このことから、他の列では3が使えないことがわかります。すると、9は 9 4 1 の組であり、1の場所から、 9 1 4 であることがわかります。
1が使えなくなってしまったので、8が決り、4の場所から、8 4 2 になり、最後の7は、同様に、7 2 5 となります。
結果
 6 5 3
10 3 1
 9 1 4
 8 4 2
 7 2 5
また、偶然ですが、並びもこのままになっています。
並べかたとしては、内周の並びが2つめと3つめであることから、最後の数が次の数の2番目にくるように並べることになります。

READ MORE

Euler : Problem 67

Posted by TAKAIY On 0 コメント


18の問題と同じで、データが大きくなった問題。
18を解いたときにもそれなりに考えて作ったんだけれども、電車に乗っているとにきいい方法を思いついたので、実装してみた。

ライン数で10分の1くらいになったんじゃないかな?





基本的な考えかたは18を解いたときと同じ。
この問題は、最大の数だけわかればいいので、上からたどっていって、合計が大きくなるものを見付ければいい。たとえば下のような場面では、
  o A B o
 o o X o o
Xの値に影響するのはA、Bの2つのみ。 それぞれAとBまでのルートの和が大きくなる方からXに来るのが大きいルート。例題の場合
1:    3
2:   7 4
3:  2 4 6
4: 8 5 9 3
2列目は、それぞれ上が3なので、10と7。

3列目。
 10  7
 /\ /\
2  4  6

2のところにくるのは、10からのルートのみなので、12になる。
4のところは、10からと7からの2通りある。 大きいほうを取って、14
6のところは、7からのルートのみなので、13
結果として、3列目の大きい方の合計は、
12 14 13

4列目
  12 14 13
  /\ /\ /\
 8  5  9  3

3列目と同様にやって、
20 19 23 16

答が23っと。


18を解いたときは、全部の情報を持っているデータの構造を作って、それに対してこの操作をするようになっていました。問題にしては重量級の仕組みです。途中の情報を後で参照したければこのほうがいいのでしょうけれど、答が出ればいいのであればそんな仕組みは不要です。
今、書いたとおりに、それぞれの段の合計数のリストだけもって、つぎの段に行けばいいわけです。
で、「あ、reduce使えばいいじゃん」と思ったわけです。
そのためには、結果と次の段のリストを使って次の結果を出す方法が必要です。
こんな風にしてみました。

4列目(8 5 9 3)を例にします。前の結果は、(12 14 13)です。 これを、4列目に2回ずつ適用して結果を出すことになります。それだと面倒です。図をよくみると、 \\\ の適用と /// の適用が見えます。ずらしてあるわけです。
なら、ずれたデータを作ればいいのではないか。というわけで、

12 14 13      :左ずらし l
   12 14 13   :右ずらし r
8   5  9  3

あいてるところはどうしましょうか? 手作業なら無視できますけど、計算ではそうはいきませんね。
データは足し算をするので、ここは、0を入れます。掛けるなら1かな。

12 14 13  0   :左ずらし l
 0 12 14 13   :右ずらし r
 8  5  9  3

こうしておいて、右ずらしと左ずらしそれぞれ足したときに大きいほうを採用する。という手順で行けば、よさそうです。





- pe-67
問題を解くのはこれだけです。
各段が1つずつのリストになった問題を受け取ります。
((3) (7 4) (2 4 6)(8 5 9 3)) という感じ。
reduceで1行ずつ取ってきて、解き方のように左右にずらし(rt-rとrt-l)て合計が大きい方をとり、新しいリストを作成するということを繰り返す。
最後のリストの最大値が答。

- pe-67-with-file
問題データをファイルから読み込んで、pe-67に渡して解く関数。
with-openでファイルを開いて、文字列を数値に変換してリスト化します。



READ MORE

Euler : Problem 65

Posted by TAKAIY On 2011年11月26日土曜日 0 コメント
eについて、ある段階まで連分数展開したものを分数表記したときの分子の数字の問題。

これは、問題57で使った公式ですぐに解ける。
問題57ではは√2だったけど、こんどはe。





この方式は、連分数展開したときの 数列aを求める必要がある。
64の答えを使ってもいいのだけれど、eの連分数は、 {2:1,2,1,1,4,1,1,6,1,1,8,1,....}  になることが分っているので、これをつかう。

a0 = 2 、このあと

a1 = 1, a2 = 2, a3 = 1,
a4 = 1, a5 = 4, a6 = 1,
a7 = 1 a8 = 6, a9 = 1,

のように規則的に並んでいる。これを、a[n] についての場合で分けるとこうなる。

  • n=0 のときは2
  • nを3で割った余りが2のときは ((n+1)/3)*2
  • それ以外は1

これで実装した。





- cf-seq-of-e
  eの数列の生成関数。 説明の通り。

- cf-numerator
  n番目まで展開したときの分子を求める。
  問題57を解いたときは数列を外部参照していたけど、持っていくように変更。
  ずうっと持って回っているのがちょっと気持ち悪い。
  defn-memoは前につくったメモ化マクロ。

- cf-denominator
  使ってないけど、分母を出すやつ。

- pu-65
  n番目の分子を計算して、中の数字を全部足す。
  この方法だと、数字が大きくなるとスタックが溢れるかもしれない。
  そのときは小さい数字から攻めていこうと思ったけど、計算できたのでよしとする。




READ MORE

Euler : Problem 64

Posted by TAKAIY On 0 コメント
平方根の正則連分数展開のループの繰り返し数の問題です。

問題文にある通りに連分数展開をしていく処理を作りました。





連分数にする手順は、以下の通りです。
初めの数を以下の形にします。

 √X + M
--------
   N

最初は、M=0、N=1になります。
これを帯分数にします。

     √X + M'
a + ---------
        N

になります。真分数の部分を連分数にするために逆数にします。

         1
a + -----------
         N
     ---------
      √X + M'


分母にある分数を有理化します。


        1
a + ----------
      √X + O
     --------
         P

これで、1段階終了です。そして、この、分母にある

 √X + O
--------
    P

を初めの手順に戻して計算を進めることで、連分数に展開していくことができます。

帯分数にして、整数部分を取り出す -> 残りの部分の逆数を採って有理化する
という操作を繰り返すという手順になります。
この手順で出てくるaを並べたものが  [4;1,3,1,8,.....] という数列になります。

これで、数列を取り出すことができるのですが、数列を作ってしまっては、問題を解くのが困難です。 たとえば、1,2,1,2 という列が出たときに、このまま1,2が交互に現れるのか、1,2,1,2,3 の繰り返しになるのかはわかりません。

しかし、上記の手順の
 √X + M
--------
    N
が再び現れれば、その後は同じものになるのは自明なので、これをつかまえることにします。

また、繰り返しの開始場所は、平方根の場合は2つめからと決っているようですから、それも利用します。

ということで実装したのがこれ。




- int-floor
  foorの整数版

以下2つは

√X + M
-------
   N
の形の数についての操作関数


- inverse-rationalize
  逆数を取って有理化する関数。 計算したものを

      √X + new-M
     ------------
        new-N
  としたときの new-M と new-N を返します。

- make-proper
   帯分数します。 帯分数を
          √X + new-M
     a + ------------
               N
  としたときの、a と new-M を返します。

- get-continued-fraction-list
  引数の平方根を連分数にしたときのaのリストを返します。
  2 を与えると、 (1 2 2 2 2 2 ....) が得られます。
  解答には使ってません。

- get-continued-fraction-args
  引数の平方根を連分数にしたときのMとNのリストを返します。
  23 を与えると、([0 1][4 7][3 2][3 7][4 1][4 7]....) が得られます。

- count-continued-flaction-loop
  引数の平方根の繰り返しの数を数えます。
  get-continued-fraction-args で作ったリストの2番目のペアが再び表われるまでの数を
  数えています。 それだけなのに、仰々しくて美しくないですね。 だめだな。

- pe-64
  範囲の中の平方数(square?)でない数について、平方数の繰り返しの数を数えて、
  奇数のものだけ取り出して数えています。


基本の関数2つの理屈を考えるのに時間が掛ってしまった。
問題の例を見てそのまま作ろうとしてしまったのが敗因。 ちゃんと紙に書いたらすぐできた。




READ MORE

Euler : Problem 63

Posted by TAKAIY On 2011年11月19日土曜日 0 コメント
XのN乗を考えたとき、Xの桁数nがNと同じになるような、ものはいくつあるかという問題。

最初、なんのことかよくわからなかった。

1の場合は、
 1^1 =1、1^2=1、1^3=1 ....   となって1^1だけ。
2の場合は、
 2^1 =1、 2^2=4 、 2^3=8 ...  となってこれも2^1だけ。
おやー。 で、昼休みが終り。

次の日、あっと思って、基数を動かして書いてみた。

1^1=1、2^1=1、3^1=3、.... 9^1=9、10^1=10 ...  となって、1から9。
1^2=2、2^2=4、3^2=9、4^2=16、5^2=25、.... 9^2=81、10^2=100 ... となって、4から9。

考えてみれば、Xが10のとき、10^nは、かならずn+1桁になってしまうので、Xは1桁の数でしかありえない。
この先を手で計算してもできそうだったけど、プログラムにしてみた。




- digits-of-pow
  xのn乗数の桁数を返す。

- pe63
  xを1から9の数として、それぞれのxについて、1以上の整数nについて桁数を調べる。


forじゃなくてmapにしたほうがらしかったかな。


READ MORE

Euler : Problem 62

Posted by TAKAIY On 0 コメント
同じ数字でできている5組の3乗数をみつける問題。

これも全数アタック





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





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

- res-map
  格納用Hash

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

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


READ MORE

Euler : Problem 61

Posted by TAKAIY On 0 コメント
四桁の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
  全ての順列について、上の関数を呼び出して、解だけ出力する。


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



READ MORE

Euler : Problem 60

Posted by TAKAIY On 2011年11月14日月曜日 0 コメント
どの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の倍数を省くとか、
・ 枝刈りをする
  まったく思いつかない
・ リストの更新処理の高速化
  データの持ち方をちゃんと考えないと





READ MORE

Code Jam Japan 予選 問題C 解いた

Posted by TAKAIY On 2011年11月13日日曜日 0 コメント

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



READ MORE

Clojure Programmingがなかなか出ないから....

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

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

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





READ MORE

Code Jam Japan 問題B 解いた

Posted by TAKAIY On 0 コメント

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

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


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


3パターンあるのでそれぞれ、やりかたを考えて対応する。

これでアルゴリズムの基本が決ったので、境界条件とか考えてコーディング。


・ sort-coffee-data
コーヒーのリストを優先度の高い順に並べ変える。
 - 満足度の高いものが前
 - 満足度が同じなら、残りの数の多いものが前 (この条件いらないけど)

・ asign-coffee
K日の期間で、指定のコーヒーをどれだけ飲めるかを計算する。
返るのは、満足度の合計、上記のP、上記のn


・update-coffee-list
残っているコーヒーのリストの賞味期限を変更する。
上記の2枚目のロジックを実装している。


・gcj-pB
解答作成本体。 
ソートしたコーヒーのリストの先頭から1つずつ、期間K日で飲めるものを決定していきながら、Kとリストのアップデートを繰り返す。 リストがなくなったら終り。
繰り返しごとに計算される満足度はs-amountに積算。

他の関数は、問題と解答の入出力関連。

かかった時間は入出力込みで、535.676461 msecs。


READ MORE

Let Over Lambda読み始めました。

Posted by TAKAIY On 2011年11月10日木曜日 0 コメント
先週の週末、娘が図書館で本を借りたいというので、ついていきました。

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


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


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

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

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




READ MORE