- D : 累積和による積分
- F : 構文解析、木構造 面白かった。計算量で圧迫してくるのでない、珍しいスタイルの出題。
A - You should output ARC, though this is ABC.
シグネチャを決める。
abc255a :: Int -- R
-> Int -- C
-> [[Int]] -- Aij
-> Int -- 答え
ちゃんとするには (!!) でリストから要素を数えて取り出すが、たかだか2行2列なのでパターンマッチで全部書いても知れている。
結果
-- (!!)
abc255a r c ass = ass !! pred r !! pred c
-- pattern
abc255a 1 1 [[a,_],_] = a
abc255a 1 2 [[_,b],_] = b
abc255a 2 1 [_,[c,_]] = c
abc255a 2 2 [_,[_,d]] = d
B - Light It Up
シグネチャを決める。
abc255b :: Int -- N
-> Int -- K
-> [Int] -- Ai
-> [(Int,Int)] -- Xi,Yi
-> Double -- 答え
「灯りを持っていない人」それぞれに対して、その人に光が届く最小限の明るさを考える。それは、最も近くにいる「灯りを持っている人」との距離である。
全ての「灯りを持っていない人」に光が届くようにするには、その明るさの最大値をとればよい。
これを逆に、「灯りを持っている人」それぞれについて、最も近くにいる「持っていない人」との距離、すなわち「誰かを照らせる最小限の明るさ」の最大値とすると、それでは光が届かない人が出てくる。
何に関する最小値を調べるのか、何に関する最大値をとるのか、がややこしいので注意したい。
maximum [ minimum [距離 p q | q <- {-灯りを持っている人-}]
| p <- {-灯りを持っていない人-}]
あとは、一括で与えられている座標列を、灯りを持っている人のそれと持っていない人のとに分離する必要がある。filter を拡張した Data.List.partition はこの仕事にちょうどぴったりである。
(haves, nothaves) = partition (flip elem as . snd) $ zip xys [1..]
距離の計算で、毎回平方根を求める必要はなく、距離の二乗のままで計算して、最後に選んだ最大値にのみ平方根を計算すれば済む。こうすると、ほとんどの計算を整数のままで実行できるのも気分的によい。
結果
import Data.List
abc255b n k as xys = sqrt $ fromIntegral $ maximum
[minimum [dist2 p q | (q,_) <- haves] | (p,_) <- nothaves]
where
(haves, nothaves) = partition (flip elem as . snd) $ zip xys [1..]
dist2 (x1,y1) (x2,y2) = (x1-x2)^2 + (y1-y2)^2
蛇足
ところで、「灯りを持っている人」の中に「持っていない人」が紛れ込むのは当然まずいが、「灯りを持っていない人」の中に「持っている人」が紛れ込んだとしても、その人に灯りを届ける最小限の明るさは、自分自身との距離0になるだけで、結果には影響しない。
つまり、「持っている人」のリストさえ正確に作れれば、計算に多少無駄がでるがコーディングは手抜きできる。具体的にいうと partition のために Data.List をインポートしなくてよくなる。
abc255b n k as xys = sqrt $ fromIntegral $ maximum
[minimum [dist2 p q | q <- haves] | p <- xys]
where
haves = map ((xys !!) . pred) as
C - ±1 Operation 1
シグネチャを決める。手抜きする。
abc255c :: [Int] -- X,A,D,N
-> Int -- 答え
普通の数列、つまり公差 $D>0$ の場合で考える。
数列の途中に $X$ が $A_i \leq X < A_{i+1}$ と挟まれるとき、$X - A_i = (X-A) \bmod D = m$, $A_{i+1} - X = D - m$ で、この小さい方が答えである。
$D$ が負のときは、初項を第 $N$ 項に差し替えて符号を反転すればよい。
と素朴に正常系だけを考えていると、見落としている場合がいろいろある。
まず、$X$ が数列より外にいる場合、つまり（$D > 0$として） $X < A$ または $A + D(N-1) < X$ の場合である。
他に、$D=0$のとき、上の手順は0除算を起こす。
結果
abc255c [x,a,d,n] =
case compare d 0 of
EQ -> abs (x - a) -- D=0ならAiは全てA
GT -> sub x a an d n -- D>0
LT -> sub x an a (- d) n -- D<0のとき、逆向きにする
where
an = a + d * pred n
sub x a1 an d n -- D>0と正規化した問題だけを考える
| x < a1 = a1 - x -- 下に外れている
| an < x = x - an -- 上に外れている
| otherwise = min m (d - m) -- 囲まれている（正常系）
where
m = mod (x - a1) d
D - ±1 Operation 2
シグネチャを決める。
abc255d :: Int -- N
-> Int -- Q
-> [Int] -- Ai
-> [Int] -- Xi
-> [Int] -- 答え
数列 $A$ 自体は変化しない。
ひとつのクエリに対する答えは $F(X_i) = \sum | A_i - X_i |$ だが、これだけで $O(N)$、これをクエリの回数だけ繰り返すと全体で $O(NQ)$ は $4 \times 10^{10}$ になり間に合わない。
ひとつの項 $F_i(X_i) = |A_i - X_i|$ は、傾き-1と1な折れ線のグラフをなす。
全ての $A_i$ に関するこのグラフの重ね合わせが $F(X_i)$ のグラフになる。そのような関数を簡潔に表現したい。ここで、関数の微分としての累積和を導入する。
$F_i(X_i)$ は、切片 $F_i(0) = A_i$、傾きは $0 \leq X < Ai$ で傾き $-1$、$A_i \leq X$ で傾き $1$ である。ここで傾きとは次の項との差 $F_i(X_i+1) - F_i(X_i)$ のこととする。つまり切片に傾きを次々に足し合わせることでそれぞれの値が得られる。
| 切片 | 傾き＼X | 0 | ... | A1 | ... | A2 | ... | |
|---|---|---|---|---|---|---|---|---|
| F1 | A_1 | -1 | -1 | 1 | 1 | 1 | 1 | |
| F2 | A__2 | -1 | -1 | -1 | -1 | 1 | 1 | |
| ： | ： | ： | ： | ： | ： | ： | ： | |
| F | 〃 | 上 | の | 総 | 和 | 〃 | 〃 |
すると、この表を縦の向きに足し合わせると $F$ の切片と傾きが得られ、それを次々に足し合わせることで $F$ のそれぞれの値が得られる。
通常の累積和はこれを配列で計算するが、この問題では$A_i,X_i$の変域が広いので IntMap で扱う必要がある。
横軸0の初期値と全ての$A_i$の変化点について、その位置の値と傾きを求めておく。それは、傾きの初期値$-1$を0、各 $A_i$ に傾きの変化量 $+2$ を与えた表を足し合わせることで作られる。
これを使って、それぞれのクエリの答えを導く。
結果
import qualified Data.IntMap as IM
abc255d :: Int -> Int -> [Int] -> [Int] -> [Int]
abc255d n q as xs = map query xs
where
-- Fの切片
f0 = sum as
-- Fiの傾きの変化点を足し合わせ
ddf = IM.fromListWith f $ (0, -n) : [(a,2) | a <- as]
-- 初期値f0と初期傾き0から足し合わせを繰り返してF(Ai)とF'(Ai)を作る
fm = IM.fromAscList $ tail $ scanl add (0, (f0, 0)) $ IM.assocs ddf
add (x1, (fx1, dfx1)) (x2, ddfx2) = (x2, (fx1 + dfx1 * (x2 - x1), dfx1 + ddfx2))
-- xiに対するFの値を求める
query xi = f + d * (xi - x)
where
Just (x, (f,d)) = IM.lookupLE xi fm
E - Lucky Numbers
シグネチャを決める。
abc255e :: Int -- N
-> Int -- M
-> [Int] -- Si
-> [Int] -- Xi
-> Int -- 答え
数列 $A$ は $A_{i+1} = S_i - A_i$ という漸化式の関係にある。
これだと毎回符号が変わってややこしい。奇数番目と偶数番目に分けて考える、つまり2つ離れた間の漸化式を作ると
$A_{i+2} = S_{i+1} - A_{i+1} = S_{i+1} - (S_i - A_i) = (S_{i+1} - S_i) + A_i$
となり、
基準として $A_1$ を何らかの値に設定すると、奇数番目は$A_1$に対して$S$で決まるオフセットでずれた値になり、偶数番目は $A_2 = S_1 - A_1$ を基準としてオフセットされた位置にくる。
そして、$A_1$をいろいろ動かしたとき、$A$が$X$と一番重なるときの重なる個数が知りたい。
$A_1$を闇雲に動かす代わりに、いずれかの $A_i$ がいずれかの $X_j$ と重なるようにする。
そこを揃えたときに $A_1$ がいくつになるかを逆算し、「$A_1$をこの値にすると一つ重なりができる（具体的には $A_i$ が $X_j$ と一致する）」というカウントを行う。
このカウント値の最大値が答えである。
$A_i$ と $X_j$ を等しくする $A_1$ の求め方について。
- $A_1 = X_j$ とするには、$A_1 = X_j$
- $A_2 = S_1 - A_1 = X_j$ とするには、$A_1 = S_1 - X_j$
- $A_3=S_2-A_2=S_2-(S_1-A_1)=(S_2-S_1)+A_1=X_j$ とするには、$A_1=X_j-(S_2-S_1)$
- $A_4=S_3-A_3=S_3-((S_2-S_1)+A_1)=(S_3-(S_2-S_1))-A_1=X_j$ とするには、$A_1=(S_3-(S_2-S_1))-X_j$
- $A_5=S_4-A_4=S_4-((S_3-(S_2-S_1))-A_1)=(S_4-(S_3-(S_2-S_1)))+A_1=X_j$ とするには、$A_1=X_j-(S_4-(S_3-(S_2-S_1)))$
- …
この繰り返しをにらむと、$S_i$ の累積ならぬ次々に引いた値
$T_0 = 0$
$T_i = S_i - T_{i-1}$
を使って、
- $A_1$ : $A_1 = X_j - T_0$
- $A_2$ : $A_1 = T_1 - X_j$
- $A_3$ : $A_1 = X_j - T_2$
- $A_4$ : $A_1 = T_3 - X_j$
- $A_5$ : $A_1 = X_j - T_4$
と、引く向きを交互に変えることで表せるとわかる。
結果
import qualified Data.IntMap as IM
abc255e :: Int -> Int -> [Int] -> [Int] -> Int
abc255e n m ss xs = maximum $ IM.elems pm
where
ts = scanl subtract 0 ss
pm = IM.fromListWith (+)
[ (f $ xj - ti, 1)
| (ti, f) <- zip ts (cycle [id, negate])
, xj <- xs]
F - Pre-order and In-order
シグネチャを決める。
答えは、表示するべき内容をそのまま反映したようなものにする。
出力例1は [[3,6],[0,0],[0,5],[0,0],[0,0],[4,2]]
出力例2（木が存在しない場合）は [[-1]] とする。
abc255f :: Int -- N
-> [Int] -- Pi
-> [Int] -- Ii
-> [[Int]] -- 答え
preorderのノード番号列を読み込んで木を構成するパーサを作ればよい。
ただし、次に続くノード番号が、左の子、右の子、あるいは無関係のものかは判別がつかない。
これを、inorderの列を使って判定する。
inorderの列は、木のノードを、その位置関係に基づいて、重なりがないように左から右に並べたものになっている。
ある部分木を取りだそうとしたとき、その木のノードが存在する左の限界と右の限界が決まる。
今着目しているノードがその範囲に収まっていれば正しく、さもなくばそこには木はないとわかる。
さらに子を探しにいくときは、自分の位置が新たな境界を定義する。
例えば入力例1
6
1 3 5 6 4 2
3 5 1 4 6 2
について、最初の1は全体の根ノードなので範囲の制限はない。つまり、左は（1始まりで）0より大きく、右は7未満であればよい。
inorderの方をみて、1は位置3にあるのでこの範囲内である。
1の左の部分木は、0より大きく、3より小さい範囲にあるはずである。そのことを意識して3に進む。
3の左の部分木は、3が位置1なので、0より大きく1より小さい範囲にあるはずである。そのことを意識して5に進む。
5はこの範囲にないのでここには木がない。戻る。
3の右の部分木は、1より大きく3より小さい範囲にあるはずである。そのことを意識して5に進む。
5はこの範囲にある。
次の6は、5の部分木の範囲にはないので、1まで戻り、1の右の部分木を調べるステップに進む。…
このように、inorderは、ノード番号からその位置を取り出すための逆引き表にして利用する。
preorderはパーサの入力になり、パーサは、受理した結果と、残りの入力列を返す。
木の受理が終わったとき、入力列が残っていたら失敗、全てちょうど消費でき、かつ根のノード番号が1のとき成功となる。
結果
せっかくなので、二分木を実際に構成するパーサと、その木を答えの形に変形する後処理に分けて実装してみる。
import Data.Array
data Tree = Leaf | Node Int Tree Tree
deriving Eq
getVal (Node x _ _) = x
getVal Leaf = 0
abc255f :: Int -> [Int] -> [Int] -> [[Int]]
abc255f n ps is
| null rest, getVal tree == 1 = ans -- 成功
| otherwise = [[-1]] -- 失敗
where
-- ノード番号からinorderの位置
ia = array (1,n) $ zip is [1..]
-- 木を受理
(tree, rest) = parse ps 0 (succ n)
-- パーサ
parse :: [Int] -- 入力
-> Int -- 下限
-> Int -- 上限
-> (Tree, [Int]) -- 結果の木と、残りの入力列
parse pps@(p:ps) lb ub
| i <= lb || ub <= i = (Leaf, pps) -- 消費しない
| otherwise = (Node p left right, ps2) -- 木を受理した
where
i = ia ! p -- pの位置
(left, ps1) = parse ps lb i -- 左の部分木をパース
(right,ps2) = parse ps1 i ub -- 右の部分木
parse [] _ _ = (Leaf, [])
-- 木から、ノード番号ごとに左と右のノード番号のリストを抽出
ans = elems $ array (1,n) $ traverse tree []
traverse (Node x l r) rest = traverse l $ traverse r $ (x, [getVal l, getVal r]) : rest
traverse Leaf rest = rest