Ruby と Java で解く AtCoder ABC129 D 2次元配列

# はじめに
*[AtCoder Problems](https://kenkoooo.com/atcoder/#/)* の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。
# 今回のお題
*[AtCoder Beginner Contest D - Lamp](https://atcoder.jp/contests/abc129/tasks/abc129_d)*
<font color="green">Difficulty: 1080</font>

今回のテーマ、2次元配列

やっていることは、単純です。

|...#..#.|元の配列|
|:--:|:--|
|12301201|元の配列を左から右にスキャン|
|33302201|スキャンした配列を右から左にスキャン|
合計2回スキャンして左右方向の光の届く範囲を求めます。
次に、上下に2回スキャンして上下方向の光の届く範囲を求めます。

左右用の配列と上下用の配列の値を合計し、その最大値を求めます。
# Java
```lamp.java
import java.util.*;

class Main {
    public static void main(String[] args) {
        final Scanner sc = new Scanner(System.in);
        final int H = Integer.parseInt(sc.next());
        final int W = Integer.parseInt(sc.next());
        final char S[][] = new char[H+2][W+2];
        for (int i=1; i<H+1; i++) {
            S[i] =  ("#" + sc.next() + "#").toCharArray();
        }
        sc.close();
        for (int i=0; i<W+2; i++) {
            S[0][i] = '#';
            S[H+1][i] = '#';
        }
        int lr[][] = new int[H+2][W+2];
        int ud[][] = new int[H+2][W+2];

        for (int i=1; i<H+1; i++) {
            int cnt = 0;
            for (int j=0; j<W+1; j++) {
                if (S[i][j]=='.') {
                    cnt++;
                } else {
                    cnt = 0;
                }
                lr[i][j] = cnt;
            }
            for (int j=W; j>0; j--) {
                if (lr[i][j]==0) {
                    cnt = 0;
                } else if (cnt==0) {
                    cnt = lr[i][j];
                } else {
                    lr[i][j] = cnt;
                }
            }
        }
        for (int j=1; j<W+1; j++) {
            int cnt = 0;
            for (int i=0; i<H+1; i++) {
                if (S[i][j]=='.') {
                    cnt++;
                } else {
                    cnt = 0;
                }
                ud[i][j] = cnt;
            }
            for (int i=H; i>0; i--) {
                if (ud[i][j]==0) {
                    cnt = 0;
                } else if (cnt==0) {
                    cnt = ud[i][j];
                } else {
                    ud[i][j] = cnt;
                }
            }
        }

        int ans = 0;
        for (int i=1; i<H+1; i++) {
            for (int j=1; j<W+1; j++) {
                int cnt = lr[i][j] + ud[i][j];
                if (ans<cnt) ans = cnt;
            }
        }
        ans -= 1;
        System.out.println(ans);
    }
}
```
なんの捻りもないコードです。

# スクリプト言語などで競プロをすることについて
*[スクリプト言語などで競プロをすることについて](https://betrue12.hateblo.jp/entry/2019/06/20/090223)*

スクリプト言語の速度について書かれたブログです。
その中で、スクリプト言語で厳しい例として取り上げられているのが、今回の *[D - Lamp](https://atcoder.jp/contests/abc129/tasks/abc129_d)*になります。

# Ruby
```ruby.rb
h, w = gets.split.map(&:to_i)
s = Array.new(h + 1).map{Array.new(w + 1, 0)}
1.upto(h) do |i|
  c = 0
  l = 1
  b = gets
  1.upto(w) do |j|
    if b[j - 1] == '.'
      l = j if c == 0
      c += 1
    elsif c > 0
      l.upto(j - 1) do |k|
        s[i][k] = c
      end
      c = 0
    end
    if j == w && c > 0
      l.upto(j) do |k|
        s[i][k] = c
      end
    end
  end
end
ans = 0
1.upto(w) do |j|
  c = 0
  l = 1
  1.upto(h) do |i|
    if (s[i][j] > 0)
      l = i if c == 0
      c += 1
    elsif c > 0
      l.upto(i - 1) do |k|
        ans = s[k][j] + c if ans < s[k][j] + c
      end
      c = 0
    end
    if i == h && c > 0
      l.upto(i) do |k|
        ans = s[k][j] + c if ans < s[k][j] + c
      end
    end
  end
end
puts ans - 1
```
スキャンの回数を少し工夫したコードで旧環境`Ruby (2.3.3)`では`TLE`でしたが、新環境`Ruby (2.7.1)`では何とか通る様です。

||C++14|Java|Ruby 2.3.1|Ruby 2.7.1|
|:--:|:--:|:--:|:--:|:--:|
||旧環境|旧環境|旧環境|新環境|
|コード長 (Byte)|1420|2044|797|797|
|実行時間 (ms)|94|465|TLE|1567|
|メモリ (KB)|35328|108364|36988|47324|
# どのくらい速くなったか
|ケース名|実行時間（旧）|実行時間（新）|新旧比|
|:--:|:--:|:--:|:--:|
|01.txt|7|59||
|02.txt|7|63||
|12.txt|1460|1089|1.34|
|13.txt|1844|1250|1.48|
|18.txt|1983|1289|1.54|
|19.txt|1949|1360|1.43|
|20.txt|11|59||
|21.txt|7|63||
|22.txt|22|70||
|23.txt|1449|981|1.48|
|24.txt|9|62||
|25.txt|10|63||
大雑把に、`1.4倍速くなっている`ようです。
`ruby`の時代が来ましたね。
# まとめ
+ ABC 129 D が通った
+ Ruby が速くなった
+ コンパイル系にはかなわないけどね

参照したサイト
*[スクリプト言語などで競プロをすることについて](https://betrue12.hateblo.jp/entry/2019/06/20/090223)*