A - Poisonous Oyster
消費期限10日過ぎた加熱用の生牡蠣を生で食べた話があったところでのこの出題。
シグネチャを決める。
abc393a :: String -- S1
-> String -- S2
-> Int -- 答え
答えが X であるのはどういう状況のときか、を書き出してみる。
| 答え | 高橋 | 青木 |
|---|---|---|
| 1 | sick | sick |
| 2 | sick | fine |
| 3 | fine | sick |
| 4 | fine | fine |
fineを1、sickを0の2進数で解釈すると、答え-1の値になる対応が見えてくる。
結果
import Data.Bool
abc393a :: String -> String -> Int
abc3c3a (t:_) (a:_) = succ $ bool 0 2 (t == 'f') + bool 0 1 (a == 'f')
B - A..B..C
シグネチャを決める。
abc393b :: String -- S
-> Int -- 答え
注目する位置を先頭から1文字ずつ進め、通過済みの、より左の部分は逆順にリストに繋ぐ。
注目する位置が B のとき、より左の部分とより右の部分が (A,C) となる組の個数を数える。
結果
abc393b s = sum $ loop [] s
where
loop _ [] = []
loop ls (c:rs)
| c == 'B' = cnt : loop (c:ls) rs
| otherwise = loop (c:ls) rs
where
cnt = length $ filter (('A','C') ==) $ zip ls rs
C - Make it Simple
シグネチャを決める。
abc393c :: Int -- N
-> Int -- M
-> [[Int]] -- ui,vi
-> Int -- 答え
重複を除去して数えるために、辺の集合を作り、その要素数を数える。
ただし、自己ループは集合に加えず弾く。
例1の 2 3 と 3 2 のような場合を同一視するため、小さい順に正規化する。
結果
import qualified Data.Set as S
abc393c :: Int -> Int -> [[Int]] -> Int
abc393c _n m uvs = m - S.size s
where
s = S.fromList [(min u v, max u v) | u:v:_ <- uvs, u /= v]
D - Swap to Gather
シグネチャを決める。Sは長いので ByteString にしておく。
import qualified Data.ByteString.Char8 as BS
abc393d :: Int -- N
-> BS.ByteString -- S
-> Int -- 答え
全体で 1 は $C$ 個あるとする。
間に 0 が $Y$ 個あるとき、これを詰めることを考える。
それより左に 1 が $X$ 個あるとき、これらを右に動かす手間は $XY$ である。
より右には 1 が $C - X$ あり、それらを左に動かす手間は $(C-X)Y$ である。
この小さい方を選ぶ。
group を使って、1 の並びの塊と 0 の並びの塊に分け、その長さのリストを持つ。
先頭と末尾は 1 のものとする。
- 個数リストが長さ1のとき、目標は達成されている。
- 個数リストが長さ3以上のとき、
x:y:z:xsとして、y個の0の並びを詰めるコストは上のように計算できる。詰めた後の状況は(x+z):xsとなるので、同じ事を繰り返す
とすればよい。
結果
import Data.Bool
abc393d :: Int -> BS.ByteString -> Int
abc393d _n s = sum $ loop ks
where
ks0 = map BS.length $ BS.group s
ks = bool id init (BS.last s == '0') $ bool id tail (BS.head s == '0') ks0
c = BS.count '1' s
loop [_] = []
loop (x:y:z:xs) = y * min x (c - x) : loop (x+z:xs)
E - GCD of Subset
シグネチャを決める。
abc393e :: Int -- N
-> Int -- K
-> [Int] -- Ai
-> [Int] -- 答え
なんもわからん。
ゼータ関数！？
なんもわからんが、克明に計算手順が書かれているから実装することはできる。
結果
import Data.Array.Unboxed
import Data.Bool
abc393e :: Int -> Int -> [Int] -> [Int]
abc393e n k as = map (ans !) as
where
ub = maximum as -- 10^6決め打ちでもいいけど
cnt0, cnt, ans0, ans :: UArray Int Int
-- A中の値iの個数
cnt0 = accumArray (+) 0 (1,ub) [(a,1) | a <- as]
-- A中の値iの倍数の個数：ここでAiに存在しない数についても勘定しているのがミソ？
cnt = listArray (1,ub) [sum [cnt0 ! j | j <- [i, i + i .. ub]] | i <- [1 .. ub]]
-- 値iの倍数がA中にK個以上あるとき、A中のK個の数をうまく選べばgcdをiにできる（最大値）
-- そうでない数はもっと小さい数にしかできない。具体的な値はまだ不明
ans0 = listArray (1,ub) [bool 0 i (c >= k) | (i,c) <- assocs cnt]
-- 値iについて、その約数jのans0の最大値が、値iを含むK個の数をA中から選んで作れるgcdの最大値
ans = accumArray max 0 (1,ub) [(j, a) | (i,a) <- assocs ans0, j <- [i, i + i .. ub]]
アライさんの説明だと、mutable arrayの値を壊さないようにループの向きを気にしたりしてDPだと捉えているけれど、immutable arrayの観点から解釈すると、何かを単に数えているだけに見える。
蛇足
ans0 の値 0 は、max をとったときに無視される値として選んでいるので、もっと厳密に、Maybe で包んでやる方法も考えられる。
また、ans を配るDPで計算すると ans0 の全てを舐めることになるが、そもそもこれは $A_i$ に出現する値だけを計算すればよいので、その約数全ての ans0 の値を集めてくる形にすれば不要な箇所の計算をlazyに回避できる。
ans0 :: Array Int (Maybe Int)
ans0 = listArray (1,ub) [bool Nothing (Just i) (c >= k) | (i,c) <- assocs cnt]
ans :: Array Int Int
ans = listArray (1,ub) $ map (maximum . catMaybes . map (ans0 !) . factors) [1 .. ub]
-- 約数列挙
factors :: Int -> [Int]
-- 実装略
しかしこうすると、ひとつの factors の計算に $O(\sqrt M)$ （ここで$M = \max A_i$ とする）かかるため、全体で $10^9$ オーダーの計算量になってTLEする…
cnt や ans の二重ループの方が $O(M^2)$ になりそうなものだが、各 $i$ に対して $M/i$ 要素しか触らないので、全体では
$$M + M/2 + M/3 + \dots + M/M = M(1 + 1/2 + 1/3 + \dots + 1/M)$$
ググると
$$\log (n + 1) < \sum_{k=1}^n \frac{1}{k} < 1 + \log n$$
という式が見つかって 結局 $O(M \log M)$ で収まるということか。
F - Prefix LIS Query
シグネチャを決める。
abc393f :: Int -- N
-> Int -- Q
-> [Int] -- Ai
-> [[Int]] -- Ri, Xi
-> [Int] -- 答え
頭が回らないのでヒントをもらう。
問題文はオンラインクエリっぽくても、オフラインでやるというのは常套手段だった。
結果
import Data.Array
import qualified Data.IntMap as IM
abc393f :: Int -> Int -> [Int] -> [[Int]] -> [Int]
abc393f n q as rxs = elems ans
where
-- Aiまで調べた後に対応するべきクエリのリストが qarr[i]
qarr = accumArray (flip (:)) [] (1,n) [(r, (i,x)) | (i, r:x:_) <- zip [1 ..] rxs]
-- LISを求めつつ、クエリに対応する
(_, anss) = mapAccumL step (IM.singleton 0 0) $ zip as $ elems qarr
-- クエリの答えを番号順に戻す
ans = array (1,q) $ concat anss
-- LIS計算とクエリ対応のステップ
step im (ai, ixs) = (im1, map f ixs)
where
-- LIS部
Just (_, cnt) = IM.lookupLT ai im -- 末尾Ai未満な最長のLISの~末尾の値~と長さ
im1 = case IM.lookupGE ai im of -- Ai以上なLISがあれば、その長さもcnt+1と等しいはずなので、単調性からこれは消す
Just (ak,_) | ak > ai -> IM.insert ai (succ cnt) $ IM.delete ak im
| otherwise -> im
Nothing -> IM.insert ai (succ cnt) im
-- クエリ部
f (i, x) = (i, ans)
where
Just (_, ans) = IM.lookupLE x im1
G - Unevenness
公式解説を開いてそっ閉じ。