■感想.
1. 方針が見えなかったので, 解説を参照して, 実装した.
2. 最初, testcase_01等 で, TLE となったが, while文 の 終了条件が不足していたので, 追加した.
3. 幸福の最大人数は, (N – 1)人 のはずなので, やや強引だと思われるが, min(ans, N – 1) の 制約条件 を 追加した.
※while文で, 幸福の最大人数の制約条件を追加する方法が分からなかったため.
本家のサイトABC 140解説をご覧下さい.
■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 39 40 41 42 43 44 |
// 解き直し. // ABC 140解説. // https://img.atcoder.jp/abc140/editorial.pdf #include <bits/stdc++.h> using namespace std; int main(){ // 1. 入力情報取得. int N, K; scanf("%d %d", &N, &K); char c[111111]; scanf("%s", c); // 2. 解説通り. // 赤印: r0, r, rn int r0 = (c[0] == 'L') ? 1 : 0; // c[0] が 'L' の 場合は, r0 = 1 を 設定. int rn = (c[N - 1] == 'R') ? 1 : 0; // c[N - 1] が 'R' の 場合は, rn = 1 を 設定. int r = 0, ans = 0; for(int i = 1; i < N; i++){ if(c[i - 1] == 'R' && c[i] == 'L') r++; // 赤印加算. if(c[i - 1] == c[i]) ans++; // 'LL' or 'RR' の 場合. } // printf("r0=%d r=%d rn=%d ans=%d\n", r0, r, rn, ans); // 3. 幸福の最大人数を計算. // 操作K回で, 幸福である人を増加. while(1){ if(K > 0 && r > 0) ans += 2, r--, K--; if(K > 0 && r == 0 && r0 > 0) ans++, r0--, K--; if(K > 0 && r == 0 && rn > 0) ans++, rn--, K--; // testcase_01等 の TLE対応. if(K == 0) break; if(r == 0 && r0 == 0 && rn == 0) break; if(ans >= N - 1) break; } // 4. 出力 ~ 後処理. // 幸福の最大人数は, N - 1人 の はず. ans = min(ans, N - 1); printf("%d\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 49 50 51 52 53 54 55 56 57 58 59 60 61 |
[入力例] 6 1 LRLRRL [出力例(debug版)] r0=1 r=2 rn=0 ans=1 3 ※AtCoderテストケースより [入力例] 13 3 LRRLRLRRLRLLR [出力例(debug版)] r0=1 r=4 rn=1 ans=3 9 ※AtCoderテストケースより [入力例] 10 1 LLLLLRRRRR [出力例(debug版)] r0=1 r=0 rn=1 ans=8 9 ※AtCoderテストケースより [入力例] 9 2 RRRLRLRLL [出力例(debug版)] r0=0 r=3 rn=0 ans=3 7 ※AtCoderテストケースより [入力例] 6 2 LRLRRL [出力例(debug版)] r0=1 r=2 rn=0 ans=1 5 ※実際, LRLRRL = L "RLRR" L -> L "LRLL" L = LL "R" LLL -> LL "L" LLL = LLLLLL となり, 幸福の最大人数 5人 に到達することが分かる. [入力例] 30 5 LRLRRLRLLRLRLLRRLRLRRRRLRLLRLR [出力例(debug版)] r0=1 r=10 rn=1 ans=8 18 ※実際, ① L "RL" RRLRLLRLRLLRRLRLRRRRLRLLRLR -> L "LR" RRLRLLRLRLLRRLRLRRRRLRLLRLR ② LLRRR "LRLL" RLRLLRRLRLRRRRLRLLRLR -> LLRRR "RRLR" RLRLLRRLRLRRRRLRLLRLR ③ LLRRRRR "LRRL" RLLRRLRLRRRRLRLLRLR -> LLRRRRR "RLLR" RLLRRLRLRRRRLRLLRLR ④ LLRRRRRRLLRRLLRRL "RLRRRR" LRLLRLR -> LLRRRRRRLLRRLLRRL "LLLLRL" LRLLRLR ⑤ LLRRRRRRLLRRLLRRLLLLL "RLLR" LLRLR -> LLRRRRRRLLRRLLRRLLLLL "LRRL" LLRLR 上記から, LLRRRRRRLLRRLLRRLLLLLLRRLLLRLR であり, 1 + 5 + 1 + 1 + 1 + 1 + 5 + 1 + 2 = 18 と集計出来るので, 幸福である人 18人 に到達することが分かる. |
■参照サイト
AtCoder Beginner Contest 140