九州大学プログラミングコンテスト2018:B - Tapu & Tapi
問題
解法
1円,10 円,100 円の順番に分ける枚数を決めていく.この時,各硬貨の枚数が偶数になれば条件を満たす.ここで,各硬貨の枚数に mod 20 をとる.なぜならば,1つ上の硬貨に位上げしても,位上げの枚数は必ず偶数になり,1つ上の硬貨の枚数が奇数であったときにもその効果の枚数が 10 以上あれば1つ上の硬貨の枚数を偶数にすることが出来るから.これを 1 -> 10 円,10 -> 100 円の2回考え,どれかの種類の硬貨の枚数を偶数にすることが出来なくなったら No で出来たら Yes.
解答
5 WA してしまった.ずっと mod 10 などで考えていて場合分けが煩雑になってしまっていた.mod 20 で考えたらすっきりとした.