直方体の向いあった頂点を結ぶ最短距離が整数になる場合の数を求める問題
全数アタックで解いた。
思ったよりも時間はかからずにできました。
向いあった頂点を結ぶ最短距離について考えます。
最短距離の候補は3つあって、辺の長さが a,b,cとすると
ここで、a≦b≦c とした場合、最短なのは3番。ようするに、もっとも長い辺を横切るようなルートが最も短いということ。
ということでこの問題は、短い2辺の和と長い辺の長さがピタゴラス数になっているような直方体をすべてみつける問題だということになります。
さて、どうやって数えようか。
ピタゴラス数を求めて数えていけば簡単じゃないかと思ったのだけれども、小さい順にピタゴラス数を並べることができないことが判明。
他に方法が思いつかないので、普通の全数アタックな方式でやることにした。
たとえば、cが20のとき、(a+b)の最大値は40。40から2までの数でピタゴラス数になるものを探すと、15と21がみつかる。
aとbに分解する。単に整数で分けていけばいいのだけれど、重複しないようにa≦bに決めてしまう。また、cが最長なので、cを超えないように数える必要がある。
(a+b)=15 のとき、aとbのくみあわせは、(1,14),(2、13)...(7,8)の7通り。
(a+b)=21 のときは、(1,20),(2 19)...(10,11)の10通り。
ということで、cが20のときの、題意に合う直方体は17種類。
例をもう一つ。
cが21のときは、20と28がみつかる。
(a+b)=20で、(1,19),(2,18)....(10,10) の10通り
(a+b)=28の時は、(1,27),(2,26)...(7,21)...(14,14) となるけれど、辺の長さは21を超えてはならないので、(7.21)以降を数えて、8つ。
cが21のときの、題意に合う直方体は18種類。
計算で求める方法を考えた。
合計がcを超えない場合は、偶数なら2で割ったもの。奇数なら1を引いて2で割ったものなんだけれど、cを超えたときにそれが使えない。上の例を観察していて、右側の数に注目。
15: (1,14),(2、13)...(7,8) -> 14..8
21: (1,20),(2 19)...(10,11) -> 20..11
20: (1,19),(2,18)....(10,10) -> 19..10
28: (8,20)...(14,14) -> 20..14
これは、始まりの値は (a+b)-1とcの小さいほうで、終りの値は (a+b)/2のceilになっている。これで式をたてた。
これでコーディング。
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| ;; Problem 86 : 2012/07/24 | |
| ;; "Elapsed time: 2840.618843 msecs" | |
| (defn is-pethagorean [x y] | |
| (let [hypo (Math/sqrt (+ (* x x) (* y y)))] | |
| (if (== 0 (rem hypo 1) ) | |
| (int hypo) | |
| nil))) | |
| (defn count-cuboids [a+b c] | |
| (+ 1 | |
| (- (if (< a+b c) (dec a+b) c) | |
| (if (odd? a+b) (/ (inc a+b) 2) (/ a+b 2))))) | |
| (defn count-all-cuboids [c] | |
| (->> (range 2 (inc (* 2 c))) | |
| (filter (partial is-pethagorean c) ,,) | |
| (map #(count-cuboids % c) ,,) | |
| (reduce + ,,))) | |
| (defn pe86 [tacget-count] | |
| (loop [cuboids-count 0, max-length 0] | |
| (if (> cuboids-count tacget-count) | |
| [max-length cuboids-count] | |
| (recur (+ cuboids-count | |
| (count-all-cuboids (inc max-length))) | |
| (inc max-length))))) |
・is-pethagorean
xとyがピタゴラス数かどうか判定する。ピタゴラス数だったらzを返し、だめならnilをnilを返します。
・count-cuboids
上の説明の通り、短かい2辺の和(a+b)と最長の辺(c)がから、全ての直方体の数を数えて返す。
・count-all-cuboids
この処理のコアです。
最長の辺の長さが(c)で、最短距離が整数になるすべての直方体の数を求めます。
すべての残りの辺の和(a+b)のリストを作って、最短距離が整数になるものを抽出して、それぞれについて直方体の数を出して、和を求めています。
・pe86
最長の辺の長さ1から順に、最短距離が整数になるすべての直方体の数を求めて、合計がターゲットを超えるまで計算します。
0 コメント:
コメントを投稿