ks2mのブログ

トヨタ自動車プログラミングコンテスト2022(AtCoder Beginner Contest 270)(Rated範囲外)

ABC

A - 1-2-4 Test
- 思考過程
B - Hammer
- 思考過程
C - Simple path
- 思考過程
D - Stones
- 思考過程
E - Apple Baskets on Circle
- 思考過程
F - Transportation
- 思考過程

コンテスト前のレート：2023
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：334位（2000点、72分42秒）

A - 1-2-4 Test

思考過程

$1, 2, 4$ 点のそれぞれについて、少なくとも一方が解けているか調べたい。
$1$ 点について調べようと思うと、 $A, B$ いずれかについて下から $1$ ビット目が立っているかどうかを調べることになる。
全部まとめると結局 $A$ or $B$ を求めるだけだった。

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);
    }
}

ここまで1分00秒＋0ペナ。157位。

B - Hammer

思考過程

場合分けを丁寧に行う。
まず原点から見て $X$ が $Y$ より手前にあるかを知りたいが、ややこしいので $Y$ が正か負かで分ける。
$Y \gt 0$ とすると、 $X \lt Y$ ならば壁の影響なく $|X|$ でゴールに到達する。
$X \gt Y$ の場合、 $Z \lt Y$ ならば $|Z| + |X-Z|$ でゴールに到達でき、そうでなければ到達不可。
$Y \lt 0$ の場合も判定を逆にして同様。

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

        if (y > 0) {
            if (x < y) {
                System.out.println(Math.abs(x));
            } else {
                if (z < y) {
                    System.out.println(Math.abs(z) + Math.abs(x - z));
                } else {
                    System.out.println(-1);
                }
            }
        } else {
            if (y < x) {
                System.out.println(Math.abs(x));
            } else {
                if (y < z) {
                    System.out.println(Math.abs(z) + Math.abs(x - z));
                } else {
                    System.out.println(-1);
                }
            }
        }
    }
}

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

C - Simple path

思考過程

履歴を持ちながら $X$ を始点にDFSを行い、 $Y$ に到達した時点で終了させる。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int n, x, y;
    static List<List<Integer>> list;

    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]);
        x = Integer.parseInt(sa[1]) - 1;
        y = Integer.parseInt(sa[2]) - 1;
        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);
        }
        br.close();

        List<Integer> res = dfs(x, -1, new ArrayList<>());
        StringBuilder sb = new StringBuilder();
        for (int i : res) {
            sb.append(i + 1).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static List<Integer> dfs(int c, int p, List<Integer> his) {
        his.add(c);
        if (c == y) {
            return his;
        }
        for (int i : list.get(c)) {
            if (i != p) {
                List<Integer> res = dfs(i, c, his);
                if (res != null) {
                    return res;
                }
            }
        }
        his.remove(his.size() - 1);
        return null;
    }
}

ここまで9分22秒＋0ペナ。178位。

D - Stones

思考過程

反例ぱっと思い付かないが、制約が微妙に小さいしおそらく貪欲では駄目なのだろう。
DPをするならば、「 $dp[i]:=$ 山が $i$ 個の時の答え」として小さい方から求めていく感じだろうか。
遷移は $A_1$ ～ $A_K$ のいずれか可能な個数を選んだ場合ということになるが、 $A_j$ について調べる際は、先手が $A_j$ 個取った後に後手が $i-A_j$ → $P_{i-A_j}$ 個にするとすると、 $dp[P_{i-A_j}]+A_j$ の最大値を求めることになる。
こんがらがってきたので、先手後手それぞれ用に、DP配列と遷移元配列を用意しておく。結局先手後手共に同じ内容になるだけで分ける意味はなさそうだったが。

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

        int[] dp1 = new int[n + 1];
        int[] dp2 = new int[n + 1];
        int[] pre1 = new int[n + 1];
        int[] pre2 = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < k; j++) {
                int ni = i - a[j];
                if (ni < 0) {
                    break;
                }

                int val1 = dp1[pre2[ni]] + a[j];
                if (val1 > dp1[i]) {
                    dp1[i] = val1;
                    pre1[i] = ni;
                }

                int val2 = dp2[pre1[ni]] + a[j];
                if (val2 > dp2[i]) {
                    dp2[i] = val2;
                    pre2[i] = ni;
                }
            }
        }
        System.out.println(dp1[n]);
    }
}

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

E - Apple Baskets on Circle

問題
合計がちょうど $K$ 個の場合に何も出力しないミスがあって1ペナ。

思考過程

最後の $1$ 周以外は計算で求め、最後の $1$ 周だけシミュレーションする形にしたい。
$A$ を昇順にソートした数列を $B$ とする。
合計が $K$ 以下である限り、 $N \times B_1 + (N-1) \times (B_2 - B_1) + (N-2) \times (B_3 - B_2) + \cdots$ と足していく。
次足したら $K$ を超えるというところで、 $K$ まで足りない個数を「 $N-$ 上記の処理回数」で割ってあと何周するかを求め、余りを取ることで最後の $1$ 周で何個必要かを求める。

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

        PriorityQueue<Long> que = new PriorityQueue<>();
        for (int i = 0; i < n; i++) {
            que.add(a[i]);
        }

        long x = 0;   // 周回数
        long sum = 0; // これまでに食べた合計
        int n2 = n;   // 1個以上残っているかごの数
        long rem = 0; // 最後の1周の際、kまであといくつ足りないか
        while (!que.isEmpty()) {
            long cur = que.poll();
            long d = cur - x;
            long wk = d * n2;
            if (sum + wk <= k) {
                sum += wk;
                n2--;
                x = cur;
            } else {
                rem = k - sum;
                long t = rem / n2;
                x += t;
                rem %= n2;

                break;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (a[i] <= x) {
                sb.append(0).append(' ');
            } else {
                if (rem > 0) {
                    // 最後の1周で食べる必要がある場合
                    sb.append(a[i] - x - 1).append(' ');
                    rem--;
                } else {
                    sb.append(a[i] - x).append(' ');
                }
            }
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで40分16秒＋1ペナ。324位。

F - Transportation

思考過程

空港を建設するのは $N+1$ 個目の島と繋ぎ、港を建設するのは $N+2$ 個目の島と繋ぐとみなしてクラスカル法をする。
$1$ ～ $N$ が連結になった時点で打ち切る。　→WA
　
空港や港が $1$ 回しか建設されずに無駄になったりして損する場合がありそう？
空港、港、道路それぞれを使うか使わないか、どれも使わないのはなしとして $2^3-1$ 通り試せば問題なさそう。　なお実際には空港島と港島を繋げるか繋げないかの $2^2$ 通りでよかったらしい。

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

public class Main {
    static int n, m;
    static int[] x, y;
    static Hen[] arr;

    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]);
        m = 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]);
        }
        sa = br.readLine().split(" ");
        y = new int[n];
        for (int i = 0; i < n; i++) {
            y[i] = Integer.parseInt(sa[i]);
        }
        arr = new Hen[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Hen h = new Hen();
            h.a = Integer.parseInt(sa[0]) - 1;
            h.b = Integer.parseInt(sa[1]) - 1;
            h.c = Integer.parseInt(sa[2]);
            arr[i] = h;
        }
        br.close();

        long ans = Long.MAX_VALUE;
        for (int i = 1; i < 8; i++) {
            ans = Math.min(ans, calc(i));
        }
        System.out.println(ans);
    }

    static long calc(int t) {
        int end = n;
        PriorityQueue<Hen> que = new PriorityQueue<>((o1, o2) -> o1.c - o2.c);
        // 道路
        if ((t & 1) == 1) {
            for (Hen h : arr) {
                que.add(h);
            }
        }
        // 空港
        if ((t >> 1 & 1) == 1) {
            end++;
            for (int i = 0; i < n; i++) {
                Hen h = new Hen();
                h.a = i;
                h.b = n;
                h.c = x[i];
                que.add(h);
            }
        }
        // 港
        if ((t >> 2 & 1) == 1) {
            end++;
            for (int i = 0; i < n; i++) {
                Hen h = new Hen();
                h.a = i;
                h.b = n + 1;
                h.c = y[i];
                que.add(h);
            }
        }

        long ans = 0;
        UnionFind uf = new UnionFind(n + 2);
        while (!que.isEmpty()) {
            Hen h = que.poll();
            if (!uf.same(h.a, h.b)) {
                uf.union(h.a, h.b);
                ans += h.c;
                if (uf.size(0) == end) {
                    break;
                }
            }
        }
        if (uf.size(0) < end) {
            return Long.MAX_VALUE;
        }
        return ans;
    }

    static class Hen {
        int a, b, c;
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }

        /**
         * xとyが同一連結成分か
         */
        boolean same(int x, int y) {
            return find(x) == find(y);
        }

        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}

ここまで59分17秒＋2ペナ。244位。

GとExは何もわからず。
一応Gで時間いっぱい愚直をして見つかればそれを出力、時間オーバーなら-1を出力することをやってみたりしたがサンプルしか通らず。
15分ほど残して撤退。

解説見たらGは知らない単語が出てきていたし、Exは数式を解読する気も起こらないのでやっぱり自分には無理な問題だった。

最終結果：ABCDEFの6完2000点、69分17秒、309位、パフォーマンス2065相当
レート変動：2023（Unrated）

Eのミスが残念だったがまあそこそこの結果。
日本で絞って195位なので100位にも200位にも当たりそうにはないかな。