山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

yukicoder contest 199 の感想

問題

yukicoder contest 199 - yukicoder

B問題まで解くことができました。C問題は紙の上では解けたんですが、コードの間違いに気が付きませんでした。

A - No.729 文字swap

指定された文字を入れ替えるだけです。

B - No.730 アルファベットパネル

同じ文字が存在すると文字列を作成できません。

コード

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Exec0730 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        String S = scan.next();
        scan.close();
        Set<Integer> set = new HashSet<Integer>();
        for(int i = 0; i < S.length(); i++) {
            char c = S.charAt(i);
            set.add((int)c);
        }
        if(set.size() == S.length()) {
            System.out.println("YES");
        }else {
            System.out.println("NO");
        }
    }
}

C - No.731 等差数列がだいすき

与えられた数列を等差数列に変換するのにかかるコストを最小化する問題です。

考え方

まず初めに等差数列の初項を、

 b_1 = a_1 + x

とします。公差が  d であることから、初項以降は、

 b_2 = b_1 + d = a_1 + x + d

 b_3 = b_2 + d = a_1 + x + 2d

 \vdots

 b_n = b_{n - 1} + d = a_1 + x + (n - 1) d

となります。

したがって、変数  x, d に関するコスト関数  f(x , d)

 f(x, d) = (b_1 - a_1)^2 + (b_2 - a_2)^2 + \cdots + (b_n - a_n)^2

 = x^2 + (x + d + c_2)^2 + \cdots + (x + (n - 1)d + c_n)^2

ここで、

 c_i = a_1 - a_i

とします。この  f(x, d) を最小化する  x, d を求めるにはいくつか方法があると思います。高校数学の範囲では平方完成を用いて求めると思います。

mathtrain.jp

僕は偏微分を用いて計算しました。 f x偏微分して得られる方程式は、

 \dfrac{\partial f}{\partial x} = 2x + 2(x + d + c_2) + \cdots + 2(x + (n - 1)d + c_n) = 0

となります。

 2nx + n(n - 1)d + 2S_1 = 0

ここで、

 S_1 = c_2 + c_3 + \cdots + c_n

とします。 f d偏微分して得られる方程式は、

 \dfrac{\partial f}{\partial d} =2(x + d + c_2) + 2 \cdot 2(x + 2d + c_2) \cdots + 2 \cdot (n - 1)(x + (n - 1)d + c_n) = 0

 3n(n - 1) + n(n - 1)(2n - 1)d + 6S_2 = 0

となります。ここで、

 S_2 = c_2 + 2c_3 + \cdots + (n - 1)c_n

とします。以上より2つの変数に対して2つの方程式が得られたので、連立方程式を解きます。2変数の連立方程式の一般解は下のサイトで確認できます。

mathtrain.jp

方程式を導く上で、2乗和の公式を使っています。

コード

import java.util.Scanner;

public class Exec0731 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double N = scan.nextInt();
        double[]a = new double[(int)N];
        for(int i = 0; i < N; i++) {
            a[i] = scan.nextLong();
        }
        scan.close();
        double sum1 = 0;
        double sum2 = 0;
        for(int i = 0; i < N - 1; i++) {
            sum1 += a[0] - a[i + 1];
            sum2 += (i + 1)  * (a[0] - a[i + 1]);
        }
        double A = 2 * N;
        double B = N * (N - 1);
        double p = -2 * sum1;
        double C = 3 * N * (N - 1);
        double D = N * (N - 1) * (2 * N - 1);
        double q = -6 * sum2;
        double t = A * D - B * C;
        double x = (p * D - B * q) / t;
        double y = (A * q - p * C) / t;
//     System.out.println(A + " " + B + " " + C + " " + D);
//     System.out.println(p + " " + q);
        double b1 = a[0] + x;
        double cost = 0;
        for(int i = 0; i < N; i++) {
            double k = a[0] + x + i * y - a[i];
            k *= k;
            cost += k;
        }
        System.out.println(b1 + " " + y);
        System.out.println(String.format("%.8f", cost));
    }
}

感想

レベル2の問題がなくて残念でしたが、C問題の解法を思いつくことができて良かったです。