A - Still TBD
シグネチャを決める。
abc119a :: String -- S
-> String -- 答え
abc119a s
| s <= "2019/04/30" = "Heisei"
| otherwise = "TBD"
yyyy/mm/dd 形式なら、文字列の大小比較で用は足りる。
B - Digital Gifts
シグネチャを決める。行の中に型の違うデータがあると面倒い。
浮動小数点数について、誤差はあまり気にしなくてよさそう。
abc119b :: Int -- N
-> [(Double, String)] -- xi,ui
-> Double -- 答え
abc119b _n xus = [if u == "JPY" then x else x * 380000 | (x,u) <- xus]
C - Synthetic Kadomatsu
シグネチャを決める。横着する。
abc119c :: [Int] -- N,A,B,C
-> [Int] -- li
-> Int -- 答え
なんか上手いことやる方法を探す、と考えると、他との兼ね合いでそれが最善とは限らなくなったりする。
10より短い竹を合成魔法する意味はない、とか。
3本の目標に対してそれぞれ、まず使う竹を確定させる。それらは全て合成することにして、さらに長さの違う分を1MP魔法で調節するときのコストは、竹の選択に対する関数になる。
あとは、竹の配分の仕方を総当たりすることで答えが見つけられる。
再帰的な解法
使える竹のリストから、一つ以上を選ぶ全ての方法について自分のコストを求め、
使わなかった残りの竹リストを渡して、残りの竹について計算する。
abc119c :: [Int] -> [Int] -> Int
abc119c [_n,a,b,c] ls = (f a $ f b $ f c $ const 0) ls
where
f _ _ [] = 200000 -- too big
f x g ys = minimum
[ abs (x - sum ps) + 10 * pred (length ps) + g qs
| (ps,qs) <- distribute ys, not $ null ps]
distribute :: [a] -> [([a], [a])]
distribute [] = [([],[])]
distribute (x:xs) = [p | (ys,zs) <- distribute xs, p <- [(x:ys,zs), (ys,x:zs)]]
目標の竹に関して事前計算する方法
目標 $A,B,C$ について、竹の全ての組み合わせ $2^N - 1$ とおりについて、コストを求めて配列に収めておく。
使う竹の組み合わせを2進表記で配列の添字とする。
使う竹が被らないような場合を総当たりで最小値を求める。
import Data.Bits
import Data.Array.Unboxed
abc119c :: [Int] -> [Int] -> Int
abc119c [n,a,b,c] ls = minimum
[ ca + cb + cc
| (ia, ca) <- assocs aA
, (ib, cb) <- assocs aB, ia .&. ib == 0, let iab = ia .|. ib
, (ic, cc) <- assocs aC, iab .&. ic == 0]
where
bnds = (1, 2^n - 1)
aA, aB, aC :: UArray Int Int
aA = listArray bnds $ map (f a) $ range bnds
aB = listArray bnds $ map (f b) $ range bnds
aC = listArray bnds $ map (f c) $ range bnds
f x i = abs (x - sum [k | (j, k) <- zip [0 ..] ls, testBit i j]) + 10 * pred (popCount i)
UArray のお陰か、$2^{3N}$ とおりを調べているにかかわらず最も速い。
竹をA,B,Cに配る方法
これまでは、目標A,B,Cについて一つずつ、使う竹を選ぶという手順を考えていたが、
視点を変えて、竹を3つのどの目標に使う（または使わない）か、を総当たりで $4^N = 2^{2N}$ とおりを試す。
import Data.List
abc119c :: [Int] -> [Int] -> Int
abc119c (_n:abc) ls = minimum
[ res
| dss <- sequence [tails [0,0,l] | l <- ls]
, Just res <- [fmap sum $ zipWithM f abc $ transpose $ [0,0,0] : dss]
]
where
f x ys
| all (0 ==) ys = Nothing
| otherwise = Just $ abs (x - sum ys) + 10 * pred (length $ filter (0 <) ys)
竹 l について [[0,0,l],[0,l],[l],[]] の4とおりを sequence で作り、
transpose により目標ごとにまとめなおす。
D - Lazy Faith
シグネチャを決める。横着する。
abc119c :: [Int] -- A,B,Q
-> [Int] -- s_i
-> [Int] -- t_i
-> [Int] -- x_i
-> [Int] -- 答え
東と西の両方向について、最寄りの神社と寺までの距離を求めておく。
- 東にだけ行くとき、東神社と東寺までの遠い方が答え
- 西にだけ行くとき、西神社と西寺までの遠い方が答え
- 東神社と西寺に行くとき、近い方まで往復して、遠いもう一方に行く行程が答え
- 西神社と東寺に行くとき、（同上）
の最小値を求める。
無い場合を含めて扱うために Maybe のままで計算する。
結果
import qualified Data.IntSet as IS
import Data.Maybe
abc119d :: [Int] -> [Int] -> [Int] -> [Int] -> [Int]
abc119d _abq ss ts xs = map f xs
where
sS = IS.fromDistinctAscList ss
tS = IS.fromDistinctAscList ts
f x = minimum $ catMaybes [ll, rr, lsrt, rslt]
where
ls = (x -) <$> IS.lookupLT x sS
lt = (x -) <$> IS.lookupLT x tS
rs = subtract x <$> IS.lookupGT x sS
rt = subtract x <$> IS.lookupGT x tS
ll = max <$> ls <*> lt
rr = max <$> rs <*> rt
aab a b
| a <= b = a + a + b
| otherwise = a + b + b
lsrt = aab <$> ls <*> rt
rslt = aab <$> rs <*> lt