久しぶりのAtCoder参加です
今回やっと入茶しました！長かった…
結果
ABCの3完でした。
ふりかえり
A問題
- 問題
- 回答
降順ソートして連結すれば解けます
main :: IO ()
main = do
abc <- map show . sortOn Down <$> getInts
putStrLn $ concat abc
B問題
- 問題
- 回答
permutationsで全パターンを出して、先頭が0のものを除いて最小値を出します。
main :: IO ()
main = do
x <- getLine
let lst = permutations x
ans = minimum [read @Int s | s <- lst, head s /= '0']
print ans
C問題
- 問題
- 回答
問題を見た瞬間途方にくれそうですが、諦めずにひとつひとつ整理していきます。
とあるAiについて、Xの飴を配る数をx, Yの飴を配る数をy, 飴玉の合計重量をSと置くと
X * x + Y * y = S
となりますが、これでは変数が多く制限時間内で答えを求められません。
そこで、ひとつひとつ変数を減らしていきます。
問題の制約より、iの合計個数をAiとすると、x + y = Aiであることから、
X * (Ai - y) + Y * y = S
となります。この数式を変形すると、
y = (S - X * Ai) / (Y - X)
であることがわかります。i = [1..N]におけるyの合計値がこの問題の答えになります。
ここで、X, Y, Aiは問題の入力値として与えられていますが、Sのみ与えられていません。なのでこの値を求めましょう。
ここが固定できればこの問題は解けそうです。
問題文から、大きい飴玉を最もたくさん配る時の合計値を求めます。
問題の制約から、大きい飴玉を最もたくさん配るのは、最も小さいAiを全て大きい飴玉で配った場合になります。
なので、min(Ai) * YをSとして使用します。
これを元にyを求める数式を解き、余りが0でない or 合計値が0より小さい場合は-1、そうでなければ合計値を解とします。
これをコードで書くと以下の様になります。
main :: IO ()
main = do
[_, x, y] <- getInteger
as <- sort <$> getInteger
let m = head as
s = y * m
calc = [if a2 /= 0 then -1 else a1 | a <- as, let (a1, a2) = (s - a * x) `divMod` (y - x)]
ans = if any (< 0) calc then -1 else sum calc
print ans
なお、実際解いていた時には
問題の制約から、大きい飴玉を最もたくさん配るのは、最も小さいAiを全て大きい飴玉で配った場合になります。
は自信がなかったので、正直賭けでした。
全体を振り返って
正直Cについては運が良かったな、と思うところもありました。ただ茶色になれて本当によかったです。ここまで2年近くかかってしまいました。
次は入緑に向けて頑張ります！自分のペースでコツコツ進められれば良いなと思っています。