A - Christmas Eve Eve Eve
シグネチャを決める。
abc115a :: Int -- D
-> String -- 答え
abc115a d = unwords $ "Christmas" : replicate (25 - d) "Eve"
過去の自分はもっと投げやりな提出をしていた。
main = readLn >>= putStrLn . (msgs !!) . subtract 22
msgs =
[ "Christmas Eve Eve Eve"
, "Christmas Eve Eve"
, "Christmas Eve"
, "Christmas"
]
B - Christmas Eve Eve
シグネチャを決める。
abc115b :: Int -- N
-> [Int] -- p_i
-> Int -- 答え
最大値がどれかわからなくても、その値さえ判ればよいというパターン。
abc115b n ps = sum ps - div (maximum ps) 2
C - Christmas Eve
シグネチャを決める。
abc115c :: Int -- N
-> Int -- K
-> [Int] -- h_i
-> Int -- 答え
いかにも尺取法。
abc115c n k hs = minimum $ zipWith (-) (drop (pred k) hs1) hs1
where
hs1 = sort hs
D - Christmas
シグネチャを決める。
abc115d :: Int -- N
-> Int -- X
-> Int -- 答え
レベル $n$ のバーガーの厚さ $t(n)$ は、$t(0) = 1, t(n) = 2t(n-1) + 3$ である。
これは $t(n) = 4 \cdot 2^n - 3$ となるので、$n = 50$ では大変な数になる。
実際に列を生成して $X$ 層食べてみるのは無理そう。
同様に、レベル $n$ のバーガーのパティの枚数は、$p(0) = 1, p(n) = 2p(n-1) + 1$ である。
これは $p(n) = 2 \cdot 2^n - 1$ となる。
考える
あと残り $y$ 枚の何かを食べる必要があり、これまでパティには $z$ 枚ありつけたという状態 $(y,z)$ を維持する。
今、レベル $k$ のバーガーを食べようとしているとき、$t(k) \leq y$ なら食べ尽くすことができ、$(y - t(k), z + p(k))$ に更新される。
途中で止まるとき、さらに内側に入る必要がある。
バンを食べると状態は $(y - 1, z)$ に更新される。
パティを食べると $(y - 1, z + 1)$ に更新される。レベル0のバーガーを食べたときも同じになる。
レベル$k$のバーガーを途中まで食べるとは、バン、レベル$k-1$バーガー、パティ、レベル$k-1$バーガー、バン、を食べられるところまで食べることである。
「食べられる所まで食べる」を、前のステップの結果 $y = 0$ になったらそれで完了、さもなくば次のステップに計算を進める、という bind 的計算によって表現する。
結果
ts, ps :: [Int]
ts = 1 : map ((3 +) . (2 *)) ts -- t()
ps = 1 : map ((1 +) . (2 *)) ps -- p()
abc115d :: Int -> Int -> Int
abc115d n x = snd $ burger n (x, 0)
where
burger :: Int -> (Int,Int) -> (Int,Int)
burger 0 (y, z) = (pred y, succ z)
burger k yz@(y, z)
| tk <= y = (y - tk, z + pk) -- レベルkバーガーを食べ尽くす
| otherwise = ban yd `next` burger (pred k) `next` putty `next` burger (pred k) -- `next` ban
where
tk = ts !! k
pk = ps !! k
ban (y, z) = (pred y, z) -- バン
putty (y, z) = (pred y, succ z) -- パティ
next yz@(0, _) _ = yz -- 食べきったらパティの枚数が答え
next yz f = f yz -- まだなら続きに託す
公式解説のやり方
命令型で再帰的に書くならそうだね、というコード。範囲外の引数をうまく許容しているところが上手いか。
abc115d = f
where
f 0 x = if x <= 0 then 0 else 1
f n x
| x <= 1 + t !! pred n = f (pred n) (pred x)
| otherwise = p !! pred n + 1 + f (pred n) (x - 2 - p !! pred n)
自分の方法は「レベルK全体をバイパスできるか」を判定しているのに対して、
これは「自分の中央のパティより下か」つまり「レベルK-1+1な下半分をバイパスできるか」で判定して、下半分もしくは上半分へ必ず再帰呼び出しするので、必ず$N$ステップかかる。
逆に自分の方法は、前半がスキップできるかどうかを調べるのを再帰呼び出しに頼っているので、どっちもどっちという感じだろうか。