yukicoder contest 199 の感想 - ヤマカサのプログラミング勉強日記

問題

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問題の解法を思いつくことができて良かったです。