[AtCoder] ABC 136 D – Gathering Children
問題
方針
子どもの移動の挙動
どのような文字列でも十分に移動を行うと、’RL’ または 'LR’ という二つのマスを行き来することになります。また、’RL’ という文字列が与えれたとき、初めに 'R’ にいた子どもは、偶数回の移動で 'R’ にいることになるので、\( 10^{100} \) 回の移動では、’R’ にいることになります。
各マスの情報
各マスのどのような情報が知りたいかというと、マス \( i \) を含めて右側の最も近い 'R’ の要素番号 \( i_r \) と左側の最も近い 'L’ の要素番号 \( i_l \) です。
マス \( i \) が 'R’ のとき、マス \( i_l \) まで右側に進む事になり、あとは 'RL’ という文字を行き来するだけになります。したがって、\( i_l – i\) が偶数ならば、マス \( i_l \) にいることになり、奇数ならば \( i_l – 1 \) にいることになります。
一方で、マス \( i \) が 'L’ のとき、マス \( i_r \) まで左側に進む事になり、あとは 'LR’ という文字を行き来するだけになります。したがって、\( i – i_r \) が偶数ならば、マス \( i_r \) にいることになり、奇数ならば \( i_r + 1 \) にいることになります。
コード
#include <bits/stdc++.h> using namespace std; typedef long long ll; struct Data { int r, l, k; }; int main() { string S; cin >> S; int n = S.length(); vector<Data> d(n); for (int i = 0; i < n; i++) { if (S[i] == 'R') { d[i].k = 0; } else { d[i].k = 1; } } d[0].r = 0; for (int i = 1; i < n; i++) { if (S[i] == 'R') { d[i].r = i; } else { d[i].r = d[i - 1].r; } } d[n - 1].l = n - 1; for (int i = n - 2; i >= 0; i--) { if (S[i] == 'L') { d[i].l = i; } else { d[i].l = d[i + 1].l; } } int cnt[n]{}; for (int i = 0; i < n; i++) { int g; if (d[i].k == 0) { g = d[i].l - i; if (g % 2 == 0) { cnt[d[i].l]++; } else { cnt[d[i].l - 1]++; } } else { g = i - d[i].r; if (g % 2 == 0) { cnt[d[i].r]++; } else { cnt[d[i].r + 1]++; } } } for (int i = 0; i < n; i++) { if (i == n - 1) { cout << cnt[i] << "\n"; } else { cout << cnt[i] << " "; } } return 0; }
ディスカッション
コメント一覧
まだ、コメントがありません