2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 3 years have passed since last update.

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

Last updated at Posted at 2020-05-04

はじめに

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

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

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

2
1
8

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
1

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?