AtCoder Beginner Contest 243(Rated範囲外)

ABC

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

A - Shampoo

問題

思考過程
  1. V \lt Aという判定をしてもいいが、3回繰り返すので、VからAを引いてしまってマイナスならば不足したと判定してもよいかと思う。
  2. よく見たら1周でなくなるとは限らなかったが、無限ループで囲えばOK。
import java.util.Scanner;

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

        while (true) {
            v -= a;
            if (v < 0) {
                System.out.println("F");
                return;
            }

            v -= b;
            if (v < 0) {
                System.out.println("M");
                return;
            }

            v -= c;
            if (v < 0) {
                System.out.println("T");
                return;
            }
        }
    }
}

ここまで2分27秒＋0ペナ。441位。


B - Hit and Blow

問題

思考過程
  1. O(N^2)でよいので、素直に二重ループを回して突き合せることにする。
  2. A_i=B_jとなった時に、i=jかどうかで、答え1をカウントするか答え2をカウントするかを分ける。
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();
        }
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = sc.nextInt();
        }
        sc.close();

        int ans1 = 0;
        int ans2 = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (a[i] == b[j]) {
                    if (i == j) {
                        ans1++;
                    } else {
                        ans2++;
                    }
                }
            }
        }
        System.out.println(ans1);
        System.out.println(ans2);
    }
}

ここまで4分53秒＋0ペナ。359位。


C - Collision 2

問題

思考過程
  1. 入力をMap＜Y座標、X座標の集合＞の形に持ち替えれば判定できそう？
  2. 左向きと右向きが混在していると厄介なので、マップを2つ用意することにする。
  3. 1人目から順に、ぶつかる人がいるかの判定と、マップへの情報追加を行っていく。

なお、集合全部を持たなくても最大や最小だけ持てば十分で、それならばnull判定など色々減らせて下記コードよりもだいぶ短くなったと思う。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;
import java.util.TreeSet;

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

        Map<Integer, TreeSet<Integer>> mapL = new HashMap<>();
        Map<Integer, TreeSet<Integer>> mapR = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (s[i] == 'L') {
                // 右向きマップ内にぶつかる人がいるか
                TreeSet<Integer> set1 = mapR.get(y[i]);
                if (set1 != null) {
                    Integer e = set1.lower(x[i]);
                    if (e != null) {
                        System.out.println("Yes");
                        return;
                    }
                }
                // 左向きマップに自身の情報を追加
                TreeSet<Integer> set = mapL.get(y[i]);
                if (set == null) {
                    set = new TreeSet<>();
                    mapL.put(y[i], set);
                }
                set.add(x[i]);
            } else {
                // 左向きマップ内にぶつかる人がいるか
                TreeSet<Integer> set1 = mapL.get(y[i]);
                if (set1 != null) {
                    Integer e = set1.higher(x[i]);
                    if (e != null) {
                        System.out.println("Yes");
                        return;
                    }
                }
                // 右向きマップに自身の情報を追加
                TreeSet<Integer> set = mapR.get(y[i]);
                if (set == null) {
                    set = new TreeSet<>();
                    mapR.put(y[i], set);
                }
                set.add(x[i]);
            }
        }
        System.out.println("No");
    }
}

ここまで11分53秒＋0ペナ。353位。


D - Moves on Binary Tree

問題

思考過程
  1. 基本的には愚直にシミュレーションすればよさそうなのだが、途中でのオーバーフローへの対処が問題。
  2. BigIntegerを使うのは書くのがめんどくさくなるし、桁数が多くなるとTLEとなる心配もあるかもしれない。
  3. 10^{18}より大きくなった場合、必ず元の頂点に戻ってくるので、現在いる頂点の深さのみを管理しておくことにする。
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]);
        long x = Long.parseLong(sa[1]);
        char[] s = br.readLine().toCharArray();
        br.close();

        long lim = 1000000000000000000L; // 10^18
        int d = 0; // 10^18を超えた頂点からの深さ
        for (int i = 0; i < n; i++) {
            if (s[i] == 'U') {
                if (d > 0) {
                    d--;
                } else {
                    x /= 2;
                }
            } else if (s[i] == 'L') {
                if (x > lim) {
                    d++;
                } else {
                    x *= 2;
                }
            } else {
                if (x > lim) {
                    d++;
                } else {
                    x *= 2;
                    x++;
                }
            }
        }
        System.out.println(x);
    }
}

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


E - Edge Deletion

問題
すぐには解けず、FとGもある程度並行して考えていた。

思考過程
  1. クラスカル法のイメージで、辺の長さが短い順に要否判定と、必要なら連結処理をすることを考えてみる。
  2. 辺の両端の頂点が同一連結成分でない場合は必ず必要、同一連結成分の場合はA-Bパスの最短距離が縮む場合に限り必要そう。
  3. 同一連結成分の場合の判定にはO(N)に毛が生えたくらいはかけても大丈夫そうなので、ダイクストラ法を使うことにする。　→TLE
  4. よく考えたら辺数が多いため、これではlogを無視してもO(M^2)=O(N^4)なので駄目だった。
    　
  5. やっぱり何らかの形でO(N^3)であるワーシャルフロイド法を使いたい感じ。
  6. ワーシャルフロイド法の結果に対して、A-B間の距離がCより短ければその辺は不要？　→WA
    　
  7. 上記6.の他に、A-K-Bのように回り道して距離がCのパスが存在する場合も辺ABは不要になるが、どうやって判定するか？
  8. ワーシャルフロイド法の中で、同一値に更新しようとしたところをメモしておけばできそう。
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 m = Integer.parseInt(sa[1]);

        Obj[] arr = new Obj[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]) - 1;
            o.b = Integer.parseInt(sa[1]) - 1;
            o.c = Integer.parseInt(sa[2]);
            arr[i] = o;
        }
        br.close();

        int inf = 1000000000;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    d[i][j] = inf;
                }
            }
        }
        for (int i = 0; i < m; i++) {
            Obj o = arr[i];
            d[o.a][o.b] = o.c;
            d[o.b][o.a] = o.c;
        }
        int[][] c = new int[n][n]; // 8
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (d[i][k] != inf && d[k][j] != inf) {
                        int alt = d[i][k] + d[k][j];
                        if (alt < d[i][j]) {
                            // 最短距離が縮んだ場合は、その時点では唯一の最短経路
                            c[i][j] = 0;
                            d[i][j] = alt;
                        } else if (i != k && j != k && alt == d[i][j]) {
                            // i, jと異なる点を経由して同一距離の経路が見つかった
                            c[i][j] = 1;
                        }
                    }
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < m; i++) {
            Obj o = arr[i];
            // 6, 7
            if (d[o.a][o.b] < o.c || c[o.a][o.b] == 1) {
                ans++;
            }
        }
        System.out.println(ans);
    }

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

ここまで89分33秒＋3ペナ。742位。



Fは既に手に入った賞品の集合を持つO(2^NNK)とかくらいになるような形しか思い付かず。
GはO(\sqrt{X})まではさすがにわかったが、そこから先は頭がこんがらがってまともに考えられず。



最終結果：ABCDEの5完1500点、104分33秒、809位、パフォーマンス1583相当
レート変動：2020（Unrated）


最近自分の実力が黄色どころか青もないような気がして仕方がない。

最近ずっと疲れてもいそうだが、やっぱりそもそも知らないことが多そう。
DPは知識と発想の境目が微妙なところではあるが・・・。