自分用メモ AtCoder Beginner Contest 017 D - サプリメント

D: サプリメント - AtCoder Beginner Contest 017 | AtCoder

複数のサプリメントを食べる方法を考える.

1,2,3,4,3,5,2,6,5,6,7みたいな場合

0 1 2 3 4 5 6  7 8 9 10 個食べる組み合わせ

1 1 2 4 8

今日何個食べるかを考えると、自分から左へ自分を含まないところまで足して考えられる。

    4 - 4 

  34 - 2       

234 - 1

1234-1

だから4は8

/////////////////////////////////////////////////////////////////////////

   1,2,3,4,3,5,2,6,5,6,7

0 1 2 3 4 5 6  7 8 9 10 個食べる組み合わせ

1 1 2 4 8 

5個目の3について考えると、

食べる - 組み合わせ

3 - 8

43 - 4

343とは食べれないので12

ここまでやって右から左への合計を求める、かつ左端はどんどん右へ近づくので、しゃくとり方を思いつきたい

これまでの和を持っておき、もし、自分の食べれる範囲指定している中に同じものがあればそれの左の部分を除外する

なぜ左かといえば、それ自身が持っている数は、それの左までの結果だから。

1. public static void main(String args)
2. {
3. N = sc.nextInt();
4. M = sc.nextInt();
5. int f = sc.nextIntArrayDec(N);
6. int used = new int[M + 1];//つながってるもの
7. long dp = new long[N + 1];//i個たべる組み合わせ
8. dp[0] = 1;
9. long sum = 1;
10. int li = 0;
11. for (int i = 1; i < N + 1; i++)
12. {
13. used[f[i - 1]]++;
14. while (used[f[i - 1]] > 1)
15. {
16. used[f[li]]--;
17. sum = diffMod(sum,dp[li]);
18. li++;
19. }
20. dp[i] = sum;
21. sum = sumMod(sum, dp[i]);
22. }
23. System.out.println(dp[N]);
24.  
25. }