AtCoder Beginner Contest 266

ABC

コンテスト前のレート：1928
レート通りのパフォーマンスが得られる順位：418位（2000点、57分50秒）

A - Middle Letter

問題

思考過程
  1. とりあえずS[\frac{length}{2}]を出力する。
  2. もし前後に1文字ズレているようだったら修正するつもりだったが、合っていたのでそのまま提出する。
import java.util.Scanner;

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

        System.out.println(s.charAt(s.length() / 2));
    }
}

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


B - Modulo Number

問題

思考過程
  1. 998244353=Mとして、M-N \% Mを求める感じ？と思ったが考えすぎで、基本はN \% Mでよさそう。
  2. それだけだと例２が-4になるので、N \% Mの結果がマイナスの場合はMを足す。
import java.util.Scanner;

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

        int mod = 998244353;
        long ans = n % mod;
        if (ans < 0) {
            ans += mod;
        }
        System.out.println(ans);
    }
}

ここまで2分51秒＋0ペナ。615位。


C - Convex Quadrilateral

問題

思考過程
  1. 2直線がなす角度が180度未満かどうかは内積か外積のようなもので判定できたような・・・と思って調べようとしてみるも、調べるのが下手で知りたい式がすぐに出てこない。（解説見たらやっぱり外積だった）
    　
  2. 誤差が怖いところではあるが、座標の制約が100とかならまあ大丈夫だろうと思い、角ABCの角度であれば「辺BCの傾き-辺ABの傾き」（ここでいう傾きはatan2で求まるラジアン単位の角度）のように求め、これが180度=\piより大きい角が存在するかどうかを判定することにする。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = 4;
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            int j = (i + 1) % n;
            int k = (i + 2) % n;
            double d1 = Math.atan2(y[j] - y[i], x[j] - x[i]);
            double d2 = Math.atan2(y[k] - y[j], x[k] - x[j]);
            double r = d2 - d1;
            if (r < 0) {
                r += Math.PI * 2;
            }
            if (r > Math.PI) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで10分38秒＋0ペナ。417位。


D - Snuke Panic (1D)

問題
配るDPならi → i+1、もらうDPならi-1 → iになるように書くのがわかりやすいと思っているのだが、混在した。

思考過程
  1. 時刻の制約が10^5しかないので、「DP[i][j]:=時刻iに座標jに高橋君がいるときの最大値」を考えてみる。
  2. すると、時刻(i-1)、座標(j-1)～(j+1)からの遷移が考えられる。
  3. 各遷移元のmaxを取り、遷移先がすぬけ君を捕まえられる時刻・座標であれば、大きさを加算する。
  4. 時刻・座標に該当するすぬけ君の情報をO(1)で取れるように入力の受け取り方を変更する。
  5. 答えはDP[10^5][i] (0 \leq i \leq 4)の最大値。
  6. 例２が3になってしまう。時刻4未満の間は遠くの座標には行けないため、座標が時刻以下であることの条件を付け足す。
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));
        int n = Integer.parseInt(br.readLine());
        int m = 100001;
        // 4
        int[] x = new int[m];
        int[] a = new int[m];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            x[t] = Integer.parseInt(sa[1]);
            a[t] = Integer.parseInt(sa[2]);
        }
        br.close();

        long[][] dp = new long[m][5];
        for (int i = 1; i < m; i++) {
            for (int j = 0; j < 5; j++) {
                // j → j-1
                if (j > 0) {
                    dp[i][j - 1] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
                // j → j
                dp[i][j] = Math.max(dp[i][j], dp[i - 1][j]);
                // j → j+1
                if (j < 4) {
                    dp[i][j + 1] = Math.max(dp[i][j + 1], dp[i - 1][j]);
                }
            }
            if (x[i] <= i) { // 6
                dp[i][x[i]] += a[i];
            }
        }

        // 5
        long ans = 0;
        for (int i = 0; i < 5; i++) {
            ans = Math.max(ans, dp[m - 1][i]);
        }
        System.out.println(ans);
    }
}

ここまで19分13秒＋0ペナ。275位。


E - Throwing the Die

問題

思考過程
  1. 例１はわかる。例２がどうやって求められているのか考える。
  2. 1回目が3.5以上なら終了し、そうでなければ2回目で3.5を出すとすると、(3.5 \times 3 + 4 + 5 + 6) \div 6 = 4.25で合う。
  3. 一般には、残り回数がRの時、次の結果がR-1回の期待値以上なら終了、そうでなければR-1回の期待値になるとする。これはメモ化再帰がわかりやすそう。（と思ったが1つ前しか見ないので普通に前から埋めていくDPでよかった。）
import java.util.Scanner;

public class Main {
    static int n;
    static double[] memo;

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

        memo = new double[n + 1];
        memo[1] = 3.5;
        System.out.println(dfs(n));
    }

    static double dfs(int rem) {
        if (memo[rem] > 0) {
            return memo[rem];
        }

        double v1 = dfs(rem - 1);
        int v2 = 0;
        int c = 0;
        for (int i = 1; i <= 6; i++) {
            if (i > v1) {
                v2 += i;
            } else {
                c++;
            }
        }
        return memo[rem] = (v1 * c + v2) / 6;
    }
}

ここまで29分58秒＋0ペナ。264位。


F - Well-defined Path Queries on a Namori

問題

思考過程
  1. サイクルが1つだけ存在し、その部分を通る場合"No"となる。
  2. サイクルを構成する頂点を通るかどうかを調べる？　いや、サンプルではサイクルを構成する頂点を1つ通るだけでは"Yes"となっており、2つ通る必要がありそう。
    　
  3. 元のグラフをサイクルの各頂点を根とするいくつかの木に分解してみると、x_iとy_iの根が同じかどうかを判定する問題になる。
  4. サイクルを検出するために通った頂点の履歴を持ちながらDFSを行う。
  5. サイクルの各頂点からDFSを行って根がどこかの情報を設定しておく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;

public class Main {
    static int n;
    static List<List<Integer>> list;
    static int[] root;
    static LinkedHashSet<Integer> roots;

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

        // 4
        roots = dfs(0, -1, new LinkedHashSet<>());
        // 5
        root = new int[n];
        for (int i : roots) {
            dfs(i, -1, i);
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            if (root[x[i]] == root[y[i]]) {
                pw.println("Yes");
            } else {
                pw.println("No");
            }
        }
        pw.flush();
    }

    // 5
    static void dfs(int x, int p, int r) {
        root[x] = r;
        for (int c : list.get(x)) {
            if (c != p && !roots.contains(c)) {
                dfs(c, x, r);
            }
        }
    }

    // 4
    static LinkedHashSet<Integer> dfs(int x, int p, LinkedHashSet<Integer> his) {
        his.add(x);
        for (int c : list.get(x)) {
            if (c != p) {
                if (his.contains(c)) {
                    // hisから頂点c以降の経路を抜き出して返す
                    LinkedHashSet<Integer> ret = new LinkedHashSet<>();
                    int size = his.size();
                    Integer[] arr = his.toArray(new Integer[0]);
                    for (int i = 0; i < size; i++) {
                        if (arr[i] == c) {
                            for (int j = i; j < size; j++) {
                                ret.add(arr[j]);
                            }
                            return ret;
                        }
                    }
                }
                LinkedHashSet<Integer> res = dfs(c, x, his);
                if (res != null) {
                    return res;
                }
            }
        }
        his.remove(x);
        return null;
    }
}

ここまで46分50秒＋0ペナ。197位。


この時点で勝ったと思いたかったが、Gも既に100人以上解いていて、この伸び方だと最終的には400人くらい解いてしまうかもという感じでまだ油断はできそうにない。
（解けなければ356位でパフォ1990ほどだった）


G - Yet Another RGB Sequence

問題

思考過程
  1. "RG"（何か別の文字）をK個、"R"をR-K(=R_2)個、"G"をG-K(=G_2)個、"B"をB個並べると考える。ただし"R"の後ろに"G"は置けない。
  2. 上記4種の合計個数をSとして、"R"の後ろに"G"を置けない制約がなければ\frac{S!}{K!R_2!G_2!B!}になりそうだが、この制約をどのように考慮すればよいか。
    　
  3. S個の中からK個を選び、残りからR_2個を選び、\cdotsという考え方ではなく、初めにK個並んでいるところの間に特に制約なくR_2個を追加し、B個を追加し、最後にG_2個を追加する時のみ"R"を追加したR_2箇所の後ろには追加できないと考える。
  4. N個のボールの間にM個仕切りを追加する方法は、_{N+M}C_M通り。最後だけ_SC_{G_2}ではなく_{S-R_2}C_{G_2}となる。
import java.math.BigInteger;
import java.util.Scanner;

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

        int mod = 998244353;
        Kaijou kai = new Kaijou(3000000, mod);
        r -= k;
        g -= k;

        long vr = kai.comb(k + r, r);
        long vb = kai.comb(k + r + b, b);
        long vg = kai.comb(k + b + g, g);
        long ans = vr * vb % mod * vg % mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static class Kaijou {
        long[] p, pi;
        int m;

        public Kaijou(int n, int mod) {
            n++;
            m = mod;
            p = new long[n];
            pi = new long[n];
            p[0] = 1;
            pi[0] = 1;
            for (int i = 1; i < n; i++) {
                p[i] = p[i - 1] * i % m;
            }
            pi[n - 1] = BigInteger.valueOf(p[n - 1])
                    .modInverse(BigInteger.valueOf(m)).longValue();
            for (int i = n - 1; i > 1; i--) {
                pi[i - 1] = pi[i] * i % m;
            }
        }

        public long comb(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[r] % m * pi[n - r] % m;
        }

        public long perm(int n, int r) {
            if (n < r) return 0;
            return p[n] * pi[n - r] % m;
        }
    }
}

ここまで61分44秒＋0ペナ。89位。



Exに40分近くも使えるまたとない機会だったが解けず。

時刻かY座標かで並べ替えて、「i番目まで見た時にi番目の位置にいる場合の最大値」というDPを考えていたが、遷移元として可能な位置を全て調べてしまうとO(N^2)で駄目で、高速に求めるには二次元セグ木のようなものがほしい気がするけど持っておらず、普通のセグ木＋平面走査的な方法でどうにかならないかと考えたりはしたが、厳しかった。

順位表を見ていて解けなくてもパフォ2400に変わりはないだろうと思い、残り10分を切った辺りで諦め。



最終結果：ABCDEFGの7完2600点、61分44秒、93位、パフォーマンス2400
レート変動：1928→1985（+57）


直近3回で-124というひどさでこの先どこまで転落するかと思ったが、まさかの半分近い回復。
もう二度と黄色に戻れないかもなんて言いつつ、こんなにすぐ射程圏内に戻れるならまだなんとかなるのかもしれない。
まあでも今回はFやGがDPではなかったおかげかな。

なお、今回はABCにおける過去最高順位だった。

外積と二次元セグ木は使えるようにしておかなければ。