Ruby と Perl と Java で解く AtCoder ABC 136 D 幅優先探索

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest 136 D - Gathering Children](https://atcoder.jp/contests/abc136/tasks/abc136_d)*
<font color="brown">Difficulty: 792</font>

今回のテーマ、幅優先探索
# Ruby
```ruby.rb
s = gets.chomp
f, c = 0, 0
p = []
0.upto(s.size - 1) do |i|
  if s[i] == 'R' && f == 1
    f = 0
    p.push(c)
    c = 0
  elsif s[i] == 'L' && f == 0
    f = 1
    p.push(c)
    c = 0
  end
  c += 1
  p.push(c) if s.size - 1 == i
end
ans = Array.new(s.size, 0)
pos = 0
while p.size > 0
  r = p.shift
  l = p.shift
  if (r + l).even?
    pos += r
    ans[pos - 1] = (r + l) / 2
    ans[pos] = (r + l) / 2
    pos += l
  elsif (r.even?)
    pos += r
    ans[pos - 1] = (r + l) / 2
    ans[pos] = (r + l) / 2 + 1
    pos += l
  else
    pos += r
    ans[pos - 1] = (r + l) / 2 + 1
    ans[pos] = (r + l) / 2
    pos += l
  end
end
puts ans.join(' ')
```
例えば、文字列 `RRLLLLRLRRLL` を `RRLLLL` `RL` `RRLL` の３つに分割して考えます。

|RRLLLL|RL|RRLL|
|:--:|:--:|:--:|
|111111|11|1111|
|033000|11|0220|
子供たちは　`RL` の部分に集まりますので、それをカウントし配列に組み込みます。

```even.rb
  if (r + l).even?
```
even や odd は *Ruby* らしいですよね。
# Perl
```perl.pl
use v5.18; # strict say state

chomp (my $s = <STDIN>);
my ($f, $c) = (0, 0);
my @p;
for my $i (0..length($s)-1) {
  if (substr($s, $i, 1) eq 'R') {
    if ($f == 1) {
      push @p, $c;
      $f = 0;
      $c = 0;
    }
  } else {
    if ($f == 0) {
      push @p, $c;
      $f = 1;
      $c = 0;
    }
  }
  $c++;
  push @p, $c if $i == length($s) - 1;
}
my @ans;
for my $i (0..length($s)-1) {
  $ans[$i] = 0;
}
my $pos = 0;
while (@p) {
  my $r = shift @p;
  my $l = shift @p;
  if (($r + $l) % 2 == 0) {
    $pos += $r;
    $ans[$pos-1] = ($r + $l) / 2;
    $ans[$pos] = ($r + $l) / 2;
    $pos += $l;
  } elsif ($r % 2 == 0) {
    $pos += $r;
    $ans[$pos-1] = int(($r + $l) / 2);
    $ans[$pos] = int(($r + $l) / 2) + 1;
    $pos += $l;
  } else {
    $pos += $r;
    $ans[$pos-1] = int(($r + $l) / 2) + 1;
    $ans[$pos] = int(($r + $l) / 2);
    $pos += $l;
  }
}
say join(' ', @ans);
```
*Perl* は配列の初期化に一手間必要です。
*Java* の int 型の初期値は **0** ですが、*Ruby* の柔軟性が光ります。

```array.pl
ans = Array.new(s.size, 0)       # Ruby

my @ans;                         # Perl
for my $i (0..length($s)-1) {
  $ans[$i] = 0;
}

int ans[] = new int[s.length()]; # Java
```
また、*Perl* は整数から実数への変換を暗黙的に行いますので、int 関数で切り捨てる必要があります。

```int.pl
    ans[pos] = (r + l) / 2           # Ruby
    $ans[$pos] = int(($r + $l) / 2); # Perl
    ans[pos] = (r + l) / 2;          # Java

```
# Java
```java.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        sc.close();
        int f = 0, c = 0;
        Queue<Integer> que = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            if (s.substring(i, i + 1).equals("R")) {
                if (f == 1) {
                    f = 0;
                    que.add(c);
                    c = 0;
                }
                c++;
            } else {
                if (f == 0) {
                    f = 1;
                    que.add(c);
                    c = 0;
                }
                c++;
                if (i == s.length() - 1) {
                    que.add(c);
                }
            }
        }
        int ans[] = new int[s.length()];
        int pos = 0;
        while (que.size() > 0) {
            int r = que.poll();
            int l = que.poll();
            if ((r + l) % 2 == 0) {
                pos += r;
                ans[pos - 1] = (r + l) / 2;
                ans[pos] = (r + l) / 2;
                pos += l;
            } else if (r % 2 == 0) {
                pos += r;
                ans[pos - 1] = (r + l) / 2;
                ans[pos] = (r + l) / 2 + 1;
                pos += l;
            } else {
                pos += r;
                ans[pos - 1] = (r + l) / 2 + 1;
                ans[pos] = (r + l) / 2;
                pos += l;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < (s.length() * 2 - 1); i++) {
            if (i % 2 == 0) {
                sb.append(ans[i / 2]);
            } else {
                sb.append(" ");
            }
        }
        System.out.println(sb);
    }
}
```
*Java* では整数の配列を join するのが大変らしいので、StringBuilder に入れています。

||Ruby|Perl|Java|
|:--:|:--:|:--:|:--:|
|コード長|685 Byte|940 Byte|1841 Byte|
|実行時間|103 ms|143 ms|203 ms|
|メモリ|5244 KB|16000 KB|32476 KB|
# まとめ
+ ABC 136 D を解いた
+ Ruby に詳しくなった
+ Perl に詳しくなった
+ Java に詳しくなった

参照したサイト
*[Javaでカンマ区切りで文字列連結するいくつかの方法](https://qiita.com/shisama/items/b27d16b3aeb1baf055b1)*