AtCoder Beginner Contest 217(Rated範囲外)

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

A - Lexicographic Order

問題

思考過程

1. ただの文字列比較。Javaの場合はcompareToメソッドで比較できる。

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();
        String t = sc.next();
        sc.close();

        if (s.compareTo(t) < 0) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

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

B - AtCoder Quiz

問題
解法はいくつか思い浮かんだが、どれも入力以外で3行程度とかではできる気はせず。

思考過程

1. 入力をソートしたものと、文字列配列{"ABC", "AGC", "AHC", "ARC"}を比較して、最初に異なっていたところが抜けているものである。
2. for文にしたいが、分岐をつ書けば実際に上記の文字列配列を用意しなくても判定できる。

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        String [] s = new String[3];
        for (int i = 0; i < 3; i++) {
            s[i] = sc.next();
        }
        sc.close();

        Arrays.sort(s);

        if (!s[0].equals("ABC")) {
            System.out.println("ABC");

        } else if (!s[1].equals("AGC")) {
            System.out.println("AGC");

        } else if (!s[2].equals("AHC")) {
            System.out.println("AHC");

        } else {
            System.out.println("ARC");
        }
    }
}

ここまで2分54秒＋0ペナ。601位。

C - Inverse of Permutation

問題
こういうのは問題文とサンプルをゆっくり読んでもこんがらがる。

思考過程

1. 何も考えずに問題文の通りと実装するだけ。

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

        int[] q = new int[n];
        for (int i = 0; i < n; i++) {
            q[p[i]] = i;
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            sb.append(q[i] + 1).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで5分22秒＋0ペナ。709位。

D - Cutting Woods

問題

思考過程

1. クエリのとき、から左右に最も近い切られた位置が知りたい。
2. これは、クエリでをTreeSetに入れておくことで、lowerとhigherメソッドで取得できる。
3. nullチェックが面倒なので、番兵を入れておく。

import java.io.PrintWriter;
import java.util.Scanner;
import java.util.TreeSet;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int l = sc.nextInt();
        int q = sc.nextInt();
        TreeSet<Integer> set = new TreeSet<>();
        // 番兵
        set.add(0);
        set.add(l);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int c = sc.nextInt();
            int x = sc.nextInt();

            if (c == 1) {
                set.add(x);
            } else {
                int a = set.lower(x);
                int b = set.higher(x);
                pw.println(b - a);
            }
        }
        pw.flush();
        sc.close();
    }
}

ここまで8分32秒＋0ペナ。168位。

E - Sorting Queries

問題

思考過程

1. ソート済みの集合と、ソート後に追加した分の集合がほしい。
2. PriorityQueue（以下キュー）と普通のQueue（以下キュー）を用意し、クエリではキューが空でなければキューから、空ならばキューから取り出すようにする。
3. ソートはキューからキューに移す操作と捉えれば辻褄が合い、移す操作も全体でで済む。

import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int q = sc.nextInt();
        PriorityQueue<Integer> que = new PriorityQueue<>();
        Queue<Integer> que2 = new ArrayDeque<>();
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int t = sc.nextInt();
            if (t == 1) {
                que2.add(sc.nextInt());
            } else if (t == 2) {
                if (!que.isEmpty()) {
                    pw.println(que.poll());
                } else {
                    pw.println(que2.poll());
                }
            } else {
                que.addAll(que2);
                que2.clear();
            }
        }
        pw.flush();
        sc.close();
    }
}

ここまで11分06秒＋0ペナ。40位。

F - Make Pair

問題
思考過程7.くらいまでで諦めかけたけどなんとか通せた。

思考過程

1. 典型90問-019とかなり近い形をしており、区間DPを考える。
2. 「以上以下の範囲での答え」とし、遷移は左右に二分割する場合の分割箇所を全探索と、両端を取り除く（両端が最後に残る場合に対応する）ケースとする。
   というか、の相方としてを全部調べたいが、と組になるケースだけ分け方が異なってしまう感じ。
   　
3. 両端を取り除くケースは、通り。
4. 左右に二分割するケースは、とを組にするとして、通り？　いや例２を見ると、さらに倍？
5. 絶対違いそうだが、サンプルが弱くてあまり大したテストができず、しばらく進展させられそうにないので一応一度提出してやっぱりWA。
   　
6. 上記4.で左側を、右側をとして、を掛ける？などと思ったりするが、近い数のコンビネーションは求められない。
7. そもそも、の場合を手作業で数えてみると、上手くやらないとに分けた時と、に分けた時に、どちらも→→という手順をカウントするといった重複が出たりする。
   　
8. DPテーブルをつにして、DPは最後に両端を取る場合に限定した通り数、DPは制約なしとし、左右分割のパターンで片方をDPから、もう片方をDPから取得すれば、重複がなくなりそう。（上記7.で、に分けた時の左側からは、→しかカウントしない）
   　
9. 上記8.で取得したとの組み合わせ通りに、左右から選ぶ順番の通り数として何倍すればよいかは、左右それぞれの要素数（操作数）をとして、となる。
   　
10. これで今度はTLEも出たが、DPを求める時に左右分割パターンの処理まで流れてしまう実装ミスがあっておかしくなっているだけだった。

import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int n, m, n2;
    static int mod = 998244353;
    static boolean[][] ok;
    static long[][] dp1, dp2;
    static Kaijou kai;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int n2 = n * 2;
        ok = new boolean[n2][n2];
        for (int i = 0; i < m; i++) {
            int a = sc.nextInt() - 1;
            int b = sc.nextInt() - 1;
            ok[a][b] = true;
        }
        sc.close();

        kai = new Kaijou(n, mod);
        dp1 = new long[n2][n2];
        dp2 = new long[n2][n2];
        for (int i = 0; i < n2; i++) {
            Arrays.fill(dp1[i], -1);
            Arrays.fill(dp2[i], -1);
        }

        long ans = dfs(0, n2 - 1, 2);
        System.out.println(ans);
    }

    // t=1の場合、両端パターン限定とする
    static long dfs(int l, int r, int t) {
        // DP(メモ)が既にある場合
        if (t == 1 && dp1[l][r] != -1) {
            return dp1[l][r];
        }
        if (t == 2 && dp2[l][r] != -1) {
            return dp2[l][r];
        }

        // 範囲の長さが2の場合
        if (l + 1 == r) {
            if (ok[l][r]) {
                return dp1[l][r] = dp2[l][r] = 1;
            } else {
                return dp1[l][r] = dp2[l][r] = 0;
            }
        }

        // 10. ここが抜けていた
        if (t == 1 && !ok[l][r]) {
            return dp1[l][r] = 0;
        }

        long ret = 0;
        // 両端を取り除くパターン
        if (l + 1 < r && ok[l][r]) {
            ret += dfs(l + 1, r - 1, 2);
            if (t == 1) {
                return dp1[l][r] = ret;
            }
        }
        // 左右二分割パターン
        for (int i = l + 1; i < r; i += 2) {
            long v1 = dfs(l, i, 1);
            long v2 = dfs(i + 1, r, 2);
            ret += v1 * v2 % mod * kai.comb((r - l + 1) / 2, (i - l + 1) / 2) % mod;
        }
        ret %= mod;
        return dp2[l][r] = ret;
    }

    // 以下ライブラリ（階乗を前計算してnCrをO(1)で求める）

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

ここまで76分01秒＋2ペナ。357位。

GとHは何もわからず。
Fに時間がかかりすぎたので最初から諦め気味ではあったが、FとGの正解者数あまり変わらないのに、20分あってもGが全く見当も付かないのは・・・。

最終結果：ABCDEFの6完2000点、86分01秒、446位、パフォーマンス1942相当
レート変動：2034（Unrated）

パフォ2034は、ちょうど2100点最遅か2000点最速かという辺りだった。

今回はDとEが比較的得意そうなタイプの問題で早くできた。
Fが典型90問で類題をやったばかりで区間DPで行こうとするまでは早かったのに、その後がひたすら長かった。
Gもできない辺り、やっぱりDPはもっとどうにかしないと。