ABC 401-500/ABC432C - Candy Tribulation - 競技プログラミング用 知識集積所

---

問題

ABC432C

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）※

考え方

各子供について、「何グラムの飴を与えることができるか？」を一覧していって、全員に共通の数字を探す方針ではとても間に合わない。
そこで、貪欲法※で探索範囲を絞る。

仮に、全員が1つ以上の小さい飴を持っている解があったとする。
この場合、これは最善の解ではない。
なぜなら、全員の小さな飴を1つずつ大きな飴に変えてあげることで、大きな飴を配る個数を増やせるからである。
したがって、誰かが大きな飴だけをもらっている方法だけ試せばよいという貪欲法※が成立する。
しかも、その「誰か」は明らかにもっとも個数の少ない子でしかありえない。
よって、全員の中から最も個数が少ない人を探し、その子に全部大きな飴を渡すパターンだけ考えて、うまくいけばそれが答え、ダメならどうやってもダメということになる。

この1パターンしか考えないならば、最小個数*yで全員に配るべき重さが確定する。
あとは、1人1人に対し、

• とりあえず全部小さい飴で渡す
• 小さい飴1つを大きい飴1つに変える（重さがy-x増える）ことを何回やれば目的の重さにできるか求める
• 不可能だった場合（増加させたい重さがy-xの倍数でない場合と、最初から目標の重さを超えていた場合）は失敗
• 可能だった場合は、渡した大きい飴の数を合計に加算していく

を繰り返せばいい。

解答例

解答例

注意点

long long型を用いること

入力例にもあるが、答えはint型の上限を超えることがある。

別解