AtCoder Beginner Contest B - Template Matching Difficulty: 828
This theme, matrix operation
It's a two-dimensional array, but using a matrix library can make operations easier. Ruby
ruby.rb
require 'matrix'
class Matrix
# v2.Cannot be assigned in 3
def []=(i, j, x)
@rows[i][j]=x
end
end
n, m = gets.split.map(&:to_i)
rows = Array.new(n + m){gets.chomp.chars.map{|c| (c == '#') ? 1 : 0}}
a = Matrix.rows(rows.shift(n))
b = Matrix.rows(rows)
(n - m + 1).times do |i|
(n - m + 1).times do |j|
if a.minor(i, m, j, m) == b
puts "Yes"
exit
end
end
end
puts "No"
matrix.rb
require 'matrix'
class Matrix
# v2.Cannot be assigned in 3
def []=(i, j, x)
@rows[i][j]=x
end
end
Call the matrix library with require'matrix'
.
In the local environment v2.7.1
, it can be assigned to the matrix element, but in the AtCoder environment v2.3.3
, it cannot be assigned, so a method is added.
The interesting thing about ** Ruby ** is that you can do this for the standard library as well.
minor.rb
if a.minor(i, m, j, m) == b
Submatrix is acquired by minor
and matrix comparison is performed.
error.rb
(n - m).times do |i|
(n - m).times do |j|
(n - m + 1).times do |i|
(n - m + 1).times do |j|
When the matrix is ~~ 1 x 1
, the matrix comparison does not go well, so the corresponding processing is included. ~~ (n --m)
was wrong and (n --m + 1)
was correct.
** Addition ** Please refer to the comment section for the 2D array version. Python
import numpy
n, m = map(int, input().split())
a = numpy.zeros([n, n], dtype=int)
b = numpy.zeros([m, m], dtype=int)
for i in range(n):
s = input()
for j in range(n):
if s[j] == '#':
a[i, j] = 1
for i in range(m):
s = input()
for j in range(m):
if s[j] == '#':
b[i, j] = 1
for i in range(n - m + 1):
for j in range(n - m + 1):
if numpy.all(a[i: i + m, j: j + m] == b):
print("Yes")
exit()
print("No")
all.py
if numpy.all(a[i: i + m, j: j + m] == b):
Numpy matrix comparison returns, for example, [[True, True], [True, True]]
, so I'm using the all function to check if everything is True
.
Ruby (Matrix) | Ruby (Array) | Python (numpy) | |
---|---|---|---|
Code length(Byte) | 420 | 288 | 534 |
Execution time(ms) | 22 | 10 | 166 |
memory(KB) | 3196 | 1788 | 12512 |
Recommended Posts