C++の練習を兼ねて, AtCoder Beginner Contest 154 の 問題D (D – Dice in Line) を解いてみた.
■感想.
1. 累積和を使う方法に気付けたので, 良かったと思う.
2. 引き続き, 過去問を振り返っていきたいと思う.
本家のサイトABC 154解説をご覧下さい.
■C++版プログラム(問題D／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 |
#include <bits/stdc++.h> using namespace std; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) double e[202020], ecum[202020]; int main(){ // 1. 入力情報. int N, K; scanf("%d %d", &N, &K); rep(i, N){ double p; scanf("%lf", &p); e[i] = (p + 1.0) / 2.0; // i番目のサイコロの期待値. } // 2. 累積和. rep(i, N) ecum[i + 1] = ecum[i] + e[i]; // 3. 出る目の合計の期待値の最大値は？ double ans = 0.0; rep(i, N - K + 1) ans = max(ans, ecum[i + K] - ecum[i]); // 4. 出力. printf("%.12lf\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 |
[入力例] 5 3 1 2 2 4 5 [出力例] 7.000000000000 ※AtCoderテストケースより [入力例] 4 1 6 6 6 6 [出力例] 3.500000000000 ※AtCoderテストケースより [入力例] 10 4 17 13 13 12 15 20 10 13 17 11 [出力例] 32.000000000000 ※AtCoderテストケースより [入力例] 20 5 5 6 11 11 3 18 8 18 7 13 6 18 2 14 17 15 3 19 12 18 [出力例] 36.500000000000 |
■参照サイト
AtCoder Beginner Contest 154