2019-12-30 ABC149 D - Prediction and Restriction 動的計画法(DP) 問題 提出コード 解法 次に出す手は、手前の手にのみ依存します。 よって、じゃんけんの出す手は、で割った余りごとに独立して考えることができます。 番目に出す手がであるときにおける、の手番についての得点の総和の最大値 とすると、答えは となります。 となります。 感想 貪欲でも解けるらしいのですが、証明を短時間で行うのが難しそうな上、DPの方が確実な気がします。 言われてみれば確かに…ってなりました。