ABC374の振り返りです。

結果

A,B,Cの2完でした。

解説

A問題

isSuffixOf使います

main :: IO ()
main = do
  s <- getLine

  putStrLn $ if "san" `isSuffixOf` s then "Yes" else "No"

B問題

問題
- https://atcoder.jp/contests/abc374/tasks/abc374_b
回答
- https://atcoder.jp/contests/abc374/submissions/58455909

再帰で解きます

main :: IO ()
main = do
  s <- zip [1 ..] <$> getLine
  t <- zip [1 ..] <$> getLine

  print $ if s == t then 0 else solve s t
  
solve :: Eq a1 => [(a2, a1)] -> [(a2, a1)] -> a2
solve [] ((ti, tc) : _) = ti
solve ((si, sc) : _) [] = si
solve ((si, sc) : st) ((ti, tc) : tt)
  | sc /= tc = si
  | sc == tc = solve st tt
  | otherwise = error "invalid pattarn"

C問題

2≤N≤20の制約から、全探索でできると判断できます。
subsequencesで1つのグループのパターンを全て洗い出し、それぞれのパターンのグループの合計人数を計算します。

合計人数の半分を計算して、それを超える内の最小値を求めれば解けます。

部署に所属する人数の合計のうち大きい方の値としてあり得る最小の値を求めてください。の制約から、半分の値を計算するときに繰り上げないといけないのですが、これを忘れて1ペナになりました

main :: IO ()
main = do
  n <- readLn @Int
  ks <- getInts

  let kss' = subsequences ks
      v = (fromIntegral (sum ks) :: Double) `ceilDiv` 2

  print $ minimum [sk | ks' <- kss', let sk = sum ks', sk >= v]

D問題(upsolved)

1≤N≤6の制約から、これも全探索でできると判断できます。
Ai-Bi, Ci-Di間は逆方向のパターンも考慮しないといけないですが、現在位置を持たせて、これも全パターン計算すれば解くことができます。
(回答は https://atcoder.jp/contests/abc374/submissions/58484229 を参考にしました。)

main :: IO ()
main = do
  [n, s, t] <- getInts
  abcds <- replicateM n do
    [a, b, c, d] <- getInts
    return ((a, b), (c, d))

  let abcds' = permutations abcds

  print $ minimum [solve edges s t | edges <- abcds']

solve :: [((Int, Int), (Int, Int))] -> Int -> Int -> Double
solve edges s t = go edges (0, 0) 0.0
  where
    go :: [((Int, Int), (Int, Int))] -> (Int, Int) -> Double -> Double
    go [] _ len = len
    go (((a, b), (c, d)) : et) (x, y) len =
      let td = sqrt (fromIntegral ((a - c) ^ 2 + (b - d) ^ 2)) / fromIntegral t :: Double
          sd1 = sqrt (fromIntegral ((x - a) ^ 2 + (y - b) ^ 2)) / fromIntegral s :: Double
          res1 = go et (c, d) (len + sd1 + td)

          sd2 = sqrt (fromIntegral ((x - c) ^ 2 + (y - d) ^ 2)) / fromIntegral s :: Double
          res2 = go et (a, b) (len + sd2 + td)
       in min res1 res2

全体を振り返って

前回に続いて、今回も簡単めだった印象でした。Dは頑張ればとけたかなあ
また次回も頑張ります！