デンソークリエイトプログラミングコンテスト2022(AtCoder Beginner Contest 239)(Rated範囲外)

コンテスト前のレート:2060
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:295位(2000点、71分42秒)

A - Horizon

問題

思考過程
  1. 一見ややこしいが基本的には問題文の通りの計算を行うだけ。
  2. int型ではオーバーフローする可能性があるため、最初からdouble型で計算する。
import java.util.Scanner;

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

        double ans = Math.sqrt(h * (12800000 + h));
        System.out.println(ans);
    }
}

ここまで1分08秒+0ペナ。219位。


B - Integer Division

問題

思考過程
  1. 単純に「/」で切り捨て除算を行おうとした場合、Xが負の場合は切り上げになってしまう。
  2. 負の場合はあらかじめ-9しておくことで帳尻を合わせる。
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();
        sc.close();

        if (x % 10 != 0 && x < 0) {
            x -= 9;
        }
        System.out.println(x / 10);
    }
}

ここまで2分45秒+0ペナ。300位。


C - Knight Fork

問題
さすがに長さ8の配列dx, dyを作ってfor文で処理するくらいはした方が早かったかもしれない。

思考過程
  1. 問題の図の通り、該当する点が8箇所しかないので、(x_1, y_1)(x_2, y_2)からの8箇所を列挙して比較する。
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

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

        Set<String> set = new HashSet<>();
        set.add((x1 - 2) + "-" + (y1 + 1));
        set.add((x1 - 2) + "-" + (y1 - 1));
        set.add((x1 - 1) + "-" + (y1 + 2));
        set.add((x1 - 1) + "-" + (y1 - 2));
        set.add((x1 + 1) + "-" + (y1 + 2));
        set.add((x1 + 1) + "-" + (y1 - 2));
        set.add((x1 + 2) + "-" + (y1 + 1));
        set.add((x1 + 2) + "-" + (y1 - 1));
        if (set.contains((x2 - 2) + "-" + (y2 + 1)) ||
                set.contains((x2 - 2) + "-" + (y2 - 1)) ||
                set.contains((x2 - 1) + "-" + (y2 + 2)) ||
                set.contains((x2 - 1) + "-" + (y2 - 2)) ||
                set.contains((x2 + 1) + "-" + (y2 + 2)) ||
                set.contains((x2 + 1) + "-" + (y2 - 2)) ||
                set.contains((x2 + 2) + "-" + (y2 + 1)) ||
                set.contains((x2 + 2) + "-" + (y2 - 1))) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで7分12秒+0ペナ。276位。


D - Prime Sum Game

問題

思考過程
  1. 範囲が狭いので全探索をする。
  2. CDのいずれを足しても素数にならない数iが存在すれば高橋君の勝ち。
  3. 素数判定はエラトステネスの篩を貼る。
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);
        int a = sc.nextInt();
        int b = sc.nextInt();
        int c = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        Eratosthenes era = new Eratosthenes(200);

        for (int i = a; i <= b; i++) {
            boolean flg = false;
            for (int j = c; j <= d; j++) {
                if (era.isSosuu(i + j)) {
                    flg = true;
                }
            }
            if (!flg) {
                System.out.println("Takahashi");
                return;
            }
        }
        System.out.println("Aoki");
    }

    // 以下ライブラリ

    static class Eratosthenes {
        int[] div;

        public Eratosthenes(int n) {
            div = new int[n + 1];
            if (n < 2) return;
            div[0] = -1;
            div[1] = -1;
            int end = (int) Math.sqrt(n) + 1;
            for (int i = 2; i <= end; i++) {
                if (div[i] == 0) {
                    div[i] = i;
                    for (int j = i * i; j <= n; j+=i) {
                        if (div[j] == 0) div[j] = i;
                    }
                }
            }
            for (int i = end + 1; i <= n; i++) {
                if (div[i] == 0) div[i] = i;
            }
        }

        public Map<Integer, Integer> bunkai(int x) {
            Map<Integer, Integer> soinsu = new HashMap<>();
            while (x > 1) {
                Integer d = div[x];
                soinsu.put(d, soinsu.getOrDefault(d, 0) + 1);
                x /= d;
            }
            return soinsu;
        }

        public boolean isSosuu(int x) {
            return div[x] == x;
        }
    }
}

ここまで10分29秒+0ペナ。190位。


E - Subtree K-th Max

問題
制約をまともに見ておらず時間ロス。

思考過程
  1. 頂点の情報を葉からまとめ上げながら木DPをし、現在調べている頂点に対するクエリをまとめて処理する。
  2. 頂点の情報は座標圧縮したBITで持ち、K_i番目は二分探索で求めるとかする? と思ったが、K_i \leq 20であるため、上位最大20個のみMultiSet(Javaにはないので自作)で保持するようにする。
  3. 1ケースのみTLEになったので、藁にも縋る思いでマージテクでごまかしてみて通った。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class Main {
    static int n, q;
    static int[] x;
    static List<List<Integer>> list;
    static List<List<Obj>> qList;

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

        Obj[] arr = new Obj[q];
        qList = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            qList.add(new ArrayList<>());
        }
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.v = Integer.parseInt(sa[0]) - 1;
            o.k = Integer.parseInt(sa[1]);
            arr[i] = o;
            qList.get(o.v).add(o);
        }
        br.close();

        dfs(0, -1);
        PrintWriter pw = new PrintWriter(System.out);
        for (Obj o : arr) {
            pw.println(o.ans);
        }
        pw.flush();
    }

    static MultiTreeSet<Integer> dfs(int a, int p) {
        MultiTreeSet<Integer> set = new MultiTreeSet<>();
        for (int c : list.get(a)) {
            if (c != p) {
                MultiTreeSet<Integer> res = dfs(c, a);
                // 思考過程3
                if (set.size < res.size) {
                    MultiTreeSet<Integer> t = res;
                    res = set;
                    set = t;
                }
                for (Object e : res.toArrayAll()) {
                    set.add((Integer) e);
                    if (set.size > 20) {
                        set.pollFirst();
                    }
                }
            }
        }
        set.add(x[a]);
        if (set.size > 20) {
            set.pollFirst();
        }
        Object[] arr = set.toArrayAll();
        // 頂点aに対するクエリの処理
        for (Obj o : qList.get(a)) {
            o.ans = (Integer) arr[arr.length - o.k];
        }
        return set;
    }

    static class Obj {
        int v, k, ans;
    }

    // 以下ライブラリ(長いため未使用メソッドを削除している)

    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        T pollFirst() {
            T e = map.firstKey();
            remove(e);
            return e;
        }

        Object[] toArrayAll() {
            Object[] arr = new Object[size];
            int idx = 0;
            for (T e : map.keySet()) {
                int num = map.get(e);
                for (int i = 0; i < num; i++) {
                    arr[idx] = e;
                    idx++;
                }
            }
            return arr;
        }
    }
}

ここまで42分30秒+3ペナ。929位。



Fは、足りない次数が最も少ない頂点と最も多い頂点を連結していくようなことをやろうとしていたが、実装に多大な時間がかかった上にWA。


G - Builder Takahashi

問題
終了1分16秒後にAC。

思考過程
  1. 最小カットの雰囲気なので、どうやったら最小カットが使えるかを考える。
  2. 最小カットは頂点ではなく辺をカットするものであるため、頂点を辺に変えたい。
  3. 頂点i2つにし、iからi+Nに容量c_iの辺を張ることにする。
  4. 他の辺は最小カットに影響を与えたくないので、容量infにしておく。
  5. 答えの金額が0になってしまい、上手くいかない。(ここでタイムアップ)
  6. 頂点1, Nをカットするのは駄目なので、c_1, c_Nをinfにする必要があった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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 m = Integer.parseInt(sa[1]);

        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++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            list.get(a).add(b);
            list.get(b).add(a);
        }
        sa = br.readLine().split(" ");
        long[] c = new long[n];
        for (int i = 0; i < n; i++) {
            c[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long inf = 10000000000000L;
        // 6
        c[0] = inf;
        c[n - 1] = inf;
        MaxFlow mf = new MaxFlow(n * 2);
        for (int i = 0; i < n; i++) {
            // 4
            for (int j : list.get(i)) {
                mf.addEdge(i + n, j, inf);
            }
            // 3
            mf.addEdge(i, i + n, c[i]);
        }
        long f = mf.flow(0, n * 2 - 1);

        // ACLのminCutは各頂点に到達可能かどうかが返される
        boolean[] b = mf.minCut(0);
        long ans = 0;
        int k = 0;
        List<Integer> list2 = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            // 倍加した頂点の一方のみ到達可能であれば、そこで切っている
            if (b[i] != b[i + n]) {
                list2.add(i + 1);
                ans += c[i];
                k++;
            }
        }
        System.out.println(ans);
        System.out.println(k);
        StringBuilder sb = new StringBuilder();
        for (int i : list2) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

// 以下ACLを移植したMaxFlow

提出
ここまで101分16秒+3ペナ。



終結果:ABCDEの5完1500点、57分30秒、1257位、パフォーマンス1355相当
レート変動:2060(Unrated)


結果はまたボロボロだが、Gが間に合っていればパフォ2200くらいだったのでまあ・・・。
それにしてもABCの成績全く安定しない。