Résolution avec Ruby et Python AtCoder ARC 059 C Méthode du carré minimum

introduction

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

Ce thème

• Contets réguliers AtCoder C - Ensemble * Difficulty: 656

Ce thème, la méthode des moindres carrés

Ruby (recherche complète)

C'est un peu difficile à comprendre même si vous lisez la phrase du problème, mais si vous lisez l'explication de l'exemple de sortie, * [Méthode du carré minimum -wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E5 Vous pouvez voir que% B0% 8F% E4% BA% 8C% E4% B9% 97% E6% B3% 95) * imagine une fonction linéaire avec une pente de «0». Tout d'abord, étant donné que la quantité de calcul est petite comme «-100 ≤ a [i] ≤ 100», elle peut être résolue franchement par une recherche complète.

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
min = Float::INFINITY
a.min.upto(a.max) do |x|
  b = a.map{|y| (x - y) ** 2}.inject(:+)
  min = b if min > b
end
puts min

Ruby (méthode du carré minimum)

Vient ensuite la solution mathématique. Puisque la fonction linéaire y = ax + b a un gradient ʻa = 0, alors y = b`.

Par conséquent, le «b» qui minimise la somme cumulée des carrés des erreurs peut être obtenu. $b = 22 / 2 / 3$

ruby.rb

n = gets.to_i
a = gets.split.map(&:to_i)
b = (a.inject(:+).to_f / n).round
min = a.map{|x| (x - b) ** 2}.inject(:+)
puts min

Ruby (méthode-matrice de carré minimum)

Des modules énumérables tels que map effectuent des opérations séquentielles sur chaque élément, mais les matrices effectuent des opérations sur tous les éléments à la fois.

ruby.rb

require 'matrix'

n = gets.to_f
a = Matrix[(gets.split.map(&:to_i))]
b = (a.inject(:+) / n).round
min = a - Matrix[(Array.new(n, b))]
puts (min * min.row_vectors[0])[0]

Python (recherche complète)

python.py

import sys

n = int(input())
a = list(map(int, input().split()))
m = sys.maxsize
for x in range(min(a), max(a) + 1):
    b = sum([(x - y) ** 2 for y in a])
    if m > b:
        m = b
print(m)

Il semble que la variable «min» ne puisse pas être utilisée.

Python (méthode du carré minimum)

python.py

n = int(input())
a = list(map(int, input().split()))
b = round(sum(a) / n)
m = sum([(x - b) ** 2 for x in a])
print(m)

Python (méthode du carré minimum --numpy)

numpy.py

import numpy as np

n = int(input())
a = np.array([list(map(int, input().split()))], dtype = np.int32)
b = np.around(np.sum(a) / n)
m = a - b
print(int(np.sum(np.power(m, 2))))

Ce n'est qu'un usage rudimentaire.

Résumé

• ARC 059 C résolu
• Familiarisez-vous avec Ruby
• Familiarisez-vous avec Python

Site référencé

• Notez que je comprends l'algorithme des moindres carrés. Et je l'ai écrit en Python. *