第三回日本最強プログラマー学生選手権-予選-（ABC262）(Rated範囲外)

ABC

コンテスト前のレート：2052
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：303位（1500点、46分58秒）

A - World Cup

問題

思考過程
  1. Y \% 4からいい感じに何年後かを求められないかと思ったが、瞬間的にはわからず方針転換する。
  2. Yから増やしていって最初に2で割り切れた値を出力することにする。
import java.util.Scanner;

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

        for (int i = y; ; i++) {
            if (i % 4 == 2) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで1分46秒＋0ペナ。941位。


B - Triangle (Easier)

問題

思考過程
  1. 三重ループを回し、全ての(a, b, c)の組み合わせについて辺が存在するかを確認する。
  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 m = sc.nextInt();
        boolean[][] g = new boolean[n][n];
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt() - 1;
            int v = sc.nextInt() - 1;
            g[u][v] = true;
        }
        sc.close();

        int ans = 0;
        for (int a = 0; a < n; a++) {
            for (int b = a + 1; b < n; b++) {
                for (int c = b + 1; c < n; c++) {
                    if (g[a][b] && g[a][c] && g[b][c]) {
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで4分04秒＋0ペナ。448位。


C - Min Max Pair

問題

思考過程
  1. A_i=iの個数から2個選ぶ通り数が答えかと思ったら、例１を見るとA_i=jかつA_j=iのケースもある。
  2. 重複カウントが怖いので、iごとに対応するj(\gt i)を数えていくことにする。
    　
  3. A_i=iの場合、それより後ろにあるA_j=jの個数。これは事前に累積和をしておけば高速に求められる。
  4. A_i \neq iの場合、A_i \gt iかつA_{A_i}=iを満たすものが1個あるかないかしかない。
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());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]) - 1;
        }
        br.close();

        int[] c = new int[n + 1];
        for (int i = 0; i < n; i++) {
            if (a[i] == i) {
                c[i + 1]++;
            }
            c[i + 1] += c[i];
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            if (a[i] == i) {
                // 3
                ans += c[n] - c[i + 1];
            } else {
                // 4
                if (a[i] > i && a[a[i]] == i) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで9分14秒＋0ペナ。386位。


D - I Hate Non-integer Number

問題

思考過程
  1. とりあえず「dp[i][j]:=i番目まででj個選んだ場合の何か」のようなDPはやりたくなるが、最終的にjで割った余りが0になることをどう表すかが難しい。
  2. 最終的にM個選ぶと固定すれば、「dp[i][j][k]:=i番目まででj個選んでMで割った余りがkの通り数」ができる。
  3. DPの遷移は選ぶ場合と選ばない場合の2パターンで、答えに足すのはdp[N][M][0]。
  4. これだとO(N^4)だが、10^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));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        int mod = 998244353;
        long ans = 0;
        for (int m = 1; m <= n; m++) { // 最終的に選ぶ個数
            long[][][] dp = new long[n + 1][n + 1][m];
            dp[0][0][0] = 1;
            for (int i = 0; i < n; i++) { // 何番目まで見たか
                for (int j = 0; j <= i; j++) { // 何個選んだか
                    for (int k = 0; k < m; k++) { // mで割った余り
                        // 選ぶ
                        int nk = (k + a[i]) % m;
                        dp[i + 1][j + 1][nk] += dp[i][j][k];
                        dp[i + 1][j + 1][nk] %= mod;
                        // 選ばない
                        dp[i + 1][j][k] += dp[i][j][k];
                        dp[i + 1][j][k] %= mod;
                    }
                }
            }
            ans += dp[n][m][0];
            ans %= mod;
        }
        System.out.println(ans);
    }
}

ここまで22分38秒＋0ペナ。389位。



Eは何もわからず。
あまりに何もわからないので10～15分後くらいには飛ばしてFへ。
Fを解いた後は正解者数からGやExは無理だと判断したが、Eもわからないのは変わらず。

基本的にはDPを疑い続けており、次数に注目するのは一瞬だけ思い付きはしたが掘り下げることができなかった。


F - Erase and Rotate

問題

思考過程
  1. サンプルを見ていて、まずは末尾を先頭に移動させる操作（以下「回転」）を行う前提で考える。というか初めは行わない手段もあることに気付いていなかった。
    　
  2. まず、末尾から順に削除または回転を行うことを考えると、末尾K個の内で最小の要素を答えの先頭に持ってくることになる。
  3. 答えの2番目の要素は、最小要素の次から末尾までの間で最小の要素。
  4. 同様に末尾に達するまで区間最小値を選び続ける。選ばれない要素は削除する。
  5. ここまでで、例えば例３では(1, 3, 4)を答えに追加し、操作回数が2回余っている状態となる。
    　
  6. 続けて、先頭から上記2.で選んだ要素の手前までを処理する。
  7. 操作をそれ以上行えない場合は問答無用で答えに追加。
  8. 次の要素の方が小さいなら追加しない（削除する）。
  9. 次の要素の方が大きい場合は一旦追加するが、その前に「答えの末尾\gt現在の要素」の場合は、そうでなくなるまで答えの末尾を削除してから追加する。
    　
  10. 上記2.～5.で作ったリストの末尾が6.～9.で作ったリストの先頭より大きい場合は、そうでなくなるまで前者のリストの末尾を削除する必要があるが、これは回転ではなく削除をすればよかったということなので、操作回数には影響ない。
    　
  11. 上記2.において、先頭から順に削除していくことで、先頭K+1個の内の最小要素を答えの先頭とすることもできる。
  12. 以降は、上記7.～9.と同様のことを末尾まで行っていくだけでよい。
    　
  13. 上記2.～10.の回転ありパターンと、11.～12.の回転なしパターンの内、小さい方を出力する。　→2ケースWA
  14. 操作回数が余っている場合、末尾の要素を消せるだけ消すのが最適だった。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

public class Main {
    static int n, k;
    static int[] p;

    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]);
        k = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        p = new int[n];
        for (int i = 0; i < n; i++) {
            p[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        // 区間最小値を取得するセグ木
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.p = p[i];
            arr[i] = o;
        }
        Obj id = new Obj();
        id.i = -1;
        id.p = Integer.MAX_VALUE;
        SegTree<Obj> st = new SegTree<>(arr, id, (v1, v2) -> {
            Obj ret = new Obj();
            if (v1.p < v2.p) {
                ret.i = v1.i;
                ret.p = v1.p;
            } else {
                ret.i = v2.i;
                ret.p = v2.p;
            }
            return ret;
        });

        List<Integer> ans1 = solve1(st);
        List<Integer> ans2 = solve2(st);
//      System.out.println(ans1);
//      System.out.println(ans2);

        // 13. 大小比較
        int s1 = ans1.size();
        int s2 = ans2.size();
        List<Integer> ans = null;
        for (int i = 0; i < s1 && i < s2; i++) {
            int e1 = ans1.get(i);
            int e2 = ans2.get(i);
            if (e1 < e2) {
                ans = ans1;
                break;
            }
            if (e1 > e2) {
                ans = ans2;
                break;
            }
        }
        if (ans == null) {
            if (s1 <= s2) {
                ans = ans1;
            } else {
                ans = ans2;
            }
        }

        // 出力
        StringBuilder sb = new StringBuilder();
        for (int i : ans) {
            sb.append(i).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    // 回転あり
    static List<Integer> solve1(SegTree<Obj> st) {
        int fp = p[0];
        int idx = n - k;
        int rem = 0; // 操作可能残回数
        int fi = n;
        // 2～5
        List<Integer> ans = new ArrayList<>();
        while (idx < n) {
            Obj o = st.prod(idx, n);
            if (o.p < fp) {
                ans.add(o.p);
                idx = o.i + 1;
                if (fi == n) {
                    rem = k - (n - o.i);
                    fi = o.i;
                }
            } else {
                break;
            }
        }

        // 6
        List<Integer> ans2 = new ArrayList<>();
        for (int i = 0; i < fi; i++) {
            if (rem == 0) {
                // 7
                ans2.add(p[i]);
            } else {
                if (i == n - 1 || p[i] > p[i + 1]) {
                    // 8
                    rem--;
                } else {
                    // 9
                    while (rem > 0 && !ans2.isEmpty() && ans2.get(ans2.size() - 1) > p[i]) {
                        rem--;
                        ans2.remove(ans2.size() - 1);
                    }
                    ans2.add(p[i]);
                }
            }
        }
        if (!ans2.isEmpty()) {
            // 10
            int x = ans2.get(0);
            while (!ans.isEmpty() && ans.get(ans.size() - 1) > x) {
                ans.remove(ans.size() - 1);
            }
        }
        ans.addAll(ans2);
        // 14
        while (rem > 0) {
            ans.remove(ans.size() - 1);
            rem--;
        }
        return ans;
    }

    // 回転なし
    static List<Integer> solve2(SegTree<Obj> st) {
        // 11
        Obj o = st.prod(0, k + 1);
        List<Integer> ans = new ArrayList<>();
        ans.add(o.p);
        int rem = k - o.i;
        // 12
        for (int i = o.i + 1; i < n; i++) {
            if (rem == 0) {
                // 7と同様
                ans.add(p[i]);
            } else {
                if (i == n - 1 || p[i] > p[i + 1]) {
                    // 8と同様
                    rem--;
                } else {
                    // 9と同様
                    while (rem > 0 && !ans.isEmpty() && ans.get(ans.size() - 1) > p[i]) {
                        rem--;
                        ans.remove(ans.size() - 1);
                    }
                    ans.add(p[i]);
                }
            }
        }
        // 14
        while (rem > 0) {
            ans.remove(ans.size() - 1);
            rem--;
        }
        return ans;
    }

    static class Obj {
        int i, p;
    }
}

// 以下ACLを移植したSegTree

提出
ここまで80分32秒＋1ペナ。538位。



最終結果：ABCDFの5完1500点、85分32秒、556位、パフォーマンス1752相当
レート変動：2052（Unrated）


2日続けて青diffを落として黄diffを通しているような結果に。
（これを書いている時点ではdifficulty出ていないが、正解者数的におそらくEは青でFは黄になると思っている）

人々と得意苦手の傾向が違うようだ。