A - Water Station
シグネチャを決める。
abc305a :: Int -- N
-> Int -- 答え
$N$ を5で割った余りが0,1,2なら、通り過ぎた手前の給水所が近い。
3,4なら、その先にある給水所の方が近い。
結果
abc305a n
| r < 3 = n - r
| otherwise = n - r + 5
where
r = mod n 5
公式解説は「浮動小数点演算で5で割って、四捨五入で整数に丸めて、5倍すればよい」と。
整数で済むことに浮動小数点演算を持ち出すのに抵抗のある世代なのですみません。
公式解説の解法2「全ての地点からの距離を数えて最小のものを選べ」
abc305a n = snd $ minimum [(abs (n - k), k) | k <- [0,5..100]]
答えは出るけど、回り道にもほどがある。
B - ABCDEFG
シグネチャを決める。
abc305b :: Char -- p
-> Char -- q
-> Int -- 答え
やり方1
地点の名前に対して、A地点からその地点までの総距離を持つ対応付けリストを作る。
p2d = zip ['A'..] $ scanl (+) 0 [3,1,4,1,5,9]
これをpとqで検索して、結果の差が距離。
abc305b p q = abs (x - y)
where
Just x = lookup p p2d
Just y = lookup q p2d
やり方2
地点の名前に対して、ひとつ左からその地点までの距離を持つ対応付けリストを作る。
p2s = zip ['B'..] [3,1,4,1,5,9]
これの、pとqの間にあるものの総和をとればよい。
abc305b p q = sum [x | (r,s) <- p2s, min p q < r, r <= max p q]
公式
「楽な実装方法」のアイデアに脱帽。
import Data.List
abc305b :: Char -> Char -> Int
abc305b p q = abs (x - y)
where
s = "A..BC...DE....F........G"
Just x = elemIndex p s
Just y = elemIndex q s
C - Snuke the Cookie Picker
シグネチャを決める。
abc305c :: Int -- H
-> Int -- W
-> [String] -- Sij
-> (Int,Int) -- 答え
abc305c h w css = ...
クッキーは少なくとも2行2列はあるので、端であったとしても必ず見つけられる問題設定になっている。
ようは、非公開な $a,b,c,d$ を推測して、その範囲なのに # でないマスを見つけることが任務。
行ごとにクッキーの枚数を数える。ただし、0枚な行は無視する。
そうすると、$d - c + 1$枚が手つかずな多数派の行と、一枚たらない1行に分かれる。
kicss = [(k,i,cs) | (i,cs) <- zip [1..] css, let k = count cs, k > 0]
count = length . filter ('#' ==)
kの最小値を持つ行がつまみ食いされている。その行と、どれでもいいのでそうでない行の内容を取り出す。
kmin = minimum [k | (k,_,_) <- kicss]
(_,i,cs1) = head [kics | kics@(k,_,_) <- kicss, k == kmin]
(_,_,cs2) = head [kics | kics@(k,_,_) <- kicss, k /= kmin]
同じ位置の文字どうしを見比べて、前者が . で後者が # な位置が答えの後半。
j = head [j | (j,'.','#') <- zip3 [1..] cs1 cs2]
結果
import Data.List
abc305c :: Int -> Int -> [String] -> (Int,Int)
abc305c h w css = (i, j)
where
kicss = [(k,i,cs) | (i,cs) <- zip [1..] css, let k = count cs, k > 0]
kmin = minimum [k | (k,_,_) <- kicss]
(_,i,cs1) = head [kics | kics@(k,_,_) <- kicss, k == kmin]
(_,_,cs2) = head [kics | kics@(k,_,_) <- kicss, k /= kmin]
j = head [j | (j,'.','#') <- zip3 [1..] cs1 cs2]
count = length . filter ('#' ==)
ユーザ解説 by pointN の方法
なるほどこれは気づかなかった。
（むしろ、そういうローカルな方法では、目標が端の場合に誤答すると思い込んでいた。）
つまみ食いのない状態では、
- クッキーの周囲4近傍のクッキーの枚数は2（角）から4
- 空きマスの周囲4近傍のクッキーの枚数は0から1
つまみ食いが一ヵ所あるとき、
- 空きマスの周囲4近傍のクッキーの枚数が1だったマスが、0になることがある
- 1のままのこともある
- 空きマスの周囲4近傍のクッキーの枚数が0だったマスは、変化しない
- つまみ食いしたマスは、元々クッキーがあったマスなので、周囲4近傍のクッキーの枚数は2から4
なので、最後の条件に該当するマスを見つければよい！
いつものような accumArray の使い方をするとこう。
import Data.Array
abc305c :: Int -> Int -> [String] -> (Int,Int)
abc305c h w css = ans
where
-- # を見つけるたびに、周囲4近傍を1増やす
counts = accumArray (+) 0 ((1,1),(h,w))
[ (xy, 1)
| (i,cs) <- zip [1..] css
, (j,'#') <- zip [1..] cs
, xy <- [(pred i, j) | 1 < i] ++ [(succ i, j) | i < h] ++
[(i, pred j) | 1 < j] ++ [(i, succ j) | j < w]
]
ans = head [xy | ((xy, c), '.') <- zip (assocs counts) (concat css), c >= 2]
もっと普通にやるならこう。
import Data.Array
abc305c :: Int -> Int -> [String] -> (Int,Int)
abc305c h w css = ans
where
arr = listArray ((1,1),(h,w)) $ concat css
-- . の周囲4近傍の # の個数を数える
ans = head
[ (i,j)
| (i, cs) <- zip [1..] css
, (j, '.') <- zip [1..] cs
, let xys = [(pred i, j) | 1 < i] ++ [(succ i, j) | i < h] ++
[(i, pred j) | 1 < j] ++ [(i, succ j) | j < w]
, 2 <= sum [1 | xy <- xys, arr ! xy == '#']
]
D - Sleep Log
A quick fox jumps over the ...じゃなかった。
シグネチャを決める。
abc305d :: Int -- N
-> [Int] -- Ai
-> Int -- Q
-> [(Int,Int)] -- li, ri
-> [Int] -- 答え
abc305d n as q lrs = ...
時刻0から時刻 $t$ までの睡眠時間を求める関数 $f(t)$ を作り、$f(r_i) - f(l_i)$ でそれぞれの答えが得られる。
$N$が大きいので、単純に区間を IntMap などに入れて、範囲内の時間を足し合わせていると間に合わない。
それでも、$l_i, r_i$ がどの区間の間なのかを知ることは必要にならないはずがないので、時刻 $A_i$ をキー、番号 $i$ を値とする IntMap を作る。
am = IM.fromAscList $ zip as [1..]
時刻 t に対して lookupLE t am の結果が Just (a,k) であったとする。
k が奇数ならば、今は起きている時間で、寝ていた時間は $A_k$ までの睡眠時間の総和。
k が偶数ならば、今は寝ている時間で、寝ていた時間は、$A_k$ までの睡眠時間の総和に加えて、今の区間の $a - t$ も寝ている。
つまり、それぞれの添え字 k に対して、時刻 $A_k$ までの睡眠時間の総和が必要である。
それは、区間の睡眠時間 $A_{2i+1} - A_{2i}$ の累積和で得られる。
sa = listArray (1,n) $ loop 0 (tail as)
loop acc (a0:a1:as) = acc : acc1 : loop acc1 as
where
acc1 = acc + a1 - a0
loop acc [an] = [acc]
結果
import qualified Data.IntMap as IM
import Data.Array
abc305d :: Int -> [Int] -> Int -> [(Int,Int)] -> [Int]
abc305d n as q lrs = [f r - f l | (l, r) <- lrs]
where
am = IM.fromAscList $ zip as [1..]
sa = listArray (1,n) $ loop 0 (tail as)
f t
| odd k = sa ! k
| True = sa ! k + t - ak
where
Just (ak, k) = IM.lookupLE t am
loop acc (a0:a1:as) = acc : acc1 : loop acc1 as
where
acc1 = acc + a1 - a0
loop acc [an] = [acc]
E - Art Gallery on Graph
シグネチャを決める。
abc305e :: Int -- N
-> Int -- M
-> Int -- K
-> [(Int,Int)] -- ai, bi
-> [(Int,Int)] -- pi, hi
-> [Int] -- 答え
定義通りに考えると、全ての頂点から全ての（警備員のいる）頂点への距離が必要で、計算量が多すぎる。
向きを変えて、警備員 $i$ は距離 $h_i$ 先の頂点まで警備できる、と考えて、それぞれの目の届く範囲を幅優先探索で塗ることにしても、一人につき $O(N)$ になってしまい、間に合わない。
警備員は、スタート地点 $p_i$ では体力 $h_i$ で警備する。そこから距離 $d \geq h_i$ 離れた頂点については、体力が減衰して $h_i - d$ で警備する。これが0になるまでさらに遠くまで影響を及ぼせる。
ある頂点に二人の警備員の監視が届いているとする。それぞれの残り警備力が $K_i, K_j$ であるとき、警備員 $i$ はそこからさらに距離 $K_i$ の頂点まで警備でき、$j$ は $K_j$ までである。この「残りの」影響範囲は $i,j$ の出発点とは無関係に決まるので、大きい方だけ考えればよい。
よって、それぞれの頂点に関して、監視している警備員の最大の警備力を求めることを考える。ある頂点について、最大警備力が $K$ と判明したとき、その隣接頂点は警備力 $K-1$ で警備される可能性がある。
これを無駄なく求めるには、警備力の大きい順に警備する頂点を持つ優先度付きキューを使えばよい。最初は、警備員の配備される位置を入れておく。警備力の大きいものから、それが警備する頂点の警備力を確定させ、さらに、隣接頂点に1少ない警備力で警備する可能性をキューに入れる。
既に警備されている頂点がキューの後方で再度出現するとき、警備力はそれ以下に決まっているので無視できる。
結果
immutable に実装するため、結果は IntSet に保存する。
（mutable arrayでもやってみたが、実行時間は大差なかった。）
IntMap で頂点の暫定警備力を記録しておく必要がある気がしたが、優先度付きキューで警備力の大きい順に考えるので、その必要はなかった。
優先度付きキューは Data.Heap である。
（これを「ヒープ」と呼ぶのは微妙な気がするが。）
警備力の大きい順にするため、体力の符号をマイナスにしている。
import qualified Data.IntSet as IS
import qualified Data.Heap as H
abc305e :: Int -> Int -> Int -> [(Int,Int)] -> [(Int,Int)] -> [Int]
abc305e n m k abs phs = IS.elems ans
where
q0 = H.fromList [H.Entry (-h) p | (p,h) <- phs]
ans = loop IS.empty q0
-- いつものグラフ
g = accumArray (flip (:)) [] (1,n)
[p | (a,b) <- abs, p <- [(a,b),(b,a)]]
loop is q
| H.null q = is -- キューが空なら完了
| IS.member p is = loop is q1 -- 警備済みの頂点ならスルー
| h == 0 = loop is1 q1 -- 警備力がちょうど0なら波及せずここで止まる
| otherwise = loop is1 q2 -- 警備力 > 0 なら、隣接頂点に波及する
where
Just (H.Entry h p, q1) = H.uncons q
is1 = IS.insert p is
-- pに隣接して、警備が未到達な頂点への警備をキューに登録
is2 = H.union q1 $
H.fromList [H.Entry (succ h) q | q <- g ! p, IS.notMember q is1]
「警備済みとか気にせず全ての隣接頂点をキューにとりあえず入れて、キューから取り出したときに採用不採用を判断」する、最後のガードを無くした形でも答えは同じになるが、Heap の操作回数がかなり多くなる。IntSet への問い合わせ回数を支払ってでも Heap の操作回数を減らす方が実行時間は稼げる。
F - Dungeon Explore
なんでかこんな上のレベルでインタラクティブ問題が来た。
得られる情報からは、
- 現在の頂点から、頂点 N に移動できるならそうする。
- そうでないとき、まだ訪問していない、最も近い頂点に向けて移動する
と動くくらいしかできることはなくて、木の形をしたイジワルな迷路でも、たぶん $2N$ までにはゴールできそうで、ループがあればもっとショートカットできてもっと歩数は節約できるだろう。
（ちゃんとした証明は公式解説にある）
頂点もたかだか100個なので、「最寄りの未到達な頂点への経路を探す」を効率的にする必要もない。
頂点に接続している辺の本数に上限が付いていたりすると、隣までは行ったことのある頂点について全ての辺が判明して、行ってみる必要がなくなったりする、とかもありそうだが、そういうこともないので、問題文での辺の本数 $M$ への言及は目くらまし。「グラフは連結かつ単純」がそれ以上のことを言っている。
結果
頂点番号に対して、隣接頂点リストを配列に持つ。
Nも小さいし計算量は気にしなくていいので、immutable arrayでやってしまう。
これが空リストなとき、その頂点は未到達という意味。
ジャッジから得られた隣接頂点リストで常に情報を更新し、
その中にNが含まれていればそこに移動し、
なければ、幅優先探索で、未到達な頂点を探すが、このとき欲しいのは「その未到達な頂点に行くための最初の一歩はどこか」なことに注意。
G - Banned Substrings
公式解説
1 文字ずつ文字を伸ばしていくことを考えると、末尾のたかだか L=6 文字を状態としてもつ DP を考えることができます。 この DP を行列累乗を使って高速化することでこの問題を解くことができます。
部分的にしか言っていることがわからない…