A - Discount Fare
シグネチャを決める。
abc113a :: Int -- X
-> Int -- Y
-> Int -- 答え
abc113a x y = x + div y 2
B - Palace
シグネチャを決める。
abc113b :: Int -- N
-> Int -- T
-> Int -- A
-> [Int] -- Hi
-> Int -- 答え
$|(T-x \times 0.006) - A|$ が最小となる $H_i$ を探す。
1000倍して
$|1000(T - A) - 6x|$ とすると整数演算できる。
結果
abc113b n t a hs = snd $ minimum
[(abs (1000 * (t - a) - 6 * h), i) | (i, h) <- zip [1 ..] hs]
C - ID
シグネチャを決める。横着する。
abc113c :: Int -- N
-> Int -- M
-> [[Int]] -- Pi,Yi
-> [String] -- 答え
まず県ごとに寄せる。
県の中で年でソートして番号$x$を確定させ、
これにより完成する認識番号を配列で集める。
結果
leading zero を付けるには、はみ出る桁に数を置いてから show してそれを除けばよい。
import Data.Array
import Data.List
abc113c :: Int-> Int -> [[Int]] -> [String]
abc113c n m pys = elems ans
where
prefs = accumArray (flip (:)) [] (1,n)
[(p, (y,i)) | (i, p:y:_) <- zip [1 ..] pys]
ans = array (1,m)
[ (i, tail $ show $ pp + x)
| (p, yis) <- assocs prefs
, let pp = 1000000 * (1000000 + p)
, (x, (y,i)) <- zip [1 ..] $ sort yis]
D - Number of Amidakuji
シグネチャを決める。
abc113d :: Int -- W
-> Int -- H
-> Int -- K
-> Int -- 答え
abc113d w h k = ...
where
w1 = pred w
考える
縦線$W$本のとき、ある高さに引く横線を引ける箇所は $W-1$ 箇所ある。
ただし規則1のため、線の引き方の場合の数は $2^{W-1}$ とはならない。
1のビットが連続しない2進数として列挙すると簡単。
import Data.Bits
yokos = gen w1 :: [Int]
gen w = [i | i <- [0 .. 2^w - 1], i .&. (i .<<. 1) == 0]
高さパラメータが $H$ のとき、横線を引ける高さが $H$ 箇所ある。
自分がこの高さにおいて $1 \leq P \leq W$ に来るような場合の数、を追跡するDPを行う。
各位置について、左隣に移る、下に進む、右隣に移る、ような横線の引き方の場合の数を数える。
（これは「配るDP」の言い方だが、同時に「左隣から移ってくる」という集めるDPのパラメータとしても解釈できる。）
import Data.Array
-- 縦線の番号0～W-1について、+1に移動するような横線の数は、そのビットが1のもの
rights = elems $ accumArray (+) 0 (0,w1) [(i, 1) | y <- yokos, i <- [0 .. w1], testBit y i]
-- -1に移動するような横線の数は、一つ下のビットが1のもの
lefts = elems $ accumArray (+) 0 (0,w1) [(i, 1) | y <- yokos, let y1 = y .<<. 1, i <- [0 .. w1], testBit y1 i]
-- 0に移動するようなパターンの数は、LでもRでもないもの
num = length yokos
mids = zipWith (\l r -> num - l - r) rights lefts
ここまで準備ができたら、$H$ 段のDPステップを実行して答えを求められる。
abc113d [h,w,k] = fin !! pred k
where
ini = 1 : replicate (pred w1) 0
fin = iterate step ini !! h
step cnt = map (reg . sum) $ transpose
[ zipWith mul lefts $ 0 : cnt
, zipWith mul rights $ tail cnt
, zipWith mul mids cnt ]
公式解説
計算量 $O(HW2^W)$ と言っているのは、DPのステップごとに、横棒の配置全てを毎回全列挙して次の段を数えている？
ここで示した step は $O(W)$ なので全体は普通に $O(HW)$ で、フィボナッチ数がどう関係してくるのかわからない。？？？