F - Greedy Takahashi Editorial by gksato
この問題は，単純に時間軸を追ってまとめてシミュレーションをすることによっても解くことができます．高橋君が同時にあちこちに何人もいたとして，彼ら全員がどのように移動するかを同時に追跡することを考えます．彼らの動きを時系列順に追うのですから，特筆すべき出来事は次の4種類のイベントになります：
- \(1 \le i \le Q\) に対する高橋君生成 \(\operatorname{Generate}(X_i,i,Y_i)\)．時刻 \(X_i\) に \(i\) 人目の高橋君を街 \(Y_i\) に発生させることを表したイベントです．
- \(1 \le i \le Q\) に対する高橋君位置決定 \(\operatorname{Measure}(Z_i,i)\)．時刻 \(Z_i\) に \(i\) 人目の高橋君がどこにいるかを決定しなければならないことを表したイベントです．
- \(1 \le i \le M\) に対するバス到着 \(\operatorname{Arrive}(T_i,i,B_i)\) ．時刻 \(T_i + 0.5\) にバス \(i\) が街 \(B_i\) に到着することを表すイベントです．
- \(1 \le i \le M\) に対するバス発車 \(\operatorname{Depart}(S_i,i,A_i)\)．時刻 \(S_i + 0.5 \) にバス \(i\) が街 \(A_i\) から発車することを表すイベントです．
さて，これらのイベント全てからなる長さ \(2(M+Q)\) の配列を時系列順でソートします（具体的には，\(X_i, Z_i, T_i, S_i\) たちの昇順で並べることとし，このパラメータが一致するイベント群については \(\mathrm{Generate}, \mathrm{Measure}, \mathrm{Arrive}, \mathrm{Depart}\) の順で並べます）．あとは，「あるバスに誰が乗っているか」「ある街に誰がいるか」「ある人はどのバス/街にいるか」をそれぞれ管理しながら時系列を追えばこの問題を解くことができます．ただしこれだとTLEです．バス到着イベントおよび発車イベントでは最大 \(Q\) 人が乗り降りするため，これらのイベント1つの処理に最悪 \(O(Q)\) かかった結果，最悪計算量が \(O(MQ+(M+Q)\log(M+Q))\) になってしまうためです．
どうすれば良いでしょうか．「バスに乗る人間は高々1人である」という制約があれば，すべてのイベントの処理が定数時間で実行できますから，計算量は \(O((M+Q)\log(M+Q))\) で抑えられるはずです．また，ある街で二人の高橋君が合流した場合，その二人は永遠に離れることがありません．そこで，合流した高橋君を合体させて一人のキメラとして扱うことにします．
このような目的のために，「誰と誰が合体しているか」を管理するUnion-Find木（素集合データ構造）を用いることにします．これを用いれば，高橋君たちを自在に合体させることができます(Union操作)．Find操作で発見されるような「キメラの中身を代表する高橋君の番号」を，キメラのIDとして使うこともできます．
すると，このUnion-Find木とともに，「あるバスの乗客キメラは（いるなら）誰か」，「ある街の滞在者キメラは（いるなら）誰か」，「あるキメラはどのバス/街にいるか」を管理し，同じ街に現れた二人以上のキメラは必ず合成するようにしながら時系列を追えば，各イベントの処理は \(\alpha\) をアッカーマン逆関数として償却 \(O(\alpha(Q))\) で行うことができます．
そこで，イベントたちのソートが \(O((M+Q)\log(M+Q))\)，時系列処理が \(O((M+Q)\alpha(Q))\) となるため，合わせて計算量 \(O((M+Q)\log(M+Q))\) でこの問題を解くことができます．
実装例(Haskell):
{-# LANGUAGE BangPatterns #-}
import Control.Applicative
import Control.Monad.Primitive
import Control.Monad.State.Strict
import Data.Maybe (fromJust)
import Data.Word (Word8)
import qualified Data.ByteString as BSW
import qualified Data.ByteString.Char8 as BS
import qualified Data.ByteString.Lazy as BSLW
import qualified Data.ByteString.Lazy.Char8 as BSL
import qualified Data.Vector.Unboxed as VU
import qualified Data.Vector.Unboxed.Mutable as VUM
import qualified Data.Vector.Algorithms.Intro as VAIT
main :: IO ()
main = do
[n,m,q] <- map read . words <$> getLine
buses <- VU.replicateM m $ readLnWith
$ (,,,) <$> (subtract 1 <$> rIntS)
<*> (subtract 1 <$> rIntS)
<*> rIntS <*> rIntS
passengers <- getVecURest q $ liftA3 (,,) rIntL
(subtract 1 <$> rIntL)
rIntL
let res = query n buses passengers
putStr $ unlines
$ map (\(ty,place) -> if ty then show (place+1)
else let (!from,!to,_,_) = buses VU.! place
in shows (from+1) $ ' ' : show (to+1))
$ VU.toList res
query
:: Int
-> VU.Vector (Int,Int,Int,Int) -- buses
-> VU.Vector (Int,Int,Int) -- passengers
-> VU.Vector (Bool,Int) -- (True, city id) or (False, bus id)
query numCities buses passengers = VU.create $ do
uf <- initMUF (VU.length passengers)
res <- VUM.replicate (VU.length passengers) (True,-1)
current <- VUM.replicate (VU.length passengers) (True,-1::Int)
cityReps <- VUM.replicate numCities (-1::Int)
busReps <- VUM.replicate (VU.length buses) (-1::Int)
VU.forM_ events $ \(!time,!evtype,!callerID,!city) ->
case evtype of
0 -> do cityRep <- VUM.read cityReps city
rep <- if cityRep < 0 then return callerID else do
_ <- unionUF uf cityRep callerID
findUF uf callerID
VUM.write cityReps city rep
VUM.write current rep (True,city)
1 -> do rep <- findUF uf callerID
result <- VUM.read current rep
VUM.write res callerID result
2 -> do busRep <- VUM.read busReps callerID
cityRep <- VUM.read cityReps city
if busRep < 0 then return () else do
rep <- if cityRep < 0 then return busRep else do
_ <- unionUF uf cityRep busRep
findUF uf busRep
VUM.write cityReps city rep
VUM.write current rep (True,city)
3 -> do repPass <- VUM.read cityReps city
VUM.write cityReps city (-1)
VUM.write busReps callerID repPass
when (repPass >= 0)
$ VUM.write current repPass (False,callerID)
_ -> error "undefined type"
return res
where
events
= VU.modify VAIT.sort
$ VU.imap (\ !i (!x,!y,!_) -> (x,0::Word8,i,y)) passengers
VU.++ VU.imap (\ !i (!_,!_,!z) -> (z,1,i,-1)) passengers
VU.++ VU.imap (\ !i (!a,!b,!_,!t) -> (t,2,i,b)) buses
VU.++ VU.imap (\ !i (!a,!b,!s,!_) -> (s,3,i,a)) buses
---- union-find 木の実装 -----
type MUFTree s = VUM.MVector s Int
type UFTree = VU.Vector Int
initMUF :: (PrimMonad m) =>
Int -> m (MUFTree (PrimState m))
{-# INLINE initMUF #-}
initMUF len = VUM.replicate len minBound
findUF :: (PrimMonad m) =>
MUFTree (PrimState m) -> Int -> m Int
{-# INLINE findUF #-}
findUF vec !i = do
vi <- VUM.read vec i
if vi < 0 then return i else go i vi
where
go !j !vj = do
!vvj <- vec `VUM.read` vj
if vvj < 0 then return vj else do
!root <- go vj vvj
vec `VUM.write` j $ root
return root
unionUF :: (PrimMonad m) =>
MUFTree (PrimState m) -> Int -> Int -> m Bool
{-# INLINE unionUF #-}
unionUF vec !i !j = do
!rooti <- findUF vec i
!rootj <- findUF vec j
if rooti == rootj then
return False
else do
!ranki <- VUM.read vec rooti
!rankj <- VUM.read vec rootj
case compare ranki rankj of
LT -> VUM.write vec rooti rootj
GT -> VUM.write vec rootj rooti
EQ -> do VUM.write vec rootj rooti
VUM.write vec rooti (ranki+1)
return True
---- 入出力処理 ----
readLnWith :: StateT BS.ByteString Maybe a -> IO a
{-# INLINE readLnWith #-}
readLnWith parser = fromJust . evalStateT parser <$> BS.getLine
getVecURest :: (VU.Unbox a) =>
Int -> StateT BSL.ByteString Maybe a -> IO (VU.Vector a)
{-# INLINE getVecURest #-}
getVecURest n s = VU.unfoldrN n (runStateT s) <$> BSL.getContents
ord8 :: Char -> Word8
{-# INLINE ord8 #-}
ord8 = fromIntegral . fromEnum
rIntL :: StateT BSL.ByteString Maybe Int
{-# INLINE rIntL #-}
rIntL = modify (BSLW.dropWhile (< ord8 '!')) *> StateT BSL.readInt
rIntS :: StateT BS.ByteString Maybe Int
{-# INLINE rIntS #-}
rIntS = modify (BSW.dropWhile (< ord8 '!')) *> StateT BS.readInt
（Markdownと＄記号が干渉してCopyがうまく作用しないようなので，もしコピーして試されるかたがいらっしゃれば https://atcoder.jp/contests/abc212/submissions/24703863 からどうぞ）
posted:
last update: