Ruby と Perl と Java と Python で解く AtCoder ARC 098 C 累積和

はじめに

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

今回のお題

AtCoder Regular Contets C - Attention
Difficulty: 641

今回のテーマ、累積和

Ruby

入力例 2 のWEWEWEEEWWWEを考察しますと、WEWEWEEiWWWEとなりiの左側のWの個数と右側のEの個数の合計が求める人数となります。
文字列の左0から右n-1に向かって、Eは単調減少、Wは単調増加ですので、計算量を抑える手法として累積和を使用します。

ruby.rb

n = gets.to_i
s = gets.chomp
e = (s[0] == 'E' ? [1] : [0])
w = (s[0] == 'W' ? [1] : [0])

1.upto(n - 1) do |i|
  if (s[i] == 'E')
    e[i] = e[i - 1] + 1
    w[i] = w[i - 1]
  else
    e[i] = e[i - 1]
    w[i] = w[i - 1] + 1
  end
end
w.unshift(0)
min = Float::INFINITY
0.upto(n - 1) do |i|
  min = e[-1] - e[i] + w[i] if min > e[-1] - e[i] + w[i]
end
puts min

sum.rb

1.upto(n - 1) do |i|
  if (s[i] == 'E')
    e[i] = e[i - 1] + 1
    w[i] = w[i - 1]
  else
    e[i] = e[i - 1]
    w[i] = w[i - 1] + 1
  end
end

ここで累積和を計算しています。

inf.rb

min = Float::INFINITY

Float::INFINITYで無限大を設定しています。

Python

python.py

import sys

n = int(input())
s = input()
e = [0] * n
w = [0] * (n + 1)
e[0] = 1 if s[0] == 'E' else 0
w[0] = 0
w[1] = 1 if s[0] == 'W' else 0
for i in range(1, n):
    if s[i] == 'E':
        e[i] = e[i - 1] + 1
        w[i + 1] = w[i]
    else:
        e[i] = e[i - 1]
        w[i + 1] = w[i] + 1
min = sys.maxsize
for i in range(n):
    if min > e[-1] - e[i] + w[i]:
        min = e[-1] - e[i] + w[i]
print(min)

max.py

min = sys.maxsize

sys.maxsizeで整数の上限値を設定しています。

Perl

perl.pl

chomp (my $n = <STDIN>);
chomp (my $s = <STDIN>);
my (@e, @w);
$e[0] = (substr($s, 0, 1) eq 'E' ? 1 : 0);
$w[0] = (substr($s, 0, 1) eq 'W' ? 1 : 0);
for my $i (1..$n-1) {
  if (substr($s, $i, 1) eq 'E') {
    $e[$i] = $e[$i - 1] + 1;
    $w[$i] = $w[$i - 1];
  } else {
    $e[$i] = $e[$i - 1];
    $w[$i] = $w[$i - 1] + 1;
  }
}
unshift @w, 0;
my $min = inf;
for my $i (0..$n-1) {
  $min = $e[-1] - $e[$i] + $w[$i] if $min > $e[-1] - $e[$i] + $w[$i];
}
print "$min\n";

inf.pl

my $min = inf;

infで無限大を設定しています。

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());
        char s[] = sc.next().toCharArray();
        sc.close();
        int e[] = new int[n];
        int w[] = new int[n + 1];
        w[0] = 0;
        if (s[0] == 'E') {
            e[0] = 1;
            w[1] = 0;
        } else {
            e[0] = 0;
            w[1] = 1;
        }
        for (int i = 1; i < n; i++) {
            if (s[i] == 'E') {
                e[i] = e[i - 1] + 1;
                w[i + 1] = w[i];
            } else {
                e[i] = e[i - 1];
                w[i + 1] = w[i] + 1;
            }
        }
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            if (min > e[n - 1] - e[i] + w[i])
                min = e[n - 1] - e[i] + w[i];
        }
        System.out.println(min);
    }
}

inf.java

        int min = Integer.MAX_VALUE;

Integer.MAX_VALUEで整数の最大値を設定しています。

	Ruby	Python	Perl	Java
コード長	379 Byte	433 Byte	488 Byte	962 Byte
実行時間	160 ms	302 ms	255 ms	181 ms
メモリ	7808 KB	17552 KB	22604 KB	32136 KB

まとめ

• ARC 098 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった
• Perl に詳しくなった
• Java に詳しくなった

参照したサイト
Python3で整数の最大値や小数の無限大を扱いたい