Problem 106

http://projecteuler.net/index.php?section=problems&id=106

とりあえず問題文を理解するのにすごい時間がかかった。
なんで、n=4で25になるのか分からなかった。
とりあえず原因は
問題文がどこまでリストの要素が昇順である仮定をつかっているのか
明記してなかった点にあると思う。
（と、問題文のせいにしてみる。）

import Data.List

needTest (x,y) = (or $ zipWith (>) x y)&&(or $ zipWith (<) x y)
divid (x:xs) = [(x:ys,xs\\ys)|ys<-comb xs (length xs `div` 2)]

tests m = [filter needTest$divid xs|n<-[4,6..m`div`2*2],xs<-comb [1..m] n]

main = print.sum.map length.tests$12

comb _ 0 = [[]]
comb [] _ = []
comb (x:xs) (n+1) = map (x:) (comb xs n) ++ comb xs (n+1)

考えたアルゴリズム
偶数個の要素をとってくる
二分割をいろいろ考える
testが必要なものだけ取り出す
以上

効率は悪い。しかし、高々１２。tractableです。