ABC393の振り返りです。
結果
ABCの3完でした。今回も簡単目だった印象です。
ふりかえり
A問題
- 問題
- 回答
全パターンをベタ書きしました
main :: IO ()
main = do
ss <- getLine
print $ f $ words ss
f ["sick", "sick"] = 1
f ["sick", "fine"] = 2
f ["fine", "sick"] = 3
f ["fine", "fine"] = 4
B問題
- 問題
- 回答
文字列の間の間隔を1から刻み、始まりの文字列を1からずらしていってA, B, Cになっているか判定します。
文字列の間隔の最大値をミスってしまって1ペナになりました
main :: IO ()
main = do
s <- VU.fromList <$> getLine
let len = VU.length s
idxs =
[ (i, j, k)
| stp <- [1 .. 50],
i <- [0 .. len - (stp * 2) - 1],
let j = i + stp,
let k = j + stp,
s VU.! i == 'A' && s VU.! j == 'B' && s VU.! k == 'C'
]
print $ length idxs
C問題
- 問題
- 回答
辺の始点を揃えてSetで管理します。
始点と終点が一緒、もしくはSetにすでに辺が存在するのであればカウントを1増やします。
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m do
[u, v] <- getInts
return (min u v, max u v)
let ans =
foldl'
( \(set, cnt) (u, v) ->
if u == v || S.member (u, v) set
then (set, cnt + 1)
else (S.insert (u, v) set, cnt)
)
(S.empty, 0)
uvs
print $ snd ans
ちなみにこの解法で解くと、1786 msもかかってしまいます。
代わりにHashSetを使うと、686 msで解くことができます。
SetをHashSetに置き換えるだけです。
main :: IO ()
main = do
[n, m] <- getInts
uvs <- replicateM m do
[u, v] <- getInts
return (min u v, max u v)
let ans =
foldl'
( \(set, cnt) (u, v) ->
if u == v || HS.member (u, v) set
then (set, cnt + 1)
else (HS.insert (u, v) set, cnt)
)
(HS.empty, 0)
uvs
print $ snd ans
全体を振り返って
B問題のミスがなければもっとratingあがったのかなと思うので反省です。
最近安定して3完してますが、問題が簡単なだけに思えます。
もっと難しい問題でも安定して解けるようにしたいと思います。