Ruby と Python で解く AtCoder ARC 059 C 最小二乗法

はじめに

AtCoder Problems の Recommendation を利用して、過去の問題を解いています。
AtCoder さん、AtCoder Problems さん、ありがとうございます。

今回のお題

AtCoder Regular Contets C - いっしょ
Difficulty: 656

今回のテーマ、最小二乗法

Ruby (全探索)

問題文を読んでもちょっと分かりづらいのですが、出力例の説明を読みますと、最小二乗法 -wikipedia で傾きが0の1次関数をイメージすることが分かります。
まずは、−100≦a[i]≦100と計算量が少ないので率直に全探索で解きます。

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 (最小二乗法)

次は、数学的解法です。
1次関数y = ax + bで傾きa = 0ですので、y = bとなります。

入力例3	a[0]	a[1]	a[2]
データ	4	2	5
誤差の二乗	$$(b - 4)^2$$	$$(b - 2)^2$$	$$(b - 5)^2$$

$$(誤差の二乗の累計) = 3b^2 - 22b + 45$$
よって、誤差の二乗の累計が最小となるbが求まります。
$$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 (最小二乗法 - 行列)

map を始めとする Enumerable モジュールは一つ一つの要素に逐次演算を行いますが、行列は全ての要素に一気に演算を行います。

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 (全探索)

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)

minという変数は使用できないようです。

Python (最小二乗法)

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 (最小二乗法 - 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))))

初歩的な使用方法にとどまっています。

	Ruby(全探索)	Ruby(最小二乗法)	Ruby(行列)	Python(全探索)	Python(最小二乗法)	Python(numpy)
コード長	169 Byte	128 Byte	174 Byte	201 Byte	122 Byte	182 Byte
実行時間	10 ms	7 ms	17 ms	23 ms	18 ms	151 ms
メモリ	1916 KB	1788 KB	4604 KB	2940 KB	2940 KB	12396 KB

まとめ

• ARC 059 C を解いた
• Ruby に詳しくなった
• Python に詳しくなった

参照したサイト
最小二乗法のアルゴリズムを理解したのでメモ。そしてPythonで書いてみた。