AtCoder Beginner Contest 178 - ks2mのブログ

A - Not
- 思考過程
B - Product Max
- 思考過程
C - Ubiquity
- 思考過程
D - Redistribution
- 思考過程
E - Dist Max
- 思考過程
F - Contrast
- 思考過程

コンテスト前のレート：1814
レート通りのパフォーマンスが得られる順位：496位

A - Not

思考過程

こういう入れ替えは、合計値から一方を引くともう一方になるので、 $1-X$ を計算する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        sc.close();

        System.out.println(1 - x);
    }
}

ここまで0分25秒＋0ペナ。135位。

B - Product Max

問題

思考過程

答えが正なら絶対値をなるべく大きくしたくて、答えが負なら絶対値をなるべく小さくしたい。
絶対値最大か最小が答えになるので、両端の組み合わせを $4$ 通り試してしまい、その中で最大のものを出力する。
$0$ をまたぐ場合、両端以外で $0$ を選ぶのが最大になるケースがないか念のため考えてみるが、正負を適切に選べば必ず答えを正にできるのでない。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long a = sc.nextLong();
        long b = sc.nextLong();
        long c = sc.nextLong();
        long d = sc.nextLong();
        sc.close();

        long ans = a * c;
        ans = Math.max(ans, a * d);
        ans = Math.max(ans, b * c);
        ans = Math.max(ans, b * d);
        System.out.println(ans);
    }
}

ここまで2分52秒＋0ペナ。780位。

C - Ubiquity

問題
C問題としては難しいと思ったけど、やや難程度だったらしい。

思考過程

「存在する」を数えようとすると、何個存在するかも何個目で存在するかもわからないので、「存在しない」を数えることを基本とする。
$0$ が存在しないのは、 $9^N$ 通り。 $9$ についても同じ。
「全体 $-$ $0$ が存在しない $-$ $9$ が存在しない $+$ 両方存在しない」を計算し、 $10^N-9^N-9^N+8^N$ 。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();

        int m = 1000000007;
        long a = power(10, n, m);
        long b = power(9, n, m);
        long c = power(8, n, m);
        long ans = a - b - b + c + m + m;
        ans %= m;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }
}

ここまで7分16秒＋0ペナ。390位。

D - Redistribution

問題
最近DPまとめコンテストをやっていた成果が出たかもしれない。

思考過程

数列の要素数を～個で全探索することを取っ掛かりとして考えてみると、以下のようになり、なんか再帰的にできそう。
- $1$ 要素のときは $[S]$ の $1$ 通り
- $2$ 要素のときは $1$ 要素目を $X$ 個と決めると、 $2$ 要素目が $S-X$ 個に決まる
- $3$ 要素のときは $1$ 要素目を $X$ 個と決めると、残りは $S-X$ 個から $2$ 要素取る場合と同じ
$dp[i]$ を「 $S=i$ の場合の答え」とすると、 $dp[i] = \sum_{j=0}^{i-3}dp[j]$ のようになる。
最初の $1$ 個目を $3$ ～ $i$ 個取る場合で全探索して、残りの部分はメモ化再帰とするのがイメージしやすかったので、その方針で実装していく。

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

public class Main {
    static long[] dp;
    static int mod = 1000000007;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int s = sc.nextInt();
        sc.close();

        dp = new long[s + 1];
        Arrays.fill(dp, -1);
        dp[0] = 1;
        System.out.println(dfs(s));
    }

    static long dfs(int s) {
        if (dp[s] != -1) {
            return dp[s];
        }

        long ret = 0;
        for (int i = s - 3; i >= 0; i--) {
            ret += dfs(i);
            ret %= mod;
        }
        return dp[s] = ret;
    }
}

ここまで15分00秒＋0ペナ。422位。

これでも比較的すんなり解けたと思ったので、250位くらいを期待していたのだが、全然早くなくて絶望し始める。

E - Dist Max

問題
マンハッタン距離全然わからん。45度回転させたところで何が変わるのかよくわからず、5分ほどでとりあえずF問題も確認。
20分程度で正解者数がE問題100人以上、F問題5人くらいとかで、Eがかなり簡単そうではあったが、わからないものはわからないのでFを頑張り、1600点を狙う。
結局Fも解けず、ラスト10～15分でEに戻ってきたらぎりぎり解けた。

思考過程

マンハッタン距離の特徴について調べる。競技プログラミングにおけるマンハッタン距離問題まとめというのが見つかる。
「回転前のマンハッタン距離 = 回転後のチェビシェフ距離（座標の差の最大値）」と書かれているが、まだピンと来ていない。
　
とりあえず例１を $x+y$ と $x-y$ に置き換えてみる。 $(2, 0), (6, -2), (5, 1)$ 。
しばらく睨んで、 $1$ 番目と $2$ 番目は $6-2=4$ 、 $1$ 番目と $3$ 番目は $5-2=3$ 、 $2$ 番目と $3$ 番目は $1-(-2)=3$ となっていることに気付き、「回転後のチェビシェフ距離（座標の差の最大値）」の意味をようやく理解する。（ $x+y$ の差と $x-y$ の差の大きい方）
結局、「 $x+y$ の最大 $-$ 最小」と「 $x-y$ の最大 $-$ 最小」の大きい方が全体の答えになる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]);
            int b = Integer.parseInt(sa[1]);
            x[i] = a + b;
            y[i] = a - b;
        }
        br.close();

        Arrays.sort(x);
        Arrays.sort(y);
        System.out.println(Math.max(x[n - 1] - x[0], y[n - 1] - y[0]));
    }
}