AtCoder Beginner Contest 180 - ks2mのブログ

A - box
- 思考過程
B - Various distances
- 思考過程
C - Cream puff
- 思考過程
D - Takahashi Unevolved
- 思考過程
E - Traveling Salesman among Aerial Cities
- 思考過程
F - Unbranched
- 思考過程

コンテスト前のレート：1741
レート通りのパフォーマンスが得られる順位：413位（1500点、48分12秒）

A - box

問題
これ本番中、ボールの数はマイナスにならないって書いてないけどいいの？とか思ってたけど、後からよく見たら $100 \leq N$ だった。

思考過程

$N-A+B$ を出力する。

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 = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        System.out.println(n - a + b);
    }
}

ここまで0分35秒＋0ペナ。263位。

B - Various distances

問題
$N$ 次元空間内の $1$ 点ではなく、 $N$ 個の点をイメージして意味不明になっていた。
問題文の通りとは思いつつも、その意味不明さのせいで手が動き出すのが遅かった。

思考過程

問題文に書かれている式の通りにそれぞれ $O(N)$ で計算する。
$2$ 乗の計算で一発でint型の範囲を超えるのでオーバーフローしないように注意する。

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[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
        }
        sc.close();

        // マンハッタン距離
        long m = 0;
        for (int i = 0; i < n; i++) {
            m += Math.abs(x[i]);
        }

        // ユークリッド距離
        long u = 0;
        for (int i = 0; i < n; i++) {
            long v = (long) x[i] * x[i]; // (long)を忘れて1WA
            u += v;
        }
        double u2 = Math.sqrt(u);

        // チェビシェフ距離
        int c = 0;
        for (int i = 0; i < n; i++) {
            c = Math.max(c, Math.abs(x[i]));
        }

        System.out.println(m);
        System.out.println(u2);
        System.out.println(c);
    }
}

ここまで5分18秒＋1ペナ。1146位。

C - Cream puff

問題

思考過程

約数を $O(\sqrt{N})$ で列挙するライブラリを用意しているので、貼って結果を出力するだけ。

import java.util.ArrayList;
import java.util.List;
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();

        List<Long> list = divList(n);
        for (long l : list) {
            System.out.println(l);
        }
    }

    // 以下ライブラリ

    static List<Long> divList(long n) {
        List<Long> list = new ArrayList<>();
        long end = (long) Math.sqrt(n);
        for (int i = 1; i <= end; i++) {
            if (n % i == 0) {
                list.add((long) i);
            }
        }
        int i = end * end == n ? list.size() - 2 : list.size() - 1;
        for ( ; i >= 0; i--) {
            list.add(n / list.get(i));
        }
        return list;
    }
}

ここまで6分36秒＋1ペナ。482位。

D - Takahashi Unevolved

問題
問題の最後に書いてある「オーバーフローに注意してください。」が余計なお世話だと思っていたら、まさかそれでドハマりするとは・・・。
色々迷走しているのでソースは汚いです。

思考過程

$A$ 倍か $+B$ か、増分が大きい方を選択して得をすることはないので、小さい方を貪欲に選択していく。
$A$ 倍の方はシミュレーションしても $O(logB)$ くらいで済むが、 $+B$ は $O(Y)$ かかるので、 $A$ 倍の操作を終えた時点の値を $Z$ として、 $(Y-1-Z)/B$ を計算する。
　
9WA＋1TLEとか出て、どう考えてもlogオーダーなのに何故TLEなのか全然わからなくなる。
$Y \lt Z \leq B$ のような場合にミスしている雰囲気を感じたので $Y \lt B$ の場合をきちんと別で処理する。　→8WA＋1TLE
$A$ 倍の増分値が $A(X-1)$ になっていたので、 $(A-1)X$ に直す。　→5WA＋1TLE
$Y \lt B$ でない場合の方も、 $Y \lt Z$ になってしまっているかもと思い条件を付け足す。
ついでに、TLEは実は $A=1$ のケースが紛れ込んでいるのではと疑い、その場合にREを投げるようにしてみる。　→変わらず
初回の掛け算の時点で $X \times A$ がlongの範囲を超える可能性があることにやっと気付いたので対策する。

提出一覧

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long x = sc.nextLong();
        long y = sc.nextLong() - 1; // 思考過程2
        int a = sc.nextInt();
        int b = sc.nextInt();
        sc.close();

        // 思考過程6
        if (a == 1) {
            throw new Exception();
        }

        if (b > y) {
            // 思考過程4
            // このifの中を以下の処理に変えたが、
            // 初回提出の「b = (int) y;」だけでも問題なかった。
            long ans = 0;
            while (true) {
                x *= a;
                if (x > y) {
                    System.out.println(ans);
                    return;
                }
                ans++;
            }
        }

        long ans = 0;
        while (x <= b) { // 思考過程7
            long c = (a - 1) * x; // 思考過程5
            if (c < b && x * a <= y) { // 思考過程6
                x *= a;
                ans++;
            } else {
                break;
            }
        }

        long c = (y - x) / b; // 思考過程2
        System.out.println(ans + c);
    }
}

ここまで26分07秒＋5ペナ。765位。

E - Traveling Salesman among Aerial Cities

問題

思考過程

制約が $O(2^N)$ な感じ。
「 $dp[S]$ ：訪問済みの都市の集合が $S$ の場合の最小コスト」とすると $O(2^N)$ で状態を表せそうだが、遷移が書けない。
「 $dp[S][j]$ ：訪問済みの都市の集合が $S$ で、最後に訪問した都市が $j$ の場合の最小コスト」とすることで、 $j$ → $1$ ～ $N$ の遷移が書ける。
最後は、 $dp[2^N-1][i]$ の各 $i$ から $1$ へ遷移させたときの最小値を求める。

試していないが、DPテーブルの初期値を $10^{18}$ とか、足し算してもオーバーフローしない値にしておけば、if文は全部不要かもしれない。

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[] x = new int[n];
        int[] y = new int[n];
        int[] z = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            z[i] = sc.nextInt();
        }
        sc.close();

        int n2 = 1 << n;
        long[][] dp = new long[n2][n];
        for (int i = 0; i < n2; i++) {
            Arrays.fill(dp[i], Long.MAX_VALUE);
        }
        dp[1][0] = 0;
        for (int i = 1; i < n2; i++) {
            for (int j = 0; j < n; j++) {
                if ((i >> j & 1) == 1) {
                    for (int j2 = 0; j2 < n; j2++) {
                        if (j == j2 || dp[i][j] == Long.MAX_VALUE) {
                            continue;
                        }
                        long d = Math.abs(x[j2] - x[j])
                                + Math.abs(y[j2] - y[j])
                                + Math.max(z[j2] - z[j], 0);
                        int next = i | (1 << j2);
                        dp[next][j2] = Math.min(dp[next][j2], dp[i][j] + d);
                    }
                }
            }
        }

        long ans = Long.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            long d = Math.abs(x[0] - x[i])
                    + Math.abs(y[0] - y[i])
                    + Math.max(z[0] - z[i], 0);
            ans = Math.min(ans, dp[n2 - 1][i] + d);
        }
        System.out.println(ans);
    }
}

ここまで44分42秒＋5ペナ。466位。

F - Unbranched

問題
解けず。

思考過程

自己ループを持たず、全ての頂点の次数が $2$ 以下という条件から、各連結成分は単独の頂点か、一直線か、サイクル（連結成分のサイズが $2$ の場合は二重辺）になっている。
サイズが最大の連結成分の作り方は、一直線のパターンが $_NP_L/2$ 通り、サイクルのパターンが $_NP_L/L$ 通りかなと思う。
（一直線のパターン数） $\times$ （ $N-L$ 頂点 $M-(L-1)$ 辺のパターン数） $+$ （サイクルのパターン数） $\times$ （ $N-L$ 頂点 $M-L$ 辺のパターン数）　のような形で、以降連結成分のサイズを $1$ ～ $L$ で全探索しながらメモ化再帰したらどうかと思ったが、せめて全ての連結成分のサイズが異なるといった条件が追加で存在しないと、重複して数えてしまって厳しそうだと思った。