mayokoex https://blog.hatena.ne.jp/mayokoex/ mayoko’s diary https://mayokoex.hatenablog.com/ yukicoder 感動しました。 問題 No.269 見栄っ張りの募金活動 - yukicoder 解法 想定解法とアイデアは変わりませんが, 計算量的に怪しい解法で通しました。一番大事なアイデアは, 「n 人目の人が前の人に比べて i 円支払うお金を増やしたら, それ以降の人はその i 円の分は絶対に増やさないといけないので, 全体としては (N-n)*i 円払うのと同じじゃん」ということです。dp[n][y] = (n 人目で残額が y 円になっているような場合の数)とします。このとき, 上の考えを使うと, dp[n][y] は, dp[n+1][y-i*(N-n)] (0 再帰で計算しました。計算量なんで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fmayokoex.hatenablog.com%2Fentry%2F2015%2F08%2F22%2F091536" title="yukicoder : No.269 見栄っ張りの募金活動 - mayoko’s diary" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-08-22 09:15:36 rich https://mayokoex.hatenablog.com/entry/2015/08/22/091536 1.0 100%