AtCoder Beginner Contest 326 振り返り

恒例の振り返りです。

結果

今回はBまでしか解けませんでした。。

各問題の振り返り

A - 2UP3DOWN

• 問題: https://atcoder.jp/contests/abc326/tasks/abc326_a

• 回答: https://atcoder.jp/contests/abc326/submissions/47018386

ちょっとハマってしまいました…

main :: IO ()
main = do
  (x, y) <- readPairInt
  if (y > x) && (y - x <= 2) || (x > y) && (x - y <= 3) then putStrLn "Yes" else putStrLn "No"

B - 326-like Numbers

• 問題: https://atcoder.jp/contests/abc326/tasks/abc326_b

• 回答: https://atcoder.jp/contests/abc326/submissions/47024205

これは特に問題なく解けました。divModが商と余りを同時に得られて便利。

main :: IO ()
main = do
  n <- readInputInt
  let listOf326Numbers = generate326Numbers
  print $ minimum $ V.filter (>= n) listOf326Numbers

isLike326Number :: Int -> Bool
isLike326Number n =
  let (hundreds, rest) = n `divMod` 100
      (tens, ones) = rest `divMod` 10
   in hundreds * tens == ones

C - Peak（Upsolved）

• 問題: https://atcoder.jp/contests/abc326/tasks/abc326_c

• 回答: https://atcoder.jp/contests/abc326/submissions/47100498

今回残念ながら解けませんでした。尺取法と呼ばれる方法を使って解くのがセオリーなようです。
Haskellの尺取法はhttps://zenn.dev/osushi0x/articles/e5bd9fe60abee4が参考になりました。

main :: IO ()
main = do
  (n, m) <- readPairInt
  positions <- readInputIntList
  print $ solve n m (VU.fromList $ L.sort positions)

solve :: Int -> Int -> VU.Vector Int -> Int
solve n m positions = shakutori 0 0 0 positions
  where
    shakutori :: Int -> Int -> Int -> VU.Vector Int -> Int
    shakutori left right maxCount positions
      | right >= n = maxCount
      | otherwise =
          let start = positions VU.! left
              end = positions VU.! right
           in if end - start < m
                then shakutori left (right + 1) (max maxCount (right - left + 1)) positions
                else shakutori (left + 1) right maxCount positions

ちなみに二分探索でも解けます。

• 別解: https://atcoder.jp/contests/abc326/submissions/47189725

main :: IO ()
main = do
  (n, m) <- readPairInt
  positions <- readInputIntList
  let sortedPositions = V.fromList $ L.sort positions
  print $ countPresents m sortedPositions n

countPresents :: Int -> V.Vector Int -> Int -> Int
countPresents m positions n =
  let findMaxPresents startPos =
        let endPos = upperBinarySearch (startPos + 1) (n - 1) (positions V.! startPos + m)
         in endPos - startPos
      upperBinarySearch low high x
        | low > high = low
        | otherwise =
            let mid = (low + high) `div` 2
             in if positions V.! mid < x
                  then upperBinarySearch (mid + 1) high x
                  else upperBinarySearch low (mid - 1) x
   in maximum $ map findMaxPresents [0 .. n - 1]

全体を振り返って

今回全然だめだった。。実力不足なので練習します！