AtCoder Beginner Contest 136 D - Gathering Children
朝からオープンキャンパスバイトで眠さMAX、ねむーです。
今回はAtCoder(https://atcoder.jp/contests/abc136/tasks/abc136_d)にて開催されました、AtCoder Beginner Contest 136 D問題「D - Gathering Children」の問題と僕との戦闘記です。
0.はじめに
1.問題文
マスの情報を表す、L と R で構成された文字列 S が与えられます。
文字列 S の長さを N としたとき、 N 個のマスが左右一列に並んでおり、左から i 番目のマスには S の左から i 番目の文字が書かれています。
ただし、左端のマスには必ず R、右端のマスには必ず L が書かれています。
はじめ、各マスには 1 人の子どもが居ます。
子どもたちはそれぞれ次の規則に従った移動を 10100 回行います。
- 今居るマスに書かれた文字に従って 1 マス移動する。すなわち、今居るマスに書かれた文字が L のとき左隣のマスに、R のとき右隣のマスに移動する。
10100 回の移動の後に各マスに居る子どもの人数を求めてください。
2.制約
- S は長さ 2 以上 105 以下の文字列であり、 S の各文字は L または R である。
- S の 1 文字目は R、 N 文字目は L である。
3.入力例
- 入力
RRRLLRLLRRRLLLLL
- 出力
0 0 3 2 0 2 1 0 0 0 4 4 0 0 0 0
4.初見の感想
- 10100回計算するのは無謀すぎる
- 部分列が「RL」の部分に子供の数字が集中する
- 部分列「RL」の左にRがいくつあるか、及び「RL」の右にLがいくつあるかがわかればよい
5.学びポイント
- for文でマスを左から1回ループして最初「R」のマスから出発して最終的に「RL」に移動する人数を数える
- for文でマスを右から1回ループして最初「L」のマスから出発して最終的に「RL」に移動する人数を数える
6.コードと簡単な解説
using System; using System.Collections.Generic; using System.Linq; class Program { static void Main(string[] args) { string S = Console.ReadLine(); int[] ans= new int[S.Length]; int right=0, left = 0; //左からループ for(int i = 0; i < S.Length-1; i++) { //人数カウント if (S[i] == 'R' && S[i + 1] == 'R') { ans[i] = 0;right++; } //Rで流れてきた分+RLマスにもともといた人1人分 if(S[i] == 'R' && S[i + 1] == 'L') { ans[i] = right / 2+1; ans[i + 1] = right / 2 + right%2+1; right = 0; } } for (int i = S.Length-1; i >0 ; i--) { if (S[i-1] == 'L' && S[i] == 'L') { ans[i] += 0; left++; } //Lで流れてきた分+RLマスにもともといた人1人分 if (S[i-1] == 'R' && S[i] == 'L') { ans[i-1] += left / 2 + left % 2; ans[i] += left / 2; left = 0; } } Console.WriteLine(string.Join(" ", ans)); } }
7.最後に
初めての水パフォでした!
嬉しいですね~