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

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Regular Contets C - Attention](https://atcoder.jp/contests/arc098/tasks/arc098_a)*
<font color="brown">Difficulty: 641</font>

今回のテーマ、累積和
# 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で整数の最大値や小数の無限大を扱いたい](https://qiita.com/neko_the_shadow/items/bc4a399b9e4a298d28c6)*