AtCoder Beginner Contest 183

ABC

コンテスト前のレート：1648
レート通りのパフォーマンスが得られる順位：632位（2100点、98分04秒）

A - ReLU

問題

思考過程
  1. マイナスを0に丸めるので、max(x, 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();
        sc.close();

        System.out.println(Math.max(x, 0));
    }
}

ここまで0分36秒＋0ペナ。342位。


B - Billiards

問題

思考過程
  1. S～反射点の長さ：反射点～Tの長さ
    = (x-S_x)：(G_x-x)=S_y：G_yが成り立つ。
  2. 少し見方を換えると、
    S～反射点の長さ：S～Tの長さ
    = (x-S_x)：(G_x-S_x)=S_y：(S_y+G_y)となる。
  3. これを変形していくと、
    (x-S_x) \times (S_y+G_y) = (G_x-S_x) \times S_y
    (x-S_x) = \frac{(G_x-S_x) \times S_y}{(S_y+G_y)}
    x = \frac{(G_x-S_x) \times S_y}{(S_y+G_y)} + S_x
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int sx = sc.nextInt();
        int sy = sc.nextInt();
        int gx = sc.nextInt();
        int gy = sc.nextInt();
        sc.close();

        double ans = (double) (gx - sx) * sy / (sy + gy) + sx;
        System.out.println(ans);
    }
}

ここまで5分18秒＋0ペナ。530位。


C - Travel

問題

思考過程
  1. O(N!)が間に合う制約なのでとりあえず順列全列挙する。
  2. 都市1を除いた順列の前後に都市1を追加したリストに対して、移動時間の合計を計算してKと一致するか判定する。
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int n, k;
    static int[][] t;
    static int ans = 0;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        k = sc.nextInt();
        t = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                t[i][j] = sc.nextInt();
            }
        }
        sc.close();

        int[] target = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            target[i] = i + 1;
        }
        permutation(target, new LinkedHashSet<>());
        System.out.println(ans);
    }

    // 以下、「if (set.size() == target.length)」内以外ライブラリ

    static void permutation(int[] target, LinkedHashSet<Integer> set) {
        if (set.size() == target.length) {
            List<Integer> list = new ArrayList<>();
            list.add(0);
            for (int i : set) {
                list.add(target[i]);
            }
            list.add(0);
            int sum = 0;
            for (int i = 1; i < list.size(); i++) {
                sum += t[list.get(i - 1)][list.get(i)];
            }
            if (sum == k) {
                ans++;
            }
            return;
        }

        for (int i = 0; i < target.length; i++) {
            if (!set.contains(i)) {
                set.add(i);
                permutation(target, set);
                set.remove(i);
            }
        }
    }
}

ここまで12分33秒＋0ペナ。619位。


D - Water Heater

問題

思考過程
  1. 問題文がぱっと読み取れなかったので、とりあえずちゃんと図示してみる。
  2. いもす法をして、Wを超えている箇所がないか調べるだけ。
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 w = Integer.parseInt(sa[1]);
        int[] s = new int[n];
        int[] t = new int[n];
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            s[i] = Integer.parseInt(sa[0]);
            t[i] = Integer.parseInt(sa[1]);
            p[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        long[] a = new long[200005];
        for (int i = 0; i < n; i++) {
            a[s[i]] += p[i];
            a[t[i]] -= p[i];
        }
        for (int i = 1; i < a.length; i++) {
            a[i] += a[i - 1];
        }
        for (int i = 0; i < a.length; i++) {
            if (a[i] > w) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで17分42秒＋0ペナ。412位。


E - Queen on Grid

問題
できてみれば単純だったが、累積和をごちゃごちゃにしたりして時間かかってしまった。

思考過程
  1. 上、左、左上からもらうDPを考える。
  2. 上からの遷移は、遷移元候補の各マスから1手で移動した場合の合計なので、dp[i][j]=\sum_{x=k}^{i-1}dp[x][j]となる（kは壁の次のマス）。左と左上からの遷移も同様。
  3. このままだとO(HW(H+W))なので、合計を求める部分を累積和にしたい。
  4. 累積和は3方向別々に取る必要がある。
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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        int mod = 1000000007;
        long[][] dp = new long[h][w];
        long[][] dp1 = new long[h][w];
        long[][] dp2 = new long[h][w];
        long[][] dp3 = new long[h][w];
        dp[0][0] = 1;
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == '#') {
                    continue;
                }
                // 縦
                if (i > 0 && s[i - 1][j] == '.') {
                    dp[i][j] += dp1[i - 1][j];
                    dp1[i][j] += dp1[i - 1][j];
                }
                // 横
                if (j > 0 && s[i][j - 1] == '.') {
                    dp[i][j] += dp2[i][j - 1];
                    dp2[i][j] += dp2[i][j - 1];
                }
                // 斜め
                if (i > 0 && j > 0 && s[i - 1][j - 1] == '.') {
                    dp[i][j] += dp3[i - 1][j - 1];
                    dp3[i][j] += dp3[i - 1][j - 1];
                }
                dp1[i][j] += dp[i][j];
                dp2[i][j] += dp[i][j];
                dp3[i][j] += dp[i][j];
                dp[i][j] %= mod;
                dp1[i][j] %= mod;
                dp2[i][j] %= mod;
                dp3[i][j] %= mod;
            }
        }
        System.out.println(dp[h - 1][w - 1]);
    }
}

ここまで34分31秒＋0ペナ。282位。


F - Confluence

問題

思考過程
  1. クエリ1はただのUnionFind。
  2. クエリ2は素直に考えれば、UnionFindの各頂点にMap＜クラス、人数＞の情報があればO(1)で求められる感じ。
  3. このマップの更新（合流する度にマージする）に多くの計算量がかかってしまいそうだが、必ず小さい方から大きい方にマージするマージテクをすれば、計算量が落ちるという話を見たことがある気がする。
  4. ACLのDSUにはサイズを見てマージする実装が組み込まれているので、それにマップの処理を追加してみた。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

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 q = Integer.parseInt(sa[1]);
        DSU uf = new DSU(n);
        sa = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            int c = Integer.parseInt(sa[i]);
            uf.list.get(i).put(c, 1);
        }
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            if (sa[0].equals("1")) {
                int a = Integer.parseInt(sa[1]) - 1;
                int b = Integer.parseInt(sa[2]) - 1;
                uf.merge(a, b);
            } else {
                int a = Integer.parseInt(sa[1]) - 1;
                int b = Integer.parseInt(sa[2]);
                int ans = uf.list.get(uf.leader(a)).getOrDefault(b, 0);
                pw.println(ans);
            }
        }
        br.close();
        pw.flush();
    }
}

// 以下「追加」コメント箇所以外ライブラリ

/**
 * Disjoint Set Union（Union Find）
 */
class DSU {
    private int n;
    private int[] parentOrSize;
    private int num;
    List<Map<Integer, Integer>> list; // 追加

    /**
     * n頂点0辺の無向グラフを作る。<br>
     * O(n)
     * 
     * @param n 頂点数
     */
    public DSU(int n) {
        this.n = n;
        this.parentOrSize = new int[n];
        Arrays.fill(parentOrSize, -1);
        num = n;
        // 追加start
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new HashMap<>());
        }
        // 追加end
    }

    /**
     * 辺(a, b)を足す。<br>
     * ならしO(α(n))
     * 
     * @param a 頂点番号（0≦a＜n）
     * @param b 頂点番号（0≦b＜n）
     * @return 代表元
     */
    int merge(int a, int b) {
        assert 0 <= a && a < n : "a=" + a;
        assert 0 <= b && b < n : "b=" + b;

        int x = leader(a);
        int y = leader(b);
        if (x == y) {
            return x;
        }
        if (-parentOrSize[x] < -parentOrSize[y]) {
            int tmp = x;
            x = y;
            y = tmp;
        }
        parentOrSize[x] += parentOrSize[y];
        parentOrSize[y] = x;
        num--;
        // 追加start
        Map<Integer, Integer> mapx = list.get(x);
        Map<Integer, Integer> mapy = list.get(y);
        for (Integer key : mapy.keySet()) {
            mapx.put(key, mapx.getOrDefault(key, 0) + mapy.get(key));
        }
        mapy.clear();
        // 追加end
        return x;
    }

    /**
     * 頂点a, bが連結かどうか。<br>
     * ならしO(α(n))
     * 
     * @param a 頂点番号（0≦a＜n）
     * @param b 頂点番号（0≦b＜n）
     * @return true：連結　false：非連結
     */
    boolean same(int a, int b) {
        assert 0 <= a && a < n : "a=" + a;
        assert 0 <= b && b < n : "b=" + b;

        return leader(a) == leader(b);
    }

    /**
     * 頂点aの属する連結成分の代表元を返す。<br>
     * ならしO(α(n))
     * 
     * @param a 頂点番号（0≦a＜n）
     * @return 代表元
     */
    int leader(int a) {
        assert 0 <= a && a < n : "a=" + a;

        if (parentOrSize[a] < 0) {
            return a;
        } else {
            return parentOrSize[a] = leader(parentOrSize[a]);
        }
    }
}

ここまで52分52秒＋0ペナ。220位。



最終結果：ABCDEFの全完、52分52秒、220位、パフォーマンス2088
レート変動：1648→1701（+53）


今回はできる問題を手堅く通せたという感じ。EのDPはもう少しスムーズに書けたかった。
正直Fが想定解通りだとはあまり思っていなかった。最近考察力がひどいので、後で「何でそんなことに気付かなかったんだ」と思うような方法があるのではという気がしていた。

5～9月は3回に1回黄パフォだったが、10月からボロボロで今回は10回ぶりの黄パフォ。間が青3回、水4回、緑2回なので本当にひどかった。
Highestの1820までは2200～2300程度を2回か、2550程度を1回出す必要があるくらいなので、まだまだ回復の道のりは遠いが、ひとまず一発水色落ちの心配はなくなって一安心。