きろく

特筆すべき記録のまとめ

九州大学プログラミングコンテスト2018:B - Tapu & Tapi

問題

beta.atcoder.jp

解法

1円,10 円,100 円の順番に分ける枚数を決めていく.この時,各硬貨の枚数が偶数になれば条件を満たす.ここで,各硬貨の枚数に mod 20 をとる.なぜならば,1つ上の硬貨に位上げしても,位上げの枚数は必ず偶数になり,1つ上の硬貨の枚数が奇数であったときにもその効果の枚数が 10 以上あれば1つ上の硬貨の枚数を偶数にすることが出来るから.これを 1 -> 10 円,10 -> 100 円の2回考え,どれかの種類の硬貨の枚数を偶数にすることが出来なくなったら No で出来たら Yes.

解答

beta.atcoder.jp

5 WA してしまった.ずっと mod 10 などで考えていて場合分けが煩雑になってしまっていた.mod 20 で考えたらすっきりとした.

f:id:babcs2035:20181020220255p:plain