AtCoder Beginner Contest 102 の感想

AtCoder Beginner Contest 102

AtCoder Beginner Contest 102 - AtCoder

今回はC問題まで解くことができました。D問題は解く方針はなんとなく分かりましたが、実装することはできませんでした。

A - Multiple of 2 and N

が偶数であれば を出力し、奇数であれば、 を出力します。

与えられる数値が意味もなく大きいのはなんだかなといつも思います。

B - Maximum Difference

数列の最大値と最小値を求める問題です。

C - Linear Approximation

絶対値の和に関する問題です。大学受験数学でたまに見かける問題ですね。

2017年慶応大医学部の問題で証明問題が出されていますね。

www.k-kyogoku.com

証明に挑戦してみようかな。

メタ的に考えると、全ての について計算する余裕がないので、最大値、最小値、中央値、最頻値、平均値などの有名な統計量を調べるとよかったかもしれないです。

コード

import java.util.Arrays;
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; i++) {
            B[i] = scan.nextInt() - i - 1;
        }
        scan.close();
        if(N == 1) {
            System.out.println(0);
            System.exit(0);
        }
        Arrays.sort(B);
        long sum = 0;
        long min = 10000000000000000L;
        int k[] = {B[N/2], B[N/2 + 1]};
        for(int i = 0; i < 2; i++) {
            sum = 0;
            for(int j = 0; j < N; j++) {
                sum += abs(k[i], B[j]);
            }
            if(min > sum) {
                min = sum;
            }
        }
        System.out.println(min);

    }
    static int abs(int a, int b) {
        if(a > b) {
            return a - b;
        }else {
            return b - a;
        }
    }
}

感想

今回、C問題を解くことができましたが、受験似たようなもの見たことがあるなと思って、「絶対値　最小」で検索して、

d.hatena.ne.jp

を見て解くことができました。まあ、ズルいっすね。

D問題は累積和を使って、計算量が 位になると当たりを付けたんですが、実装は無理でした。