Solving with Ruby and Java AtCoder ABC129 D 2D array

Introduction

This theme

AtCoder Beginner Contest D - Lamp Difficulty: 1080

This theme, 2D array

What you are 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 of light in the left-right direction. Next, scan up and down twice to find the range of light in the up and down direction.

Sum the values in the left and right array and the top and bottom array to find 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's a cord without any twist.

About competing in script languages etc.

A blog about the speed of scripting languages. Among them, the one that is taken up as a strict example in the script language is this * 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

It was TLE in the old environmentRuby (2.3.3) , but it seems to pass somehow in the new environmentRuby (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) Old and new
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 era of ruby has arrived.

Summary

Referenced site

Recommended Posts

Solving with Ruby and Java AtCoder ABC129 D 2D array
Solving with Ruby, Perl and Java AtCoder ABC 136 D Breadth-first search
Solving with Ruby, Perl and Java AtCoder ABC 128 C
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 1)
Solving with Ruby, Perl and Java AtCoder ABC 129 C (Part 2) Dynamic programming
Solving in Ruby, Perl and Java AtCoder ABC 113 C Reference
Solve with Ruby AtCoder ABC177 D UnionFind
AtCoder ABC127 D hash to solve with Ruby 2.7.1
Sorting AtCoder ABC 111 C hashes to solve in Ruby, Perl and Java
Try to link Ruby and Java with Dapr
atcoder ABC70 D problem
[At Coder] Solve the ABC183 D problem with Ruby
[At Coder] Solve the ABC182 D problem with Ruby
ABC177 --solving E in Ruby
Store in Java 2D map and turn with for statement
Learning Ruby with AtCoder 13 How to make a two-dimensional array
AtCoder dwango Programming Contest B in Ruby, Perl and Java
Convert 2D array to csv format with Java 8 Stream API
Use java with MSYS and Cygwin
Distributed tracing with OpenCensus and Java
Install Java and Tomcat with Ansible
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Learning Ruby with AtCoder 6 [Contest 168 Therefore]
Use JDBC with Java and Scala.
[Java] Declare and initialize an array
AtCoder ARC 081 C hash to solve in Ruby, Perl and Java
Output PDF and TIFF with Java 8
[Java] Difference between array and ArrayList
Solving with Ruby AtCoder 1st Algorithm Practical Test A Exception Handling
What is a Ruby 2D array?
Encrypt with Java and decrypt with C #
Solve ARC104 D Multiset Mean with Scala, Java, C ++, Ruby, Perl, Elixir
[Introduction to Java] About array operations (1D array, 2D array declaration, instantiation, initialization and use)
With ruby ● × Game and Othello (basic review)
Monitor Java applications with jolokia and hawtio
Getting Started with Ruby for Java Engineers
Link Java and C ++ code with SWIG
Learning Ruby with AtCoder 7 [Contest 168 Triple Dots]
Let's try WebSocket with Java and javascript!
[Java] Reading and writing files with OpenCSV
Convert JSON to TSV and TSV to JSON with Ruby
[Java] array
[Ruby] Array
Java array
java (array)
Java array
[Java] Array
Initialize Ruby array with 0 like Java, that is, set the default value to 0
Java array
java array
[Java] Array
Learning Ruby with AtCoder 9 [1st Algorithm Practical Test 3rd] Sorting of array elements
Solving with Ruby AtCoder ACL Beginner Contest C Union Find (DSU)
Solve with Ruby AtCoder ABC177 D UnionFind
AtCoder ABC127 D hash to solve with Ruby 2.7.1
AtCoder Beginner Contest 169 A, B, C with ruby
[Ruby] Arguments with keywords and default values of arguments
I implemented Ruby with Ruby (and C) (I played with builtin)
AtCoder ABC 169 C Floating Point Fits in Ruby
Build and test Java + Gradle applications with Wercker
JSON with Java and Jackson Part 2 XSS measures
Create jupyter notebook with Docker and run ruby
[Java] Understand in 10 minutes! Associative array and HashMap