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

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Beginner Contest 136 D - Gathering Children
Difficulty: 792

今回のテーマ、幅優先探索

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でカンマ区切りで文字列連結するいくつかの方法