AtCoder ABC129 D 2D-Array In Ruby und Java gelöst

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Beginner Contest D - Lamp Difficulty: 1080

Dieses Thema, 2D-Array

Was Sie tun, ist einfach.

Scannen Sie insgesamt zweimal, um den Lichtbereich in linker und rechter Richtung zu ermitteln. Scannen Sie anschließend zweimal nach oben und unten, um den Lichtbereich in Auf- und Abwärtsrichtung zu ermitteln.

Summieren Sie die Werte des linken und rechten Arrays sowie des oberen und unteren Arrays, um den Maximalwert zu ermitteln. 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);
    }
}

Es ist eine Schnur ohne Verdrehung.

Über den Wettbewerb in Skriptsprache usw.

• Über den Wettbewerb in Skriptsprache usw. *

Ein Blog über die Geschwindigkeit von Skriptsprachen. Unter diesen wird als striktes Beispiel in der Skriptsprache dieses * D - Lamp * verwendet.

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

Der Code mit einer leicht festgelegten Anzahl von Scans war "TLE" in der alten Umgebung "Ruby (2.3.3)", aber er scheint in der neuen Umgebung "Ruby (2.7.1)" irgendwie zu bestehen.

Wie schnell

Es scheint ungefähr 1,4-mal schneller zu sein. Die Ära des Rubins ist angebrochen.

Zusammenfassung

• ABC 129 D bestanden
• Ruby ist schneller
• Ich kann nicht mit dem Kompilierungssystem übereinstimmen

Referenzierte Site

• Über den Wettbewerb in Skriptsprache usw. *