AtCoder Beginner Contest 169 - ks2mのブログ

A - Multiplication 1
- 問題概要
- 思考過程
B - Multiplication 2
- 問題概要
- 思考過程
C - Multiplication 3
- 問題概要
- 思考過程
D - Div Game
- 問題概要
- 思考過程
E - Count Median
- 問題概要
- 思考過程
F - Knapsack for All Subsets
- 問題概要
- 思考過程

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

A - Multiplication 1

問題
自分が人にAtCoderのことを説明するとき、「一番簡単な問題はこんな感じ」と例に出すような内容。

問題概要

$A \times B$ を求めよ。

$1 \leq A, B \leq 100$
入力は全て整数

思考過程

$100^2$ はintの範囲に収まるのでint型でOK。

import java.util.Scanner;

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

        System.out.println(a * b);
    }
}

ここまで0分18秒＋0ペナ。71位。

B - Multiplication 2

問題
また単純な掛け算かと思いきや、結構気を付けることが多い。
サンプルのおかげで1ペナ回避。

問題概要

$N$ 個の整数 $A_1$ ～ $A_N$ が与えられる。
$A_1 \times \cdots \times A_N$ を求めよ。
ただし、結果が $10^{18}$ を超える場合は、'-1' を出力せよ。

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^{18}$
入力は全て整数

思考過程

単純に掛け算していき、 $10^{18}$ を超えたら '-1' とする実装では、 $10^{17}$ に $10^5$ を掛けたりするとlong型でもオーバーフローする。
オーバーフローしないように $10^{18}$ を超えるかどうか判定する方法がぱっと思いつかないので、BigIntegerを使うことで、オーバーフローを気にしないでよくする。
例３が、 $0$ を掛ける前に $10^{18}$ を超えることで '-1' になってしまったので、実際に掛け算していく前に $0$ が含まれているか判定する処理を追加した。

import java.math.BigInteger;
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();
        BigInteger[] a = new BigInteger[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextBigInteger();
            if (a[i].compareTo(BigInteger.ZERO) == 0) {
                System.out.println(0);
                return;
            }
        }
        sc.close();

        BigInteger lim = BigInteger.valueOf(1000000000000000000L);
        BigInteger ans = BigInteger.ONE;
        for (int i = 0; i < n; i++) {
            ans = ans.multiply(a[i]);
            if (ans.compareTo(lim) > 0) {
                System.out.println(-1);
                return;
            }
        }
        System.out.println(ans.toString());
    }
}

ここまで4分31秒＋0ペナ。649位。

C - Multiplication 3

問題
BigIntegerを使った後だったので、何も考えずにBigDecimalを使った。
改めて制約を見ると、多分doubleでは精度が足りなくて駄目なんだと思う。

問題概要

$A \times B$ の小数点以下を切り捨て、整数で出力せよ。

$0 \leq A \leq 10^{15}$
$0 \leq B \lt 10$
$A$ は整数
$B$ は小数第 $2$ 位まで与えられる

思考過程

BigDecimalを使ってそのまま掛け算し、整数に丸める。

import java.math.BigDecimal;
import java.util.Scanner;

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

        a = a.multiply(b).setScale(0, BigDecimal.ROUND_DOWN);
        System.out.println(a.toPlainString());
    }
}

ここまで6分29秒＋0ペナ。140位。

D - Div Game

問題
考察や実装より題意を把握するのに時間がかかった気がする。

問題概要

正の整数 $N$ が与えられる。 $N$ に対して以下の操作を最大何回行えるかを求めよ。

以下の条件をすべて満たす正の整数を選ぶ
- ある素数 $p$ と正の整数 $e$ を用いて $z=p^e$ と表せる
- $N$ が $z$ で割り切れる
- 以前の操作で選んだどの整数とも異なる
$N$ を $N/z$ に置き換える

入力は全て整数
$1 \leq N \leq 10^{12}$

思考過程

$z$ が素数の何乗かなので、素因数分解してみる。
$p$ が異なれば必ず $z$ も異なるので、素因数ごとに独立して考えても、以前の $z$ と被ることはない。
特定の素因数について考えたとき、以前と異なる数にするためには、 $e$ が異なればよいため、 $e=1, 2, \cdots$ の順に選べるだけ選ぶ。

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

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

        // 素因数分解（マップのキー：素因数　値：累乗数）
        Map<Long, Integer> map = bunkai(n);
        int ans = 0;
        for (int v : map.values()) {
            int sum = 0;
            for (int e = 1; ; e++) {
                sum += e;
                // 1 + 2 + ・・・が累乗数を超えたら終了
                if (sum > v) {
                    break;
                }
                ans++;
            }
        }
        System.out.println(ans);
    }

    // 以下ライブラリ

    static Map<Long, Integer> bunkai(long n) {
        Map<Long, Integer> soinsu = new HashMap<>();
        int end = (int) Math.sqrt(n);
        long d = 2;
        while (n > 1) {
            if (n % d == 0) {
                n /= d;
                if (soinsu.containsKey(d)) {
                    soinsu.put(d, soinsu.get(d) + 1);
                } else {
                    soinsu.put(d, 1);
                }
                end = (int) Math.sqrt(n);
            } else {
                if (d > end) {
                    d = n - 1;
                }
                d++;
            }
        }
        return soinsu;
    }
}

ここまで12分22秒＋0ペナ。134位。

E - Count Median

問題
解法エスパーに近いところから入ってしまったので、そこそこの裏付けができた段階で投げてしまったが、無事通った。

問題概要

$N$ 個の整数 $X_1$ ～ $X_N$ （ $A_i \leq X_i \leq B_i$ ）の中央値として考えられる値がいくつあるか求めよ。
※ $N$ が偶数のとき、中央値は中央 $2$ 要素の平均

$2 \leq N \leq 2 \times 10^5$
$1 \leq A_i \leq B_i \leq 10^9$
入力は全て整数

思考過程

例２を見て、 $N$ が奇数の場合は、「 $B$ の中央値 $-A$ の中央値 $+1$ 」ではないかと思う。
実際、 $X$ の中央値の最小値は全て $A$ と一致させた場合、最大値は全て $B$ と一致させた場合となる。
間の値も多分全部取れそう。念のため例２に適当に増やして $N=5$ で考えても多分同じ。
$N$ が偶数の場合は、 $A$ の中央 $2$ 要素の平均から $B$ の中央 $2$ 要素の平均まで $1/2$ ずつ全ての値を取れそうか？
$2$ 倍してみると、奇数の場合とほぼ同じで、 $A$ の中央 $2$ 要素の和から $B$ の中央 $2$ 要素の和まで全ての値を取れそう。

import java.util.Arrays;
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();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

        Arrays.sort(a);
        Arrays.sort(b);
        if (n % 2 == 1) {
            System.out.println(b[n / 2] - a[n / 2] + 1);
        } else {
            System.out.println((b[n / 2 - 1] + b[n / 2]) - (a[n / 2 - 1] + a[n / 2]) + 1);
        }
    }
}

ここまで22分20秒＋0ペナ。91位。
Fがとても難しければうれしいような途中経過になったけど、そんな甘くはなく。。

F - Knapsack for All Subsets

問題
ものすごく既視感のある問題。
問題名でピンと来て、実際にほとんど同じ過去問（ABC159-F：Knapsack for All Segments）がすぐに見つかったのだが、これの提出を流用したことで早く解けたのか、逆に引きずられて遅くなったのか・・・。

問題概要

長さ $N$ の整数列 $A_1$ ～ $A_N$ と正の整数 $S$ が与えられる。
集合 $\{1, 2, \ldots N\}$ の空でない部分集合 $T$ について、 $f(T)$ を以下のように定める。

$T$ の空でない部分集合 $\{x_1, x_2, \ldots x_k\}$ であって、 $A_{x_1} + A_{x_2} + \cdots + A_{x_k} = S$ を満たすものの個数

$T$ として考えられる集合 $2^N-1$ 通り全てに対する $f(T)$ の和を、 $998244353$ で割った余りを求めよ。

入力は全て整数
$1 \leq N, S, A_i \leq 3000$

思考過程

ABC159-Fの提出ソースをコピペしてきて、違うところを直すことを考える。
例１で見比べると、今回の方が $f(\{1, 3\})$ に相当するものが多い。ABC159-Fは連続する区間だったので全部で $_NC_2$ 通りだったが、今回は連続していない。
DPの遷移で、 $2^i$ を掛けたり $2^{N-i}$ を掛けたりなどいじってみるが、例３が合う気配が全くないので、雑なことをやめてちゃんと考える。
「 $dp[i][j]$ ： $i$ 個目の要素まで見て、合計が $j$ になる何らかの場合の数*1」という定義は概ねそのまま。
通常のナップサックDPのように、 $i$ 個目の要素を選ぶ場合と選ばない場合に分けて考える。
選ばない場合は、 $T$ に含めない場合と、 $T$ に含めた上で $T$ の部分集合に含めない場合の $2$ 通りがあるため、まずは「 $dp[i+1][j] += dp[i][j] \times 2$ 」とする。
選ぶ場合は、 $T$ に含めた上で $T$ の部分集合にも含める場合の $1$ 通りのみで、通常のナップサックDPと同様に $j$ から $j + A_i$ への遷移。
なんかいまいち自信を持てないけど、 $dp[N][S]$ と例３の答えが合ったので提出。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int mod = 998244353;
        long[][] dp = new long[n + 1][s + 1];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= s; j++) {
                dp[i + 1][j] += dp[i][j] * 2; // 選ばない場合
                if (j + a[i] <= s) {
                    dp[i + 1][j + a[i]] += dp[i][j]; // 選ぶ場合
                }
            }
            for (int j = 0; j <= s; j++) {
                dp[i + 1][j] %= mod;
            }
        }
        System.out.println(dp[n][s]);
    }
}

後から見てみれば、2倍する以外はただのナップサック。

最終結果：ABCDEFの全完、63分39秒、275位、パフォーマンス2113
レート変動：1781→1818

初めて1700を超えてから5ヶ月経ってようやく1800到達。

*1:「何らかの場合の数」は実際には答えそのものなのだが、この時点では何をカウントできているのかよくわかっていなかった。