ねむーの日記~AtCoderな日々~

福岡に住むプログラミング好きのブログです!

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.はじめに

今回も、プログラミング言語C#を使用しています。

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.最後に

初めての水パフォでした!

嬉しいですね~