Recherche de priorité de largeur AtCoder ABC 136 D résolue en Ruby, Perl et Java

introduction

• Utilisez les recommandations dans AtCoder Problems * pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest 136 D - Gathering Children Difficulty: 792

Ce thème, recherche de priorité de largeur 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(' ')

Par exemple, envisagez de diviser la chaîne «RRLLLLRLRRLL» en trois parties: «RRLLLL» «RL» RRLL ».

Les enfants se rassembleront dans la partie RL, alors comptez-la et incorporez-la dans le tableau.

even.rb

  if (r + l).even?

Pair et impair semblent être * 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 * nécessite beaucoup de travail pour initialiser le tableau. La valeur initiale du type * Java * int est ** 0 **, mais la flexibilité de * Ruby * brille.

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

De plus, * Perl * convertit implicitement un entier en un nombre réel, vous devez donc le tronquer avec la fonction 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);
    }
}

En * Java *, il semble difficile de joindre un tableau d'entiers, donc je l'ai mis dans StringBuilder.

Résumé

• Résolu ABC 136 D
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Perl
• Familiarisez-vous avec Java

Site référencé

• Plusieurs façons de concaténer des chaînes en Java séparées par des virgules *