AtCoder465振り返りです。
参加ペース落としているので3週間ぶりの参加です。
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
問題文通りにとくだけです。
Haskellだと先頭3要素をパターンマッチで取り出せるので便利ですね
-- Main
f [a1, a2, a3] cnt
| a1 < a2 && a2 > a3 = cnt + 1
| otherwise = cnt
f as@(a1 : a2 : a3 : rest) cnt
| a1 < a2 && a2 > a3 = f (tail as) (cnt + 1)
| otherwise = f (tail as) cnt
main :: IO ()
main = do
_ <- readLn @Int
as <- getInts
print $ f as 0
B問題
- 問題
- 回答
∣x−i∣≤D であることから、文字列Sのうち、ある1文字の座標iを起点として[i-D, i+D]の閉区間を全探索することを考えます。
長さMの文字列Sに対し、1文字ごとに[i-D, i+D]の範囲を全探索することから計算量としてはO(2MD)となりますが、問題の制約0≤D<M≤100であることから最大でも2 * 10 ^ 4程度なので十分高速です。
各文字ごとに[i-D, i+D]の範囲をチェックし、一つでもGがあったら除外するようにしましょう。ここは内部でリスト内表表記を使ってGがある点を抽出し、空リストであれば通過するようにしました。(空リストチェックはnullを使いました)
但し範囲外アクセスする可能性があるため、エラーにならないように考慮する必要があります。HaskellならMaybeを使って範囲外アクセスした時にNothingを返すようにすると便利です。
-- Main
main :: IO ()
main = do
[n, d] <- getInts
s <- getLine
let sv = VU.fromList s
ans =
[ idx
| let ss = zip [0 ..] s,
(idx, c) <- ss,
c == '.',
null
[ idx + delta
| delta <- [-d .. d],
let cc = sv VU.!? (idx + delta),
cc == Just 'G'
]
]
print $ length ans
どうでもいいですが、リスト内包表記をネストするとフォーマットがうまくいかずオフサイドルールに引っかかってめんどくさかったです。
C問題
- 問題
- 回答
permutationsで全列挙して辞書順比較します。
辞書順比較はそのまま比較すればよいです。今回の回答は自作関数のfromDigitsを使って整数にしましたが、リストそのままでも比較できます。
整数の長さは1≤N≤10なので十分高速です。(permutationsの計算量が調べてもわからなかったので、ご存じの方いればおしえてください
)
-- Main
main :: IO ()
main = do
n <- readLn @Int
ps <- fromDigits 10 <$> getInts
qs <- fromDigits 10 <$> getInts
let ns = map (fromDigits 10) $ permutations [1 .. n]
ans =
[ nn
| nn <- ns,
ps < nn,
nn < qs
]
print $ length ans
全体を振り返って
今回は比較的簡単めだった印象です。
引き続き精進してD問題が解けるようにしていきたいです。