Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search

Introduction

• AtCoder Problems * Use Recommendations to solve past problems. Thanks to AtCoder and AtCoder Problems.

This theme

AtCoder Beginner Contest 136 D - Gathering Children Difficulty: 792

This theme, breadth-first search 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(' ')

For example, consider dividing the string RRLLLLRLRRLL into three parts: RRLLLL RL`` RRLL.

Children will gather in the RL part, so count it and incorporate it into the array.

even.rb

  if (r + l).even?

Even and odd seem to be * 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 * takes a lot of work to initialize the array. The initial value of the * Java * int type is ** 0 **, but the flexibility of * Ruby * shines.

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

Also, * Perl * implicitly converts from an integer to a real number, so you need to truncate it with the int function.

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);
    }
}

In * Java *, it seems to be difficult to join an array of integers, so I put it in StringBuilder.

Summary

• Solved ABC 136 D
• Become familiar with Ruby
• Become familiar with Perl
• Become familiar with Java

Referenced site

• Several ways to concatenate strings separated by commas in Java *