C++の練習を兼ねて, AtCoder Beginner Contest 130 の 問題D (D – Enough Array) を解いてみた.
■感想.
1. 苦手な DP の訓練となったと思う.
2. 解答を見る前に, 解けたので, 及第点は取れたと思う.
本家のサイトABC 130解説をご覧下さい.
■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 32 33 34 35 36 37 38 |
#include <bits/stdc++.h> using namespace std; using LL = long long; const LL MAX = 1e5 + 1; LL dp[MAX], a[MAX], c[MAX]; int main() { // 1. 入力情報取得. LL N, K; scanf("%lld %lld", &N, &K); for(int i = 1; i <= N; i++) scanf("%lld", a + i), c[i] += c[i - 1] + a[i]; // 2. 連続部分列に含まれる全ての要素の値の和が, K以上のものを数える. // dp[i]: 位置 i までで, 条件を満たす部分列の個数. LL buf = 0; for(LL i = 1; i <= N; i++){ // 2-1. K以上 となったので, K以上 の 範囲を探索. if(c[i] >= K){ for(LL j = buf; j <= i; j++){ if(c[i] - c[j] >= K) continue; if(c[i] - c[j] < K){ // 前回分 dp[i - 1] に j個 を 加算. dp[i] = dp[i - 1] + j; buf = j - 1; break; } } } } // 3. 出力 ～ 後処理. // for(int i = 0; i <= N; i++) cout << dp[i] << " "; printf("%lld\n", dp[N]); 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 |
[入力例] 4 10 6 1 2 7 [出力例(debug版)] 0 0 0 0 2 2 ※AtCoderテストケースより [入力例] 3 5 3 3 3 [出力例(debug版)] 0 0 1 3 3 ※AtCoderテストケースより [入力例] 10 53462 103 35322 232 342 21099 90000 18843 9010 35221 19352 [出力例(debug版)] 0 0 0 0 0 2 8 14 20 27 36 36 ※AtCoderテストケースより [入力例] 27 12345 1111 2222 3333 4444 5555 6666 7777 8888 9999 111 222 333 444 555 666 777 888 999 11111 22222 33333 44444 55555 66666 77777 88888 99999 [出力例(debug版)] 0 0 0 0 0 3 7 13 20 28 36 44 52 60 68 76 85 94 103 120 140 161 183 206 230 255 281 308 308 [入力例] 20000 1234567890 99999 99998 99997 99996 99995 99994 99993 99992 99991 99990 99989 99988 99987 99986 99985 99984 99983 99982 99981 99980 99979 99978 99977 99976 99975 99974 99973 99972 99971 99970 ～(略, 99999 から 80000 までの数字 20000個)～ 80019 80018 80017 80016 80015 80014 80013 80012 80011 80010 80009 80008 80007 80006 80005 80004 80003 80002 80001 80000 [出力例] 19820696 |
■参照サイト
AtCoder Beginner Contest 130