AtCoder482振り返りです。
結果
AB完でした。
ふりかえり
A問題
- 問題
- 回答
問題文通り解くだけです
main :: IO ()
main = do
s <- getLine
putStrLn $ bool "odd" "even" $ even (length [() | c <- s, c == 'o'])
B問題
- 問題
- 回答
行、列、斜めで全探索しました。
もっと綺麗に書けたかもしれませんが、愚直に解いています。
main :: IO ()
main = do
ss <- replicateM 5 getLine
let grid = IA.listArray @UArray ((1, 1), (5, 5)) $ concat ss
r = maximum [cnts | i <- [1 .. 5], let cnts = length [() | j <- [1 .. 5], grid IA.! (i, j) == 'o']]
c = maximum [cnts | j <- [1 .. 5], let cnts = length [() | i <- [1 .. 5], grid IA.! (i, j) == 'o']]
d1 = length [() | i <- [1 .. 5], j <- [1 .. 5], i == j, grid IA.! (i, j) == 'o']
d2 = length [() | i <- [1 .. 5], j <- [1 .. 5], i + j == 6, grid IA.! (i, j) == 'o']
print $ 5 - maximum [r, c, d1, d2]
C問題(upsolved)
- 問題
- 回答
区間の個数を求めることから、累積和で解けそう。と思いきや
1≤H,W≤10^9, 1≤u≤d≤H, 1≤l≤r≤W
の制約があるのでメモリ不足でREになります。
solve :: [(Int, Int)] -> (Int, Int) -> [[Int]] -> [Int]
solve rcs (h, w) =
map
( \q -> case q of
[1, u, d] -> rcsums VU.! d - rcsums VU.! (u - 1)
[2, l, r] -> ccsums VU.! r - ccsums VU.! (l - 1)
_ -> error "invalid query"
)
where
(rs, cs) = unzip rcs
rsums = elems $ accumArray @UArray (+) 0 (1, h) $ map (,1) rs
csums = elems $ accumArray @UArray (+) 0 (1, w) $ map (,1) cs
rcsums = VU.fromList $ scanl' (+) 0 rsums
ccsums = VU.fromList $ scanl' (+) 0 csums
-- Main
main :: IO ()
main = do
[h, w, n, q] <- getInts
rcs <- replicateM n getPairInt
qs <- replicateM q getInts
mapM_ print $ solve rcs (h, w) qs
UArrayのIntは一つの要素ごとに8byteを使うので、一つのarrayで8 * 10^9 ≒ 8GBのメモリを使うことになります。
AtCoderは通常1024MiBであることから、(1, w)もしくは(1, h)のarrayを作るとメモリが足りずエラーとなります。
参考までに、型ごとのメモリの目安をまとめておきます。
| 配列の種類 | 1要素あたり | 実用的な上限の目安（要素数） |
|---|---|---|
UArray / IOUArray / STUArray の Int
|
8 byte | 約 5×10⁷〜10⁸（10⁸で約800MB、ギリギリ） |
同上の Int32
|
4 byte | 約 2×10⁸ |
同上の Word8
|
1 byte | 約 8×10⁸ |
同上の Bool
|
1 bit（ビット詰め） | 10⁹ でも約125MB |
boxed Array（Array Int Int など） |
ポインタ8byte＋ボックス化した値（Intなら16byte）＋サンク | 約 10⁷ 程度 |
メモリ領域が足りず累積和を使えない場合、どうすればいいのでしょう
この場合は、二分探索を使うとよさそうです。
あらかじめ駒の位置でsortしておき、区間の最小値、最大値を二分探索で解きます。これなら新しくarrayを作る必要がないのでメモリを大幅に使わず区間の大きさを求めることができます。
solve :: [(Int, Int)] -> (Int, Int) -> [[Int]] -> [Int]
solve rcs (h, w) =
map
( \q -> case q of
[1, u, d] -> (maybe (VU.length rs' - 1) pred (lookupGTIdxV d rs')) - (maybe 0 succ (lookupLTIdxV u rs')) + 1
[2, l, r] -> (maybe (VU.length cs' - 1) pred (lookupGTIdxV r cs')) - (maybe 0 succ (lookupLTIdxV l cs')) + 1
)
where
(rs, cs) = unzip rcs
rs' = VU.fromList $ sort rs
cs' = VU.fromList $ sort cs
-- Main
main :: IO ()
main = do
[h, w, n, q] <- getInts
rcs <- replicateM n getPairInt
qs <- replicateM q getInts
mapM_ print $ solve rcs (h, w) qs
全体を振り返って
以下反省点です
- 空間計算量の見積もりを怠った（というより許容範囲を把握していなかった） -> AtCoderの使用可能なメモリ量を把握しておく
- REが出たときにエラーの原因を突き止めるのに時間がかかった -> 1ができればエラーの原因に検討がつくのでなんとかできるはず
- 二分探索で区間の大きさを求める手法をしらなかった -> 今回の問題を復習してとけるようにしておく
引き続き頑張ります！