AtCoder Beginner Contest 026

問題

D問題がかなり簡単というか、ニュートン法使う問題で楽に解けました。

A - 掛け算の最大値

受験数学でもありそうな問題ですね。

なので、 を[tex; x] かの関数として表しても良いし、相加平均・相乗平均の関係から、 と分かります。

が偶数なのも優しいですね。

B - N重丸

一瞬、ん？と考えさせられましたが、十財に円を描いてみると分かりやすいですね。例題もヒントになっています。

コード

import java.util.Arrays;
import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int []R = new int[N];
        for(int i = 0; i < N; i++) {
            R[i] = scan.nextInt();
        }
        scan.close();
        Arrays.sort(R);

        double ans = 0;
        int sng = 1;
        for(int i = N - 1; i >= 0; i--) {
            ans += sng * R[i] * R[i];
            sng *= -1;
        }
        ans = ans * Math.PI;
        System.out.println(ans);

    }
}

C - 高橋君の給料

根付き木を使う問題かな？と思って解くのをあきらめたんですが、解説を見るとそうではないようでした。なので、もう一回考えて解きました。

コード

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        int []B = new int[N];
        for(int i = 0; i < N - 1; i++) {
            B[i] = scan.nextInt();
        }
        scan.close();
        Map<Integer, ArrayList<Integer>> map = new HashMap<Integer, ArrayList<Integer>>();
        for(int i = 1; i <= N - 1; i++) {
            if(map.containsKey(B[i - 1])) {
                ArrayList<Integer> list = map.get(B[i - 1]);
                list.add(i + 1);
                map.put(B[i - 1], list);
            }else {
                ArrayList<Integer> list = new ArrayList<Integer>();
                list.add(i + 1);
                map.put(B[i - 1], list);
            }
        }
        int []m = new int[N + 1];
        for(int i = 1; i <= N; i++) {
            if(!map.containsKey(i)) {
                m[i] = 1;
            }
        }

        for(int i = N; i >= 1; i--) {
            if(map.containsKey(i)) {
                ArrayList<Integer> list = map.get(i);
                if(list.size() == 1) {
                    m[i] = 2 * m[list.get(0)] + 1;
                }else {
                    int t1 = list.get(0);
                    int t2 = list.get(1);
                    int min = Math.min(m[t1], m[t2]);
                    int max = Math.max(m[t1], m[t2]);
                    for(int j = 2; j < list.size(); j++) {
                        int t = list.get(j);
                        min = Math.min(min, m[t]);
                        max = Math.max(max, m[t]);
                    }
                    m[i] = min + max + 1;
                }
            }
        }
        System.out.println(m[1]);

    }
    static void disp(int []m) {
        for(int i = 0; i < m.length - 1; i++) {
            System.out.println(m[i + 1]);
        }
    }
}

D - 高橋君ボール1号

方程式を解く問題です。三角関数と多項式が混じっているので代数的に解くことが難しいです。なので数値計算で解きましょう。

ニュートン法で解くことができるとおもいます。

入試問題の背景としてのニュートン法 | 高校数学の美しい物語

ニュートン法の初期値をどうするかですか、

とすると、

になるので、この点から始めるとよさそうです。あんまりニュートン法について詳しくないんですが、 を満たす解が見つからなければ、初期値を変えて対応しましょう。

コード

import java.util.Scanner;

public class ProblemD {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        double A = scan.nextDouble();
        double B = scan.nextDouble();
        double C = scan.nextDouble();
        scan.close();
        double t0 = (B + 100 )/ A;
        //double f0 = A * t0 + B * Math.sin(C * Math.PI * t0);
        //System.out.println(f0);
        // g(t) = At + B sin(Cπt) - 100
        // dg / dt = A + BCπcos(Cπt)
        double temp = t0;
        double t = 0;
        for(int i = 0; i < 1000; i++) {
            t = temp - (A * temp + B * Math.sin(C * Math.PI * temp) - 100)
                    / (A + B * C * Math.PI * Math.cos(C * Math.PI * temp));
            temp = t;
            double f = A * t + B * Math.sin(C * Math.PI * t);
            //System.out.println(f);
            if(Math.abs(f - 100) < 0.00000001) {
                break;
            }
        }
        System.out.println(t);
    }
}