AtCoder Beginner Contest 281 D問題 Max Multiple
問題
提出解答
問題の概要
個の整数
から
個の整数を選び出す方法のうち, その
個の総和が
の倍数になる取り出し方は存在するか? 存在するならば
の倍数になるような取り出し方のうち, その総和の最大値を求めよ.
制約
解法
動的計画法で解くことにする. に対して,
を以下で定義する.
から
個選び出す方法のうち,
で割った余りが
であるような選び方のうち, その総和の最大値 (存在しないならば
).
自明なケースは のときで,
である.
更新については を選択するか, しないかで場合分けすることによって,
となる.
これによる最終解答は である. 計算量は
時間である.