AtCoder部 2026-03-04

2026年3月4日
AtCoder部

ABC436 E - Minimum Swap

Pi=jP_i=j のとき辺 i−ji-j を張ったグラフを考える。このグラフはいくつかのサイクルからなる。

同じサイクルに含まれる2頂点をスワップするとサイクルが2つに分解され、異なるサイクルに含まれる2頂点をスワップするとサイクルがマージされる。

最短手順で大きさ1のサイクルに分解するには同じサイクルに含まれる2頂点をスワップし続ければいい。

元々大きさ S1,S2,…,SkS_1, S_2, \dots, S_k のサイクルにわかれていたとすると、1回目の操作は (S12)+(S22)+⋯+(Sk2)\binom{S_1}{2}+\binom{S_2}{2}+\dots+\binom{S_k}{2} 通りある。

main :: IO ()
main = do
  n <- getInt
  ps <- getInts

  uf <- Dsu.new (n + 1)
  mapM_ (uncurry (Dsu.merge uf)) $ zip ps [1 ..]
  ans <- V.sum . V.map (\g -> let sz = VU.length g in sz * (sz - 1) `div` 2) <$> Dsu.groups uf
  print ans

ABC381 D - 1122 Substring

各場所からスタートして、次の2要素が等しいかつ区間内にない数である限り区間を伸ばしたときの長さを求めたい。 これはしゃくとり法で求められる。

split :: [a] -> [(a, a)]
split [] = []
split [a] = []
split (a : b : rest) = (a, b) : split rest

main :: IO ()
main = do
  n <- getInt
  as <- getInts

  let ev = split as
      od = split (drop 1 as)
      solve = shakutori' (\st (a, b) -> a == b && IntSet.notMember a st) (\st (a, _) -> IntSet.insert a st) (\st (a, _) -> IntSet.delete a st) IntSet.empty
      ansEv = maximumDef 0 $ map snd $ solve ev
      ansOd = maximumDef 0 $ map snd $ solve od
  print $ 2 * max ansEv ansOd

ABC373 D - Hidden Weights

略

← All Posts