AtCoder Beginner Contest 357 における A から D 問題の解法解説
問題A: Sanitizer
N人の人が順番に手を消毒します。各人が必要とする消毒液の量 $H_i$ が与えられ、合計 $M$ 単位の消毒液があるとき、何人目までが完全に手を消毒できるかを求める問題です。
実装としては、配列に格納された各 $H_i$ を順に累積し、その合計が $M$ を超えた時点のインデックスを確認します。累積和が $M$ を超えない場合は、全員が消毒可能です。
#inclu ...
7月1日 16:24 投稿
桁の和がsとなるn桁の正整数の個数を求める
これは条件付きの正整数分割問題であり、直接的な計算式は存在しません。
小規模な場合は全探索が可能です。数百桁規模になると動的計画法が有効です。しかし数千桁規模では動的計画法でも数十分から数時間要します。さらに万桁規模になると、時間・空間的な制約によりPCでの計算は不可能になります。
「挿入法と包含排除原理の組み合わせ」が強力な手法です。
核心となる ...
5月12日 17:53 投稿