たこパ。
A - おいしいたこ焼きの作り方
シグネチャを決める。
abc005a :: Int -- x
-> Int -- y
-> Int -- 答え
abc005a x y = div y x
B - おいしいたこ焼きの食べ方
シグネチャを決める。
abc005b :: Int -- N
-> [Int] -- Ti
-> Int -- 答え
abc005b _n = minimum
C - おいしいたこ焼きの売り方
シグネチャを決める。横着する。
abc005c :: [Int] -- T,N,M
-> [Int] -- Ai
-> [Int] -- Bi
-> Bool -- 答え
AとBを混ぜたイベントキューと、焼き上がった在庫キューとの二本立てで管理するとリアルなシミュレーションになるが、
面倒なので、AiとBiをそのままキューとして処理する。
結果
abc005c [t,_n,_m] as bs = loop as bs
where
loop (a:as) bbs@(b:bs)
| a > b = False -- 在庫なし、この客は待たされる
| a + t < b = loop as bbs -- 古すぎるのでこれは廃棄
| otherwise = loop as bs -- a ≦ b, b ≦ a + t なのでそれを売る
loop _ [] = True -- 全ての客がさばけた
loop _ _ = False -- たこ焼きが足らなかった
D - おいしいたこ焼きの焼き方
シグネチャを決める。
abc005c :: Int -- N
-> [[Int]] -- Dij
-> Int -- Q
-> [Int] -- Pi
-> [Int] -- 答え
$N \leq 50$ だからとなめて痛い目にあった。
結果
Dij の二次元累積和 arr で、任意の領域の合計が得られるようにしておく。
全ての角 (x,y) と角 (xh,yw) の組み合わせ $N^4$ について合計を求め、
その面積 (xh-x) * (yw-w) を添え字として、答えの候補として raws に最大値を集める。
raws は面積がちょうどの領域に関する最大値だが、それ以下でもよいので、
scanl max で小さい方のも許すように ans に集める。
import Data.Array.Unboxed
abc005d :: Int -> [[Int]] -> Int -> [Int] -> [Int]
abc005d n dss _q ps = map (ans !) ps
where
arr :: UArray (Int,Int) Int
arr = listArray ((0,0),(n,n)) $ concat $
scanl (zipWith (+)) (replicate (succ n) 0) $
map (scanl (+) 0) dss
raws :: UArray Int Int
raws = accumArray max 0 (1, n * n)
[ (h * w, area)
| x <- [0 .. pred n], xh <- [succ x .. n], let h = xh - x
, y <- [0 .. pred n], yw <- [succ y .. n], let w = yw - y
, let area = arr ! (xh, yw) - arr ! (xh, y) - arr ! (x, yw) + arr ! (x,y)]
ans :: UArray Int Int
ans = listArray (1, n * n) $ scanl1 max $ elems raws