A - Restricted
シグネチャを決める。
abc063a :: Int -- A
-> Int -- B
-> String -- 答え
結果
abc063a [a, b]
| ans >= 10 = "error"
| otherwise = show ans
where
ans = a + b
B - Varied
シグネチャを決める。
abc063b :: String -- S
-> Bool -- 答え
それぞれの文字の出現回数を数えて、1を超えるものがあったらアウト。
リストベース
import Data.List
abc063b :: String -> Bool
abc063b = all isSingleton . group . sort
where
isSingleton [_] = True
isSingleton _ = False
配列ベース
import Data.Array.Unboxed
abc063b :: String -> Bool
abc063b s = all (1 >=) $ elems (accumArray (+) 0 ('a','z') [(c,1) | c <- s] :: UArray Char Int)
文字コードとビット操作ベース
配列の代わりにビットを使い、衝突が最初に見つかったところで終了する。
import Data.Bits
abc063b :: String -> Bool
abc063b s = loop (0 :: Int) s
where
loop _ [] = True
loop b (c:cs) = b /= b1 && loop b1 cs
where
b1 = setBit b $ fromEnum c
総当たりで文字が異なることを調べる
公式解説の最初の方針
import Data.List
abc063b :: String -> Bool
abc063b s = and [c /= d | c:ds <- tails s, d <- ds]
C - Bugged
シグネチャを決める。
abc063c :: Int -- N
-> [Int] -- s_i
-> Int -- 答え
引っかかって真面目にDP
可能な点数の組み合わせは $2^{100}$ とおりはなく、$0 ～ 100 \times 100$ の範囲しかないので、
それを全て見つけた上で、10の倍数でない最大値か、どれもなければ0を答える。
import Data.Array.Unboxed
import Data.List
abc063c :: Int -> [Int] -> Int
abc063c n ss =
| null cands = 0
| otherwise = head cands
where
ub = 100 * n
arr0 = listArray (0, ub) $ True : repeat False :: UArray Int Bool
arrN = foldl' step arr0 ss
step arr s = accum (flip const) arr [(t + s, True) | (t, True) <- assocs arr]
cands = [p | p <- [ub, pred ub .. 1], mod p 10 /= 0, arrN ! p]
もっと賢く、直接求める
満点が10の倍数でなければそれが自明に最大。
10の倍数であるとき、いずれか1問をわざと失点することで表示されることを目指す。
そうするとき、配点が最小なものの方がよいが、配点が10の倍数では意味がないので、そうでないものから選ぶ。
しかしそういう候補がないときは、どうやっても0点。
abc063c n ss
| isOK total = total -- 真の最大値がそのまま使えるならそれが答え
| null oks = 0 -- 配点が全て10の倍数だと、どう失点しても10の倍数から逃れられない
| otherwise = total - minimum oks -- 最小限の失点で10の倍数でなくする
where
total = sum ss
isOK x = mod x 10 /= 0
oks = filter isOK ss
D - Widespread
シグネチャを決める。
abc063d :: Int -- N
-> Int -- A
-> Int -- B
-> [Int] -- h_i
-> Int -- 答え
シミュレーションしていては間に合わない。
一度の攻撃で全ての敵に B のダメージは与えることができ、狙った一体だけは追加で $D = A - B$ を与えられる。
K 回の攻撃で終わらせられたとすると、
- 全員にそれぞれ $KB$ のダメージを与える。弱い敵はその巻き添えだけで倒れる。
- これでは足らない敵それぞれについて、全部で K 回狙うことができる。
これで足りるとは、$\lceil (h_i - KB) / D\rceil$ の総計が K 以下ということ。
この条件を満たす最小のKを二分探索で探す。
結果
import qualified Data.Vector.Unboxed as UV
abc063d :: Int -> Int -> Int -> [Int] -> Int
abc063d n a b hs = snd $ binarySearch prop 0 (10^9 + 1)
where
hv = UV.fromListN n hs
d = a - b
prop k = k >= UV.foldl' f 0 hv
where
kb = k * b
f acc h = acc + divrup (max 0 $ h - kb) d
divrup :: Int -> Int -> Int
divrup x y = negate $ div (negate x) y
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