サイシードプログラミングコンテスト2021（AtCoder Beginner Contest 219）(Rated範囲外)

ABC

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

A - AtCoder Quiz 2

問題

思考過程
  1. とりあえず最初にエキスパートを処理してしまいたくなったので、90以上の場合の出力を行う。
  2. 70以上、40以上、それ以外に分けて、1つ上のボーダーからXを引いた値を出力する。
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();

        if (x >= 90) {
            System.out.println("expert");
        } else if (x >= 70) {
            System.out.println(90 - x);
        } else if (x >= 40) {
            System.out.println(70 - x);
        } else {
            System.out.println(40 - x);
        }
    }
}

ここまで1分27秒＋0ペナ。247位。


B - Maritozzo

問題

思考過程
  1. 3の文字列を配列に入れておけば、T_iを0～2の数値に変換することで、場合分けすることなく処理できる。
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();
        }
        char[] t = sc.next().toCharArray();
        sc.close();

        for (int i = 0; i < t.length; i++) {
            int x = t[i] - '1';
            System.out.print(s[x]);
        }
        System.out.println();
    }
}

ここまで3分02秒＋0ペナ。168位。


C - Neo-lexicographic Ordering

問題

思考過程
  1. コンパレータさえ作れれば、あとはソートして出力するだけ。
  2. コンパレータは要は2つの文字列の比較を実装すればよいが、それは問題文の「辞書順とは？」の通り。
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static char[] x;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        x = sc.next().toCharArray();
        int n = sc.nextInt();
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.s = sc.next().toCharArray();
            arr[i] = o;
        }
        sc.close();

        Arrays.sort(arr);
        PrintWriter pw = new PrintWriter(System.out);
        for (Obj o : arr) {
            pw.println(o.s);
        }
        pw.flush();
    }

    static class Obj implements Comparable<Obj> {
        char[] s;

        @Override
        public int compareTo(Obj o) {
            int min = Math.min(s.length, o.s.length);
            for (int i = 0; i < min; i++) {
                int a = 0;
                int b = 0;
                for (int j = 0; j < 26; j++) {
                    if (s[i] == x[j]) {
                        a = j;
                    }
                    if (o.s[i] == x[j]) {
                        b = j;
                    }
                }
                if (a != b) {
                    return a - b;
                }
            }
            return s.length - o.s.length;
        }
    }
}

ここまで9分27秒＋0ペナ。389位。


D - Strange Lunchbox

問題
解けず。40分以上費やした挙句、ほとんど変わっていないTLE解を3回投げた後、諦めてE問題に進む。
ソースは後から解説ACした時のもの。

思考過程
  1. 「dp[i][j][k_1][k_2]:=i番目まで見て、弁当j個買って、たこ焼きk_1個、たい焼きk_2個の組み合わせが存在するか」みたいなDPしか思いつかず、O(N^2XY)でTLE。
  2. 実装上は、Map＜j、(k_1 \times 1000 + k_2)のSet＞という形で持って必要な遷移しかしないようにはなっていたと思うが、6ケースほど通らず。
    　
  3. コンテスト後に解説通り、「dp[i][k_1][k_2]:=i番目まで見て、たこ焼きk_1個、たい焼きk_2個の組み合わせを達成する弁当の個数の最小値」で実装。
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);
        int n = sc.nextInt();
        int x = sc.nextInt();
        int y = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
            b[i] = sc.nextInt();
        }
        sc.close();

        int inf = 1000;
        int[][][] dp = new int[n + 1][x + 1][y + 1];
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                Arrays.fill(dp[i][j], inf);
            }
        }
        dp[0][0][0] = 0;

        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= x; j++) {
                for (int j2 = 0; j2 <= y; j2++) {
                    // 選ばない
                    dp[i + 1][j][j2] = Math.min(dp[i + 1][j][j2], dp[i][j][j2]);
                    // 選ぶ
                    int nx = Math.min(j + a[i], x);
                    int ny = Math.min(j2 + b[i], y);
                    dp[i + 1][nx][ny] = Math.min(dp[i + 1][nx][ny], dp[i][j][j2] + 1);
                }
            }
        }
        if (dp[n][x][y] == inf) {
            System.out.println(-1);
        } else {
            System.out.println(dp[n][x][y]);
        }
    }
}

　


E - Moat

問題
Dの初回提出くらいのタイミングで一度EとFの問題を見るだけは見たが、すぐに解けそうにはなかったのでなかなか飛ばす決心が付かなかった。
サンプルが弱かったら多分これも解けなかった。
実装はダラダラと長くなったが、もう通れば何でもいいやという感じだった。

思考過程
  1. まず条件を満たすように線を引くこと自体がかなり困難。
  2. 制約がかなり小さいので、線を引くか引かないかを全探索できないか？ と思うが、2^{40}通りの全探索は厳しく、縦線と横線の2^{20}通りずつで半分全列挙的なことができたとしても、相変わらず条件を満たしているかどうかの判定が難しそう。
  3. 各マスが堀の内側に入っているかどうかを全探索するとしたら？ これは2^{16}通りとなり、しかも線の引き方と1対1で対応する。
    　
  4. あとは2^{16}通りそれぞれが条件を満たしているかどうかを調べられればよい。
  5. 2^{16}通りのそれぞれで、堀の内側とする部分をB_{i, j} = 1として表す。
    　
  6. A_{i, j} = 1かつB_{i, j} = 0の部分があったら、全ての村が含まれないためNG。
  7. B_{i, j} = 1の部分が非連結だと、1つの多角形でなかったり、自己交差があったりしてNG。
  8. B_{i, j} = 1の部分が穴開き地形になっている場合、質問の通りNG。
import java.util.ArrayDeque;
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 n = 16;
        int[][] a = new int[4][4];
        for (int i = 0; i < 4; i++) {
            for (int j = 0; j < 4; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        int ans = 0;
        int end = 1 << n;
        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        // 4. 堀の内側となる部分を2^16通り全探索
        label:
        for (int k = 1; k < end; k++) {
            // 5. 堀の内側を表す配列を構成
            int[][] b = new int[4][4];
            for (int j = 0; j < n; j++) {
                b[j / 4][j % 4] = k >> j & 1;
            }
            // 6. 全ての村が含まれるか
            // 7. 連結判定用の仕込み
            int cnt = 0;
            int s = 0;
            for (int i = 0; i < 4; i++) {
                for (int j = 0; j < 4; j++) {
                    if (a[i][j] == 1 && b[i][j] == 0) {
                        continue label;
                    }
                    if (b[i][j] == 1) {
                        cnt++;
                        s = i * 4 + j;
                    }
                }
            }

            // 7. 4方向BFSでb[i][j] == 1の箇所を全部たどれるかにより連結判定
            boolean[][] d = new boolean[4][4];
            Queue<Integer> que = new ArrayDeque<>();
            que.add(s);
            d[s / 4][s % 4] = true;
            int cnt2 = 1;
            while (!que.isEmpty()) {
                int cur = que.poll();
                int cx = cur / 4;
                int cy = cur % 4;
                for (int i = 0; i < 4; i++) {
                    int nx = cx + dx[i];
                    int ny = cy + dy[i];
                    if (nx < 0 || 4 <= nx || ny < 0 || 4 <= ny || b[nx][ny] == 0) {
                        continue;
                    }
                    if (!d[nx][ny]) {
                        int next = nx * 4 + ny;
                        que.add(next);
                        d[nx][ny] = true;
                        cnt2++;
                    }
                }
            }

            // 7. あらかじめ数えた数と、BFSでたどった数が一致すれば連結
            if (cnt == cnt2) {
                // 8. 中央4マスが堀の外側の場合、b[i][j] == 0の箇所をたどって
                //    周囲の12マスいずれかに到達できれば穴開きでない
                for (int i = 1; i <= 2; i++) {
                    for (int j = 1; j <= 2; j++) {
                        if (!d[i][j]) {
                            boolean flg = false;
                            boolean[][] e = new boolean[4][4];
                            que = new ArrayDeque<>();
                            e[i][j] = true;
                            que.add(i * 4 + j);
                            label2:
                            while (!que.isEmpty()) {
                                int cur = que.poll();
                                int cx = cur / 4;
                                int cy = cur % 4;
                                for (int x = 0; x < 4; x++) {
                                    int nx = cx + dx[x];
                                    int ny = cy + dy[x];
                                    if (nx < 0 || 4 <= nx || ny < 0 || 4 <= ny || b[nx][ny] == 1) {
                                        continue;
                                    }
                                    // 周囲12マスのいずれかに到達した
                                    if (nx == 0 || nx == 3 || ny == 0 || ny == 3) {
                                        flg = true;
                                        break label2;
                                    }
                                    if (!e[nx][ny]) {
                                        int next = nx * 4 + ny;
                                        que.add(next);
                                        e[nx][ny] = true;
                                    }
                                }
                            }
                            if (!flg) {
                                continue label;
                            }
                        }
                    }
                }
                ans++;
            }
        }
        System.out.println(ans);
    }
}

ABCEと解いた時点で83分34秒＋0ペナ。576位。



残り15分余りはG問題に使ったが、全く間に合わず。
クエリを後ろから見ていくことで、値書き換えの流れを表す有向グラフを構築できるのではないかなどと考えていたが、解説見たら全然違っていた。



最終結果：ABCEの4完1100点、83分34秒、706位、パフォーマンス1626相当
レート変動：2034（Unrated）


もうこの先2週連続のARCで青落ちしなければ奇跡だと思う。
相変わらずABCは振るわない成績が続いているので、ABCがRatedになってしまうと1800台くらいしか維持できなそう。