AtCoder ABC 136 D Suche nach Breitenpriorität Gelöst in Ruby, Perl und Java

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Beginner Contest 136 D - Gathering Children Difficulty: 792

Dieses Thema, Breite Priorität Suche 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(' ')

Teilen Sie beispielsweise die Zeichenfolge "RRLLLLRLRRLL" in drei Teile: "RRLLLL" "RL" "RRLL".

Kinder werden sich im RL-Teil versammeln, also zähle ihn und baue ihn in das Array ein.

even.rb

  if (r + l).even?

Gerade und ungerade scheinen * Ruby * zu sein. 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 * erfordert viel Arbeit, um das Array zu initialisieren. Der Anfangswert des Typs * Java * int ist ** 0 **, aber die Flexibilität von * Ruby * ist hervorragend.

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

Außerdem konvertiert * Perl * implizit von einer Ganzzahl in eine reelle Zahl, sodass Sie sie mit der Funktion int abschneiden müssen.

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 * scheint es schwierig zu sein, einem Array von Ganzzahlen beizutreten, deshalb habe ich es in StringBuilder eingefügt.

Zusammenfassung

• Gelöstes ABC 136 D.
• Machen Sie sich mit Ruby vertraut
• Machen Sie sich mit Perl vertraut
• Machen Sie sich mit Java vertraut

Referenzierte Site

• Verschiedene Möglichkeiten, Zeichenfolgen in Java durch Kommas getrennt zu verketten *