AtCoder Beginner Contest 204(Rated範囲外)

コンテスト前のレート:2080
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:302位(1600点、89分29秒)

A - Rock-paper-scissors

問題

思考過程
  1. ARC117-Cを思い出し、3-x-yのような計算で求めたくなる。
  2. 上記では、例えばx=y=2のような場合に上手くいかない。
  3. 6-x-y3で割った余りを求めればできそう。
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();
        int y = sc.nextInt();
        sc.close();

        System.out.println((6 - x - y) % 3);
    }
}

ここまで1分11秒+0ペナ。254位。


B - Nuts

問題

思考過程
  1. maxかmin関数を使ってif文を使わずにできないかと思ったが、一瞬ではできず、素直に題意通り処理する。
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];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] >= 10) {
                ans += a[i] - 10;
            }
        }
        System.out.println(ans);
    }
}

ここまで2分31秒+0ペナ。334位。


C - Tour

問題

思考過程
  1. O(N^2)が通る制約なので、N回BFSを行い、たどり着いた都市の数をカウントする。
  2. スタート地点も忘れずにカウントする。
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.Queue;
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 m = sc.nextInt();
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            list.get(a).add(b);
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            Queue<Integer> que = new ArrayDeque<>();
            que.add(i);
            boolean[] b = new boolean[n];
            b[i] = true;
            ans++; // 2
            while (!que.isEmpty()) {
                int cur = que.poll();
                for (int nx : list.get(cur)) {
                    if (!b[nx]) {
                        que.add(nx);
                        b[nx] = true;
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで5分18秒+0ペナ。106位。


D - Cooking

問題

思考過程
  1. Tの部分集合で、合計いくつのものが作れるかを知りたい。
  2. dp[i][j]:=i番目までで合計がjとなる部分集合が存在するか」をすると、O(N^2T_{max})なので間に合いそう。
  3. 遷移は、dp[i][j]がtrueの場合、dp[i+1][j]dp[i+1][j+T_i]をtrueにする。(j+T_iが配列外参照にならないように適当に対策する)
     
  4. 最終的に、Tの部分集合の合計でiが作れる場合、iと「Tの合計-i」の大きい方が答えの候補となるので、iを全部調べて答えの候補の最小値を求める。
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[] t = new int[n];
        for (int i = 0; i < n; i++) {
            t[i] = sc.nextInt();
        }
        sc.close();

        int m = 1000 * n;
        boolean[][] dp = new boolean[n + 1][m + 1];
        dp[0][0] = true;
        int sum = 0;
        for (int i = 0; i < n; i++) {
            sum += t[i];
            for (int j = 0; j <= m - t[i]; j++) {
                if (dp[i][j]) {
                    dp[i + 1][j] = true;
                    dp[i + 1][j + t[i]] = true;
                }
            }
        }

        int ans = Integer.MAX_VALUE;
        for (int i = 0; i <= m; i++) {
            if (dp[n][i]) {
                ans = Math.min(ans, Math.max(i, sum - i));
            }
        }
        System.out.println(ans);
    }
}

ここまで9分59秒+0ペナ。109位。



E問題は見事に三分探索にハマって解けず。
無限に6ケースWAを繰り返していた。

調べたことと言えば、X+\frac{1}{X}が下に凸であるっぽいことと、整数の三分探索の実装くらい。
(持っている三分探索が実数のものだけだったので、実装ミスがないか確認のために。)

最後に三分探索から離れてDの約数を全探索することを一瞬考えたが、約数を全列挙するO(M \sqrt{D})だけでTLEしそうと思って諦めた。


F問題は行列累乗使い慣れてなさ過ぎて無理。
W \leq 10^5とかならDPでできたかどうか・・・。



終結果:ABCDの4完1000点、9分59秒、773位、パフォーマンス1622相当
レート変動:2080(Unrated)


E問題、これだけ時間があったのだから、実験とかしてみてもよかったかもしれない。
いつも結構実験から入るくせに、こういう時だけ全く実験していないのは何故って感じ。

行列累乗はフィボナッチ数列を求めるレベルの簡単なものでもぱっとは書けないくらいなので、行列累乗を使う問題を何問か集めて練習した方がいいとは思いつつ、ここ数ヶ月ずっとモチベ低いのでやれていない。