A - 22222
ワンライナー。
main = getLine >>= putStrLn . filter ('2' ==)
B - cat
- 比較関数を指定して整列するには
Data.List.sortBy - 特定の前処理をしてから
compareするにはData.Funciton.on
ワンライナーに毛が生えた程度。
import Control.Monad
import Data.List
import Data.Function
main = do
n <- readLn
ss <- replicateM n getLine
putStrLn $ concat $ sortBy (compare `on` length) ss
C - Debug
例の2でわかるように、一度置き換えをすると、連鎖してその前の部分を再検討する必要が生じる。
そこで、普通に前から見る代わりに後ろから処理することで、手戻りの必要がなくなる。
結果
main = getLine >>= putStrLn . foldr step ""
step 'W' ('A':xs) = 'A':'C':xs
step x xs = x:xs
計算量
アライグマ「C問題は、WAをACに変えたあと、その1個前からもう一回調べ直すことにすればいいのだ！ 戻る回数はWAを消す回数だから全部でO(N)回で、O(N)時間になってるのだ！」
「もう一度調べ直す」ということは前から処理するつもりでいて、引き返した距離をまた無駄に歩いて行くと、$O(N^2)$ になる気がする。
引き返しが始まったとき、「引き返しが終わったらどこから再開するか」を覚えておいて、そこまで飛んで続きをするなら $O(N)$ で合ってる。
なんにせよ、命令的な手順は複雑だ。
D - Colorful Bracket Sequence
シグネチャを決める。
abc394d :: String -- S
-> Bool -- 答え
- 開き括弧を見たらスタックに積む。
- 閉じ括弧を見たら、最新の開き括弧が対応するものかをスタックと突き合わせて調べ、正しいならスタックから除去して続ける。
スタックに開き括弧を積むと、対応する閉じ括弧をいちいち考える必要があるが、閉じ括弧の方を積めば、等しいかどうかで判別できる。
結果
abc394d = iter ""
iter ys ('<':xs) = iter ('>':ys) xs
iter ys ('[':xs) = iter (']':ys) xs
iter ys ('(':xs) = iter (')':ys) xs
iter (y:ys) (x:xs) = x == y && iter ys xs
iter ys "" = null ys
iter "" xs = False
問題文について
ちょっと書きぶりがたどたどしすぎる気が。
「括弧の対応が取れている」を厳密に書こうとした努力は認めるけど。
そうでないとき、削除された前後の文字列を 1 つに連結し、新たに T とする。
は、)))[]((( を ))) と ((( にしてから ((())) とすることも許されるように読めるし。
（『連結し』で、順序を変えてはいけないとは言っていない）
E - Palindromic Shortest Path
シグネチャを決める。
abc394e :: Int -- N
-> [String] -- Cij
-> [[Int]] -- 答え
元のグラフの二つの頂点の組に対応する $N^2$ 個の頂点 $(u,v) ; (1 \leq u, v \leq N)$ と、
元のグラフで文字 $c$ により遷移する $p \xrightarrow{c} i, \ j \xrightarrow{c} q$ （向きに注意）に対して
$(i,j) \to (p,q)$ という有向辺を持つ大きなグラフを考える。
大きなグラフの頂点 $(u,u)$ は、$u$ から $u$ が長さ0の回文で移動できることから、距離コスト0とする。
文字 $c$ により遷移する $u \xrightarrow{c} v \ (u \neq v)$ な $(u,v)$ は、$u$ から $v$ が長さ1の回文で移動できることから、距離コスト1とする。
ある頂点 $(u,v)$ が距離コスト0の頂点から $(i,i) \xrightarrow{a}\xrightarrow{b}\xrightarrow{c} (u,v)$ という関係にあるとき、元のグラフでは $u$ から $v$ は $cbaabc$ という回文で移動できる。
ある頂点 $(u,v)$ が 距離コスト1の $i \xrightarrow{x} j$ な頂点 $(i,j)$ から $(i,j) \xrightarrow{a}\xrightarrow{b}\xrightarrow{c} (u,v)$ という関係にあるとき、元のグラフでは $u$ から $v$ は $cbaxabc$ という回文で移動できる。
つまり、大きいグラフの有向辺は距離コストを2増やすとして、各頂点の最小の距離コストを求めればよい。
結果
after_contest が2つ追加されている。
おそらく、大きなグラフのほぼ全てのマスに同じ文字が入ったものと想像する。
そのような入力に対して、大きいグラフの辺をまじめに計算すると $O(N^4)$ になり爆発するので、必要なときに計算する構造にする。
Data.Map を使った、見通しのよいimmutableな実装は次のようになる。
after_contest は通らないが、それを除けば 641msでACしている。
import Data.Array
import qualified Data.Sequence as Q
import qualified Data.Map as M
abc394e :: Int -> [String] -> [[Int]]
abc394e n css = [[M.findWithDefault (-1) (i,j) mZ | j <- [1 .. n]] | i <- [1 .. n]]
where
-- u -[c]-> v となるvをu,cごとに集める
fwd = accumArray (flip (:)) [] ((1,'a'),(n,'z')) [((u,c), v) | (u,cs) <- zip [1 ..] css, (v,c) <- zip [1 ..] cs, c /= '-']
-- uをv,cごとに集める
rev = accumArray (flip (:)) [] ((1,'a'),(n,'z')) [((v,c), u) | (u,cs) <- zip [1 ..] css, (v,c) <- zip [1 ..] cs, c /= '-']
-- N個の(i,i)は距離0な出発点
q00 = [((i,i), 0) | i <- [1 .. n]]
-- i-[c]->jであるようなO(N^2)個の(i,j)は距離1な出発点
q01 = [((i,j), 1) | (i,cs) <- zip [1 ..] css, (j,c) <- zip [1 ..] cs, c /= '-']
-- 初期状態
m0 :: M.Map (Int,Int) Int
m0 = M.fromList $ q01 ++ q00 -- 後ろ優先
mZ = loop m0 $ Q.fromList $ q00 ++ q01
loop m Q.Empty = m
loop m (((i,j), d) Q.:<| q1) = loop m1 q2
where
pqs = [((p,q), d + 2) | c <- ['a' .. 'z'], p <- rev ! (i,c), q <- fwd ! (j, c), M.notMember (p,q) m]
m1 = M.union m $ M.fromList pqs
q2 = q1 Q.>< Q.fromList pqs
計算結果を Data.Array.ST で記録するように直せば、after_contest なしで41ms、込みでも381msで走った。
F - Alkane
アル○カン？自動人形（オートマタ）？
シグネチャを決める。
abc394f :: Int -- N
-> [[Int]] -- Ai,Bi
-> Int -- 答え
アライさんの誤謬に自分もひっかかって、「でもF問題がそんなに簡単じゃおかしいよな」とは思ったがそのままお手上げになった。
正しい方の説明の図解に従って、どこかの末端を根として、「自分を葉としてアルカンを成す子が3つ以上あるとき、大きい方から3つ選んで、それらと、自分と、自分の親でアルカンを成す」という最大サイズを再帰的に求めることができる。
で、これだけでは不正解で、「自分を葉としてアルカンを成す子が4つ以上あるとき、大きい方から4つ選んで、それらと、自分で、完結したアルカンを成す」という最大サイズも勘定に入れる必要がある。
結果
import Data.List
import Data.Array
abc394f :: Int -> [[Int]] -> Int
abc394f n uvs
| n < 5 = -1
| ans == 1 = -1
| otherwise = succ ans
where
-- グラフ
g :: Array Int [Int]
g = accumArray (flip (:)) [] (1,n) $ concat [[(u,v), (v,u)] | u:v:_ <- uvs]
-- アリティが1な頂点を適当に根と指名する、gは木なので必ずある
root = head [v | (v,[_]) <- assocs g]
-- 根から再帰的に降りることで上下を決めて、DPで計算する。
(_,ans) = iter root root
-- 親p現在vについて、アルカンのサイズ-1と、自分も含めて子孫の答えの最大値
iter p v
| lenIsGE 4 xs = post k kk
| lenIsGE 3 xs = post k 0
| otherwise = post 1 0
where
(xs, ys) = unzip [iter v c | c <- g ! v, c /= p]
xs4 = take 4 $ sortBy (flip compare) xs
k = succ $ sum $ take 3 xs4 -- 上に持ち上げる、下3つと自分のサイズ
kk = sum xs4 -- ここで折り返す、下4つ(と自分のサイズ-1)
post k j = (k, maximum $ k : j : ys)
lenIsGE :: Int -> [a] -> Bool
lenIsGE k xs
| k <= 0 = True
| otherwise = not $ null $ drop (pred k) xs
G - Dense Buildings
シグネチャを決める。
abc394g :: [Int] -- H,W
-> [[Int]] -- Fij
-> Int -- Q
-> [[Int]] -- ABYCDZi
-> [Int] -- 答え
例1ではやたらとややこしい解が目くらましに書いてあるが、ようは、始点から終点までの間の経路で最も低いビルの高さまで降りて、水平移動して、目標の高さまで戻ればよいだけ。
ただし、最短経路を辿るよりも回り道をした方が、低いところまで降りずに済むことがある、という話。
つまり、クエリの始点と終点の間を、なるべく高いビルだけを伝って到達できるようにしたときの、最も低いビルの高さが判ればよい。
ビルのそれぞれに、クエリの始点と終点のエージェントを配置する。
高いビルから始め、順に、高さが自分以上の周囲のビルと行き来可能にする。
対応するエージェントが往来可能になったら、そのときに建てたビルの高さが知りたかったもの。
これをするには、Union-Find を用いて、高いビルから順に建てていく。
Union-Find の各ノードにエージェントの集合を付けて、意味のある統合動作が行われたとき、
両者のエージェント集合を和集合にする。
また、共通要素があるとき、それらは、エージェント同士が往来できるようになったことを意味する。
…という方針でやったら、WAが出まくった。
AtCoder Companionsでヒントを貰ったところ「クエリの始点と終点が同じビルのとき、Union-Findが発動しないから、単に高さの差を答えとせよ」という落とし穴にはまっていた。
問題の制約「$(A_i,B_i,Y_i) \neq (C_i,D_i,Z_i)$」は「全く同じはないよ、どこか違うよ」という意味だから、そうだね…
結果
自作のUnion-Findは、統合の成否だけでなく、統合前後の代表ノード番号も返すようにしてあるので、エージェント集合を持ち回せる。公式解説にある「マージテク」がこれに類するものなのかはわからないが、出題の時間制限5secに対して1933msでACした。
公式解説では、こういう場合のUnion-Findの気の利いた使い方として、橋をかけると考えて、隣接するビルのペア全てを考えて、低い方のビルの高さをソートのキーとして、どことどこを橋渡しすればよいかを列挙するとよいとある。
上手いやり方なのだけど、そうするとビル1つに対してソート対象が4つになって重くなってしまった。
なので上の解では、ビルを高さ順にソートして、ビルが建築済みかどうかを追跡するフラグ配列を管理して、隣接する建設済みビル最大4つに橋を架ける、という手順をとった。