yukicoder No.269 見栄っ張りの募金活動

• 問題
• AC

最初に$S$から$0+K+...+(N-1)K = N(N-1)K/2$を引いておくと、１つ前の生徒の金額以上に寄付をするという問題に変わる。定式化すると、総和が$S-N(N-1)K/2$になるような長さ$N$の数列で、単調非減少であるものを数え上げればよいことになる。これは分割数、つまり非負整数$S-N(N-1)K/2$を$N$個の非負整数に分割する方法を数え上げることに等しい。¹ ${\mathcal O}(SN)$。

---

1. $S < N(N-1)K/2$の場合の答えは$0$である。 ↩︎