Euler: Problem 106

Posted by YpsilonTAKAI On 2020年3月16日月曜日 0 コメント
これも 103:シリーズです。

12個の数列について、ルール2がすでに満たされている場合、条件を満たすためには、ルール1について何セットの組み合わせをチェクしなければならないかという問題。

ルール1は、どのサブセットを取っても合計が違うということですが、ルール2から要素数が多い方が要素の合計が大きいことは確定なので、要素数が同じである場合だけ確認すればよいということになります。。
要素数が同じ2つの数列の和が等しいかどうか確認する必要があるのはどんなときか考えればよいということ。

「こういう選択をしたら同じになる可能性がある」か、「こういう選択をしたら片方が大きくなる」のどちらかの選択方法をみつければよい。
たとえば、1,2.3 と 10,11,12のぺあであれば、まあ、確実に後の方が大きいよね。

ってなことを考えて、いくつか例を書いてみたんですが、思いついたのがこの方式。


左から1つずつ比べて行って全部片方が大きければ、和もそちらが大きいでしょう。

ということで、そろまま実装してみたら、正解が出たので、それで終了。


(ns euler.pe_106
(:require [clojure.math.combinatorics :as combo]))
;; Prablem 106
;; "Elapsed time: 456.3979 msecs"
(defn create-sets [basel m]
(let [pair-a (combo/combinations basel m)]
(reduce into #{}
(for [pair pair-a]
(let [reminder (sort (clojure.set/difference (set basel) (set pair)))]
(->> (combo/combinations reminder m)
(map #(if (< (first pair) (first %))
(vector pair %)
(vector % pair)) ,,)))))))
(defn needs_verify? [[a b]]
(let [comparison (map > a b)]
(not
(or (every? true? comparison)
(every? false? comparison)))))
(defn part-size-list [N]
(range 2 (+ 1 (quot N 2))))
(defn base-list [N]
(range 1 (+ 1 N)))
(defn pe106-check [N]
(let [basel (base-list N)
m-list (part-size-list N)]
(apply +
(for [m m-list]
(->> (create-sets basel m)
(map needs_verify? ,,)
(filter true? ,,)
(count))))))
view raw pe_106.clj hosted with ❤ by GitHub
ラベル: ,

0 コメント:

コメントを投稿