This theme, least squares method
It's a little difficult to understand even if you read the problem statement, but if you read the explanation of the output example, * [Least Squares -wikipedia](https://ja.wikipedia.org/wiki/%E6%9C%80%E5 You can see that% B0% 8F% E4% BA% 8C% E4% B9% 97% E6% B3% 95) * imagines a linear function with a slope of 0.
First of all, since the amount of calculation is small, -100 ≤ a [i] ≤ 100, it can be solved frankly by full search.
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
Next is the mathematical solution.
Since the linear function y = ax + b has a slope ʻa = 0, then y = b`.
| Input example 3 | a[0] | a[1] | a[2] |
|---|---|---|---|
| data | 4 | 2 | 5 |
| The square of the error |
Therefore, the b that minimizes the cumulative square of the error can be obtained.
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
Enumerable modules such as map perform sequential operations on each element, but matrices perform operations on all elements at once.
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.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)
It seems that the variable min cannot be used.
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)
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))))
It is only a rudimentary usage.
| Ruby(Full search) | Ruby(Least squares) | Ruby(queue) | Python(Full search) | Python(Least squares) | Python(numpy) | |
|---|---|---|---|---|---|---|
| Code length | 169 Byte | 128 Byte | 174 Byte | 201 Byte | 122 Byte | 182 Byte |
| Execution time | 10 ms | 7 ms | 17 ms | 23 ms | 18 ms | 151 ms |
| memory | 1916 KB | 1788 KB | 4604 KB | 2940 KB | 2940 KB | 12396 KB |
Referenced site
Recommended Posts