[AtCoder] ABC 136 D – Gathering Children

2020年10月4日

問題

方針

子どもの移動の挙動

どのような文字列でも十分に移動を行うと、’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;
}