A - Last Two Digits
シグネチャを決めるまでもない。必ず3桁な入力を整数として解釈したら負けである。
結果
main = getLine >>= putStrLn . tail
B - Practical Computing
シグネチャを決める。
abc254b :: Int -> [[Int]]
これはパスカルの三角形、または二項係数そのものであるが、たかだか $N \leq 30$ なので問題文どおりに生成する。
結果
abc254b n = take n ncrs
ncrs = [1] : map step ncrs
step ncr = zipWith (+) (0 : ncr) (ncr ++ [0])
C - K Swap
シグネチャを決める。
abc254c :: Int -> Int -- N, K
-> [Int] -- ai
-> Bool -- 結果
添え字を0始まりにして考える。
どのように操作を行っても、数列の $i$ 番目の要素は、$K$ 間隔の位置である $i + nK$ 番目（$n$ は負を含む任意の整数）にしか来ることができない。
つまり、$A$ を $K$ 間隔で取り出した多重集合 $A_j = \{ a_{nK+j} \;|\; n = 0,1\dots \} \; (0 \leq j < K)$ と、$A$ を整列した列 $S = (s_1, s_2, \dots, s_N)$ を $K$ 間隔で取り出した多重集合 $S_j = \{ s_{nK+j} \;|\; n = 0,1,\dots \} \; (0 \leq j < K)$ が、$A_j = S_j \; (0 \leq j < K)$ である必要がある。
結果
import Data.List
import Data.Function
abc254c :: Int -> Int -> [Int] -> Bool
abc254c n k as = and $ zipWith ((==) `on` sort) ds es
where
f = transpose . chop k
ds = f as
es = f $ sort as
chop :: Int -> [a] -> [[a]]
chop n = unfoldr step
where
step [] = Nothing
step xs = Just $ splitAt n xs
chop は Data.List.Split の関数であるが、import すると怒られた。
D - Together Square
シグネチャを決める。
abc254d :: Int -> Int
公式解説、ユーザ解説が非常に豊富にあるのでそちらも参照して。
素数を $[P_i]$ とする。数を素因数分解して考える。
任意の整数 $t = \prod P_i^{T_i}$ に対して、$t^2 = \prod P_i^{2 T_i}$ である。すなわち、平方数はべき乗の数がすべて偶数である。
この事実をもとに考えると、$a = \prod P_i^{A_i}$ と掛け合わせたら平方数になるような数 $b = \prod P_i^{B_i}$ は、$a \times b = \prod P_i^{A_i + B_i}$ について、$A_i + B_i$ が全て偶数である必要がある。つまり、$A_i$ と $B_i$ の偶奇が全て同じとなるような $b$ の個数だけ、$a$ と掛け合わせたら平方数となる数がある。
よって、べき乗の数の偶奇パターン全て $[偶,偶,\dots] \sim [奇,奇,\dots]$ について、$1 \leq i \leq N$ にそのような数がいくつあるかを数えられれば、その個数の二乗の和が答えである。
偶奇パターンを網羅しようとすると、$N$ 以下の最大の素数が $P_c$ であるときパターンは長さ $c$ になる。$2 \times 10^5$ 以下の素数は17984個もあるので、長さ17984の [Bool] で表すか、ビット列に落とし込んでも $0 \sim 2^{17984}-1$ の整数でこれを表現するには Int では収まらない。（なお、力づくで Integer で表して Map で数えて AC することもできる。）
しかしよく考えると、$P_{17983} \cdot P_{17984} > 2 \times 10^5$ のように、全てのビット列が現れるわけではないので、べき乗の数が奇数な素数だけの積で代表させることができる。つまり $t = \prod P_i^{T_i}$ であるとき、$N(t) = \prod P_i^{T_i \bmod 2}$ とする。これは $t \geq N(t)$ なので Int で扱える。
素因数分解は作り置きのスニペットを使う。
結果
import Data.Array.Unboxed
import Data.List
abc254d :: Int -> Int
abc254d n = sum . map (^ 2) . elems arr
where
arr :: UArray Int Int
arr = accumArray (+) (1,n) [(norm i, 1) | i <- [1 .. n]]
norm :: Int -> Int -- 関数 N
norm = product . map head . filter (odd . length) . group . primeFactors
-- @gotoki_no_joe
primeFactors :: Int -> [Int]
primeFactors n = loop n pprimes
where
pprimes = 2 : 3 : [y | x <- [5,11..], y <- [x, x + 2]] -- pseudo primes
loop n pps@(p:ps)
| n == 1 = []
| n < p * p = [n]
| r == 0 = p : loop q pps
| otherwise = loop n ps
where
(q,r) = divMod n p
続き
ひとつめの公式解説で言っている $\frac{i}{f(i)}$ は上の $N(\cdot)$ と同じものである。
$f(i)$ を高速に求めるために、候補となる $i$ 以下の平方数の降順のリストを素早く取り出せる sqm :: IntMap [Int] を作った。
import qualified Data.IntMap as IM
import Data.List
import Data.Maybe
import Data.Array.Unboxed
abc254d :: Int -> Int
abc254d n = sum $ map (^2) $ elems arr
where
arr :: UArray Int Int
arr = accumArray (+) 0 (1,n) [(idivfi i, 1) | i <- [1..n]]
sqs = reverse $ takeWhile (n >=) $ map (^ 2) [1 ..]
sqm = IM.fromAscList $ reverse [(head sq, sq) | sq <- init $ tails sqs]
idivfi i = head
[ q
| sq <- snd $ fromJust $ IM.lookupLE i sqm
, let (q,r) = divMod i sq
, r == 0]
結果、素因数分解した方が速かった。
E - Small d and k
シグネチャを決める。
abc254e :: Int -> Int -- N,M
-> [(Int,Int)] -- (ai,bi)
-> Int -- Q
-> [(Int,Int)] -- (xi,ki)
-> [Int] -- 答え
グラフの問題と聞いて身構えてしまうが、問題文に太字で「各頂点の次数は3以下」とヒントが書いてある。また、毎回のクエリで聞かれる距離も $0 \leq k_i \leq 3$ と小さい。
出発点 $x_i$ から距離1の頂点は、次数が3として3個、そこから距離1の頂点は次数3のうち $x_i$ でないものはもう2個、さらに距離1の頂点はもう2個で、$1 + 3 + 3 \times 2 + 3 \times 2 \times 2 = 22$ 頂点しかない。親を除くのをさぼっても $1 + 3 + 3 \times 3 + 3 \times 3 \times 3 = 40$ しかないので、力づくで挙げてしまえば済む。
結果
import Data.Array
import Data.List
abc254e :: Int -> Int -> [(Int,Int)] -> Int -> [(Int,Int)] -> [Int]
abc254e n m abs q xks = map (query g) xks
where
g = accumArray (flip (:)) [] (1,n) [p | (a,b) <- abs, p <- [(a,b),(b,a)]]
query g (x,k) = sum $ nub $ concat $ take (succ k) $ iterate (concatMap (g !)) [x]