遅くなりましたが、前回のABC振り返りです。
※前回の記事はこちら
https://qiita.com/flowerhill/items/d5f9f6b81d42ce81ca95
今回の結果
今回はA,B 2完でした。成長しない。。
各問題の振り返り
A - Scoreboard
XとYがN回試合をして、scoreを多く取った方を出力する問題です。
foldして比較すれば解けます。
main :: IO ()
main = do
n <- readLn @Int
scores <- replicateM n readPairInt
let (xTotal, yTotal) = L.foldl' (\(xAcc, yAcc) (x, y) -> (xAcc + x, yAcc + y)) (0, 0) scores
putStrLn if xTotal > yTotal then "Takahashi" else if xTotal < yTotal then "Aoki" else "Draw"
B - Extended ABC
拡張ABC文字列を判定する問題です。拡張文字列とはA,B,Cがこの順番で並んでいる文字列のことを指します。
例えばAABBCCCCは拡張ABC文字列ですが、AABACCCCは拡張ABC文字列ではありません。
解答ですが、本番ではかなり愚直に解きました。BS.groupを使って文字列をグループ分けし、グループ分け後の配列のサイズで以下のように場合分けしました。
- サイズが1の場合:
"A" || "B" || "C" - サイズが2の場合:
"AB" || "BC" || "AC" - サイズが3の場合:
"ABC"
グループ分けすると、配列が["AA", "BBB", "CCCC"]のようになるので、isPrefixOfを使って先頭のみ抽出しています。
ちなみに、条件を間違えて2ペナ食らいました。
main :: IO ()
main = do
s <- BS.getLine
putStrLn $ judge $ BS.group s
judge :: [BS.ByteString] -> String
judge g
| null g = "Yes"
| length g == 1 = if isPrefixOfA (head g) || isPrefixOfB (head g) || isPrefixOfC (head g) then "Yes" else "No"
| length g == 2 = if isPrefixOfA (head g) && isPrefixOfB (g !! 1) || isPrefixOfB (head g) && isPrefixOfC (g !! 1) || isPrefixOfA (head g) && isPrefixOfC (g !! 1) then "Yes" else "No"
| length g == 3 = if isPrefixOfA (head g) && isPrefixOfB (g !! 1) && isPrefixOfC (g !! 2) then "Yes" else "No"
| otherwise = "No"
where
isPrefixOfA = BS.isPrefixOf (BS.pack "A")
isPrefixOfB = BS.isPrefixOf (BS.pack "B")
isPrefixOfC = BS.isPrefixOf (BS.pack "C")
他の人の回答を見て知ったのですが、この問題はもっと簡単に解くことができます。
ここでは2つ例を挙げます。
- ソート後と前が同じならば拡張ABC文字列と判定する
module Main where
import qualified Data.ByteString as BS
main :: IO ()
main = do
s <- BS.getLine
putStrLn $ if BS.sort s == s then "Yes" else "No"
-
'A','B','C'の順番で文字列をdropWhileして空文字なら拡張ABC文字列と判定する。
module Main where
main :: IO ()
main = do
s <- getLine
let s1 = dropWhile (== 'C') $ dropWhile (== 'B') $ dropWhile (== 'A') s
putStrLn $ if s1 == "" then "Yes" else "No"
C - Lining Up 2
以下の数列が与えられた時、列を作る問題です。
A_1, A_2,.., An
列の作り方はAi = jのように値が与えられているので、AiがAjの後ろに並ぶように作ります。
また、先頭はAi = -1となるAになります。
先頭を探すのは難しくないのですが、Aiの後ろに並ぶ値Ajを探すとき、Aj = iとなるAを毎回探すと、
毎回Aiに対応するAjを探すことになるので計算量がO(n^2)となってしまいます。
問題の制約を見ると
1≤N≤3×10^5
となっているため、これだとTLEになりそうです。自分は二分探索かなーと思ったのですが、これだとうまく解けずにWAとなってしまいました。
正解はもっと単純にIntMap(HaskellのHashMapみたいなもの。keyがintegerになる。)を使えばよくて、これを使って先頭から列を作っていきます。
まずはこのようにIntMapを作ります。これで、Aのリストがkey, 区間[1, n]の値がvalueになります。
let asMap = IM.fromList $ zip as [1 ..]
この後は、-1を起点にして、次の要素をたどりながら列を作っていきます。
valueの値をkeyに指定している要素が次に後ろに並ぶ要素になるので、valueをkeyにして連結すると求める列が作れます。
solve :: IM.IntMap Int -> Int -> [Int]
solve map key
| IM.member key map = val : solve map val
| otherwise = []
where
val = map IM.! key
全体像はこんな感じです。
module Main where
import qualified Data.ByteString.Char8 as BS
import Data.Char (isSpace)
import qualified Data.IntMap as IM
import qualified Data.List as L
import Debug.Trace (traceShow, traceShowId)
main :: IO ()
main = do
getLine
as <- L.unfoldr (BS.readInt . BS.dropWhile isSpace) <$> BS.getLine
let asMap = IM.fromList $ zip as [1 ..]
putStrLn $ unwords . map show $ solve asMap (-1)
solve :: IM.IntMap Int -> Int -> [Int]
solve map key
| IM.member key map = val : solve map val
| otherwise = []
where
val = map IM.! key
全体を振り返って
なかなかレートが上がらずもどかしいですが、少し要領をつかめて来た気がしています。ただC問題はIntMap使えばいいことに気付けば解けたので、若干悔しい思いはあります。
悔しい気持ちはありつつも、焦らず一つ一つ理解して進めて行けたらいいなあと思っています。