A - Train
えーれっしゃ。
シグネチャを決める。
abc107a :: Int -- N
-> Int -- i
-> Int -- 答え
abc107a n i = succ n - i
B - Grid Compression
シグネチャを決める。
abc107b :: Int -- H
-> Int -- W
-> [String] -- aij
-> [String] -- 答え
最初は空白でない行や列が、操作の結果そうなるようなことはない。
transpose を使ってリストのリストを転置すれば、空白行を除く処理だけで両方こなせる。
結果
abc107b _h _w = transpose . filter (elem '#') . transpose . filter (elem '#')
C - Candles
シグネチャを決める。
abc107c :: Int -- N
-> Int -- K
-> [Int] -- x_i
-> Int -- 答え
ストレートに
自分は原点にいて、正方向にも負方向にもろうそくが存在しうる。
正方向と負方向のろうそくについて別にして、座標の絶対値を昇順に配列に入れたとする。
$P[i]$ と $N[j]$ とする。添字の上限をそれぞれ $p,n$ とする。
正方向に $K$ 本点火するとき、$P[K]$ かかる。
正方向に $0 < a < p$ 本点火し、原点まで戻って、負方向に残り $K - a$ 本点火するとき、$P[a] + P[a] + P[K-a]$ かかる。
負方向に $K$ 本点火するとき、$N[K]$ かかる。
負方向に $0 < b < n$ 本点火し、原点まで戻って、正方向に残り $K - b$ 本点火するとき、$N[b] + N[b] + P[K-b]$ かかる。
これらはどれも $O(N)$ で計算でき、それらの最小値を選ぶ。
import Data.Array.Unboxed
abc107c :: Int -> Int -> [Int] -> Int
abc107c _n k xs = minimum $
[ ps ! k | k <= pp] ++
[ ns ! k | k <= nn] ++
[ pa + pa + ns ! (k - a) | (a,pa) <- assocs ps, k - a <= nn, 0 < k - a] ++
[ nb + nb + ps ! (k - b) | (b,nb) <- assocs ns, k - b <= pp, 0 < k - b]
where
(xs1, xs2) = span (0 >) xs
nn = length xs1
pp = length xs2
ps, ns :: UArray Int Int
ns = listArray (1, nn) $ reverse $ map negate xs1
ps = listArray (1, pp) xs2
尺取法
離れた場所のろうそくを選択する意味はないので、連続したK本のろうそくに点火することを考える。
その両端の符号が同じとき、遠い方、絶対値の大きい方までの時間がかかる。
両端の符号が異なるとき、近い方について往復し、遠い方に行きっぱなしで終わるやり方をとる。
abc107c _n k xs = minimum $ zipWith maomao xs $ drop (pred k) xs
where
maomao xL xR
| xR <= 0 = aL
| 0 <= xL = xR
| otherwise = aL + xR + min aL xR
where
aL = - xL
小 ＋ 小 ＋ 大 = 小 ＋ 大 + min(小, 大)
D - Median of Medians
シグネチャを決める。
abc107d :: Int -- N
-> Int -- K
-> [Int] -- x_i
-> Int -- 答え
あちこちの解説を見てもなかなか難解だ。
ステップ1:二分探索
大方針として、答えを探すのに二分探索を用いる。
その判定述語がテクニカル。
中央値の中央値の候補を $M$ とすると、長さ1のものも含めて ${}_{N+1} C_2$ 個ある連続部分列のそれぞれの中央値 $m_i$ について、
$M$ 未満な中央値の個数 ≦ $M$ 以上な中央値の個数となってほしい。（中央値の定義を2段目に使った形）
$M$ 以上なものの個数と未満なものの個数を数えやすくする工夫として、$a_i$ から次のような数列 $B_i$ を作る。
B[i] = \begin{cases} 1 \; (a_i \ge M) \\ -1 \; (a_i < M) \end{cases}
すると、$a_L$ から $a_R$ までの連続部分列について、$F(L,R) = \sum_{i = L}^R B[i]$ という値は、列の中央値が $M$ 未満のとき負、$M$ 以上のとき0以上になる。
なので、前者の個数≦後者の個数となるなら、$M$ は真の解以上の値とわかるので、この判定は（実現できれば）二分探索の述語として機能する。
ステップ2:累積和
$B[i]$ のさまざまな区間和を取り出せる必要があるので、累積和をとってみる。
$S[i] = B[1] + \dots + B[i]$ とする。（$S[0] = 0$ とする）
すると $F(L,R) = S[R] - S[L-1]$ である。
ここまでは普通だが、$F(L,R)$ の値を $L,R$ について総当たりで調べるのは個数が多過ぎて無理。
ステップ3:反転数または転倒数
$F(L,R) \geq 0$ な場合の個数を数えたい。
$S[R] - S[L-1] \geq 0$, $S[L-1] \leq S[R]$ と変形すると、
これは「反転していない個数」の方を数えることになる。
普通の人はセグメント木とかを使って数えるけれど、ちょっと工夫してみよう。
$-N \leq S[i] \leq N, 0 \leq i \leq N$ なので、Data.Ix を使って $(S[i],i)$ を順序を保って整数に写像する。
これを Data.Set に入れると、$S[i]$ の値が重複してもsnd要素で別の（少しだけ大きい）値になり、findIndex で個数を数えられる。
その結果が ${}_{N+1}C_2$ の半数以上かを判定すれば、最初の目標である二分探索の述語が完成する。
結果
import Data.List
import Data.Bool
import qualified Data.Set as S
import Data.Ix
abc107d :: Int -> [Int] -> Int
abc107d n as = snd $ binarySearch prop (succ amax) (pred amin)
where
amin = minimum as
amax = maximum as
nC2 = div (n * succ n) 2
bnds = ((-n,0),(n, n))
prop m = (nC2 <=) $ (2 *) $ sum $ snd $ mapAccumL step S.empty $ zipWith (curry $ index bnds) ss [0 ..]
where
bs = map (bool (-1) 1 . (m <=)) as
ss = scanl' (+) 0 bs
step :: S.Set Int -> Int -> (S.Set Int, Int)
step set v =
case S.lookupLT v set of
Nothing -> (S.insert v set, 0)
Just e -> (S.insert v set, succ $ S.findIndex e set)
binarySearch :: (Int -> Bool) -> Int -> Int -> (Int, Int)
binarySearch prop unsat sat = loop unsat sat
where
loop a b
| ende = (a, b)
| prop m = loop a m
| True = loop m b
where
ende = a == m || b == m
m = div (a + b) 2
結果は AC, 1015ms, 51MBとまずまず。
なお、findIndex のない Data.IntSet ではTLEする。