Codingame『Bender - Algorithmic Complexity』

　気が変わって難易度：ハードの一番下にある問題をやってみた。
データの説明に最も適する近似曲線は何ですか？という問題。

　自分で作ってて思ったけど、超クソコードです。テストは通ったんですけどね。
どうしたらもっと綺麗に書けるんだろうなぁ……。
一回のループで全部の傾きと切片を得て、R²値をザッと計算するのが早いんだろうけど。
メモリがっつり食べたりしないだろうか…。気にし過ぎかな。

一応、恥をさらす意味で置いておきます。

using System;
using System.Linq;
using System.IO;
using System.Text;
using System.Collections;
using System.Collections.Generic;

/**
 * Auto-generated code below aims at helping you parse
 * the standard input according to the problem statement.
 **/
class Solution
{
    static void Main(string[] args)
    {
        int n = int.Parse(Console.ReadLine());
        int[] d_x = new int[n];
        int[] d_y = new int[n];
        double ave_num = 0;
        double ave_t = 0;

        Console.Error.WriteLine("N:{0}", n);
        
        for (int i = 0; i < n; i++)
        {
            string[] inputs = Console.ReadLine().Split(' ');
            int num = int.Parse(inputs[0]);
            int t = int.Parse(inputs[1]);
            Console.Error.WriteLine("{0} {1}", num, t);
            
            d_x[i] = num;
            d_y[i] = t;
            ave_num += (double)num;
            ave_t += (double)t;
        }
        ave_num = ave_num/(double)n;
        ave_t = ave_t/(double)n;
        Console.Error.WriteLine("average_num:{0}", ave_num);
        Console.Error.WriteLine("average_t:{0}", ave_t);
        
        string result = "";
        double ch = 0;
        double r = 0;
        ch = ErLogN(d_x, d_y);
        if(ch > r) {
            result = "O(log n)";
            r = ch;
        }
        ch = ER_N(d_x, d_y);
        if(ch > r) {
            result = "O(n)";
            r = ch;
        }
        ch = ErNLogN(d_x, d_y);
        if(ch > r) {
            result = "O(n log n)";
            r = ch;
        }
        ch = ErN2(d_x, d_y);
        if(ch > r) {
            result = "O(n^2)";
            r = ch;
        }
        ch = ErN2LogN(d_x, d_y);
        if(ch > r) {
            result = "O(n^2 log n)";
            r = ch;
        }
        ch = ErN3(d_x, d_y);
        if(ch > r) {
            result = "O(n^3)";
            r = ch;
        }
        ch = Er2N(d_x, d_y);
        if(ch > r) {
            result = "O(2^n)";
            r = ch;
        }
        if(r < 0.8) {
            result = "O(1)";
            r = ch;
        }
        // Write an action using Console.WriteLine()
        // To debug: Console.Error.WriteLine("Debug messages...");

        Console.WriteLine(result);
    }
    
    //O(1)
    static double Er1(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = 1.0;
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[1]{0}x + {1}", a, b);
        
        a = 0;
        b = sumy / (double)(d_x.Length);
        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }
    
    //O(log(n))
    static double ErLogN(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = Math.Log((double)d_x[n]);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[2]{0}x + {1}", a, b);

/*
        double avey = sumy/(double)(d_y.Length);
        double sump1 = 0;
        double sump2 = 0;
        double r2 = 0;
        for(int n = 0; n < d_y.Length; n++) {
            double tmp = (double)d_y[n] - (a * nx[n] + b);
            sump1 += (tmp * tmp);
            tmp = (double)d_y[n] - avey;
            sump2 += tmp * tmp;
        }
        r2 = 1.0 - (sump1 / sump2);

        Console.Error.WriteLine("R2 = {0}", r2);
        
        return r2;
*/
        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }

    //O(n)
    static double ER_N(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = (double)d_x[n];
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[3]{0}x + {1}", a, b);

        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }

    //O(n * log(n))
    static double ErNLogN(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = (double)d_x[n] * Math.Log((double)d_x[n]);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[4]{0}x + {1}", a, b);

        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }
    
    //O(n^2)
    static double ErN2(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = Math.Pow((double)d_x[n], 2.0);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[5]{0}x + {1}", a, b);

        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }

    //O(n^2 * log(n))
    static double ErN2LogN(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = Math.Pow((double)d_x[n], 2.0) * Math.Log((double)d_x[n]);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[6]{0}x + {1}", a, b);

        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }

    //O(n^3)
    static double ErN3(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = Math.Pow((double)d_x[n], 3.0);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[7]{0}x + {1}", a, b);

        return CoefficientOfDetermination(nx, d_y, sumy, a, b);
    }

    //O(2^n)
    static double Er2N(int[] d_x, int[] d_y)
    {
        double[] nx = new double[d_x.Length];
        double sumxx = 0;
        double sumxy = 0;
        double sumx = 0;
        double sumy = 0;
        for(int n = 0; n < d_x.Length; n++) {
            nx[n] = Math.Pow(2.0, (double)d_x[n]);
            sumxy += nx[n]*(double)d_y[n];
            sumxx += nx[n]*nx[n];
            sumx += nx[n];
            sumy += (double)d_y[n];
        }
        double t = sumxx * (double)(d_x.Length) - sumx * sumx;
        double a = (sumxy * (double)(d_x.Length) - sumx*sumy) / t;
        double b = (sumxx * sumy - sumxy * sumx) / t;
        Console.Error.WriteLine("[8]{0}x + {1}", a, b);

        double r = CoefficientOfDetermination(nx, d_y, sumy, a, b);
        if(r == double.NaN) return 0;
        else return r;
    }

    //未使用
    static double LinearRegression()
    {
        return 0;
    }
    
    //決定係数R2を求める
    static double CoefficientOfDetermination(double[] nx, int[] d_y, double sumy, double a, double b)
    {
        double avey = sumy/(double)(d_y.Length);
        double sump1 = 0;
        double sump2 = 0;
        double r2 = 0;
        for(int n = 0; n < d_y.Length; n++) {
            double tmp = (double)d_y[n] - (a * nx[n] + b);
            sump1 += (tmp * tmp);
            tmp = (double)d_y[n] - avey;
            sump2 += tmp * tmp;
        }
        r2 = 1.0 - (sump1 / sump2);

        Console.Error.WriteLine("R2 = {0}", r2);
        
        return r2;
    }
}