🏆

ABC407 を Haskell で

に公開
Haskell
競技プログラミング
AtCoder
tech

結果

2 完でした。
C は Word8 を使って実装したせいでアンダーフローに気づけませんでした。
コンテスト中に慣れない実装をするものではないですね。

A

問題文

正整数 A と正の奇数 B が与えられます。

実数 A/B との差が最小となる整数を出力してください。

ただし、制約のもとでそのような整数がただ一つ存在することが証明できます。

制約

  • 1 \leq A \leq 407
  • 1 \leq B \leq 407
  • Bは奇数
  • 入力はすべて整数

方針

A \mod B \leq \lfloor B/2 \rfloor であれば \lfloor A/B \rfloor 、そうでなければ \lceil A/B \rceil となります。

実装

solve :: Int -> Int -> Int
solve a b = if a `mod` b <= b `div` 2 then a `div` b else a `div` b + 1

main :: IO ()
main = do
    [a, b] <- ints
    print $ solve a b

B

問題文

1,2,3,4,5,6の6種類の目が出るサイコロを2つ振ったときに、次の2つの条件の少なくとも一方を満たす確率を求めてください。

  • 2つの出目の合計が X 以上である。
  • 2つの出目の差の絶対値が Y 以上である。

ここで、どちらのサイコロについても6種類のどの目が出るかは同様に確からしく、それぞれのサイコロの出目は独立であるとします。

制約

  • 2 \leq X \leq 13
  • 0 \leq Y \leq 6
  • 入力はすべて整数

方針

リストモナドで全探索

実装

solve :: Int -> Int -> Double
solve x y = ((/ (36 :: Double)) . int2Double . length) $ do
    a <- [1 .. 6]
    b <- [1 .. 6]
    guard $ a + b >= x || abs (a - b) >= y
    pure True

main :: IO ()
main = do
    [x, y] <- ints
    print $ solve x y

C

問題文

AtCoder社の入口には特殊なパスコード入力装置があり、この装置は文字列を1つ表示する画面と2つのボタンからなります。

画面に表示される文字列をtとします。 t ははじめ空文字列であり、ボタンを押すことで t に以下の変化が起きます。

  • ボタンAを押すと、 t の末尾に0が追加される。
  • ボタンBを押すと、 t に含まれるすべての数字が、それぞれ次の数字に置き換わる。ここで、 0 から 8 までの数字については次の数字は1大きな数を表す数字とし、 9 の次の数字は 0 とする。

たとえば、 t が 1984 のときにボタンAを押すと t は 19840 に変化し、さらにボタンBを押すと t は 20951 に変化します。

文字列 S が与えられます。 t が空文字列である状態からボタンを0回以上押して t を S に一致させるとき、ボタンを最少で何回押す必要があるかを求めてください。

制約

  • Sは0,1,2,3,4,5,6,7,8,9からなる文字列
  • 1 \leq |S| \leq 5 \times 10^5（|S|はSの長さを表す）

方針

ゴールである S から開始時点の空文字列に変換するプロセスを考えます。
S = S_N \ldots S_2S_1 とすると、下 2 桁 S_2S_1 が S_2^{\prime}0 となるまでボタン B を押し、ボタン A を一度押してから、 S^{\prime} = S^{\prime}_N \ldots S^{\prime}_2 について同様の操作を行うことを再帰的に繰り返すことで、最小回数で t を空文字列に戻すことができます。S_{i+1}^{\prime} = S_{i+1} - S_i \mod 10 なので、求める値は \sum_{i = 1}^{N-1}{\lparen S_{i+1} - S_i \mod 10 \rparen} + S_1 + |S| です。

実装

solve :: BS.ByteString -> Int
solve s = buttonAClickCount + buttonBClickCount
  where
    buttonAClickCount :: Int
    buttonAClickCount = BS.length s

    buttonBClickCount :: Int
    buttonBClickCount =
        sum $
            fromIntegral
                <$> BS.zipWith (\c c' -> (10 + c - c') `mod` 10) s (BS.snoc (BS.tail s) zero)

    zero :: Word8
    zero = c2w '0'

main :: IO ()
main = do
    s <- BSC.getLine
    print $ solve s

Discussion