ABC374の振り返りです。
結果
A,B,Cの2完でした。
解説
A問題
- 問題
- 回答
isSuffixOf使います
main :: IO ()
main = do
s <- getLine
putStrLn $ if "san" `isSuffixOf` s then "Yes" else "No"
B問題
- 問題
- 回答
再帰で解きます
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は頑張ればとけたかなあ
また次回も頑張ります！