C++の練習を兼ねて, AtCoder Beginner Contest 136 の 問題D (D – Gathering Children) を解いてみた.
■感想.
1. 解答を見る前に, 解けたので, 及第点取れたと思う.
2. 1グーゴル(巨大な偶数)回後の位置を, 初期位置のマスの文字(及び位置) と 方向転換するマスの位置との関係から, 偶奇に場合分けして把握できたので, 良かったと思う.
本家のサイトABC 136解説をご覧下さい.
■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 45 46 47 48 49 50 |
#include <bits/stdc++.h> using namespace std; const int MAX = 123321; char S[MAX]; int nextL[MAX], nextR[MAX], goal[MAX], ans[MAX]; int main(){ // 1. 入力情報取得. scanf("%s", S); int l = strlen(S); // 2. 各初期位置について, 以下の情報を保存(0-index). // 2-1. 初期位置に, 'R' が記載されていたとして, 次に, 'L' が 始めて出現するケース. int posL = -1; for(int i = l - 1; i >= 0; i--){ if(S[i] == 'L') posL = i; nextL[i] = posL; } // 2-2. 初期位置に, 'L' が記載されていたとして, 次に, 'R' が 始めて出現するケース. int posR = -1; for(int i = 0; i < l; i++){ if(S[i] == 'R') posR = i; nextR[i] = posR; } // 3. 各マスについて, 1グーゴル回後の位置を計算. // 初期位置が, 'R' or 'L' で 分岐. for(int i = 0; i < l; i++){ if(S[i] == 'R'){ int dist = nextL[i] - i; if(dist % 2 == 0) goal[i] = nextL[i]; else goal[i] = nextL[i] - 1; } if(S[i] == 'L'){ int dist = i - nextR[i]; if(dist % 2 == 0) goal[i] = nextR[i]; else goal[i] = nextR[i] + 1; } } // 4. 移動後の位置情報が, goalに保存されているので集計. for(int i = 0; i < l; i++) ans[goal[i]]++; // 5. 出力 ～ 後処理. for(int i = 0; i < l; i++) printf("%d ", ans[i]); 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 |
[入力例] RRLRL [出力例] 0 1 2 1 1 ※AtCoderテストケースより [入力例] RRLLLLRLRRLL [出力例] 0 3 3 0 0 0 1 1 0 2 2 0 ※AtCoderテストケースより [入力例] RRRLLRLLRRRLLLLL [出力例] 0 0 3 2 0 2 1 0 0 0 4 4 0 0 0 0 ※AtCoderテストケースより [入力例] RLRRLLRRRLLLRRRRLLLLRRRRRLLLLLRRRRRRLLLLLLRRRRRRRLLLLLLLRRRRRRRRLLLLLLLLRRRRRRRRRLLLLLLLLLRRRRRRRRRRLLLLLLLLLL [出力例] 1 1 0 2 2 0 0 0 3 3 0 0 0 0 0 4 4 0 0 0 0 0 0 0 5 5 0 0 0 0 0 0 0 0 0 6 6 0 0 0 0 0 0 0 0 0 0 0 7 7 0 0 0 0 0 0 0 0 0 0 0 0 0 8 8 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 10 10 0 0 0 0 0 0 0 0 0 |
■参照サイト
AtCoder Beginner Contest 136