ABC163 D - Sum of Large Numbers
問題原文
問題要旨
の 個の数字が与えられる。
この中から 個以上の数を選ぶ時、その和としてありうるものの個数を求めよ。
解法
不要なものを頑張って引こうとすると地獄をみるよ!
こう言うのはちゃんと特殊な条件(今回だと 10^{100} とかいうバカでかい数)に注目して、ちぇんとレールに載るように考察を進めるのが大事。
バカでかい数がくっつくことに注目すると、「選んだ個数が異なる場合、和が等しくなることはない」ということがわかる。
ここから、 個選んだ場合にありうる和をそれぞれ求めたくなる。
で、例えば4つ選んだ場合を考えると、最大の和は大きい方から4つ取ったもので、最小の和は小さい方から4つ取ったものになる。その間の数は、数が連続していることから自由に調節できて全部作れる。
こういう計算を それぞれについてやればOK。
実装
シンプル。変に頭つかいたくないので からやってる。
N, K = map(int, input().split()) MOD = 10 ** 9 + 7 low, high = 0, 0 ans = 0 for x in range(1, N + 2): low += x - 1 high += N - x + 1 if x >= K: ans += (high - low + 1) ans %= MOD print(ans)
感想
問題よく見たら通り数のMODだった(和のMODの通り数のMODかと思って頭爆発してた、いやできるかもしれんけどわからん。なにもわからん。)
最近 Dで変にスピードを意識するあまり、明後日の方向に考察が進むことが多い気がしてかなしい。