ABC163に参加してきました！（Java使用、ネタバレ注意！）

　今回もABCに参加してきたので、感想をば。結果から言うと、今回もC問題まで解いたのですが、解くまでにかかる時間が大分短くなって、19分で解けるようになりました！（今回は難易度が低かったし、サーバーの問題でunratedになったから意味ないとか言わんでくれ.....）

　さて、おそらくD問題の一般解の求め方の方がA、B、C問題より需要がありそうなので（ていうか僕自身も忘れたくないので）、今回はその求め方を書いていきます。

　本番中は眠すぎて、何言ってんだコイツとおｍ何をすればいいのかわからなかったんですが、翌日きちんと解いてみたらそんなに難しくはありませんでした。

リンク：https://atcoder.jp/contests/abc163/tasks/abc163_d

　まずは、問題文。

 ${10}^{100}$, ${10}^{100}+1$, ..., ${10}^{100}+N$ の $N+1$ 個の数があります。

この中から $K$ 個以上の数を選ぶとき、その和としてあり得るものの個数を $mod({10}^9+7)$ で求めてください。

 K個の数字を選んだ時に作れる和の種類を答えろとのことなので、多分各Kにおける、（最大値ー最大値）＋１の値を足し合わせていけばよいのだろうと。入力例を見ても、ダブっているものは引かれていました。

入力例 1 Copy

Copy

3 2

出力例 1 Copy

Copy

10

以下の $10$ 通りが考えられます。

• $\left({10}^{100}\right)+({10}^{100}+1)=2\times {10}^{100}+1$
• $\left({10}^{100}\right)+({10}^{100}+2)=2\times {10}^{100}+2$
• $\left({10}^{100}\right)+({10}^{100}+3)=({10}^{100}+1)+({10}^{100}+2)=2\times {10}^{100}+3$
• $({10}^{100}+1)+({10}^{100}+3)=2\times {10}^{100}+4$
• $({10}^{100}+2)+({10}^{100}+3)=2\times {10}^{100}+5$
• $\left({10}^{100}\right)+({10}^{100}+1)+({10}^{100}+2)=3\times {10}^{100}+3$
• $\left({10}^{100}\right)+({10}^{100}+1)+({10}^{100}+3)=3\times {10}^{100}+4$
• $\left({10}^{100}\right)+({10}^{100}+2)+({10}^{100}+3)=3\times {10}^{100}+5$
• $({10}^{100}+1)+({10}^{100}+2)+({10}^{100}+3)=3\times {10}^{100}+6$
• $\left({10}^{100}\right)+({10}^{100}+1)+({10}^{100}+2)+({10}^{100}+3)=4\times {10}^{100}+6$

 ちょっとはみ出てるのは許してください。一応、手で全部書き出してみたのですが、各Kに対する最小値と最大値の間の値は全種類作り出すことができます！ちなみに、異なるK内の値同士でダブルことがあるかもしれないとも一瞬頭をよぎりましたが、制約が下記の通りで、和の値の桁数高々10^10だった（ミスってたらコメください）ので、各Kごとに足し合わせていくだけで大丈夫。

制約

• $1\le N\le 2\times {10}^5$
• $1\le K\le N+1$
• 入力は全て整数

そんなこんなで書いたコードがこちら。

1. import java.util.*;
2. import java.util.ArrayDeque;
3. import java.util.Queue;
4. import java.math.RoundingMode;
5. import java.math.BigDecimal;
6.  
7.  
8.  
9. public class Main{
10. public static void main(String[] args){
11. Scanner sc = new Scanner(System.in);
12. long n = sc.nextLong();
13. long k = sc.nextLong();
14. long mod = 1000000007L;
15. long sum = 0;
16. long min = 0;
17. long max = 0;
18. for(long i = k; i <= n+1; i++) {
19. min = i*(i-1)/2;
20. max = i*(2*n-(i-1))/2;
21. sum+=(max-min+1)%mod;
22. }
23. System.out.println(sum%mod);
24. }
25. }

きちんと出力する時点でもう１度modの処理をしとくのもお忘れなく！

　 最近はこんな感じのきちんと題意を理解すれば実装はBレベルな問題が多いですな～。頭が柔らかくなるように引き続き頑張ります！