A - Multiple of 2 and N
シグネチャを決める。
abc102a :: Int -- N
-> Int -- 答え
abc102a = gcd 2
Preludeに gcd があるので、これでいい。下のように一生懸命やってもいいけど。
abc102a n
| even n = n
| otherwise = 2 * n
B - Maximum Difference
シグネチャを決める。
abc102b :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
abc102b _n as = maximum as - minimum as
最大値と最小値を一つのループで同時に求めると、少し速くなるかもしれない。
minmaximum (x:xs) = foldl' step (x,x) xs
where
step (l,u) x
| x < l = (x,u)
| u < x = (l,x)
| otherwise = lu
C - Linear Approximation
シグネチャを決める。Bと同じだった。
abc102c :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
悲しさは
$\sum_i |A_i - (b+i)| = \sum_i |(A_i - i) - b|$
ここで $C_i = A_i - i$ とおくと $=\sum_i |C_i - b|$ となる。固定の値 $b$ と $C_i$ との差が小さくなるようにするには、
$C_i$の平均をとればよい。というのは間違いで、中央値をとる。
ある $b$ に対する悲しさを $S[b]$ とする。
ある $b$ に対して、$b$ と等しい $C_i$ の値が $p$ 個、より小さい値が $q$ 個、より大きい値が $r$ 個あるとする。
（$p + q + r = N$ である。）
$b$を1減らすことにより、より小さい $q$ 個の値から、それぞれ悲しさが1減り、逆に、より大きい $r$ 個の値から悲しさが1増える。さらに、$b$ とちょうど等しかった $p$ 個の値からも1ずつ悲しさが増える。結局
$S[b-1] = S[b] + p - q + r = N - 2q$
となる。同様に
$S[b+1] = S[b] + p + q - r = N - 2r$
つまり、$S[b]$ を小さくするには、$q$と$r$の大きい方にずらせばよい。どちらに動かしても変わらない位置が極小の谷となる。それは $q = r$ つまり中央値である。
$N$ が偶数のとき、数学的には中央値とは中央2つの値の算術平均と定義されているが、この $S[b]$ に関してはその間のどの値でも一定になるのでどちらでもよい。
結果
import Data.List
abc102c :: Int -> [Int] -> Int
abc102c n as = sum $ map (abs . subtract b) cs
where
cs = sort $ zipWith (-) as [1 ..]
b = cs !! div n 2
速度を追求するなら
abc102c :: Int -> [Int] -> Int
abc102c n as = UV.sum cs2 - UV.sum cs1 + b * (UV.length cs1 - UV.length cs2)
where
n2 = div n 2
(cs1,cs2) = UV.splitAt n2 $ UV.modify (\v -> VAI.selectBy compare v n2) $ UV.fromListN n $ zipWith (-) as [1 ..]
b = UV.minimum cs2
D - Equal Cut
シグネチャを決める。B,Cと同じだった。
abc102d :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
両側に2要素はあるように二分する全ての場合について、分割した両側を、
なるべく等分するように二分して、P,QまたはR,Sを決める。
4分割を決める計算を毎回独立した計算として二分探索ですると全体で $O(N \log N)$ になる。
それには、$A_i$ の累積和を使って、区間の和を $O(1)$ で求められるようにしておく。
二分割の位置を左から右に順に調べていくと、4分割の位置も前回より右にずれるしかない尺取法を使うことができ、全体で $O(N)$ で終わる。
ただし、前回の状態から続きを計算するような動作がスマートに書きづらい。
結果：二分探索
中点として $m$ を選んだとき、上側と下側の差は $d = |(u - m) - (m - l)|$
中点以下の値 $m_1 \leq m$ では $d_1 = u + l - 2m_1$
中点超の値 $m_2 > m$ では $m_2 = 2m_2 - u - l$
これが小さい方を選ぶ。$m_1 = l$ や $m_2 = u$ という選ぶべきでない値が出てきたときも、これにより相手側が選ばれる。
import qualified Data.IntSet as IS
abc102d :: Int -> [Int] -> Int
abc102d n as = minimum
[ maximum pqrs - minimum pqrs
| m <- take (n - 2) $ drop 2 $ IS.elems is
, let pqrs = f m ub $ f lb m [] ]
where
is = IS.fromAscList $ scanl' (+) 0 as
ub = IS.findMax is
lb = 0
-- (l,u) の中間値に近い m を is から探し、u-m,m-lをrestに追加して返す
f l u rest
| d1 <= d2 = u - m1 : m1 - l : rest
| otherwise = u - m2 : m2 - l : rest
where
m0 = div (l + u) 2
Just m1 = IS.lookupLE m0 is
d1 = u + l - m1 - m1
Just m2 = IS.lookupGT m0 is
d2 = m2 + m2 - u - l
結果：尺取法
区間が空にならないようにとると、$P,Q,R,S$ の初期値は $A_1, A_2, A_3, \sum_{i=4}^n A_i$ である。
PとQの仕切りを右にひとつ進めると、Qの左端が$A_i$のとき $P' = P + A_i, Q' = Q - A_i$と変わる。
QとR, RとSの仕切りも同様である。
PとQの差は、仕切りをひとつ進めると $|(P + A_i) - (Q - A_i)| = |P - Q + 2A_i|$ となる。
これと元の値 $|P - Q|$ を比べ、小さくなるような右にずらすべき。
RとSの差についても同様。
どちらに仕切りも進める必要がないとき、それはQとRの仕切り位置に対する最適解が見つかったことになるので、
それを出力し、QとRの仕切りをひとつ進めて続行する。
続けると、最初にRとSの間の仕切りが（S = 0 になってしまうため）動かせなくなる。これは終了の合図。
abc102d :: Int -> [Int] -> Int
abc102d _n as = minimum $ maomao (as !! 0) (tail as) (as !! 1) (drop 2 as) (as !! 2) (drop 3 as) (sum $ drop 3 as)
where
maomao p a1s@(a1:_) q a2s@(a2:_) r a3s@(a3:_) s
| delta1 < 0 = maomao (p + a1) (tail a1s) (q - a1) a2s r a3s s
| delta2 < 0 = maomao p a1s q a2s (r + a3) (tail a3s) (s - a3)
| otherwise = ans : maomao p a1s (q + a2) (tail a2s) (r - a2) a3s s
where
delta1 = abs (p - q + a1 + a1) - abs (p - q)
delta2 = abs (r - s + a3 + a3) - abs (r - s)
ans = maximum [p,q,r,s] - minimum [p,q,r,s]
maomao _p _a1 _q _a2 _r _a3 _s = []