A - Maximal Value
Aから入力サイズが可変なのは珍しいかも。
シグネチャを決める。
abc468a :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
between compare の結果が LT,GT の並びになっている個数、でやってみよう。
結果
abc468a n = length . filter id . between f . between compare
where
f LT GT = True
f _ _ = False
between f xs = zipWith f xs $ tail xs
B - Corridor Watch
シグネチャを決める。
abc468b :: Int -- M
-> Int -- D
-> String -- S
-> Int -- 答え
普通に配列でマークするやり方
マスが監視されていない、というフラグを配列に作り、ガードマンの前後Dマスのフラグを倒す。
ガードマンの人数($\leq M$) × ガードマン一人の影響範囲($=2D+1$) の手間が掛かる。つまり $O(MD)$
import Data.Array
abc468b :: Int -> Int -> String -> Int
abc468b m d s =
length $ filter id $ elems $
accumArray (flip const) True (1,m)
[(j,False) | (i,'G') <- zip [1 ..] s, j <- [max 1 $ i - d .. min m $ i + d]]
リスト処理だけでするやり方
「そのマスにガードマンがいない」をTrueとする長さMのリストを作る。
このリストの、注目しているマスに対応する要素の前後D要素も含めて切り出した部分リストが
全てTrueなら、確かにそのマスは監視が届いていない。
この切り出しには Data.List.Split.divvy が使える。
ただし、端のマスに前後を補完する必要がある。
import Data.List.Split
abc468b :: Int -> Int -> String -> Int
abc468b m d s =
length $ filter and $ divvy (d + d + 1) 1 $
replicate d True ++ map ('G' /=) s ++ replicate d True
データ構造が違うだけで計算量は上と同じ。
上をもっと効率よくする尺取法
$2D+1$ 要素の真理値を毎回 and するのでなく、
$2D+1$マスの区間のガードマンの人数を尺取法で数え、0人である場合を数えれば同じ結果が得られる。
abc468b :: Int -> Int -> String -> Int
abc468b m d s = length $ filter (0 ==) $ scanl (+) acc0 $ zipWith (-) (drop w xs) xs
where
xs = replicate d 0 ++ map g1 s ++ replicate d 0
g1 'G' = 1
g1 _ = 0
w = d + d + 1
acc0 = sum $ take w xs
公式解説の最後にBonus問題が出ている。
このアプローチの計算量は $O(M)$ なので、これなら間に合う。
C - Between P and Q
シグネチャを決める。
abc468c :: Int -- N
-> [Int] -- Pi
-> [Int] -- Qi
-> Int -- 答え
ストレートな解法
$N \leq 10$ と小さい。
$(1,2,\dots,N)$ の順列は $10! = 3,628,800$ 個と大したことないので、
辞書順に実際に生成して、PからQまでの間を数えることができる。
ただし、Data.List.permutations は辞書順を考慮してくれないし、
その結果を Data.List.sort で辞書順に直す、は富豪が過ぎるので、
辞書順に順列を生成する関数を自前で書く必要がある。
abc468c n ps qs = length $ takeWhile (qs >) $ dropWhile (ps >=) $ perm [1 .. n]
perm [] = [[]]
perm xs = [x:zs | (x,ys) <- sel xs, zs <- perm ys]
sel = go id
where
go _ [] = []
go f (x:xs) = (x, f xs) : go (f . (x :)) xs
計算量は $O(N!)$ となる。
順列の背番号を逆算する方法
$(1,2,\dots,K)$ の順列の個数は $K!$ であることから、
辞書順で $n$ 番目のものをピンポイントで生成したり、
ある順列が辞書順で何番目になるのかもピンポイントで算出できる。
リストに重複はないと仮定し、要素の標準の順序での辞書順での順位を数えることを考える。
空リストは常に0位である。
要素数$m+1$のリストについて、その順列は、
リストのそれぞれの要素を先頭とする順列 $m!$ とおりが $m+1$ 個ある。
そのうち、先頭要素未満の要素が $k$ 個あるとすると、
それらを先頭とする順列 $k \cdot (m+1)!$ 個が辞書順に前にあり、
残りの順位は、リストの後続の順位で求められる。
abc468c :: Int -> [Int] -> [Int] -> Int
abc468c _ ps qs = max 0 $ indexof qs - indexof ps - 1
where
-- 階乗
facts = scanl (*) 1 [1 ..]
-- indexof xs0 :: 順列としてのxs0の順位を数える(0始まり)
indexof [] = 0
indexof (x:xs) = k * facts !! m + indexof xs
where
k = length $ filter (x >) xs
m = length xs
計算量は $O(N)$ となり、公式解説の最後にあるBonus問題もこの方法なら間に合う。
ただし、上のコードは $k, m$ の求め方がnaiveなので、そこを補強する必要がある。
$m$はnから1ずつ減少するだけなので、いちいちlengthで数える必要はない。
$k$は、未使用な要素に1を充てたセグメント木を管理し、
先頭要素未満の未使用要素の個数を総和で取り出すことで対応できそう。
D - Pre-Palindrome
シグネチャを決める。
微妙な長さと、$O(1)$でのランダムアクセスがオマケに付いてくるので
Data.ByteString を使うことにする。
import qualified Data.ByteString.Char8 as BS
abc468d :: BS.ByteString -- S
-> Int -- 答え
考える
Zアルゴリズムとか難しくてわからないので、naiveにやることを考える。
回文が奇数長のとき、中心を位置 $k$ として、$k-1$と$k+1$, $k-2$と$k+2$, … が等しいか調べるが、
2つめの等しくない場合が出現したとき、そこまでの個数が答えとなる。
回文が偶数長のときは、$k$と$k-1$, $k+1$と$k-2$, … と一つずれる。
このアプローチの計算量は $S$ の長さを $N$ として $O(N^2)$ になる。
$N \leq 10^4$ なのでぎりぎり間に合う計算。
abc468d bs =
sum [f [k, k-1 .. 0] [k .. ub] | k <- [0 .. ub]] +
sum [f [k, k-1 .. 0] [k+1 .. ub] | k <- [0 .. ub]]
where
ub = pred $ BS.length bs
f is js = length . takeWhile (2 >) . scanl1 (+) $ zipWith p is js
p i j = if BS.index bs i == BS.index bs j then 0 else 1
1500msでどうにか間に合った。
公式解説の末尾、長さが10倍になるとこの解法では時間は100倍なので大変なことになる。
計算量を抑えるやり方はわからない。
E - Sum of Average
シグネチャを決める。
abc468e :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
どうにもわからなくて解説を見た。
公式解説の解法1
何を食べたらそういう式変形を思いつくのかというレベル
ポイントは、$\sum_{1 \leq l \leq r \leq N}$ という二重ループを、
$\sum_r \sum_l$ と $\sum_l \sum_r$ と都合のいいように分解することで、
不変な要素をループの外に追い出すことができるところかしら。
abc468e n as = summ $ zipWith3 f hs (reverse hs) bs
where
hs = scanl add 0 $ map modRecip [1 .. n]
bs = scanl add 0 as
f h h1 b = mul b (h - h1)
式をそのままコードにした感じ。
ユーザ解説の解法（改）
こちらの方がまだ納得がいく。
求めるものは可能な全ての部分区間の平均値 $f(l,r) = \frac{1}{r-l+1} (A_l + \dots + A_r)$ の総和 $\sum_{l \leq r} f(l,r)$
これを、平均をとる要素数ごとに分けて考える。$\sum_{k = 1}^N \sum_{i = 1}^{N-k+1} f(i,i+k-1)$
そして、平均をとるために要素数で割るのを後回しにする $\sum_{k=1}^N \frac{1}{k} \sum_{i=1}^{N-k+1} (A_i + \dots + A_{i+k-1})$
この式の後半を $S_k = \sum_{i=1}^{N-k+1} (A_i + \dots + A_{i+k-1})$ とする。
言葉で言うと、「長さ $k$ の連続部分列の総和」と説明できる。
さて、例えば $N=6, k=3$ としたとき、
$S_3 = (A_1 + A_2 + A_3) + (A_2 + A_3 + A_4) + (A_3 + A_4 + A_5) + (A_4 + A_5 + A_6)$
$=1A_1 + 2A_2 + 3A_3 + 3A_4 + 2A_5 + 1A_6$
となる。
このようにみたときの、$S_k$ に対して各 $A_i$ が結局どれだけの重みで算入されているかを「寄与」と呼んだりする。
中央部の項では $k$ になるが、端は1、次は2、と1ずつ増えて、また端に向けて減少していく。
$S_k$ を毎回ゼロから算出しようとすると困難だが、$S_k$ から $S_{k+1}$ を求めることを考える、
逆に言うとその差分を求めることを考える、というのがアイデア。
ユーザ解説の図も参照しながら考えると、
$S_0 = 0$
$S_k = S_{k-1} + (A_k + A_{k+1} + \dots + A_{N-k+1})$
となる。
（半分を超えると逆に減少していくが、このときは $N-k+1$ 番目から $k$ 番目までを引く、と考える。）
ユーザ解説ではこの階差のさらに階差をとることで、変動が $A_k$ と $A_{N-k+1}$ の2点だけで起きるようにしている。
そこまでしなくても、$A_i$ の累積和 $B_m = \sum_{i=1}^m A_i$ を使うと
$S_k = S_{k-1} + B_{N-k+1} - B_k$
とできるのでこれで十分。
import Data.Array.Unboxed
abc468e :: Int -> [Int] -> Int
abc468e n as = summ $ zipWith mul ss $ map modRecip [1 ..] -- Σ 1/k Sk
where
bb = listArray (0,n) $ scanl add 0 as :: UArray Int Int -- 累積和 B_m
vs = zipWith (-) (map (bb !) [n, n-1 .. 0]) $ elems bb -- Skの 増分 Bn - B0, B[n-1] - B1, …
ss = scanl1 add vs -- Sk
F - Chmax
シグネチャを決める。
abc468f :: Int -- N
-> [Int] -- Pi
-> Int -- 答え
LISをとって、それらを $P_i$ から除いた残りでLISをとって、それらの長さの和、かと思ったら違ったのでもうわからない。
ので解説を見たが、「もう少し考察を進めることで」あたりがもう何もわからない。
問題の設定として、xとyのいずれか一方はここまでの最大値に張り付かせることになるので、
「2回LISをとる」では都合が良すぎる（LISとしては使わない最大値を強制的に選択させられる場合がある）ので間違い
ということのようだ。
公式解説のやり方1
読み替えながら引き写す。
xとyのどちらがどちらかを区別する必要はないので、$x < y$に固定することにする。
つまり、yは常にこれまでの最大値となるので追跡する必要がなくなる。
操作1の手順は続きに「$x < y$となるよう必要なら交換する」が書いてあると思えばよい。
$c_i[x]$ を、i番目の操作まで終わった時点で、小さい方の値がxである場合のcの最大値、とする。
そのような場合がないときは $-\infty$ としておく。
$c_0[0] = 0, c_0[x>0] = -\infty$ とする。
$c_{i-1}[x]$ から、$P_i$ によって $c_i[x]$ を構築する。
最大値が更新される場合（解説のマル２, $P_i > \max(P_1, \dots, P_{i-1})$のとき）
全てのxについて $c_i[x] = c_{i-1}[x] + 1$ と増やす。
これは実際に+1する代わりに、全体のオフセットを別で管理しておき、これを+1することで対応する。
最大値が更新されない場合（解説のマル１）
$P_i$の点だけを $c_i[P_i] = \max_{0\leq j < P_i} c_{i-1}[j] + 1$ と、$P_i$ より小さい範囲の最大値＋１に更新し、
その他は $c_i[x \neq P_i] = c_{i-1}[x]$ と維持する。
最終結果は $\max_x c_N[x]$ で得られる。
$c_i[x]$ をセグメント木で管理する。
$P_i$ に加えてその直前までの最大値を foldM の入力とし、
c のオフセットを foldM の状態で持ち回している。
abc468f n ps = runST $
do
st <- makeSegTree max minBound $ 0 : replicate n minBound :: ST s (SegTree (STUArray s) Int)
ofs <- foldM (step st) 0 $ zip ps pms
(ofs +) <$> rootSegTree st
where
-- Piのここまでの最大値
pms = scanl max 0 ps
-- 最大値更新のとき、ベースラインを+1して終わり
step _t ofs (p, pmax) | pmax < p = return $! succ ofs
-- そうでないとき、piの値を未満の値の最大値+1に更新する
step st ofs (p, _max) = do
val <- succ <$> querySegTree st 0 p
writeSegTree st p val
return ofs
公式解説のやり方2
「もう少し考察を進める」…
問題の設定から、yは常にPiのこれまでの最大値を辿ることになる。
xは、yを犠牲にして、LISを辿ることができる。
なので、「これまでの最大値となる突出した $P_i$ を全て除いた数列Q」のLISがxのスコア、取り除いた要素の個数がyのスコアとなるやり方で最善」ということか。
雰囲気でしか判っていなくて証明はとてもできないが、信じて実装する。
（これ今のAIと証明支援系の組合せでオート証明できるのかしら。）
import qualified Data.IntSet as IS
abc468f :: Int -> [Int] -> Int
abc468f n ps = n - length qs + lengthLIS qs
where
qs = [p | (p, pmax) <- zip ps $ scanl1 max ps, p < pmax]
lengthLIS :: [Int] -> Int
lengthLIS = IS.size . foldl' step IS.empty
where
step is x =
case IS.lookupGE x is of
Nothing -> IS.insert x is
Just y | y == x -> is
| otherwise -> IS.insert x $ IS.delete y is
G - Restricted Permutation
シグネチャを決める。
abc468g :: Int -- N
-> String -- S
-> Int -- 答え
考えてみる
長さ1のとき、$(1)$ は必ず含まれるので、$S_1 = \texttt{o}$ に決まっている。
長さ$N$のとき、全体は $(1,2,\dots,N)$ の順列なので $S_N = \texttt{o}$ に決まっている。
これらは、Sの両端が x でないという保証を与える。
ある $j < k$ に関して、$S_j = S_k = \texttt{o}, S_{j < i < k} = \texttt{x}$ だったとする。
この条件を満たす$P$には $(1,\dots,j)$ の順列が連続部分列として含まれ、
さらにその両端に $j+1,\dots,k$ が並んで $(1,\dots,k)$ の順列をなす連続部分列があるが、
$(1,\dots,i)$ $(j<i<k)$ な部分列にはならない。
Sの長さiまでの条件を満たす順列の個数を $C_i$ としたとき、
$C_j$ な順列の両側に $j+1,\dots,k$ を並べるやり方は、
つまり $j$を$j$までの順列の代わりとして $j,j+1,\dots,k$ を並べるのと同じなので
その場合の数は $C_i \cdot (k-j+1)!$ とわかる。
そのうち、$A_j$ な順列の両端に $j+1$ が来る並べ方を除き、
距離2までの位置に$j+2$が来る並べ方を除き、…として $C_k$ に繋げる計算がわからない。
おてあげ。
解説を見ると、ユーザ解説がいっぱい生えてる。
公式解説のやり方
Sが指定する、順列があることを指定している上限の値を順に $A_1 < A_2 < \dots < A_M$ と呼ぶ。
$A_1 = 1, A_M = N$ である。
また、この問題の特別な形として、長さ n の $S = \texttt{oxxx...xxxo}$
つまり1とnのときだけは順列になり、それ以外では順列にならないような並べ方の場合の数
を考え、これを $d[n]$ とする。
すると元の問題の答えは $\prod_{i=1}^{M-1} d[A_{i+1} - A_i + 1]$ となる。
（これは上の考察と同じ事を言っている。）
（つまりここからがミソ。）
$(1,\dots,N)$ の順列 $N!$ 個の内訳を、
その中に含む短い順列 $(1,\dots,k<N)$ の長さ $2\leq k \leq N$ の最小値で分類することを考える。
（最初の考察どおり、$k=N$ は必ず存在するので数え落としはない。
また、全てに $k=1$ が該当してしまうので、$2 \leq k$で考える。）
最小値が $k$ であるようなものの個数は $d[k] \cdot (N-k+1)!$ である。
$k=2,\dots,N$についてこれらを足し合わせたら合計は $N!$ になるはずなので、
$N! = \sum_{k=2}^N d[k] \cdot (N-k+1)!$ となる。
$N=2$ を当てはめると
左辺 $2! = 2$
右辺 $\sum_{k=2}^2 d[k] \cdot (2-k+1)! = d[2] \cdot 1!$
より $d[2] = 2$
$N \geq 3$ のとき、$N-1$ までと$N$を分離すると
左辺 $N!$
右辺 $\sum_{k=2}^{N-1} d[k] \cdot (N-k+1)! + d[N] \cdot 1!$
より $d[N] = N! - \sum_{k=2}^{N-1} d[k] \cdot (N-k+1)!$ という漸化式が得られる。
import Data.List
abc468g :: Int -> String -> Int
abc468g _ s
| cond = prodd $ between (\ai ai1 -> deelist !! (ai1 - ai)) $ elemIndices 'o' s
| otherwise = 0
where
cond = head s == 'o' && last s == 'o'
facts = scanl mul 1 [1 ..] -- 階乗、最大でN+1まで 0含めて facts !! x == x!
deelist = 1 : 2 : map deefun [3 ..] -- x>0に関して d[x] = deelist !! pred x
deefun k = reg $ (facts !! k) - summ (zipWith mul (tail $ take (k-1) deelist) (reverse $ take k facts))
between f xs = zipWith f xs $ tail xs
お腹いっぱいなので、3つも生えてるユーザ解説はお残しで。