A - ABC333
シグネチャを決める。
abc109a :: Int -- A
-> Int -- B
-> Bool -- 答え
abc109a a b = odd a && odd b
B - Shiritori
シグネチャを決める。
abc109b :: Int -- N
-> [Strng] -- Wi
-> Bool -- 答え
abc109b n ws = cond1 && cond2
where
...
単語の連続において、前の末尾と次の先頭が一致している必要がある。
cond2 = and $ between (\x y -> last x == head y) ws
between f xs = zipWith f xs $ tail xs
単語は全て唯一である必要がある。
集合に直してサイズがNのまま、ソートして前後が異なる、など、いくつかやり方はある。
import qualified Data.Set as S
cond1 = n == S.size (S.fromList ws)
import Data.List
cond1 = and $ between (/=) $ sort ws
公式解説では、総当たりで調べても平気、とあったが、文字列の比較なので比較が $O(1)$ でなく文字列の長さだけかかるので思ったより遅くなるはず。
import Data.List
cond1 = and [notElem x xs | x:xs <- tails ws]
自分の過去の提出では、クイックソートの構造を応用した、えらい張り切った計算を定義していた。
cond1 = noDupe ws
noDupe :: Ord a => [a] -> Bool
noDupe [] = True
noDupe (p:xs) = null bs && noDupe as && noDupe cs
where
(as,bs,cs) = foldr step ([],[],[]) xs
step x (as,bs,cs) =
case compare x p of
LT -> (x:as,bs,cs)
EQ -> (as,x:bs,cs)
GT -> (as,bs,x:cs)
C - Skip
なんか流れてきたこのポストに類題として挙げられていたのでふり返ってみた。
シグネチャを決める。
abc109c :: Int -- N
-> Int -- X
-> [Int] -- xi
-> Int -- 答え
ようは、初期位置と各目標との距離のGCDを求めればよい。
結果
import Data.List
abc109c :: Int -> Int -> [Int] -> Int
abc109c _n x0 xs = foldl1' gcd [abs (x - x0) | x <- xs]
D - Make Them Even
シグネチャを決める。
出力形式を横着する。長さは出力側で数えることにする。
abc109d :: Int -- H
-> Int -- W
-> [[Int]] -- a_i,j
-> [[Int]] -- 答え
操作回数を最小化する必要はないので、全てのマスを触る勢いでやる。
左から順に、奇数なら右隣に移す、を繰り返す。
これを全ての行についてやった後、一番右の列について、上から順に、奇数なら下隣に移す、を繰り返す。
最大 $HW-1$ 回で、右下以外は必ず偶数にできる。
結果
…という計算を直接実行する代わりに、端からの累積和が奇数なマスは移動を実行することになる、と読み替えると、immutableな計算で表現しやすくなる。
import Data.List
abc109d h w ass = cmds2 ++ cmds1
where
cmds1 =
[ [y, x, y, succ x]
| (y, as) <- zip [1 ..] ass
, (x, True) <- zip [1 .. pred w] $ map odd $ scanl1 (+) as ]
cmds2 =
[ [y, w, succ y, w]
| (y, True) <- zip [1 .. pred h] $ map odd $ scanl1 (+) $ map sum ass ]
cmds = cmds2 ++ cmds1
公式解説だと、行ごとに進行方向を折り返している。そういう考え方もあるのね。