今回、型を定めにくいスタイルの出題が気になった。
A - Programming Education
最大3行の数値列が与えられると解釈してシグネチャを決める。
abc112a :: [Int] -- N,A,B
-> String -- 答え
abc112a [1] = "Hello World"
abc112a [2,a,b] = show $ a + b
B - Time Limit Exceeded
シグネチャを決める。横着する。
abc112b :: Int -- N
-> Int -- T
-> [[Int]] -- c_i,t_i
-> String -- 答え
abc112b _n t cts
| null cands = "TLE"
| otherwise = show $ minimum cands
where
cands = [ci | ci:ti:_ <- cts, ti <= t]
C - Pyramid
シグネチャを決める。横着する。
abc112c :: Int -- N
-> [[Int]] -- x_i, y_i, h_i
-> [Int] -- 答え
全てのデータが高さ0でも、びっしり埋まっていると、そうでなくてピラミッドが存在しうる余白が唯一、という場合もありうるかと思ったが、$N \leq 100$ ではまばらすぎてそういうことは無理だった。
なので、高さが0でないデータが一つは存在する。
中心 $C_X,C_Y$ の候補を適当に設定したとき、調査データ $x_i, y_i, h_i > 0$ から、そこに中心があったときのピラミッドの高さが計算できる。全ての $h_i > 0$ な調査データから算出される高さが一致するとき、それは答えの候補になる。
$h_i = 0$ な調査データからは、高さの上限が算出される。これを超えるような候補は却下される。
結果
abc112c _n xyhs = head [[cx, cy, h] | cx <- [0 .. 100], cy <- [0 .. 100], Just h <- [f cx cy]]
where
(xyhs0, xyhs1) = partition ((0 ==) . (!! 2)) xyhs
f cx cy
| any (h1 /=) hs = Nothing
| null fails = Just h1
| otherwise = Nothing
where
h1:hs = [abs (cx - x) + abs (cy - y) + h | x:y:h:_ <- xyhs1]
fails = [() | x:y:_ <- xyhs0, abs (cx - x) + abs (cy - y) < h1]
D - Partition
シグネチャを決める。
abc112d :: Int -- N
-> Int -- M
-> Int -- 答え
答えな最小公倍数を $G$ とする。
$a_i$ が全て $G$ の倍数なので、$\sum a_i = M$ も $G$ の倍数になる。
つまり $GE = M$ となる整数 $E$ が存在する。
さて、そんな$M$を$N$個の$a_i$に分割する。$a_i = k_i G$ としたとき、
$\sum a_i = G \sum k_i$ より $\sum k_i = E$
$k_i$ は正整数なので $\sum k_i \geq N$ となり、$N \leq E$
この $E$ をなるべく小さくすることで $G$ を最大化できる。
つまり、$M$ の約数のうち、$N$ 以上で最小の $E$ について$M/E$ が答え。
結果
abc112d n m = div m $ head $ dropWhile (n >) $ factors m
-- 約数列挙の factors は省略