昨日のAtCoderの振り返りです。
今回の結果
A,B 2完でした。CはTLEで終わりました。
各問題の振り返り
A - Yay!
要は一文字しか出ない文字を探せば良いのですが、すんなり解けずちょっと工夫が必要でした。解法としては一文字目と残りの文字を分けて、
- 一文字目が残りの文字に現れなかったら一文字目が解
- 現れた場合はその文字が解
という風にして解きました。
main :: IO ()
main = do
s <- getLine
let (init : rest) = s
print $ if init `notElem` rest then 1 else fromJust (L.findIndex (/= init) rest) + 2
B - Which is ahead?
列が与えられて、2人の人Ai, Biのうちどちらが最初の方のindexに出てくるかを求める問題です。長さNの文字列に対して、適用するクエリはQ個となります。
制約条件を見ると行列の長さNの制約条件が
1≤N≤100
クエリの数Qが
1≤Q≤100
となっており、文字列一つごとにクエリを実行したとしても計算量はO(n^3)で1.0 * 10^6オーダです。これ愚直に解いても行けるんじゃね…？と思ってやってみたら普通にACできました。実行時間も1msと短めです。関係ないけどelemIndex便利。
main :: IO ()
main = do
_ <- BC.getLine
ps <- readInputInts
q <- readLn @Int
abs <- replicateM q readPairInt
mapM_ (\(a, b) -> print $ if a `L.elemIndex` ps < b `L.elemIndex` ps then a else b) abs
C - Divide and Divide
長さNの文字列Sに対して、Q個の文字列置換を実行するという問題です。
さっきとは打って変わって、N, Qの制約条件が
1≤N≤2×10^5,
1≤Q≤2×10^5
となっていたので、これは愚直に解くと無理だろうなあと思っていたら案の定TLEになってしまいました。（実行時間は2213ms）
その時の解法はこんな感じです。
main :: IO ()
main = do
_ <- readLn @Int
s <- BC.getLine
q <- readLn @Int
cds <- replicateM q readPairChar
BC.putStrLn $ L.foldl' applyOperation s cds
applyOperation :: BC.ByteString -> (Char, Char) -> BC.ByteString
applyOperation s (c, d) = BC.map (\x -> if x == c then d else x) s
createMap :: [(Char, Char)] -> M.Map Char Char -> M.Map Char Char
createMap [] m = m
createMap ((c, d) : ops') m = createMap ops' (M.insert c d m)
クエリをData.Mapで作ってfoldlで回しています。
この解法だと、長さNの文字列にQ個のクエリを繰り返す実行するため、計算量はO(NQ)、つまり4×10^10オーダになります。これは厳しいですね。
結局解法がわからなかったので、Contest後に公式の解法を見ると解き方がわかりました。実はちょっと工夫が必要な問題です。
解き方としては、最初に全アルファベット[a..z]の対応関係のマップを作っておいて、入力値を元にMapを更新していきます。
最初のマップはこんな感じです。
let initMap = M.fromList [(c, c) | c <- ['a' .. 'z']]
これを使うと、以下のようなマップが作成できます。つまり、最初は何も変換しないマップが出来上がります。
ghci> M.fromList [(c, c) | c <- ['a' .. 'z']]
fromList [('a','a'),('b','b'),('c','c'),('d','d'),('e','e'),('f','f'),('g','g'),('h','h'),('i','i'),('j','j'),('k','k'),('l','l'),('m','m'),('n','n'),('o','o'),('p','p'),('q','q'),('r','r'),('s','s'),('t','t'),('u','u'),('v','v'),('w','w'),('x','x'),('y','y'),('z','z')]
ここから、入力値を元にマップを更新していきます。
例えば、以下のような入力値が与えられた時に
r a
t e
d v
a r
このようにマップを更新していきます。
-
('r', 'r')⇨('r', 'a') -
('t', 't')⇨('t', 'e') -
('d', 'v')⇨('r', 'a') -
('a', 'a')⇨('a', 'r'),('r', 'a')⇨('r', 'r')
最後の行がポイントで、入力値を元に対応関係の表を先に作っておくことで初期値のアルファベットが最終的にどの値になるかのマップをこれで作ることができます。
これを使うと、TLEとなっていた解法がO(NQ)だったのに対して、O(ρ(N+Q))(ρはアルファベットの長さ26)になります。
ρは定数になるので、これはO(N+Q)となり2×10^5 * 2 = 4×10^5のオーダとなります。これならいけそうですね。
これを実装するとこのようになりました。Data.MapはTravaesalなのでmapを使ってkey-valueのvalueのみ更新できます。便利。
applyOps :: M.Map Char Char -> [(Char, Char)] -> M.Map Char Char
applyOps = L.foldl' applyOp
where
applyOp m (c, d) = M.map (\x -> if x == c then d else x) m
結果は無事ACで、実行時間も1203msに短縮できました。
全体を振り返って
前回、今回の問題を見ていて気づいたのですが、アルゴリズムとは別に「計算量を抑える工夫が必要な問題」で詰まるケースが多そうです。
こういうのは実装で詰まるとそっちに脳のリソースが取られると厳しくなりそうなので、もっと実装をスムーズにできるようになるのが大事かなあと思いました。
とりあえず、地道に問題を解いてもっとHaskellと仲良くなろうと思います。