A - Right Triangle
シグネチャを決める。
abc116a :: Int -- |AB|
-> Int -- |BC|
-> Int -- |CA|
-> Int -- 答え
abc116a ab bc _ca = div (ab * bc) 2
角Bが直角なので、ヘロンの公式はいらない。
B - Collatz Problem
シグネチャを決める。
abc116b :: Int -- s
-> Int -- 答え
普通にする
出現した数を覚えておき、もう一度出現したときに、今の添え字が答えになる。
import qualified Data.IntSet as IS
abc116b :: Int -> Int
abc116b s = loop IS.empty s 1
f :: Int -> Int
f x = if even x then div x 2 else 3 * x + 1
loop :: IM.IntSet -> Int -> Int -> Int
loop is a cnt
| IS.member a is = cnt
| otherwise = loop (IS.insert a is) (f a) (succ cnt)
公式解説の「また」
コラッツ数列なので、最終的に $4 \to 2 \to 1 \to 4$ のループになる。
つまり、それ以外の数が重複することはない（するなら、上のループに到達できない）ので、
1,2のときは答えは4、それ以外のとき、初めて4になった添え字+3が答え。
abc116b 1 = 4
abc116b 2 = 4
abc116b s = (4 +) $ length $ takeWhile (4 /=) $ iterate f s
C - Grand Garden
シグネチャを決める。
abc116c :: Int -- N
-> [Int] -- h_i
-> Int -- 答え
Data.List.Split.wordsBy により、0な要素を捨て、それで区切られる部分列に分割することができる。linesBy と異なり、wordsBy は連続する空白をまとめて捨ててくれる。
こうして正規化した分割に対して、全てを1減らす。その個数分だけ水やりの回数をカウントする。
分割それぞれについて自身を再帰する。
結果
import Data.List.Split
abc116c :: Int -> [Int] -> Int
abc116c _n hs = loop hs
loop :: [Int] -> Int
loop hs = sum $ map (succ . loop . map pred) $ wordsBy (0 ==) hs
ユーザ解説の方法
より高速な解法 by MMNMM に従う。
これはつまり、解説にある絵の水色で塗られた「壁」の向かい合う間を埋めるために水やりを1ずつ必要とするので、その総数の半分が答えになる、という仕組み。
abc116c _n hs = flip div 2 $ sum $ map abs $ zipWith (-) (hs ++ [0]) (0:hs)
D - Various Sushi
シグネチャを決める。
abc116d :: Int -- N
-> Int -- K
-> [[Int]] -- t_i, d_i
-> Int -- 答え
わからなくて解説を見た。以下、ほぼ抜き書きな解説。
$p$ 種類のネタで獲得できるおいしさ基礎点の最大値を $f(p)$ とする。
スシをおいしさの降順で整列し、前 $K$ 個と後半に分ける。
前 $K$ 個のネタの種類数が $x$ おいしさの総和が $s$ のとき、$f(x) = s$ であるといえる。
前 $K$ 個は種類を気にせず大きい方から選択したのだから、それよりスコアが上がる選択肢はないからである。
またそのことを踏まえると、この $K$ 個からいずれかのネタを粛正し、それ以外の選択しているネタで補填することで、より少ないネタの種類数 $y < x$ での $f(y)$ を作ろうとすると、おいしさはより落ちる（または等しい）ものしか残っていないので、$f(y) \leq f(x)$ であるとわかる。
また、種類を減らすとボーナスポイントも減るため、最終スコアは確実に少なくなるので、種類を減らす方向に調べる必要はない。
逆に、おいしさを減らす危険を冒してでも種類を増やし、かつおいしさを極力減らさないようにするには、
- 前 $K$ 個のうち、おいしさの小さい物から順に諦めて、それ以降の中から、おいしさの大きいものから順に加える。
- ただし、種類数を減らさないために、既存のもののうち、ネタごとに、おいしさ最大のものは食べること確定
- 追加する側は、種類数を増やすために、新規のネタのものだけ。つまり、まだ選ばれていないネタのうち、おいしさ最大のものだけが候補
となる。このようにして $z > x$ について $f(z)$ を順に構成し、ボーナスポイントを加えた後の最大値を選ぶ。
データ構造としては、選択しているネタの集合を管理する IntSet と、おいしさ×種類の (Int,Int) のリスト、逆順に取り出すためのスタック（はリスト）があればできそうだ。
結果
import qualified Data.IntSet as IS
abc116d :: Int -> Int -> [[Int]] -> Int
abc116d _n k tds =
-- 種類ボーナスポイントを加えて最大値をとる
maximum $ zipWith (+) (loop total1 is1 ds1 dts2) (map (^2) [x1 ..])
where
-- おいしさの降順に前K個と残りに分ける
(dts1, dts2) = splitAt k $ sortBy (flip compare) [(d, t) | t:d:_ <- tds]
-- 前K個で選んだネタ集合と、諦められるスシのおいしさの昇順リスト
(is1, ds1) = foldl' step (IS.empty, []) dts1
step (is, ds) (d,t)
| IS.member t is = (is, d:ds)
| otherwise = (IS.insert t is, ds)
-- 前K個のおいしさの総和
total1 = sum $ map fst dts1
-- 前K個の種類数
x1 = IS.size is1
-- 種類数を増やしおいしさの減少を抑えるやり方で一つずつ交換
loop acc is dds@(dx:ds) ((d,t):dts)
| IS.member t is = loop acc is dds dts -- 使えないdtは捨てる
| otherwise = acc : loop (acc - dx + d) (IS.insert t is) ds dts
loop acc _s _ _ = [acc] -- 候補のどちらかが尽きたら終わり