久しぶりのAtCoder Rated参加です

結果

今回はABの2完でした。

ふりかえり

A問題

末尾から3文字取って比較します

main :: IO ()
main = do
  _ <- readLn @Int
  s <- takeEnd 3 <$> getLine
  printYn $ s == "tea"

B問題

部分文字列をすべて抽出して、先頭と末尾が両方tで長さが3以上のものを抽出します。
その後に充填率を計算して最大値を取ればよいです。

部分文字列をすべて抽出する関数を持っていなかったのでその場で作りました。

main :: IO ()
main = do
  s <- getLine
  let subs = substrings s
      ans =
        [ (x - 2) / (t - 2)
          | s' <- subs,
            let t = fromIntegral $ length s',
            t >= 3.0,
            head s' == 't' && last s' == 't',
            let x = fromIntegral $ countBy (== 't') s'
        ]
  print $ bool (maximum ans) 0.0 (null ans)

{-- lib --}
substring :: Int -> Int -> String -> String
substring start len str = take len (drop start str)

substringK :: Int -> String -> [String]
substringK k s = [substring i k s | i <- [0 .. length s - k]]

substrings :: String -> [String]
substrings s = concat [substringK i s | i <- [1 .. length s]]

C問題

問題
- https://atcoder.jp/contests/abc418/tasks/abc418_c
回答
- https://atcoder.jp/contests/abc418/submissions/68372490 (upsolved)

プレイヤーが必ず勝つxを求める前に、ディーラーが勝つための最善の戦略を考えます。

ディーラーはできるだけ少ない個数を均等に配ろうとするので、可能な限り(b-1)個づつ配るのがディーラーが勝つための最善戦略になります。

よって、プレイヤー側が勝つためには、xに

可能な限り(b-1)個づつ配った場合の個数 + 1

を指定すれば良いことになります。

当然フレーバーの種類によってはAi < b-1となることもあるので、そのような場合はAi個配ることになります。

なので、ディーラーの配る最善策の個数は

Σmin(Ai, b-1)ということになります。

もう少し噛み砕くと

Ai < b - 1のとき ΣAi
Ai >= b - 1のとき Σ(b-1)

ということになります。つまり、答えは

(Ai < b - 1 となるAiのすべての個数) + (Ai > b - 1となるフレーバーの個数 x (b - 1)) + 1

になります。

(Ai < b - 1 となるAiのすべての個数)は毎回計算すると計算量が大きくなりTLEとなるため、事前に累積和を計算しておきましょう。

そうすると、さきほどの解は

(Ai < b - 1 となる最大のAiでの累積和) + (Ai > b - 1となるフレーバーの個数 x (b - 1)) + 1

となりますから、Ai < b - 1 となる最大のAiを二分探索で解いて計算すれば答えが得られます。自分はめんどうだったのでIntMapを作ってlookupLEで計算しました。

main :: IO ()
main = do
  [n, q] <- getInts
  ai <- sort <$> getInts
  bs <- replicateM q $ readLn @Int

  let sn = VU.fromList $ scanl' (+) 0 ai
      im = IM.fromList $ zip ai [1 ..]
      maxA = maximum ai

  forM_ bs \b -> do
    if b <= maxA
      then do
        let idx = snd $ fromMaybe 0 $ IM.lookupLE (b - 1) im
            m = sn VU.! idx
            l = (b - 1) * (n - idx)
        print $ m + l + 1
      else print (-1)

全体を振り返って

またぼちぼち頑張りますー