ABC403の振り返りです。久しぶりの参加です
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
範囲内の奇数を取得し、配列からアクセスして合計します
main :: IO ()
main = do
n <- readLn @Int
as <- getInts
print $ sum [as !! (i - 1) | i <- [1 .. n], odd i]
B問題
- 問題
- 回答
部分配列をすべて取得してzipWithで比較します。
計算量はO(T^2)ですが、T は長さ 4 以上 10 以下の英小文字と ? からなる文字列とあるので、問題なしと判断しました。
main :: IO ()
main = do
t <- getLine
u <- getLine
let tLen = length t
uLen = length u
ts = [take uLen $ drop i t | i <- [0 .. (tLen - uLen)]]
f = zipWith (\uc tc -> tc == '?' || tc == uc)
printYn $ any (and . f u) ts
C問題
- 問題
- 回答
1 X Y: ユーザ X にコンテストページ Y の閲覧権限を付与する。
2 X: ユーザ X にすべてのコンテストページの閲覧権限を付与する。
とあるので、ユーザ毎にに各コンテストページの管理テーブルを用意します
ただし、これだけだと2のパターンでユーザごとにコンテストページの閲覧権限をすべて付与することになってしまうため、TLEになることが目に見えています。
そのため、①サイト個別の権限管理テーブルと②サイト全体の権限管理テーブルの2つを用意します。
もう一点注意することとして、空間計算量の問題があります。
権限の管理テーブルをArrayで実装した場合、①のサイト個別の権限管理テーブルだと、
N人のユーザ x M個のサイト
の数だけ要素数を持っておく必要があります。
これだと、制約
1≤N≤2×10^5
1≤M≤2×10^5
から、Intが4バイト(32bit環境)だとして、最悪空間計算量が
(2*10^5)^2 * 4 = 1.6 * 10^11 = 160GB
となってしまい、制約条件の1024 MBを軽く超えてREになってしまいます。
参考までに、実装は以下のようになります。
main :: IO ()
main = do
[n, m, q] <- getInts
qs <- replicateM q getInts
auth <- newArray @IOUArray ((1, 1), (n, m)) False
allAuth <- newArray @IOUArray (1, n) False
forM_ qs $ \case
[1, x, y] -> do
writeArray auth (x, y) True
[2, x] -> do
writeArray allAuth x True
[3, x, y] -> do
all <- readArray allAuth x
indiv <- readArray auth (x, y)
printYn $ all || indiv
REを防ぐためには、Setを使って管理するようにします。
これだとREが出ず、ACできます。
main :: IO ()
main = do
[n, m, q] <- getInts
qs <- replicateM q getInts
let indivAuth = S.empty
allAuth = IS.empty
f indivAuth allAuth qs
f :: S.Set (Int, Int) -> IS.IntSet -> [[Int]] -> IO ()
f _ _ [] = return ()
f indivAuth allAuth (q : qs') = case q of
[1, x, y] -> do
f ((x, y) `S.insert` indivAuth) allAuth qs'
[2, x] -> do
f indivAuth (x `IS.insert` allAuth) qs'
[3, x, y] -> do
let indiv = (x, y) `S.member` indivAuth
al = x `IS.member` allAuth
printYn $ al || indiv
f indivAuth allAuth qs'
_ -> error "invalid pattern"
全体を振り返って
早く茶色になりたい！