Posted by 概要
コンテストの日から少し時間が空いてしまいましたが、2週間前？くらいに参加したABC163(2020/4/19)で相変わらずD問題がクリアすることができなかったので、復習のために解説を確認しながら、概念を理解してACするプログラムを実装しました。
問題
https://atcoder.jp/contests/abc163/tasks/abc163_d
解説
https://img.atcoder.jp/abc163/editorial.pdf
動画(Youtube)
理解
まずM個の数である10^100の部分は非常に大きい数であるため、選択する数が変わると合計の値は他の数の組み合わせとは重複しないので、各選択した数の組み合わせによる合計値を求めれば算出可能となります。
本問題でキーとなる部分は、M個からK個選ぶ場合の最大値は大きい方からK個選ぶ場合であり、最小値は小さい方からK個選ぶ場合となり、これらの最大値と最小値の間の値は全てを組み合わせで生成できるという点となります。したがって、作成できる数の総和は最大値-最小値で算出できます。
次に、2つの連続するrからlまでの数の合計は、(l+r)*(r-l+1)/2で求めることができます。というポイントを抑えて実装すると下記のようになりました。
実装
N, K = map(int, input().split())
def sumLR(l, r):
return (l+r)*(r-l+1)//2
mod = 10**9 + 7
count = 0
for n in range(K, N+2):
max = sumLR(N-n+1, N)
min = sumLR(0, n-1)
count += max - min + 1
count %= mod
print(count)