AtCoder447振り返りです。
三ヶ月ぶりだと思ってなかったので我ながらびっくり(そんなつもりはなかった)
結果
ABCの3完でした。
今回もキープ
ふりかえり
A問題
- 問題
- 回答
席の間が一つづつ空くということは、"空いた席が人数 N -1 個 以上であること"と同じになります。
これをそのままコードにすればよいです
main :: IO ()
main = do
[n, m] <- getInts
printYn $ n - m >= (m - 1)
B問題
- 問題
- 回答
accumArrayを使って出現文字数をカウントします。
最大出現回数の文字がひとつとは限らないので、最大出現回数の文字をリストとして取得しておきます。
ここで取得した文字を除外すればそれが答えになります。
main :: IO ()
main = do
s <- getLine
let cnt = accumArray (+) 0 ('a', 'z') [(c, 1) | c <- s] :: UArray Char Int
mx = snd . head $ sortOn (Down . snd) $ assocs cnt
mxCs = findArrayIndices (== mx) cnt
putStrLn $ [c | c <- s, c `notElem` mxCs]
C問題
- 問題
- 回答
文字列Aの出現回数をカウントして、zipWithする or 先頭からひとつひとつ比較して差分をとればよさそうです。
出現回数をカウントするということで、ランレングス圧縮してとけばよさそうと思いましたがこれだとWA, REになりました。(ランレングス圧縮の回答)
main :: IO ()
main = do
s <- getLine
t <- getLine
let s' = [c | c <- s, c /= 'A']
t' = [c | c <- t, c /= 'A']
print
if s' /= t'
then -1
else
let [sr, tr] = map runLengthEncode [s, t]
in solve sr tr
solve :: [(Char, Int)] -> [(Char, Int)] -> Int
solve [] [] = 0
solve [(sc, sn)] [] = if sc == 'A' then sn else 0
solve [] [(tc, tn)] = if tc == 'A' then tn else 0
solve s@((sc, sn) : st) t@((tc, tn) : tt)
| sc == 'A' && tc == 'A' = abs (sn - tn) + solve st tt
| sc == 'A' && tc /= 'A' = sn + solve st t
| sc /= 'A' && tc == 'A' = tn + solve s tt
| sc /= 'A' && tc /= 'A' = solve st tt
なぜランレングス圧縮だとダメだったのでしょうか。
例えば、S = BB, T = BABの様な場合は回答を考えてみます。この場合回答は1になります。
これをランレングス圧縮すると、以下のようになります。
S
('B', 2)
T
('B', 1), ('A', 1), ('B', 1)
これを先頭から比較すると、先頭が違うので-1になってしまいます。
この時点で間違いです。
つまり、同じ文字の間にAが挟まった場合、ランレングス圧縮すると分割されてしまい正しく比較することができない、これがWAの原因です。（おそらくREも）
ではどう対応すればよいのでしょうか？
ここまで考えてみたのですが、そもそもランレングス圧縮しなくても先頭から愚直に比較すればよさそうです。
むしろランレングス圧縮してしまうと、上記のようなバグに対応するのが難しいので、やめて普通に比較することにしました。
その回答が以下になります。
solve [] [] = 0
solve (sh : st) [] = let cnt = if sh == 'A' then 1 else 0 in cnt + solve st []
solve [] (th : tt) = let cnt = if th == 'A' then 1 else 0 in cnt + solve [] tt
solve s@(sh : st) t@(th : tt)
| sh == 'A' && th == 'A' = solve st tt
| sh == 'A' && th /= 'A' = 1 + solve st t
| sh /= 'A' && th == 'A' = 1 + solve s tt
| sh /= 'A' && th /= 'A' = solve st tt
main :: IO ()
main = do
s <- getLine
t <- getLine
let s' = [c | c <- s, c /= 'A']
t' = [c | c <- t, c /= 'A']
print
if s' /= t'
then -1
else
solve s t
これだと期待通りパスしました。
※補足
A以外の文字間にある文字Aの数をカウントする方法だともっとシンプルにかけました(回答)
この場合はA以外の文字列の間にAがひとつも無い場合は0としてカウントされます。(例えば、ABBAABAは[1, 0, 2, 1]に変換されます)
solve = go 0
where
go n [] = [n]
go n ('A' : cs) = go (n + 1) cs
go n (_ : cs) = n : go 0 cs
main :: IO ()
main = do
s <- getLine
t <- getLine
print $
if filter (/= 'A') s /= filter (/= 'A') t
then -1
else
sum $ zipWith (\a b -> abs (a - b)) (solve s) (solve t)
D問題(upsolved)
- 問題
- 回答
問題をみたところそれほどむずかしくなさそうなので解いてみました。
Aの出現回数、ABの出現回数を持っておいて、先頭からカウントしていきます。
Aが出たらAの出現回数を+1, Bが出たらAの出現回数を1減らしてABの出現回数を増やし、Cが出たら回答を1つカウントしてAB`の出現回数を1減らす、と言うふうにして解きました。
solve :: [Char] -> Int
solve = go 0 0
where
go _ _ [] = 0
go cntA cntAB (c : cs) = case c of
'A' -> go (cntA + 1) cntAB cs
'B'
| cntA > 0 -> go (cntA - 1) (cntAB + 1) cs
| otherwise -> go cntA cntAB cs
'C'
| cntAB > 0 -> 1 + go cntA (cntAB - 1) cs
| otherwise -> go cntA cntAB cs
_ -> error "invalid pattern"
-- Main
main :: IO ()
main = do
s <- getLine
print $ solve s
全体を振り返って
気がつけば久しぶりの参加でした。
別にサボっていたつもりはなかったのでびっくりです。
引き続きマイペースにがんばっていこうと思います。