はじめに
今回はC問題でRE(x2)を克服できず。終了直後に怪しいところを直してみるとあっさりAC。コンテスト中に気が付きたいなー。
A問題
与えられた数式そのままでAiを求めてから合計を計算する。
main = do
n <- readLn :: IO Int
let ans = sum [((-1)^i)*(i^3)| i <- [1..n]]
print ans
提出
https://atcoder.jp/contests/abc425/submissions/69643827
B問題
-1以外で使われている数字を集め、[1..n]との補集合を取り出す。
取り出した補集合の値を(-1)の位置と交換しながらすすめ最後まで行けたらOK。
条件の作り方がいまいちでパターンマッチの書き方がややこしくなってしまった。
main = do
n <- readLn :: IO Int
as <- readInts
let bs = zip as [1..]
let cs = map fst $ filter ((/=(-1)).fst) bs
let ds = [1..n] \\ cs
let cands = solve ds as
if any (==(-1)) cands then do
putStrLn "No"
else do
putStrLn "Yes"
putStrLn $ unwords $ map show cands
solve :: [Int] -> [Int] -> [Int]
solve [] [] = []
solve [] (a:as)
| a /= (-1) = a : solve [] as
| otherwise = [-1]
solve dds@(d:ds) [] = [-1]
solve dds@(d:ds) (a:as)
| a == (-1) = d : solve ds as
| otherwise = a : solve dds as
提出
https://atcoder.jp/contests/abc425/submissions/69664382
C問題
1のタイプのQueryでずらす量を管理する。さらにずらす量はmodn にしておく。
さらにlからrまでの和をO(1)で求められるように累積和を求めておくが
2のタイプのQueryはlとrが逆になることがあるのでそうすると累積和の計算範囲がややこしくなるため
最初からAiを2倍にして累積和をとっておきlとrの大小関係が逆になった場合はrにn足して必ずlよりもrが大きくなるようにしてから区間和を計算すれば良い。
main = do
[n,q] <- readInts
as <- readInts
qs <- replicateM q readInts
let ss = scanl (+) 0 $ as ++ as -- 2周分用意する
let arr = AU.listArray (0,2*n) ss :: AU.UArray Int Int
-- print arr
putStr $ unlines $ map show $ solve n 0 arr qs
solve _ _ _ [] = []
solve n idx arr (q:qs) = case q of
(1:c:_) -> solve n ((c + idx)`mod`n) arr qs
(2:l:r:_) -> arr AU.! r2 - arr AU.! (l2-1) : solve n idx arr qs
where
l1 = (l + idx)`mod`n
r1 = (r + idx)`mod`n
l2 = if l1 <= idx then l1 + n else l1
r2 = if r1 <= idx || r1 < l2 then r1 + n else r1
提出(RE x2)
https://atcoder.jp/contests/abc425/submissions/69674798
提出(AC)
https://atcoder.jp/contests/abc425/submissions/69688226
D問題
コンテスト後に解きました。まとめて処理すれば良いという方針は決まれどfilterやfilterMが入り混じったコード実装に手こずりました。
main = do
[h,w] <- readInts
ss <- replicateM h getLine
let g = AU.listArray ((1,1),(h,w)) $ concat ss :: AU.UArray (Int,Int) Char
let cands = solve g
let ans = filter id $ AU.elems cands
print $ length ans
solve :: AU.UArray (Int,Int) Char -> AU.UArray (Int,Int) Bool
solve g = runSTUArray $ do
-- 未訪問(-1)を設定する
arr <- newArray ((1,1),(h,w)) False :: ST s (STUArray s (Int,Int) Bool)
let starts = [(i,j)| i <- [1..h], j <- [1..w], g AU.! (i,j) == '#']
bfs arr starts []
return arr
where
(_,(h,w)) = AU.bounds g
-- bfs
-- arr :: 訪問済みリスト
-- vs :: 現在同じ距離に属する節点リスト
-- us :: 次の距離に属する節点リスト
bfs arr [] [] = return () -- 候補がなくなった(終了)
bfs arr [] us = do -- usの候補を精査する
let fDir (i,j) = filter (AU.inRange ((1,1),(h,w))) [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] -- 4方向で範囲内のものを取り出す
cands <- forM us $ \neighbor -> do -- その先の接続先を確認
let neighbors2 = fDir neighbor
neighbors3 <- filterM (\(i,j) -> readArray arr (i,j)) neighbors2 -- 訪問済みの個数を数える
if length neighbors3 == 1 then
return (Just neighbor)
else
return Nothing
let neighborsFinal = catMaybes cands
bfs arr neighborsFinal [] -- 次のグループへ
bfs arr (v:vs) us = do -- メインの処理
writeArray arr v True
let fDir (i,j) = filter (AU.inRange ((1,1),(h,w))) [(i+1,j),(i-1,j),(i,j+1),(i,j-1)] -- 4方向で範囲内のものを取り出す
let dir4 = fDir v
neighbors1 <- filterM (\(i,j) -> not <$> readArray arr (i,j)) dir4 -- 訪問済みでないこと
bfs arr vs (neighbors1 ++ us)
提出
https://atcoder.jp/contests/abc425/submissions/69698994
おわりに
C問題は合ってるはずなんだけど。。。と最後まで間違いを見つけられませんでした。終了後10分くらいでもしやと思い l1<idx を l1<=idx のように変えたらあっさりACしました。