A - Entrance Examination
シグネチャを決める。
abc117a :: Double -- T
-> Double -- X
-> Double -- 答え
abc117a t x = t / x
B - Polygon
シグネチャを決める。
abc117b :: Int -- N
-> [Int] -- Li
-> Bool -- 答え
abc117b _n ls = lmax < lrest
where
lmax = maximum ls
lrest = sum ls - lmax
-- 別解
abc117b _n ls = 2 * maximum ls < sum ls
一番長い辺を除いた辺の長さの合計を求めるトリック。
C - Streamline
シグネチャを決める。
abc117c :: Int -- N
-> Int -- M
-> [Int] -- Xi
-> Int -- 答え
$N \geq M$ なら初手で終わるので、そうではない、いずれかは動かす必要がある場合を考える。
往復する意味はないので、踏破する必要のある区間について、正方向にのみ移動するとする。
$N$ 個のコマにより $N$ 個の区間を踏破できる。
このとき、隣接するコマの踏破する区間の隙間は、歩かずに済む範囲である。
これをなるべく大きくとることが望ましい。
つまり、$X_i$ を整列し、差分をとることで隙間候補の距離を求め、その大きい方$N-1$個は踏破の必要がない。
$X_i$ の最大値から最小値を引いた全体区間から、これを引いたら答えになる。
結果
import Data.List
abc117c n _m xs = ((maximum xs - minimum xs) +) $ sum $ take (pred n) $ sort $ between (-) $ sort xs
between f xs = zipWith f xs $ tail xs
あえて負の数にすることで、sort は絶対値の降順になり、最後に引くときまでそのままで済んでしまった。
$N \ge M$ のとき、take は区間の全てを取り出し、答えは正しく0になる。
D - XXOR
シグネチャを決める。
abc117d :: Int -- N
-> Int -- K
-> [Int] -- Ai
-> Int -- 答え
桁ごと（ビットごと）に考えて、$A_i$ のそのビットが1な値の個数と0な値の個数を比べる。
1の方が多いならそのままにすることで、それらが1として結果に足し込まれる。
0の方が多いなら$X$のそのビットを1にすることで反転させる。
しかし$X$は自由でなく$K$以下という制約があるので、上位ビットから順に、$K$を越えていないか確認しながら$X$（と結果）を構成していく必要がある。
結果
import Data.List
import Data.Bits
import Data.Array.Unboxed
abc117d :: Int -> Int -> [Int] -> Int
abc117d n k as = snd $ foldl' step (0, 0) [39, 38 .. 0]
where
cnts :: UArray Int Int
cnts = accumArray (+) 0 (0,39) [(i,1) | a <- as, i <- [0 .. 39], testBit a i]
step (x, acc) i
| x1 <= k, ci < di = (x1, acc + (di .<<. i))
| otherwise = (x , acc + (ci .<<. i))
where
x1 = setBit x i -- Xのビットiを1に
ci = cnts ! i -- ビットiの1の個数
di = n - ci -- 0の個数
ユーザ解説 by drken
半分全列挙でもできる、とだけ書かれている。どういうことだろう。
「上6桁下6桁」とあるのは10進で言っているだけで、2進数で20桁ずつに分けて考える感じだろうか。
$f(X)$ はビットを数えて高速に求められるようにしておく。
$X$ を $K$ 以下の $2^{20} \cdot i$ $(i \leftarrow 0, 1, \dots)$ について $\newcommand{\argmax}{\mathop{\rm arg~max}\limits} X_H = \argmax \ f(X)$ を求める。$2^{20} \fallingdotseq 10^6$ オーダー。
さらに、$X$ を $K$ 以下の $X_H, X_H + 1, \dots, X_H + 2^{20} - 1$ について $\max f(X)$ を求めると、これが答え。やはり $10^6$ オーダーなので、間に合う。
abc117d :: Int -> Int -> [Int] -> Int
abc117d n k as = maximum [f x | x <- [xH .. min k $ xH + bit 20 - 1]]
where
cnts :: UArray Int Int
cnts = accumArray (+) 0 (0,39) [(i,1) | a <- as, i <- [0 .. 39], testBit a i]
f x = sum [(if testBit x i then n - c else c) .<<. i | (i,c) <- assocs cnts]
(_, xHN) = maximum [(f x, - x) | x <- [0, bit 20 .. k]]
xH = - xHN
$X_H$ は同じ $f(X)$ を与える最小値の方が都合がよいので少しトリックが入っている。
さてこれ、何をしているのかじっくり考えてみると、普通の解法では1ビットずつ全探索しているところを、上20ビット下20ビットまとめて全探索する、とやっているだけで、基本方針は実は変わっていない。
これを半分全列挙、と呼んでいいのかしら。