Résolution avec Ruby, Python et numpy AtCoder ABC054 B Calcul de la matrice

introduction

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

Ce thème

AtCoder Beginner Contest B - Template Matching Difficulty: 828

Ce thème, le calcul matriciel

C'est un tableau à deux dimensions, mais l'utilisation d'une bibliothèque de matrices peut faciliter les opérations. Ruby

ruby.rb

require 'matrix'

class Matrix
  # v2.Ne peut pas être attribué en 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.Ne peut pas être attribué en 3
  def []=(i, j, x)
    @rows[i][j]=x
  end
end

Appelez la bibliothèque de matrices avec require'matrix'. Dans l'environnement local v2.7.1, il peut être affecté aux éléments de la matrice, mais dans l'environnement AtCoder v2.3.3, il ne peut pas être attribué, donc une méthode est ajoutée. La chose intéressante à propos de ** Ruby ** est que vous pouvez également le faire pour les bibliothèques standard.

minor.rb

    if a.minor(i, m, j, m) == b

La sous-matrice est acquise par «mineur» et la matrice est comparée.

error.rb

(n - m).times do |i|
  (n - m).times do |j|

(n - m + 1).times do |i|
  (n - m + 1).times do |j|

Lorsque la matrice est ~~ "1 x 1", la comparaison des matrices ne se passe pas bien, donc le traitement correspondant est inclus. ~~ (n --m) était faux et (n --m + 1) était correct.

** Addenda ** Veuillez vous référer à la section des commentaires pour la version de tableau bidimensionnel. 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):

La comparaison de matrices numpy renvoie, par exemple, «[[True, True], [True, True]]», nous utilisons donc la fonction all pour vérifier si elles sont toutes «True».

Résumé

• Résolu ABC 054 B
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python
• Est devenu familier avec numpy