Solving with Ruby and Python AtCoder ARC 059 C Least Squares

Introduction

This theme

This theme, least squares method

Ruby (search all)

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

Ruby (least squares method)

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 $(b - 4)^2$ $(b - 2)^2$ $(b - 5)^2$
(cumulative squared error) = 3b ^ 2 --22b + 45

Therefore, the b that minimizes the cumulative square of the error can be obtained. $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 (Least Squares-Matrix)

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 (full search)

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 (least squares)

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 (least squares --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))))

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

Summary

Referenced site

Recommended Posts

Solving with Ruby and Python AtCoder ARC 059 C Least Squares
Solving with Ruby and Python AtCoder ARC067 C Prime Factorization
Solving with Ruby, Perl, Java, and Python AtCoder ARC 098 C Cumulative sum
Solving with Ruby and Python AtCoder AISING2020 D Iterative Squares
Solving with Ruby and Python AtCoder ABC011 C Dynamic programming
Solving in Ruby, Perl, Java, and Python AtCoder ARC 066 C Iterative Squares Hash
Solving with Ruby, Perl, Java, and Python AtCoder ABC 065 C factorial
Solving with Ruby and Python AtCoder ABC057 C Prime Factorization Bit Search
Solving with Ruby, Perl, Java and Python AtCoder CADDi 2018 C Prime Factorization
Solving with Ruby and Python AtCoder Tenka1 Programmer Contest C Cumulative sum
Solving with Ruby and Python AtCoder CODE FESTIVAL 2016 qual C B Priority queue
Solving with Ruby and Python AtCoder ABC178 D Dynamic programming
Solving with Ruby and Python AtCoder ABC151 D Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 A
Solving with Ruby and Python AtCoder ABC153 E Dynamic programming
Solving with Ruby, Perl, Java and Python AtCoder ATC 002 B
Solving with Ruby and Python AtCoder ABC138 D Adjacency list
Solving with Ruby, Perl, Java and Python AtCoder diverta 2019 Programming Contest C String Manipulation
Solve with Ruby, Python and Java AtCoder ARC104 B Cumulative sum
Solving with Ruby, Python and numpy AtCoder ABC054 B Matrix operation
Solving with Ruby, Python and networkx AtCoder ABC168 D Adjacency list
Solving with Ruby AtCoder ABC110 C String Manipulation
Solving with Ruby, Perl, Java and Python AtCoder ABC 107 B String Manipulation
Solving with Ruby, Perl, Java, and Python AtCoder AGC 033 A Breadth-first search
Solving with Ruby, Perl, Java and Python AtCoder ABC 165 D Floor function
Solving with Ruby, Perl, Java and Python AtCoder ABC 131 D Array Sorting
Solve with Ruby, Perl, Java and Python AtCoder ABC 047 C Regular Expression
AtCoder ARC080 D simulation solved in Ruby and Python
Sorting AtCoder ARC 086 C hashes to solve in Ruby, Perl, Java and Python
Scraping with Node, Ruby and Python
Solve with Ruby and Python AtCoder ABC133 D Cumulative sum
Solved AtCoder ABC 114 C-755 with Python3
Solving in Ruby, Python and Java AtCoder ABC141 D Priority Queuing
Encrypt with Ruby (Rails) and decrypt with Python
Easy web scraping with Python and Ruby
RaspberryPi L Chika with Python and C #
AtCoder ABC172 C Cumulative Sum Binary Search Solved by Ruby and Python
Solving the Lorenz 96 model with Julia and Python
Challenge AtCoder (ABC) 164 with Python! A ~ C problem
Solve with Ruby and Python AtCoder ABC084 D Cumulative sum of prime numbers
Solve AtCoder 167 with python
Ruby, Python and map
Python and Ruby split
Benchmark for C, Java and Python with prime factorization
Comparison of CoffeeScript with JavaScript, Python and Ruby grammar
Version control of Node, Ruby and Python with anyenv
Programming with Python and Tkinter
Encryption and decryption with Python
Solve AtCoder ABC166 with python
Light blue with AtCoder @Python
[AtCoder explanation] Control ABC180 A, B, C problems with Python!
[AtCoder explanation] Control ABC188 A, B, C problems with Python!
Python and hardware-Using RS232C with Python-
Mandelbrot Benchmark (C, PHP, HHVM, Ruby, Python, PyPy, and Kinx)
Python on Ruby and angry Ruby on Python
ABC163 C problem with python3
Solving Sudoku with Python (Incomplete)
Python and ruby slice memo
Zundokokiyoshi with python / ruby / Lua
[AtCoder explanation] Control ABC158 A, B, C problems with Python!
Solving Sudoku with Python (Part 2)