AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC163 D - Sum of Large Numbers

問題原文

atcoder.jp

問題要旨

 10^{100} + 0, 10^{100} + 1 ...  10^{100} + N N  + 1 個の数字が与えられる。
この中から  K 個以上の数を選ぶ時、その和としてありうるものの個数を求めよ。

  •   1 \leq N \leq 2 × 10^{5}

解法

不要なものを頑張って引こうとすると地獄をみるよ!

こう言うのはちゃんと特殊な条件(今回だと 10^{100} とかいうバカでかい数)に注目して、ちぇんとレールに載るように考察を進めるのが大事。
バカでかい数がくっつくことに注目すると、「選んだ個数が異なる場合、和が等しくなることはない」ということがわかる。

ここから、  x = K, K + 1, K +2 ... N + 1 個選んだ場合にありうる和をそれぞれ求めたくなる。
で、例えば4つ選んだ場合を考えると、最大の和は大きい方から4つ取ったもので、最小の和は小さい方から4つ取ったものになる。その間の数は、数が連続していることから自由に調節できて全部作れる。

こういう計算を  x それぞれについてやればOK。

実装

シンプル。変に頭つかいたくないので  x = 0 からやってる。

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で変にスピードを意識するあまり、明後日の方向に考察が進むことが多い気がしてかなしい。