Tableau 2D AtCoder ABC129 D résolu en Ruby et Java

introduction

• Utilisez les recommandations dans AtCoder Problems * pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest D - Lamp Difficulty: 1080

Ce thème, tableau 2D

Ce que vous faites est simple.

Scannez un total de 2 fois pour trouver la plage de lumière dans les directions gauche et droite. Ensuite, scannez deux fois de haut en bas pour trouver la plage de lumière dans le sens haut et bas.

Additionnez les valeurs des tableaux gauche et droit et des tableaux supérieur et inférieur pour trouver la valeur maximale. 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);
    }
}

C'est un cordon sans aucune torsion.

À propos de la compétition en langage de script, etc.

• À propos de la compétition en langage de script, etc. *

Un blog sur la vitesse des langages de script. Parmi eux, celui qui est pris comme exemple strict dans le langage de script est celui-ci * 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

Le code avec un nombre de scans légèrement conçu était TLE dans l'ancien environnement Ruby (2.3.3), mais il semble passer en quelque sorte dans le nouvel environnementRuby (2.7.1).

À quelle vitesse

En gros, il semble être "1,4 fois plus rapide". L'ère du «rubis» est arrivée.

Résumé

• ABC 129 D réussi
• Ruby est plus rapide
• Je ne peux pas correspondre au système de compilation

Site référencé

• À propos de la compétition en langage de script, etc. *