Ruby と Perl と Java と Python で解く AtCoder AGC 033 A 幅優先探索

はじめに

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

今回のお題

AtCoder Grand Contest 033 A - Darker and Darker
Difficulty: 1245

今回のテーマ、幅優先探索

Ruby

以前解きました AtCoder Typical Contest 002 A - 幅優先探索 の応用編になります。
特に、実行時間制限: 1 sec と厳しい条件が付いています。

ruby.rb

h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
    else
      que.push(i)
      que.push(j)
    end
  end
end
ans = 0
while que.size > 0
  y = que.shift
  x = que.shift
  ans = cm[y][x] + 1
  if cm[y + 1][x] == -1
    cm[y + 1][x] = ans
    que.push(y + 1)
    que.push(x)
  end
  if cm[y - 1][x] == -1
    cm[y - 1][x] = ans
    que.push(y - 1)
    que.push(x)
  end
  if cm[y][x + 1] == -1
    cm[y][x + 1] = ans
    que.push(y)
    que.push(x + 1)
  end
  if cm[y][x - 1] == -1
    cm[y][x - 1] = ans
    que.push(y)
    que.push(x - 1)
  end
end
puts ans - 1

前回のコード をコピペし、若干の修正を加えるだけで水diffクリア。

array.rb

cm = Array.new(h + 2){Array.new(w + 2, 0)}

上下左右をチェックする際、nilでエラーを貰わない様、配列を大きくしています。

push.rb

h, w = gets.split.map(&:to_i)
cm = Array.new(h + 2){Array.new(w + 2, 0)}
que = []
1.upto(h) do |i|
  s = gets.chomp
  1.upto(w) do |j|
    if s[j - 1] == '.'
      cm[i][j] = -1
    else
      que << i << j
      cm[i][j] = 0
    end
  end
end
ans = 0
while que.size > 0
  y = que.shift
  x = que.shift
  ans = cm[y][x] + 1
  if cm[y + 1][x] == -1
    cm[y + 1][x] = ans
    que << y + 1 << x
  end
  if cm[y - 1][x] == -1
    cm[y - 1][x] = ans
    que << y - 1 << x
  end
  if cm[y][x + 1] == -1
    cm[y][x + 1] = ans
    que << y << x + 1
  end
  if cm[y][x - 1] == -1
    cm[y][x - 1] = ans
    que << y << x - 1
  end
end
puts ans - 1

コメントでいただいたpushの代わりに<<を使用するコードです。
こちらは、実行時間が短縮しています。

Python

Python は今回TLE でした。
他の競技者の解答を見てみると、numpy を使用している例が多いです。

cmd.exe

C:\Users\user>pacman -S mingw-w64-x86_64-python-numpy

早速インストールしました。

追記
PyPyですと通りました。

PyPy.py

from collections import deque

h, w = map(int, input().split())
cm = [[0 for j in range(w + 2)] for i in range(h + 2)]
que = deque([])
for i in range(1, h + 1):
    s = input()
    for j in range(1, w + 1):
        if s[j - 1] == ".":
            cm[i][j] = -1
        else:
            que.append(i)
            que.append(j)
ans = 0
while len(que) > 0:
    y = que.popleft()
    x = que.popleft()
    ans = cm[y][x] + 1
    if cm[y + 1][x] == -1:
        cm[y + 1][x] = ans
        que.append(y + 1)
        que.append(x)
    if cm[y - 1][x] == -1:
        cm[y - 1][x] = ans
        que.append(y - 1)
        que.append(x)
    if cm[y][x + 1] == -1:
        cm[y][x + 1] = ans
        que.append(y)
        que.append(x + 1)
    if cm[y][x - 1] == -1:
        cm[y][x - 1] = ans
        que.append(y)
        que.append(x - 1)
print(ans - 1)

Perl

Perl は今回TLE でした。
他の競技者の解答を見てみると．．．せっ 正解者が誰もいない。

Java

今回は２本立てです。
一つ目は、前回のコード をコピペして、若干の修正を加えたもの。

java.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int cm[][] = new int[h + 2][w + 2];
        Deque<Integer> que = new ArrayDeque<>();
        for (int i = 1; i <= h; i++) {
            String s = sc.next();
            for (int j = 1; j <= w; j++) {
                if (".".equals(s.substring(j - 1, j))) {
                    cm[i][j] = -1;
                } else {
                    que.add(i);
                    que.add(j);
                }
            }
        }
        sc.close();
        int ans = 0;
        while (que.size() > 0) {
            int y = que.poll();
            int x = que.poll();
            ans = cm[y][x] + 1;
            if (cm[y + 1][x] == -1) {
                cm[y + 1][x] = ans;
                que.add(y + 1);
                que.add(x);
            }
            if (cm[y - 1][x] == -1) {
                cm[y - 1][x] = ans;
                que.add(y - 1);
                que.add(x);
            }
            if (cm[y][x + 1] == -1) {
                cm[y][x + 1] = ans;
                que.add(y);
                que.add(x + 1);
            }
            if (cm[y][x - 1] == -1) {
                cm[y][x - 1] = ans;
                que.add(y);
                que.add(x - 1);
            }
        }
        System.out.println(ans - 1);
    }
}

array.java

        int cm[][] = new int[h + 2][w + 2];

上下左右をチェックする際、ArrayIndexOutOfBoundsExceptionを貰わない様、配列を大きくしています。

class.java

import java.util.*;

class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int h = Integer.parseInt(sc.next());
        int w = Integer.parseInt(sc.next());
        int s[][] = new int[h + 2][w + 2];
        Queue<Pair> que = new ArrayDeque<>();
        for (int i = 1; i <= h; i++) {
            char c[] = sc.next().toCharArray();
            for (int j = 1; j <= w; j++) {
                if (c[j - 1] == '.') {
                    s[i][j] = -1;
                } else {
                    que.add(new Pair(i, j));
                }

            }
        }
        sc.close();

        Pair p;
        int ans = 0;
        while (!que.isEmpty()) {
            p = que.poll();
            ans = s[p.x][p.y] + 1;
            if (s[p.x + 1][p.y] == -1) {
                s[p.x + 1][p.y] = ans;
                que.add(new Pair(p.x + 1, p.y));
            }
            if (s[p.x - 1][p.y] == -1) {
                s[p.x - 1][p.y] = ans;
                que.add(new Pair(p.x - 1, p.y));
            }
            if (s[p.x][p.y + 1] == -1) {
                s[p.x][p.y + 1] = ans;
                que.add(new Pair(p.x, p.y + 1));
            }
            if (s[p.x][p.y - 1] == -1) {
                s[p.x][p.y - 1] = ans;
                que.add(new Pair(p.x, p.y - 1));
            }
        }
        System.out.println(ans - 1);
    }
}

class Pair {
    int x;
    int y;

    public Pair(int x, int y) {
        this.x = x;
        this.y = y;
    }
}

ArrayDeque が遅い様なので、出し入れを減らすためクラスを生成しクラスごと渡しています。

Java は、やればできる子でした。

	Ruby	Ruby(<<)	Python	PyPy	Perl	Java	Java(class)
コード長 (Byte)	753	676	878	878	777	1511	1580
実行時間 (ms)	843	801	TLE	599	TLE	779	345
メモリ (KB)	27132	27132	52484	37692	174720	114932	70740

まとめ

• AGC 033 A を解いた
• Ruby に詳しくなった
• numpy をインストールした
• Java はできる子でした

参照したサイト
numpyの使い方
Ruby と Perl と Java と Python で解く AtCoder ATC 002 A