A - Garden

問題 ABC106A

シグネチャを決める。

abc106a :: Int -- A
        -> Int -- B
        -> Int -- 答え
abc106a a b = pred a * pred b

B - 105

問題 ABC106B

シグネチャを決める。

abc106b :: Int -- N
        -> Int -- 答え

$N$ 個の整数についてそれぞれ試し割りを $\sqrt N$ 回行って $O(N^{3/2})$ かけても $N \leq 200$ なので大したことはない。

abc106b :: Int -> Int
abc106b n = length
  [ ()
  | x <- [1, 3 .. n]
  , 8 == sum [if d * d == x then 1 else 2 | d <- takeWhile ((x >=) . (^ 2)) [1 ..], mod x d == 0] ]

平方数のときは1、そうでないときはdとx/dで2つの約数を数える、というロジックが必要だった。

エラトステネスのふるい的な表を作って、倍数のインクリメントにより約数を数える方が計算機に優しい。

import Data.Array.Unboxed

abc106b n = length [() | x <- [1, 3 .. n], cnt ! x == 7]
  where
    cnt :: UArray Int Int
    cnt = accumArray (+) 0 (1,n) [(j, 1) | i <- [3, 5 .. n], j <- [i, 3 * i .. n]]

奇数は偶数な約数など持たないのでiは奇数だけ考える。jも奇数倍だけ考える。
これの計算量は調和級数 $1 + 1/2 + 1/3 + \dots + 1/N \sim \log N + \gamma$ と関係したものになる。

公式解説の「ズルい解法」

abc106b n = length $ takeWhile (n >=) [105,135,165,189,195]

ユーザ解説 by hamayanhamayan

enumdiv が $O(\sqrt n)$ だと言っているけど、sort を呼んでいるのでもう少し掛かったりしないしら。
約数の個数が $m$ のとき $O(\sqrt n + m \log m)$ という感じ。
$m$は$n$よりずっと小さいから無視できる？

C - To Infinity

問題 ABC106C

シグネチャを決める。

abc106c :: String -- S
        -> Int    -- K
        -> Char   -- 答え

以下、$G$ を五千兆 ($5,000,000,000,000,000 = 5 \times 10^{15}$) とする。
$K$ の上限は $10^{18}$ なので $G$ よりは大きいが。

1 はずっと長さ1のまま。
2 は毎日2倍の長さになるので、1文字が最後には $2^G$ 個になる。これは$K$の上限をはるかにしのぐ巨大な数。
3 は$3^G$、以降は考えるまでもない。

先頭から1が続く限りはそのまま、その他の数字が現れたら$G$日後はその先はずっとその数字と思えばよい。

結果

abc106c s k = loop s 1
  where
    loop ('1':ds) i | i < k = loop ds (succ i)
    loop ( d :_)  _         = d

D - AtCoder Express 2

問題 ABC106D

シグネチャを決める。横着する。

abc106d :: [Int]   -- N,M,Q
        -> [[Int]] -- Li,Ri
        -> [Int]   -- 答え

真面目にやると $O(MQ)$ で大変なことになる。
ここでは今から効率的なアルゴリズムを考えていくが、世の中のデータベースなるものは、そういうことなしに、ナイーブな計算をブン回される哀れな機械なのかしら。生まれ変わってもDBサーバにはなりたくない。

ここでは、$N \leq 500$ が小さいことを利用すればいいのだろうか。
各駅 $a$ について、そこから出発する列車で終点が $b$ なもの、つまり $(L_i, R_i) = (a,b)$ の個数を数える。
さらに近い方からの累積和をとることで、終点が $q$ またはそれより手前なものの数が数えられる。これを $C[a,b]$ とする。
クエリ $(p, q)$ に対しては、$C[p,q] + C[p+1,q] + \dots + C[q,q]$ が答えになるわけだが、これも毎回計算せず、始発駅軸での累積和を求めておくことで、$O(1)$ で答えられる。

これはつまり、列車 $(L,R)$ をこの座標の点と見なし、クエリ $(p,q)$ とは $(p,p)$ から $(q,q)$ の範囲の正方形領域に含まれる点の個数を数える、二次元累積和、いわゆる狭義のいもす法で解決できる。

結果

import Data.Array.Unboxed
import Data.List.Split

abc106d :: [Int] -> [[Int]] -> [[Int]] -> [Int]
abc106d [n,_m,_q] lrs pqs = map f pqs
  where
    n1 = succ n
    c0,cnt :: UArray (Int,Int) Int
    c0 = accumArray (+) 0 ((1,1),(n,n)) [((l,r),1) | l:r:_ <- lrs]
    cnt = listArray ((0,0),(n,n)) $ concat $
          scanl (zipWith (+)) (replicate (succ n) 0) $
          map (scanl (+) 0) $ chunksOf n $ elems c0
    f (p:q:_) = cnt ! (q,q) - cnt ! (pred p, q)

点は $y = x$ 以上の領域にしかないため、$y = x$ 未満の領域についての計算を f において省略している。

ユーザ解説 by seekworser

意表を突いたオフライン解法。これは面白い。

1からNの範囲のセグメント木を用意する。
全ての列車について、$R_i$ に1を足しこんでおく。
これで駅1から各駅までの範囲に収まる列車の本数がわかる。

列車の $L_i$ について、$R_i$ を取り出せるようにしておく。
クエリを $p$ の昇順に考える。

まだ残っている列車のうち、$L_i < p$ であるような列車について、$R_i$ を取り出して、セグメント木から取り除く。
これで、駅 $L_i$ から各駅までの範囲に収まる列車の本数がわかる。
なので、セグメント木に $[1,q]$ について問いあわせれば、答えがわかる。

オフライン解法なので、結果をクエリ順に出力する。

import Control.Monad
import Control.Monad.ST
import qualified Data.Vector.Unboxed.Mutable as MUV
import Data.Array

abc106d :: [Int] -> [[Int]] -> [[Int]] -> [Int]
abc106d [n,_m,q0] lrs pqs = runST $
  do
    rqa <- makeRQArray (+) 0 $ elems cnt0
    res <- MUV.new q0 :: ST s (MUV.MVector s Int) -- 結果を格納する
    forM_ [1 .. n] $ \k -> do -- 左の駅から順に
      forM_ (queries ! k) $ \(q,j) -> do -- その駅のクエリを処理
        x <- queryRQArray rqa 0 q
        MUV.write res j x
      forM_ (trains ! k) $ \r -> do
        modifyRQArray rqa (pred r) pred
    forM [0 .. pred q0] $ MUV.read res
  where
    cnt0 = accumArray (+) 0 (1, succ n) [(r,1) | _:r:_ <- lrs] -- 列車の到着駅にマーク
    trains = accumArray (flip (:)) [] (1,n) [(l,r) | l:r:_ <- lrs] -- 始発駅に対して到着駅をメモる
    queries = accumArray (flip (:)) [] (1,n) [(p,(q,j)) | (j, p:q:_) <- zip [0 ..] pqs] -- クエリの左端に対して右端とクエリの番号をメモる

セグメント木の実装は省略。
というか、ACL版を使えるようにならないと？

ユーザ解説 by drken

は消えているblogの解法1の再解説。
上のseekworser解では、セグメント木に終点をマークしてタイミングを見て消す、とやっていたところを、
最初は0なセグメント木にタイミングを見て始点をマークする、という向きになっているだけで根元は同じだと思う。

Nが大きくなっても大丈夫、と言っているが、セグメント木が$O(N)$のメモリを使うので、$10^5$ あたりまでで。

hama_du さんの解法2では、列車の情報をセグメント木に破壊的に書き込む代わりに、
永続セグメント木を使って全てのスナップショットを残しておくことで、
解法1をオンラインアルゴリズムに改変すると書いている。

そしてこれらの手法を「平面走査」と呼んでいる。以前JOI問題で勉強したときとスタイルが違う気もするが、広い概念なのかな。

さらに解法3では、ウェーブレット木というデータ構造を用いる解法も紹介されているが、これはまたの機会にしよう。