最近個人的な都合でなかなか参加できてないですが、ABC417参加したので振り返りです。
今回は30分遅れのUnratedでした。
結果
今回はABCの3完でした。
Unratedなので順位の変動はなしです。
ふりかえり
A問題
- 問題
- 回答
takeしてdropします。
main :: IO ()
main = do
[n, a, b] <- getInts
s <- getLine
putStrLn $ (drop a . take (n - b)) s
あとから知ったのですが、dropEndを使うと便利です
main :: IO ()
main = do
[n, a, b] <- getInts
s <- getLine
putStrLn $ (drop a . dropEnd b) s
B問題
- 問題
- 回答
ランレングス圧縮して、削除するたびに個数を減らすように書きました。
問題の制約から広義単調増加なので、toAscListを使うと元のリストに戻すことができます。
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
let im = foldl' (\acc a -> IM.insertWith (+) a 1 acc) IM.empty as
im' = foldl' (flip (IM.adjust (\v -> v - 1))) im bs
ans = concat [replicate v k | let lst = IM.toAscList im', (k, v) <- lst, v > 0]
printList ans
こちらも後で知ったのですが、\\を使うと2つのリストのdiffが取れるのでもっと簡単に解くことができます。
https://hackage.haskell.org/package/base-4.21.0.0/docs/Data-List.html#v:-92--92-
main :: IO ()
main = do
[n, m] <- getInts
as <- getInts
bs <- getInts
printList $ as \\ bs
C問題
- 問題
- 回答
一見するとj−i=Ai+Ajから、iとjの組み合わせをすべて探索して解けばよさそうに見ます。
ですが、この解法だと一つのiに対してO(N)個のjを探索しなければならないので、結果的にO(N^2)の計算量がかかってしまうことになります。
Nの制約が 1≤N≤2×10^5 であることを考えると、最悪計算量が4×10^10になるので、TLEになることが想像できます。
なので、あるiに対応するAi, jに対するAjを求めるのは計算量がかからないことに注目して解きました。
具体的にどうするかというと、まずj−i=Ai+Ajを式変形します。
これを式変形すると
i+Ai=j-Aj
になります。
つまり、
『あるi+Aiに対応するj-Aiがいくつあるか求めよ』
という問題に帰着させることができます。
こうすると後は簡単で、先にj-Ajを計算してIntMapに放り込んでおき、i+Aiでlookupします。
lookupの計算量はO(logN)と見て良いので、全体の計算量はO(NlogN)になります。
出現回数を算出したかったので、今回はkey, valueを(j-Aj, 出現回数)として扱っています。
main :: IO ()
main = do
n <- readLn @Int
as <- zip [1 ..] <$> getInts
let js = [j - aj | (j, aj) <- as]
im = foldl' (\acc k -> IM.insertWith (+) k 1 acc) IM.empty js
cnt = sum [fromMaybe 0 mj | (i, ai) <- as, let mj = IM.lookup (i + ai) im]
print cnt
今回はIntMapを使いましたが、IntMultiSetを使う方法もあるかもしれません。
全体を振り返って
来週にはRatedに復帰したいです