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

はじめに

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

今回のお題

AtCoder Beginner Contest D - Lamp
Difficulty: 1080

今回のテーマ、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);
    }
}

なんの捻りもないコードです。

スクリプト言語などで競プロをすることについて

スクリプト言語などで競プロをすることについて

スクリプト言語の速度について書かれたブログです。
その中で、スクリプト言語で厳しい例として取り上げられているのが、今回の *D - Lamp*になります。

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 が速くなった
• コンパイル系にはかなわないけどね

参照したサイト
スクリプト言語などで競プロをすることについて