A - AtCoder Crackers
シグネチャを決める。
abc105a :: Int -- N
-> Int -- K
-> Int -- 答え
abc105a n k = if mod n k == 0 then 0 else 1
全員同じ枚数配れるなら0、余りが出るなら1枚多く貰える人がでる。
過去の自分は if でなく signum で1を作っていた。min 1 でもいいか。
B - Cakes and Donuts
シグネチャを決める。
abc105b :: Int -- N
-> Bool -- 答え
abc105b n = or [mod x 4 == 0 | x <- [n, n - 7 .. 0]]
ドーナツ高価くない？
C - Base -2 Number
シグネチャを決める。
abc105c :: Int -- N
-> String -- 答え
考える
$N = 0$ のときは特別扱いする。
最下位桁から、その桁が1のとき結果に足し込む値の符号が逆転する。なので2桁セットで考える。
$N > 0$ の場合を考える。
$N$ の普通の2進表記において、偶数桁のビットはそのままー2進表記に採用できる。
奇数桁のビットが0のときはー2進表記でも0にしておけばよい。
これが1のとき、ー2進表記で1にすると、真の値から元の重みの倍だけ小さくなってしまう。
これを補正するため、その次の桁に1を足し込む。
この操作を2桁ずつ繰り返せばできる。
$N < 0$ の場合は、$-2N$ という正の値を上の手続きでー2進表記にした後、1ビット右シフトする（末尾の0を消す）ことで実現できる。
abc105c n =
case signum n of
0 -> "0"
1 -> encode n
-1 -> init $ encode $ -2 * n
where
encode = dropWhile ('0' ==) . loop ""
loop res k
| k == 0 = res
| r <= 1 = loop ('0' : d0 : res) q
| r > 1 = loop ('1' : d0 : res) (succ q)
where
(q,r) = divMod k 4
d0 = if odd r then '1' else '0'
ユーザ解説 by drken
普通の基数表記をするアルゴリズムと同様に、$-2$ で割っていけばよい、というびっくりな話。
ただし、mod も rem も負の奇数を $-2$ で割った余りは $-1$ になってしまうのだけどそれを $+1$ にするために、商に1を足して補正する必要がある。
$K = -2q - 1$ のとき $K = -2(q + 1) - 1 + 2$ ということ。
abc105c :: Int -> String
abc105c 0 = "0"
abc105c n = loop n ""
where
loop 0 = id
loop k =
case divMod k (-2) of
(q, 0) -> loop q . ('0' :)
(q, -1) -> loop (succ q) . ('1' :)
これはすごい。
D - Candy Distribution
シグネチャを決める。
abc105d :: Int -- N
-> Int -- M
-> [Int] -- Ai
-> Int -- 答え
累積和と剰余で考える。
$A_1 + A_2 + \dots + A_k = S[k]$ とする。
右端を $r$ に固定したとき、何らかの左端 $\ell \leq r$ までの和は $A_\ell + \dots + A_r = S[r] - S[\ell - 1]$ で、
これが $\equiv 0 \mod M$ とは $S[\ell - 1] \equiv S[r] \mod M$ である。
つまり、$S[r] \bmod M$ と等しい値を持つ $S[\ell - 1]$ の個数を数えればよい。
これは、$r=1,2,\dots$ と順に調べながら、剰余がその値になる区間の個数を+1していくことでできる。
import qualified Data.IntMap as IM
abc105d :: Int -> Int -> [Int] -> Int
abc105d _n m as = sum $ snd $ mapAccumL step IM.empty $ scanl (+) 0 as
where
step im s = (IM.insertWith (+) r 1 im, IM.findWithDefault 0 r im)
where
r = mod s m