C++の練習を兼ねて, AtCoder Grand Contest 008 の 問題B (B – Contiguous Repainting) を解いてみた.
■感想.
1. 解説を見る前に解けたので, とりあえず良かったと思う.
2. 一番最後に塗った, 連続K個のマス以外のマスは, マスの色を自由に決定可能に見えたので, その方針で実装して, AC版となった.
3. 引き続き, 大量に残っている未着手の問題を, 時間見つけて復習していきたいと思う.
本家のサイトAGC 008 Editorialをご覧下さい.
■C++版プログラム(問題B／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 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 |
#include <bits/stdc++.h> using namespace std; using LL = long long; LL A[123456], kPlus[123456], kTotal[123456]; int main(){ // 1. 入力情報取得. int N, K; scanf("%d %d", &N, &K); LL pTotal = 0; for(int i = 0; i < N; i++){ scanf("%lld", &A[i]); if(A[i] > 0) pTotal += A[i]; } // 2. プラスのみの累積和, 符号に依らない累積和 を 保存. // ex. // kPlus[4] は, A[0] ～ A[4] で, プラスのものだけを合計. // kTotal[4] は, A[0] ～ A[4] を合計. kPlus[0] = (A[0] > 0) ? A[0] : 0; kTotal[0] = A[0]; for(int i = 1; i < N; i++){ // kPlus更新. if(A[i] > 0) kPlus[i] += kPlus[i - 1] + A[i]; else kPlus[i] = kPlus[i - 1]; // kTotal更新. kTotal[i] += kTotal[i - 1] + A[i]; } // for(int i = 0; i < N; i++) printf("%lld ", kPlus[i]); // printf("\n"); // for(int i = 0; i < N; i++) printf("%lld ", kTotal[i]); // printf("\n"); // 3. スコアの最大値を計算. LL ans = 0; for(int i = K - 1; i < N; i++){ LL kp = (i > K - 1) ? kPlus[i] - kPlus[i - K] : kPlus[i]; LL kt = (i > K - 1) ? kTotal[i] - kTotal[i - K] : kTotal[i]; // K個連続で, 黒色にする場合. ans = max(ans, pTotal - kp + kt); // K個連続で, 白色にする場合. ans = max(ans, pTotal - kp + 0); } // 4. 出力. printf("%lld\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 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 |
[入力例] 5 3 -10 10 -10 10 -10 [出力例(debug版)] 0 10 10 20 20 -10 0 -10 0 -10 10 ※AtCoderテストケースより [入力例] 4 2 10 -10 -10 10 [出力例(debug版)] 10 10 10 20 10 0 -10 0 20 ※AtCoderテストケースより [入力例] 1 1 -10 [出力例(debug版)] 0 -10 0 ※AtCoderテストケースより [入力例] 10 5 5 -4 -5 -8 -4 7 2 -4 0 7 [出力例(debug版)] 5 5 5 5 5 12 14 14 14 21 5 1 -4 -12 -16 -9 -7 -11 -11 -4 17 ※AtCoderテストケースより [入力例] 32 8 1 -4 1 -4 2 -1 3 -5 6 -2 3 -7 3 0 9 -5 0 -4 8 -8 0 -1 6 -8 8 -7 2 -4 2 0 9 -7 [出力例(debug版)] 1 1 2 2 4 4 7 7 13 13 16 16 19 19 28 28 28 28 36 36 36 36 42 42 50 50 52 52 54 54 63 63 1 -3 -2 -6 -4 -5 -2 -7 -1 -3 0 -7 -4 -4 5 0 0 -4 4 -4 -4 -5 1 -7 1 -6 -4 -8 -6 -6 3 -4 56 |
■参照サイト
AtCoder Grand Contest 008