A - Sharing Cookies
シグネチャを決める。
abc067a :: Int -- A
-> Int -- B
-> Bool -- 答え
素直な解法
abc067a a b = any d3 [a, b, a + b]
where
d3 x = mod x 3 == 0
「なお」
公式解説に「なお、～」と書かれているトリックは、A,Bを3で割った余りが1と2ならば足して3で割り切れることから、下の表の×のところだけをあぶり出そうということ。
| 0 | 1 | 2 | |
|---|---|---|---|
| 0 | ○ | ○ | ○ |
| 1 | ○ | × | ○ |
| 2 | ○ | ○ | × |
素直な人は、○のところを見つけようと、こう書くだろう：
abc067a a b =
case (mod a 3, mod b 3) of
(0,_) -> True
(_,0) -> True
(1,2) -> True
(2,1) -> True
_ -> False
×は2つしかないのでもっと短くなる。
abc067a a b = notElem (mod a 3, mod b 3) [(1,1),(2,2)]
B - Snake Toy
シグネチャを決める。
abc067b :: Int -- N
-> Int -- K
-> [Int] -- l_i
-> Int -- 答え
大きい方からK個取ればよい。
結果
import Data.List
abc067b :: Int -> Int -> [Int] -> Int
abc067b _n k ls = sum $ take k $ sortBy (flip compare) ls
C - Splitting Pile
シグネチャを決める。
abc067c :: Int -- N
-> [Int] -- a_i
-> Int -- 答え
すぬけくんが取る枚数を $i$ としたときのすぬけくんの合計 $x_i$ アライグマの合計 $y_i$ とする。
$x_i$ は累積和で $O(N)$ で計算できる。
全てのカードの合計を $T$ とする。
絶対値をとる前の二人の合計の差 $d_i = x_i - y_i$ とする。
$d_0 = 0 - T = -T$
$d_k - d_{k-1} = (x_k - y_k) - (x_{k-1} - y_{k-1}) = (x_k - x_{k-1}) - (y_k - y_{k-1}) = a_k - (- a_k) = 2a_k$
これで $d_1, \dots, d_N$ を求めれば、$\min_{1 \leq i < N} | d_i |$ が答えである。
ここで $d_0, d_N$ は候補に含めないことが重要。（例2参照）
結果
import Data.List
abc067c :: Int -> [Int] -> Int
abc067c _n as = minimum $ map abs $ init $ tail $ scanl' step (- total) as
where
total = sum as
step d a = d + a + a
D - Fennec VS. Snuke
シグネチャを決める。横着する。
abc067d :: Int -- N
-> [[Int]] -- a_i, b_i
-> Bool -- 答え 先手勝ちなら True
考える
グラフは木なので、特定の2頂点間の経路は一つしかないため、そんなに複雑な話にはならない。
頂点1とNを結ぶ経路（背骨と呼ぶことにする）を考える。すると、
木は、
- フェネックに確定している、頂点1にぶら下がる部分木（背骨方面以外）
- 背骨の頂点（1とN以外）にぶら下がる、どちらにも確定していない部分木群
- すぬけくんに確定している、頂点Nにぶら下がる部分木（背骨方面以外）
という３つの部分に大分される。
こう見ると、最善の方針は、背骨を真っ先に取りにいくことで、それらにぶら下がった部分木を確保し、背骨が占領されたら全ての頂点が確定するので、それを順に消費していくことだとわかる。
という洞察をそのまま実装
1から木を走査することで、Nまでの経路、背骨を取り出す。
背骨を真ん中で分けて、フェネックとすぬけくんの取り分とする。
グラフから背骨の辺を除くことで森にしたものを考える。
それらの木の頂点数を数える。それぞれの取り分となる頂点数が決まる。
フェネックが先手なので、フェネックの取り分がすぬけくんより多いときフェネックの勝ちになる。
import Data.Array.Unboxed
abc067d :: Int -> [[Int]] -> Bool
abc067d n uvs = f > s
where
g :: Array Int [Int]
g = accumArray (flip (:)) [] (1,n) $
[(u,v) | u:v:_ <- uvs] ++
[(v,u) | u:v:_ <- uvs]
-- 1からNへの背骨をなす頂点リスト
Just spine = dfs 0 1
dfs p u
| u == n = Just [u]
| otherwise = (u :) <$> msum [dfs u c | c <- g ! u, c /= p]
-- 背骨をなす頂点でないことを判定する表 not spine
ns :: UArray Int Bool
ns = accumArray (flip const) True (1,n) [(u, False) | u <- spine]
-- 背骨の経路を除いたグラフ、つまり両端とも背骨でない辺のみからなる
g1 :: Array Int [Int]
g1 = listArray (1,n) [if ns ! u then vs else filter (ns !) vs | (u,vs) <- assocs g]
size p = loop 0 p (0 :: Int)
where
loop p u acc = foldr ($!) (succ acc) [loop u v | v <- g1 ! u, v /= p]
-- 背骨が奇数のときは真ん中はフェネックが取る
(spF, spS) = splitAt (div (succ $ length spine) 2) spine
f = sum $ map size spF
s = sum $ map size spS
もう一ひねり
貪欲な最善の戦略とその結末を考えたとき、
「各頂点は結局、頂点1,Nからの距離が近い方のものになる」
にすぎないという洞察ができるらしい。
このとき、先手のフェネックの方が強くて、距離が等しい頂点はフェネックの取り分になる。
これなら、背骨とか考えず、距離を2度数えて比較するだけで答えが出る。
import Data.Array.Unboxed
abc067d :: Int -> [[Int]] -> Bool
abc067d n uvs = f > s
where
g :: Array Int [Int]
g = accumArray (flip (:)) [] (1,n) $
[(u,v) | u:v:_ <- uvs] ++
[(v,u) | u:v:_ <- uvs]
-- 1とNからの各頂点の距離
dF, dS :: UArray Int Int
dF = array (1,n) $ dist 0 0 1 []
dS = array (1,n) $ dist 0 0 n []
-- dist d p v :: 頂点vは親pから到達し距離dである、という状況で距離を数える
dist d p v rest = (v, d) : foldr ($) rest [dist (succ d) v u | u <- g ! v, u /= p]
f = length $ filter id $ zipWith (<=) (elems dF) (elems dS)
s = n - f