ABC399の振り返りです。
結果
ABの2完でした。
ふりかえり
A問題
- 問題
- 回答
2つの文字列をzipして比較し、異なる文字の数をカウントすれば解けます
main :: IO ()
main = do
_ <- readLn @Int
s <- getLine
t <- getLine
print $ foldl' (\acc (s, t) -> bool acc (acc + 1) (s /= t)) 0 $ zip s t
B問題
- 問題
- 回答
降順ソートして、グルーピングします。
入力例の場合だと、
[3 12 9 9]
iを保持するためにzip [1..]して降順ソートし、グルーピングすると
[[(2, 12)], [[(3, 9), (4, 9)]], [(1, 3)]]
となります。
iをkey, rankをvalueとしたIntMapを作ります。IntMapで作っておくと、elemsした時にkeyの昇順でvalueを取得することができます。
valueはグループの数ずつ足してfoldしていけばよいので、コードは以下のようになります。
main :: IO ()
main = do
_ <- readLn @Int
psg <- groupOn snd . sortOn (Down . snd) . zip [1 ..] <$> getInts
let ans =
fst $
foldl'
( \(im', r) p ->
let im'' = IM.fromList [(i, r) | (i, _) <- p]
in (IM.union im'' im', r + length p)
)
(IM.empty, 1)
psg
mapM_ print $ IM.elems ans
C問題
- 問題
- 回答 upsolved
dfsもしくはunion-findで解くことができます。
dfsの場合は、探索中に訪問済みのノードに到達した時にカウントを増やすようにします。
グラフが複数に分断されている場合を考慮して、すべてのノードを始点にしてdfsを行います。
この時、始点が訪問済みの場合はskipするようにしておきます。そうすると、各ノードには一度しか訪問しないため、計算量はO(n)になります。（この全てのノードを始点にするのが思いつかず、時間ぎりぎり間に合いませんでした）
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getInts
let g = buildG (1, n) uvs
cnt = dfs' g n
print $ snd cnt - m
-- print $ cnt - m
{-- lib --}
-- 深さ優先探索（グラフ用）
type Graph = Array Int [Int]
type Edge = (Int, Int)
type Bounds = (Int, Int)
-- グラフ構築
buildG :: Bounds -> [[Int]] -> Graph
buildG bounds edges = accumArray (flip (:)) [] bounds edges'
where
edges' = concatMap (\[u, v] -> [(u, v), (v, u)]) edges
dfs' g n =
foldl'
( \acc@(seen, cnt) idx ->
bool (go g acc idx) acc (IS.member idx seen)
)
(IS.empty, 0)
[1 .. n]
where
go g (seen, cnt) v
| IS.member v seen = (seen, cnt + 1)
| otherwise = foldl' (go g) (seen', cnt) next_vs
where
next_vs = g ! v
seen' = IS.insert v seen
この問題は、グラフがいくつかの塊に分かれることから、ある辺の両端のノードがどちらもunionに属している場合にカウントすると捉えることができます。
この場合は、union-findとして解くことが可能です。
ある辺の両端のノードがどちらもunionに属しているは、↓のような実装を持っていればそのまま解くことができます。
sameUF :: UnionFind -> Int -> Int -> IO Bool
sameUF uf x y = (==) <$> getRoot uf x <*> getRoot uf y
全体のコードはこのような形になります。
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m getInts
uf <- newUF (1, n)
cnt <- newIORef (0 :: Int)
forM_ uvs $ \[u, v] -> do
same <- sameUF uf u v
if same
then modifyIORef' cnt (+ 1)
else unit uf u v
readIORef cnt >>= print
{-- lib --}
{-- union find --}
-- UnionFind 各ノードの親ノード 各ノードが属する木のsize
-- ノード番号をuniqなintとして持っておく
-- arrayを使って、各ノードに対応する親ノード、sizeが取得できるようにする
-- UnionFind (IOUArray lowerbound upperbound) (IOUArray parent size)
data UnionFind = UnionFind (IOUArray Int Int) (IOUArray Int Int)
newUF :: (Int, Int) -> IO UnionFind
-- (<*>) :: Applicative f => f (a -> b) -> f a -> f b を適用
-- IO (a -> b) -> IO a -> IO b となる
newUF (s, e) = UnionFind <$> newArray (s, e) (-1) <*> newArray (s, e) 1
getRoot :: UnionFind -> Int -> IO Int
getRoot uf@(UnionFind parent _) x = do
p <- readArray parent x
if p == (-1)
then return x
else do
p' <- getRoot uf p
writeArray parent x p' -- 経路圧縮
return p'
-- union by size
unite :: UnionFind -> Int -> Int -> IO ()
unite uf@(UnionFind parent size) x y = do
same <- sameUF uf x y
when same $ return ()
x' <- getRoot uf x
y' <- getRoot uf y
when (x' /= y') $ do
sizeX <- readArray size x'
sizeY <- readArray size y'
if sizeX > sizeY
then do
writeArray parent y' x'
writeArray size x' (sizeX + sizeY)
else do
writeArray parent x' y'
writeArray size y' (sizeX + sizeY)
sameUF :: UnionFind -> Int -> Int -> IO Bool
-- (<*>) :: Applicative f => f (a -> b) -> f a -> f b を適用
-- IO (Int -> Bool) -> IO Int -> IO Bool となる
-- IO (== (root uf x)) <*> IO (root uf y) という形になる
sameUF uf x y = (==) <$> getRoot uf x <*> getRoot uf y
全体を振り返って
がんばります！(C問題解けたなあ、、)
おまけ
今回もRustで解き直してみました。
自前のunion-findを使ってますが、ac-library-rsがあればdsuを使って解けるとおもいm