ABC386の振り返りです。気づけば久しぶりの参加でした。
眠気がひどくて気づけば座ったまま寝てるレベルだったので、今回はUnratedの参加です。
結果
ABCの3完でした。
Unratedなのでratingの変動はありません。
もう少し速く解ける様になりたいな,,
ふりかえり
A問題
- 問題
- 回答
sortして、数字でgroupingして、それぞれの長さを出力します。
最後にもう一回sortして、[1, 3]か[2, 2]のどちらかであればOKです。
最初にsortをするのを忘れて1ペナになりました。
main :: IO ()
main = do
abcd <- sort <$> getInts
let p = sort $ map length $ group abcd
putStrLn if p == [1, 3] || p == [2, 2] then "Yes" else "No"
B問題
- 問題
- 回答
00にマッチするとまるごと次にすすめ、それ以外だと一つづつ次にすすめます。
Haskellのパターンマッチを活用して、('0':'0':t)のようにマッチさせてときました。
solve :: String -> Int
solve s = go s 0
where
go [] cnt = cnt
go ('0' : '0' : st) cnt = go st (succ cnt)
go (_ : st) cnt = go st (succ cnt)
go _ _ = error "invalid parameter"
C問題
- 問題
- 回答
問題文の条件から、文字列の長さは高々1つしか変わりません。よって、条件を整理すると
- SがTより一文字多い場合
- TがSより一文字多い場合
- SとTが同じ長さの場合
の3つに分けられます。
さらに、1.と2.は同じ解き方で解けるので、実質的には
- 片方がもう片方より一文字多い場合
- 両方が同じ長さの場合
とできます。
- の場合は、再帰を利用して
f1 :: String -> String -> Int
f1 s1 s2 = go s1 s2 0
where
go s1@(h1 : t1) s2@(h2 : t2) cnt = if h1 == h2 then go t1 t2 cnt else go t1 s2 cnt + 1
go _ _ cnt = cnt
2.の場合は、foldl'を使って
f2 :: String -> String -> Int
f2 s1 s2 =
snd $
foldl'
( \(h : t, cnt) c ->
if h /= c
then (t, cnt + 1)
else (t, cnt)
)
(s2, 0)
s1
でとけました。
最初は1.も2.と同じ様にfoldl'で解こうとして
f1 :: String -> String -> Int
f1 s1 s2 =
snd $
foldl'
( \(s@(h : t), cnt) c ->
if h /= c
then (s, cnt + 1)
else (t, cnt)
)
(s2, 0)
s1
としたのですが、これだと
例えばSが"abc", Tが"ab"となった時に
Sが'c'の時に、Tの方に比較できる文字がないためエラーになってしまいます。(SとTが逆でも同様です。)
色々試行錯誤してmaybeで包むなども考えましたが、時間がないので再帰でときました。（結果的に3ペナだしました)
最終的なコードは以下の通りになりました。
main :: IO ()
main = do
_ <- getLine
s <- getLine
t <- getLine
putStrLn $ if solve s t <= 1 then "Yes" else "No"
solve :: [Char] -> [Char] -> Int
solve s t
| lenS == lenT = f2 s t
| lenS == lenT - 1 = f1 t s
| lenS == lenT + 1 = f1 s t
| otherwise = maxBound
where
lenS = length s
lenT = length t
f1 :: String -> String -> Int
f1 s1 s2 = go s1 s2 0
where
go s1@(h1 : t1) s2@(h2 : t2) cnt = if h1 == h2 then go t1 t2 cnt else go t1 s2 cnt + 1
go _ _ cnt = cnt
f2 :: String -> String -> Int
f2 s1 s2 =
snd $
foldl'
( \(h : t, cnt) c ->
if h /= c
then (t, cnt + 1)
else (t, cnt)
)
(s2, 0)
s1
全体を振り返って
なんとか3完できましたが、もっと速くとけないとなーと思いました。
来年に向けてもっと精進していきたいです。