HaskellでABC465を解く

はじめに

今回なんとかD問題滑り込みで間に合いました。

A問題

整数で判定できるように式変形しておいてから判定します。

A問題提出

main = do
  [a,b] <- readInts
  putStrLn $ bool "No" "Yes" $ 3*a > 2*b

B問題

A,B,L,Rの位置関係を丁寧に場合分けして解きました。解説にあるように1時間ずつ単価を足していく方法のほうが手続き型的に分かりやすいですね。あとminとかmaxとか使うと場合分けをなくせますが、考える時間を取りたくないので泥臭い方法を選択しました。

B問題提出

main = do
  [x,y,l,r,a,b] <- readInts
  if a <= l then
    if b <= l then
      print $ y*(b-a)
    else if b <= r then
      print $ y * (l-a) + x * (b-l)
    else
      print $ y * (l-a) + x * (r-l) + y * (b-r)
  else if a <= r then
    if b <= r then
      print $ x * (b-a)
    else
      print $ x * (r-a) + y * (b-r)
  else
    print $ y * (b-a)

C問題

Sequenceを使ってHeadとTailどっちかに1から順に追加していきます。
２回反転した後だとTailにそのまま追加できるのでそこまでの反転回数の偶奇を覚えておけばよいです。

C問題提出

main = do
  n <- readLn :: IO Int
  s <- getLine
  let si = zip s [1..]
  let cands = F.toList $ solve Seq.Empty True si
  putStrLn $ unwords $ map show cands

solve = step
  where
    step sq True [] = sq
    step sq False [] = Seq.reverse sq
    step sq dir ((c,i):cs)
      | c == 'o' = let sq1 = if dir then sq Seq.|> i else i Seq.<| sq
                   in step sq1 (not dir) cs
      | otherwise = let sq1 = if dir then sq Seq.|> i else i Seq.<| sq
                   in step sq1 dir cs

D問題

コンテスト終了ギリギリで思いつきました。x,yも割って行って同じ値になったとするとそこから逆に辿れることになるので、それぞれ同じ数値になるまでの試行回数をカウントしてその合計値が解になります。思い付くまで時間かかりましたが思い付けばプログラムはすごくシンプルになりました。

D問題提出

main = do
  t <- readLn :: IO Int
  replicateM_ t $ do
    [x,y,k] <- readInts
    print $ f x y k (0,0)

f m n k (cm,cn)
  | m > n = f m1 n k (succ cm,cn)
  | m < n = f m n1 k (cm, succ cn)
  | m == n = cm + cn
  where
    m1 = m `div` k
    n1 = n `div` k

おわりに

諦めかけていたところで解法を思いついての4完なのでかなり嬉しいコンテスト回になりました。