AtCoder452振り返りです。
結果
ABの2完でした。完敗です。
ふりかえり
A問題
- 問題
- 回答
elemするだけです
main :: IO ()
main = do
nm <- getPairInt
printYn $ elem nm [(1, 7), (3, 3), (5, 5), (7, 7), (9, 9)]
B問題
- 問題
- 回答
再帰で解きます。行が1かh,列が1かwだったら'#', そうでなければ.です。
solve h w = f 1
where
f rw
| rw == h = [g 1 rw]
| otherwise = g 1 rw : f (rw + 1)
g cl rw
| cl == w = "#"
| cl == 1 || rw == 1 || rw == h = '#' : g (cl + 1) rw
| otherwise = '.' : g (cl + 1) rw
-- Main
main :: IO ()
main = do
[h, w] <- getInts
mapM_ putStrLn $ solve h w
C問題(upsolved)
- 問題
- 回答
脊椎と肋骨に名前を書くアートってなんなんだ…？？というのは置いておいて、j番目の文字列Sjに着目してYesとなる条件を整理すると以下のようになります。
- Sjの長さがNである
- 全てのAi,Biについて以下を満たす文字列Skが存在する(重複は許容する)
i. Skの長さがAiである
ii. Sjのj番目の文字とSkのBi番目の文字が同じである
上記の条件を満たす場合はYes, 満たさない場合はNoになります。
ただし、全探索で実装した場合、2の条件を調べる時に「あるSiに対して全てのSを調査する」ことになるため、Ai, Biの数をN, 文字列Sの数をM とするとAB計算量がO(N * M^2)となってしまいます。
Nは1≤N≤10ですが、Mが1≤M≤200000となるため、計算回数の見積もりが最大2.0 * 10 ^ 11となりTLEとなります。
ここで、計算量を抑えるためにどうすればいいか考えます。
よく考えると、2の条件
『ある文字列Skにおける、長さAiとBi番目の文字』はあらかじめ全て計算しておくことができることに気がつきます。
これが使えるのであれば、あらかじめ計算してSetにしておけばよさそうです。
実装するとこんな感じでしょうか
let set = S.fromList [(ai, bi, v VU.! (bi - 1)) | [ai, bi] <- abs, v <- sv, VU.length v == ai]
あらかじめ計算するのにO(N)、2の条件を調査するのにO(MNlogM)なので、有効な時間に収まりそうです。
全部実装すると以下のようになりました。
solve n set abs sv =
[ VU.length v == n
&& and
[ (ai, bi, v VU.! (i - 1)) `S.member` set
| (i, [ai, bi]) <- abs
]
| v <- sv
]
-- Main
main :: IO ()
main = do
n <- readLn @Int
abs <- replicateM n getInts
m <- readLn @Int
sv <- replicateM m $ VU.fromList <$> getLine
let set = S.fromList [(ai, bi, v VU.! (bi - 1)) | [ai, bi] <- abs, v <- sv, VU.length v == ai]
mapM_ printYn $ solve n set (zip [1 ..] abs) sv
ちなみに、コンテスト中は計算量の見積もりをO(NM)に間違えてTLE, Setに修正した時は『Sjの長さはN』という条件を見落としてWAになってしまいました。
計算量の見積もり（というか具体的な処理の流れ）を把握しきれなかったのと、条件を見落としていたのが敗因でした。
全体を振り返って
正直今回のCは落としていい問題ではなかったので悔しいです。
引き続き精進します。