A - Approximation
シグネチャを決める。
abc407a :: Int -- A
-> Int -- B
-> Int -- 答え
$A \div B = q \dots r$ とする。つまり $\displaystyle \frac{A}{B} = q + \frac{r}{B}$ である。
$B$が奇数であることに注意して、$\displaystyle \frac{r}{B} < \frac{1}{2}$ なら答えは $q$ さもなくば $q + 1$ となる。
条件式は $2r < B$ と変形できる。
結果
abc407a a b
| r + r < b = q
| otherwise = succ q
where
(q, r) = divMod a b
B - P(X or Y)
シグネチャを決める。
abc407b :: Int -- X
-> Int -- Y
-> Double -- 答え
$6 \times 6 = 36$ 通りの全ての場合について調べ、条件を満たすものを数える。場合の数で割れば答え。
結果
abc407b x y = fromIntegral c / 36
where
c = length [() | a <- [1 .. 6], b <- [1 .. 6], x <= a + b || y <= abs (a - b)]
C - Security 2
シグネチャを決める。長いので ByteString で受け取る。
import qualified Data.ByteString.Char8 as BS
import Data.Char
abc407c :: BS.ByteString -- S
-> Int -- 答え
自分の解法
$S$ の $i$ 文字めの数字を $D[i]$ とする。$S$ の長さを $N$ とする。
自分の操作は「Aを押して0を出す、Bを何回か押してそれをどれかの数字にする」の繰り返しになる。
$i$ 文字めについて、Bを押す回数を $R[i]$ とする。
この数字はさらに後続のBの押下により、さらに変化する。最終結果は $\displaystyle D[i] \equiv \sum_{k=i}^N R[k] \bmod 10$ になる。
もう少し平たく書くと
$D[i] \equiv R[i] + R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 次の項は
$D[i+1] \equiv R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 辺々引いて
$D[i] - D[i+1] \equiv R[i] \bmod 10$
「次の数字との差だけ回せばヨシ」で、末尾まで考える必要がなくなってしまった。不思議。
Aを押す回数も加えて $\sum (1 + R[i])$ の和が答え。
zipWith を使うと $D[N]$ を数え忘れるので補正する。
abc407c s = (dN +) $ sum $ between op $ map digitToInt $ BS.unpack s
where
op a b = succ $ mod (a - b) 10
dN = succ $ digitToInt $ BS.last s
between :: (a->a->b) -> [a] -> [b]
between f xs = zipWith f xs $ tail xs
フレンズさんのヒント版
時計を逆回しにして数えるとき「ボタンBが何回押されたか」はつまり $\sum_{k=i}^N R[i]$ で、これを $S[i]$ と置いて上の式
$D[i] \equiv R[i] + R[i+1] + R[i+2] + \dots + R[N] \bmod 10$ 置き換えて
$D[i] \equiv R[i] + S[i+1] \bmod 10$ 移項して
$R[i] \equiv D[i] - S[i+1] \bmod 10$ これを使って
$S[i] \equiv R[i] + S[i+1] \bmod 10$ を繰り返せと言っている。
abc407c bs = sum $ snd $ mapAccumL step 0 [n1, pred n1 .. 0]
where
n1 = pred $ BS.length bs
step s1 i = (s, succ r)
where -- s1 = S[i+1]
d = digitToInt $ BS.index bs i -- D[i]
r = mod (d - s1) 10 -- R[i] ≡ D[i] - S[i+1] mod 10
s = mod (r + s1) 10 -- S[i] ≡ R[i] + S[i+1] mod 10
D - Domino Covering XOR
シグネチャを決める。
abc407d :: Int -- H
-> Int -- W
-> [[Int]] -- Aij
-> Int -- 答え
$H, W \leq 20$ と思い込んで諦めてしまったが、実は $HW \leq 20$ というごく小規模の話で、総当たりをするだけだった。
(1,1) から (H,W) まで順にマスを見て、
- ドミノが既に置かれていたら何もできないので続きの結果をそのまま返す
- ドミノを置かれていないとき、以下の3通りの場合を計算して、最終結果の最大値を返す
- 置かずに、その数を使う
- 横に置く（右端でないとき）（右隣のマスもドミノが塞いでいないとき）
- 縦に置く（下端でないとき）
という深さ優先探索を実装する。
結果
マスはたかだか20個なので、immutable arrayで書く。
import Data.Array.Unboxed
import Data.Bits
abc407d :: Int -> Int -> [[Int]] -> Int
abc407d h w ass = dfs 0 f0 $ range ((1,1),(h,w))
where
f0 = listArray ((1,1),(h,w)) $ repeat False :: UArray (Int,Int) Bool -- ドミノが置かれているかフラグ配列の初期値
a = listArray ((1,1),(h,w)) $ concat ass :: UArray (Int,Int) Int
dfs acc _f [] = acc
dfs acc f (ij@(i,j):ijs)
| f ! ij = dfs acc f ijs
| otherwise = maximum $
[dfs ac1 f ijs | let !ac1 = xor acc $ a ! ij] ++
[dfs acc f1 ijs | j < w, let ij1 = (i, succ j), not $ f ! ij1, let f1 = f // [(ij,True), (ij1,True)]] ++
[dfs acc f2 ijs | i < h, let f2 = f // [(ij,True), ((succ i,j),True)]]
E - Most Valuable Parentheses
シグネチャを決める。テストケース一つ分の計算を考える。
abc407e :: Int -- N
-> [Int] -- Ai
-> Int -- 答え
ハマった
前から順にDPして、位置 $i$ に対して
- 開き括弧の開いている数 $p$ $(0 \leq p, p \leq i, p \leq 2N - i)$ をキー
- $p$ で達成できる総和の最大値を値
という表を更新していけば答えが得られる。
しかし $i = N$ のとき $p \leq N$ で、$O(N^2)$ になって計算量が大きすぎる。
ヒントから
～「2個追加して1個丸をつける」を貪欲にやっていけばいいのだ。プライオリティキューでできるのだ！
正しい括弧列の性質から、どの位置でも、閉じていない開き括弧の個数が0以上である必要がある。
そして問題の性質として、開き括弧でない位置は閉じ括弧になる。（開きの数が減る）
つまり、先頭から任意の位置までの区間で、半数以上が開きである必要がある。
ここからがアイデアで、この条件を満たすことを先頭から考えると、
- 先頭は必ず開き
- 次から、2文字追加するごとに、開きと指定していなかった1文字を開きに指定する
これは、新規の2文字でなく、これまでの中から自由に選んでよい
このとき、問題の目標を達成するためには、選べる候補のうちで最大の値をもつマスを選べばよい。
つまり優先度付きキューに溜め込んでおけばよい。
結果
大きい方を優先するために、全てを符号反転して扱う。
import qualified Data.Heap as PQ
import Data.List.Split
import Data.Tuple
import Data.Maybe
abc407e :: Int -> [Int] -> Int
abc407e _n (a:as) = (a -) $ sum $ snd $ mapAccumL step PQ.empty $ chunksOf 2 $ map negate as
where
step pq [a1] = (PQ.insert a1 pq, 0) -- 実際には何もしない
step pq [a1, a2] = swap $ fromJust $ PQ.uncons $ PQ.insert a1 $ PQ.insert a2 pq
F - Sums of Sliding Window Maximum
シグネチャを決める。
abc407f :: Int -- N
-> [Int] -- Ai
-> [Int] -- 答え
abc407f n as = ...
where
ぜんぜんわからないのでヒントをもらう。
話が複数段階あるのが難しかった理由かな。
ステップ1
長さ1の連続部分列はN個、長さ2は$N-1$個、…、長さNは1個ある。
これらに対して、各 $A_i$ がその部分列の最大値であるような場合がいくつあるかを知りたい。
$A_i$ の大きい方から順に考えて、
$i$ より左と $i$ より右に、未使用な値（つまり $A_i$ 以下の値）がいくつあるかを数える。
左右がその範囲に収まる部分列全てについて、最大値は $A_i$ となる。
という区間を調べるために、「使用済みな整数の集合」を状態にしてループする。
番兵として0と$N+1$を最初から入れておく。
import qualified Data.IntSet as IS
import Data.Function
(_, alrs) = mapAccumL step is0 $ sortBy (flip compare `on` fst) $ zip as [1 ..]
is0 = IS.fromList [0, succ n]
step is (ai, i) = (IS.insert i is, (ai, i - l, r - i))
where
Just l = IS.lookupLT i is
Just r = IS.lookupGT i is
alrs は $A_i$ の大きい順に、$A_i$ の値、位置 $i$ の左右で未使用な値の個数、の3項組のリスト。
ステップ2
長さkを気にしないとき、alrs の要素 $(a,l,r)$ について、$a$ を最大値とする部分列の個数は $(l+1)(r+1)$ である。
長さを考慮するとき、$(0,0),(l,0),(0,r),(l,r)$ を頂点とする長方形の内部の格子点について、
$x + y = k - 1$ という直線が通過する個数が部分列の個数になる。
一般性を損なわずに $l \leq r$ と仮定して、この値は $k=0$ から順に
これは $1, 2, 3, \dots, l, l+1, l+1, \dots, l+1, l, l-1, \dots, 1$ という長さ $l + r + 1$ の列となり、
以降は0になる。
これをkごとに足し合わせれば答えになるはず。
import Data.Array.Unboxed
abc407f n as = elems arr
where
...
arr :: UArray Int Int
arr = accumArray (+) 0 (1, n)
[ (k, a * m)
| (a, l, r) <- alrs, let ll = min l r, let rr = max l r, let l1 = succ ll
, (k, m) <- zip [1 ..] $ [1 .. ll] ++ replicate (succ rr - ll) l1 ++ [ll, pred ll .. 1]
]
しかしこれでは TLEx5 になる。$O(N^2)$ の演算をしているので当然。
ステップ3
ステップ2で、$N$ 個の台形状の数列を作り、要素ごとに足し合わせた。
個々に作る代わりに、全てを足し合わせた数列を一度に作るために、累積和による積分を行う。
つまり、ひとつの台形数列
$0, 1, 2, \dots, l, l+1, \dots, l+1, l, \dots, 1, 0, 0, \dots$ は前後の差分をとると
$1, 1, 1, \dots, 1, 0, \dots, 0, -1, -1, \dots, -1, 0, 0, \dots$ となり、もう一度すると
$1, 0, \dots, 0, -1, 0, \dots, 0, -1, 0, \dots, 0, 1, 0, \dots$ となる。
この2階差分を全ての台形について足し合わせてから、2度累積和を行うと、全体を足し合わせた数列が$O(3N)$で求められる。
abc407f n as = tail $ scanl' (+) 0 $ tail $ scanl' (+) 0 $ elems arr
where
...
arr :: UArray Int Int
arr = accumArray (+) 0 (0, pred n) $ concatMap alr2e alrs
alr2e (a, l, r) = [(i,b) | (i,b) <- [(0,a),(l,-a),(r,-a),(l + r,a)], inRange (0, pred n) i]
ヒントには
遅延セグ木でできるのだ！ 工夫すればimos法でもできるのだ
とあったが、後者しか思いつかなかった。
G - Domino Covering SUM
D問題より100倍広く、その代わりにXORではなく和をとる。
いずれかの幅がある程度制限されていれば、ドミノで埋まっているマスのパターンごとの最大値を持ってDPできるが、この問題では制約がないので最大で $44 \times 45$ マスになり、計算量が爆発する。
アライグマ「G問題はフローなのだ！
マスを頂点、隣接するマスの間に重みAij+Ai'j'の辺を張ったグラフで、最小重みマッチングを求めれば良いのだ。
全部の辺の重みに定数Mを足して重みを0以上にしてから最小費用流を求めれば、min_k(流量kの最小費用-kM)で求まるのだ！」
蟻本に最小費用流の項があるのは確認した。