A - "atcoder".substr()
リスト処理の練習問題。
結果
abc264a :: Int -> Int -> String
abc264a l r = drop (pred l) $ take r "atcoder"
B - Nice Grid
シグネチャを決める。
abc264b :: Int -> Int -- R, C
-> Bool -- 黒ならTrue
図をぐっとにらむと「最も近い壁との距離が奇数なら黒」という規則で判別できそうだと思いつく。
結果
abc264b r c = odd $ minimum [r, c, 16 - r, 16 - c]
C - Matrix Reducing
シグネチャを決める。
abc264c :: Int -> Int -- H1, W1
-> [[Int]] -- Aijのリストのリスト
-> Int -> Int -- H2, W2
-> [[Int]] -- Bijのリストのリスト
-> Bool -- 答え
削除する行数、列数は必ず $H_1 - H_2, W_1 - W_2$ である。
1行目どうしを見比べて $W_1 - W_2$ 列消して一致する方法を調べたとして、一つもなかったとしても、1行目がそもそも捨てるべき行かもしれないので…と悩みだしそうになるが、問題の規模がたかだか10行10列までなので、最悪でも $({}_{10} C_5)^2 = 63504$ とおりを調べれば答えは見つかる。
${}_nC_k$ に相当する、$n$ 個のうち $k$ 個が False であるようなリストを全て作る。
comb n 0 = [replicate n True]
comb n k
| n < k = []
| otherwise = map (True :) (comb (pred n) k) ++
map (False :) (comb (pred n) (pred k))
このリストを使って、リストから False のところを除去する。
reduce bs xs = [x | (x, True) <- zip xs bs]
あとは、 ass から適当に除去したもので bss と一致するものがあるか探せばよい。
結果
abc264c h1 w1 ass h2 w2 bss =
any (bss ==)
[ map (reduce wcs) ass1
| hcs <- comb h1 (h1 - h2), let ass1 = reduce hcs ass
, wcs <- wcs0]
where
wcs0 = comb w1 (w1 - w2)
D - "redocta".swap(i,i+1)
シグネチャを決める。
abc264d :: String -- S
-> Int -- 答え
転倒数というやつなのだが、対象の文字列 "atcoder" はたかだか7文字で、文字の重複もないので、実際にやってみれば済むと思う。
0始まりで、列の $i$ 文字めにある文字を先頭に移動させるには $i$ 回の入れ替えが必要で、その結果、先頭から$i-1$文字は一つ後ろにずれる。以降は、先頭文字を無視して考えても同じである。
1つの文字について移動させ、交換回数と結果の文字列を返す
import Data.List
import Data.Maybe
step :: String -> Char -> (String, Int)
step s c = (delete c s, fromJust $ elemIndex c s)
これを前の文字から順に実施し、交換回数の和をとる。
結果
import Data.List
abc264d :: String -> Int
abc264d s = sum $ snd $ mapAccumL step s "atcoder"
step :: String -> Char -> (String, Int)
step s c = (delete c s, fromJust $ elemIndex c s)
E - Blackout 2
シグネチャを決める。
abc264e :: Int -> Int -> Int -- N,M,E
-> [(Int,Int)]] -- (Ui,Vi) のペアのリスト
-> Int -- Q
-> [(Int)] -- Xi のリスト
グラフの連結に関する問題なので、Union-Findが使えるか考えてみる。
Union-Findは切り離しが苦手だが、時計を逆戻しすれば、最終場面で切れていた電線が $X_Q, X_{Q-1}, \dots, X_1$ の順に繋がって、送電が回復していくように見える。
Union-Findには、それぞれの分割に対して任意の情報を付加できる版を用いて、都市の数 $cc :: Int$ と、発電所の有無 $pp :: Bool$ という二つの情報を貼り付ける。
まず、$X_i$ で指定されていない辺 $(Ui, Vi)$ を全てUnionする。
このとき都市の数は単純に足し合わせ、発電所の有無は論理和をとる。
こうして作った最終局面の全ての分割のうち、発電所のあるものについて都市の数の和をとるとそれが最後の答えである。
以降、$X_i$ の逆順に、以下の手順で送電される都市の増分を調べる。
（ただし $X_1$ については実は結果は使わない。）
$U_{X_i}$ と $V_{X_i}$ が同じ分割なら、答えは変化なし。
異なる分割である場合、まず$U_{X_i}$ の属する分割の情報 $(cc_1,b_1)$ と $V_{X_i}$ の属する分割の情報 $(cc_2,b_2)$ を得て、下の表のように送電される都市が増える。
| 真理値 | $b_2 = \top$ | $b_2 = \bot$ |
|---|---|---|
| $b_1 = \top$ | 変化なし | $+ cc_2$ |
| $b_1 = \bot$ | $+ cc_1$ | 変化なし |
答えを記録したら、Unionを実行する。
任意のペイロードが載せられるUnion-Findの手抜き実装を示す。
type UnionFind a = (Array Int (Either Int (Int, a)), a -> a -> a)
-- 配列要素は 親id または ランク(正の数),ペイロード のペア
-- 1からNまでのN要素が独立した初期状態を作る
-- ペイロードの統合関数も保持する
newUF :: (a -> a -> a) -> Int -> [a] -> UnionFind a
newUF f n as = (listArray (1, n) [Right (1, a) | a <- as], f)
-- 補助関数 ノードの根まで辿り、代表id, rank, ペイロードを返す
getRoot :: UnionFind a -> Int -> (Int, Int, a)
getRoot uf@(ar, _) i =
case ar ! i of
Left k -> getRoot uf k
Right (r, v) -> (i, r, v)
idof (i, _, _) = i
-- ふたつのノードが同じ分割に属しているか判定する
findUF :: UnionFind a -> Int -> Int -> Bool
findUF uf i j = idof (getRoot uf i) == idof (getRoot uf j)
-- ふたつのノードが同じ分割に属していることを登録する
uniteUF :: UnionFind a -> (Int, Int) -> UnionFind a
uniteUF uf@(ar, f) (i, j)
| a == b = uf
| otherwise =
case compare r s of
GT -> (ar // [(b, Left a), (a, Right (r, f p q))], f)
LT -> (ar // [(a, Left b), (b, Right (s, f p q))], f)
EQ -> (ar // [(a, Left b), (b, Right (succ s, f p q))], f)
where
(a, r, p) = getRoot uf i
(b, s, q) = getRoot uf j
-- 全てのペイロードを、代表idとペアにして返す
getCont :: UnionFind a -> [(Int, a)]
getCont (ar,_) = [(i,p) | (i, Right (_, p)) <- assocs ar]
得られた $X_i$ の系列を逆順に返せば終わりである。
結果(TLE)
import Data.Array
import Data.List
abc264e :: Int -> Int -> Int -> [(Int,Int)] -> Int -> [Int] -> [Int]
abc264e n m e uvs q xs = scanr (+) ansQ ccds
where
-- 先頭 N 個は都市、後半 M 個が発電所
uf0 = newUF ufF (n+m) (replicate n (1,False) ++ replicate m (0, True))
-- 電線の配列
uvA = listArray (1,e) uvs
-- 電線が切れないかチェック表
uvX = accumArray (&&) True (1,e) [(x,False) | x <- xs]
-- 切れない電線を配線する
uf1 = foldl' {-'-} uniteUF uf0 [uv | (uv,True) <- zip uvs (elems uvX)]
-- 最後まで通電している都市の数
ansQ = sum [cc | (_,(cc, True)) <- getCont uf1]
-- 逆順に Xi を繋いだufを作りつつ、都市数の増加を追跡
(_,ccds) = mapAccumR step uf1 (tail xs)
step uf xi
| a == b = (uf, 0)
| pp1 == pp2 = (uf1, 0)
| pp1 = (uf1, cc2)
| otherwise = (uf1, cc1) -- pp2 = True
where
uvx@(ux, vx) = uvA ! xi
(a, _, (cc1,pp1)) = getRoot uf ux
(b, _, (cc2,pp2)) = getRoot uf vx
uf1 = uniteUF uf uvx
ufF (cc1,pp1) (cc2,pp2) = (cc1 + cc2, pp1 || pp2)
-- UnionFindは上記
さすがにPure Arrayをこんな風に使って時間が間に合うわけもなかった。
Data.Vector.Mutable を使って、さらに getRoot のときには経路圧縮を行う版に差し替える。
本体も計算の順序を配慮する形に直す必要がある。
続き
nok0氏の解説
「発電所を区別する必要はないから、全て同じものとみなす」と「通電している都市の数は発電所の属する分割の要素数-1」でわかるから、Union-Findはペイロードの機能は不要（ただし分割の要素数が得られるもの）でよい。
なるほどその発想はなかった。やってみた。
Data.Array の代わりに定数時間で1か所の更新ができる Data.IntMap を使ってみた。経路圧縮がむしろ更新を増やして重くしていたようで、それを省略したらACできた。（！）
cirno3153氏の解説 に至っては、何を言っているのか全く理解できない orz...