[Java] AtCoder ABC129 D 2D array solved with Ruby and Java

3 minute read

Introduction

AtCoder Problems is used to solve past problems. Thank you AtCoder and AtCoder Problems.

This time

AtCoder Beginner Contest D-Lamp

Difficulty: 1080

This theme, 2D array

What you’re doing is simple.

|…#..#.|original array| |:–:|:–| |12301201| Scan the original array from left to right | |33302201| Scan the scanned array from right to left | Scan a total of 2 times to find the range that light can reach in the left and right directions. Next, scan twice up and down to find the vertical light reach.

The values of the left and right arrays and the top and bottom arrays are added together to obtain the maximum value.

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);
    }
}

It is a cord with no twist.

About competing professionals in script languages etc.

About competing professionals in scripting languages

A blog about the speed of scripting languages. Among them, this time, D-Lamp is taken up as a severe example in the script language.

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

It is a code that devises the number of scans a bit, it was TLE in the old environment Ruby (2.3.3), but it seems to be manageable in the new environment Ruby (2.7.1).

||C++14|Java|Ruby 2.3.1|Ruby 2.7.1| |:–:|:–:|:–:|:–:|:–:| || Old environment | Old environment | Old environment | New environment | | Code length (Byte)|1420|2044|797|797| |Execution time (ms)|94|465|TLE|1567| |Memory (KB)|35328|108364|36988|47324|

How fast

| Case name | Execution time (old) | Execution time (new) | New-old ratio | |:–:|:–:|:–:|:–:| |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|| Roughly, it seems to be 1.4 times faster. The age of ruby has come.

Summary

  • ABC 129 D passed
  • Ruby got faster
  • It doesn’t match the compilation system though

Referred site About competing professionals in scripting languages