Ruby と Perl と Java と Python で解く AtCoder diverta 2019 Programming Contest C 文字列操作

はじめに

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

今回のお題

AtCoder diverta 2019 Programming Contest C - AB Substrings
Difficulty: 911

今回のテーマ、文字列操作

Ruby

与えられた文字列を、BXA BX XA でそれぞれカウントします。
この内、BXA は BXA 同士で合体しても又 BXA になりますので、まずこれを処理して、BXA の個数を減らします。
同様に、BXA と BX が合体しても BX、XA と BXA が合体しても XA ですので、それを利用してカウントします。

ruby.rb

n = gets.to_i
w = x = y = z = 0
n.times do |i|
  s = gets.chomp
  w += s.scan("AB").size
  if s[0] == "B"
    if s[-1] == "A"
      x += 1
    else
      y += 1
    end
  elsif s[-1] == "A"
    z += 1
  end
end
if x > 1
  w += x - 1
  x = 1
end
if [x, y, z].max == y
  w += x
  w += z
elsif [x, y, z].max == z
  w += x
  w += y
end
puts w

scan.rb

  w += s.scan("AB").size

Ruby の場合、s.scan("AB").sizeでABの個数をカウントしています。

string.rb

    if s[-1] == "A"

[-1] で最後尾の文字にアクセスできるのが凄いですね。

Python

python.py

import re

n = int(input())
w = x = y = z = 0
for i in range(n):
    s = input()
    t = re.sub(r'AB', "X", s)
    w += len(s) - len(t)
    if s[0] == "B":
        if s[-1] == "A":
            x += 1
        else:
            y += 1
    elif s[-1] == "A":
        z += 1
if x > 1:
    w += x - 1
    x = 1
if max(x, y, z) == y:
    w += x
    w += z
elif max(x, y, z) == z:
    w += x
    w += y
print(w)

len.py

    t = re.sub(r'AB', "X", s)
    w += len(s) - len(t)

Python の関数に詳しくないので、置換前後の文字数からABの個数をカウントしています。

Perl

perl.pl

use List::Util qw/max/;

chomp (my $n = <STDIN>);
my ($w, $x, $y, $z);
for my $i (1..$n) {
  chomp (my $s = <STDIN>);
  $w++ while $s =~ /AB/g;
  if (substr($s, 0, 1) eq "B") {
    if (substr($s, -1, 1) eq "A") {
      $x++;
    } else {
      $y++;
    }
  } elsif (substr($s, -1, 1) eq "A") {
    $z++;
  }
}
if ($x > 1) {
  $w += $x - 1;
  $x = 1;
}
if (max($x, $y, $z) == $y) {
  $w += $x;
  $w += $z;
} elsif (max($x, $y, $z) == $z) {
  $w += $x;
  $w += $y;
}
print "$w\n";

reg.pl

  $w++ while $s =~ /AB/g;

Perl の場合、常套句があります。
やはり、文字処理は Perl がつおいですね。

Java

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.next());
        int w = 0, x = 0, y = 0, z = 0;
        for (int i = 0; i < n; i++) {
            String s = sc.next();
            String t = s.replaceAll("AB", "X");
            w += s.length() - t.length();
            if (s.substring(0, 1).equals("B")) {
                if (s.substring(s.length() - 1, s.length()).equals("A")) {
                    x++;
                } else {
                    y++;
                }
            } else if (s.substring(s.length() - 1, s.length()).equals("A")) {
                z++;
            }
        }
        sc.close();
        if (x > 1) {
            w += x - 1;
            x = 1;
        }
        if (Math.max(x, Math.max(y, z)) == y) {
            w += x;
            w += z;
        } else if (Math.max(x, Math.max(y, z)) == z) {
            w += x;
            w += y;
        }
        System.out.println(w);
    }
}

replaceAll.java

            String t = s.replaceAll("AB", "X");
            w += s.length() - t.length();

Java の場合、Python と同様に置換前後の文字数からABの個数をカウントしています。

	Ruby	Python	Perl	Java
コード長	364 Byte	428 Byte	507 Byte	1071 Byte
実行時間	22 ms	62 ms	9 ms	250 ms
メモリ	1788 KB	3188 KB	640 KB	38660 KB

まとめ

• diverta 2019 Programming Contest C を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった

参照したサイト
Rubyで文字列（二文字以上）の出現回数を数える
Perl表技集　マッチした数を取得する