Codeforces Round 780 (Div. 3) A – Vasya and Coins / B – Vlad and Candies を解いた記録
A – Vasya and Coins
問題の概要
1円硬貨が \(a\) 枚， 2円硬貨が \(b\) 枚ある．持っている硬貨を使ってピッタリ支払うことが不可能な最小の金額を出力せよ．
制約
- \(0 \leq a, b \leq 10^{8}\)
- 入力はすべて整数
解法
1円硬貨が0枚の場合は，どう頑張ってもピッタリ奇数円は支払えないので1円が答えです．
1円硬貨が1枚以上ある場合は，\(a+2b+1\)円が答えです．
実装例
B – Vlad and Candies
問題の概要
\(n\) 種類のキャンディがあり，\(i\) 種類目のキャンディは \(a_{i}\) 個ある．
下記のルールに従ってキャンディを食べるとき，すべてのキャンディを食べ切れるだろうか？
- 毎回1つのキャンディを食べる．
- キャンディの種類を選ぶとき，現時点で最もたくさんあるものを選ぶ．最もたくさんあるキャンディが複数種類ある場合は，任意の1種類を選ぶ．
- 同じ種類のキャンディを連続して食べることはできない．
制約
- \(1 \leq n \leq 2 \times 10^{5}\)
- \(1 \leq a_{i} \leq 10^{9}\)
- 入力はすべて整数
解法
キャンディが1種類しかない場合は，そのキャンディが2個以上あると詰みです．以下，キャンディが2種類以上あるときを考えます．
初期状態で一番たくさんあるキャンディの個数と2番目にたくさんあるキャンディの個数に着目しましょう．
この2種類のキャンディの個数の差が1以内であれば，2種類のキャンディを交互に食べ続けることができるので詰みません．
2以上の差がある場合は，ルールを守りながらキャンディを食べ続けることはできないので詰みです．