AtCoder434振り返りです。
風邪ひいてるのでUnratedで参加しました
結果
ABの2完でした。
ふりかえり
A問題
- 問題
- 回答
1000かけてbで割ります
風船を n 個付けられた物体は、物体の質量が nB [g] 未満 である時、またその時に限り、空に飛び立ちます。というのがポイントで、
$\lfloor W * 1000 \div b \rfloor$
となるでは問題の条件を満たせないので
$\lfloor W * 1000 \div b \rfloor + 1$
が答えとなります。
main :: IO ()
main = do
[w, b] <- getInts
let d = (w * 1000) `div` b
print $ d + 1
B問題
- 問題
- 回答
鳥の種類でgroupByして種類ごとに平均値を出せばよいです
main :: IO ()
main = do
[n, m] <- getInts
abs <- sort <$> replicateM n getTuple
let grp = groupBy (\(a, _) (b, _) -> a == b) abs
ans =
[ fromIntegral s / fromIntegral len
| lst <- grp,
let bs = [b | (_, b) <- lst]
len = length bs
s = sum bs
]
mapM_ print ans
C問題(upsolved)
- 問題
- 回答
最初は「何言ってるの？」となりますが、冷静に条件を整理すると解法がわかります。
現在取りうる高度の上限・下限の値を持っておき、そこから移動可能な範囲を計算します。
移動可能な範囲が[l, u]の間にあればYesそうでなければNoとなります。
現在取りうる高度の上限をcurr_u, 下限をcurr_lとし、移動時間をtとすると、
次にとりうる高度の上限next_u, 下限next_lは以下のようになります。
next_u = min((curr_u + t), u)
next_l = max((curr_l - t), l)
また、移動可能かどうかの判定は、移動不可能となる条件が
curr_u - t > u
もしくは
curr_l + t < l
であることから、否定をとって
curr_u - t <= u
かつ
curr_l + t >= l
となります。(ドモルガンの定理)
欲しいのは最後の値だけなのでfoldl'で計算し、判定結果や現在時刻、取りうる高度の範囲をaccとして引き回せば解けそうです。
結果として、以下のコードになりました。
main = do
t <- readLn @Int
tlus <- replicateM t do
[n, h] <- getInts
tuls <- replicateM n getInts
let ans =
foldl'
( \acc@(bl, (t', l', h')) [t, l, u] ->
let diffT = t - t'
in if not bl
then acc
else
((h' + diffT) >= l && (l' - diffT) <= u, (t, max (l' - diffT) l, min (h' + diffT) u))
)
(True, (0, h, h))
tuls
printYn $ fst ans
ちなみに、問題文のtは時刻であって移動にかかる時間ではないので移動結果の高度を求めるには当然tの差分を計算する必要があります。
このtの差分を取るというのが完全に抜けてしまってWAとなりました。悔しい。
全体を振り返って
解法あってたのにACできなくて悔しいです。ただ情報整理や検討にかなり時間をかけてしまっているので、もっと早く解けるとこういうミスも減りやすくなるのかな、と思いました。
対策としては似た様な問題をたくさん解いて覚える、くらいしか思いつきませんが…