ABC389の振り返りです。最近振り返りさぼっててすみません。
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
CharからIntに変換する関数を作りました。
main = do
ans <- do
[x, 'x', y] <- getLine
return $ charToInt x * charToInt y
print ans
charToInt :: Char -> Int
charToInt c = ord c - ord '0'
digitToIntで解くこともできます。こっちの方がスマートです。
main :: IO ()
main = do
s <- map digitToInt <$> getLine
print $ head s * last s
B問題
- 問題
- 回答
1から掛けていって、xと同じになったら返します。
main :: IO ()
main = do
x <- readLn @Int
print $ f x
f :: Int -> Int
f x = go 1 1
where
go n ans
| ans == x = n - 1
| ans < x = go (n + 1) (ans * n)
| otherwise = error "invalid pattern"
C問題
- 問題
- 回答
問題文通り、Data.Sequenceをキューとして使って解いていきます。先頭からヘビを除外した場合、全てのヘビから除外するヘビの長さを引くと時間がかかってしまうので、削除した値を保持しておきます。
同様に、計算量を減らすためにヘビの追加時に全体の長さ+追加するヘビの長さとしたいので、全体のヘビの長さも保持しておきます。
main :: IO ()
main = do
q <- readLn @Int
qs <- replicateM q getInts
f qs
f = foldM_ (flip go) (Seq.empty, 0, 0)
where
go [1, l] (seq, minus, tail) = return (seq Seq.|> (tail, l), minus, l + tail)
go [2] (seq, minus, tail) = do
case Seq.viewl seq of
Seq.EmptyL -> error "empty queue"
(_, l) Seq.:< seq' -> return (seq', minus + l, tail)
go [3, k] (seq, minus, tail) = do
print $ fst (Seq.index seq (k - 1)) - minus
return (seq, minus, tail)
go _ _ = error "invalid pattern"
ちなみに、この問題はk番目のヘビの頭の座標 - 先頭のヘビの頭の座標で解くこともできます。
このように解くと、除外したヘビの長さの合計や全体のヘビの長さを保持しておく必要ないのでよりシンプルに解けます。
ソースはこのような感じです。
main :: IO ()
main = do
q <- readLn @Int
qs <- replicateM q getInts
f qs
f :: [[Int]] -> IO ()
f = foldM_ go Seq.empty
where
go seq [1, l] = do
let tail = case Seq.viewr seq of
Seq.EmptyR -> 0
_ :> (_, tail) -> tail
return $ seq :|> (tail, tail + l)
go seq [2] = do
case Seq.viewl seq of
Seq.EmptyL -> error "empty queue"
_ :< seq' -> return seq'
go seq [3, k] = do
let head = case Seq.viewl seq of
Seq.EmptyL -> error "empty queue"
(head, _) :< _ -> head
khead = fst (Seq.index seq (k - 1))
print $ khead - head
return seq
go _ _ = error "invalid pattern"
全体を振り返って
今回調子よかったので、次回からもこんな感じで解いていければと思います！