freee プログラミングコンテスト2022（AtCoder Beginner Contest 264）(Rated範囲外)

ABC

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

A - "atcoder".substr()

問題

思考過程
  1. Stringのsubstringメソッド使用することによってindexがL以上R未満の範囲の部分文字列を取得することができるので、それを出力する。
import java.util.Scanner;

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

        System.out.println("atcoder".substring(l - 1, r));
    }
}

ここまで0分41秒＋0ペナ。73位。


B - Nice Grid

問題
埋め込むのが一番早かったかも。

思考過程
  1. そんなに長大でないif文でなんか上手いこと判定できないかと思うが、ぱっとできそうにない。
  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 r = sc.nextInt() - 1;
        int c = sc.nextInt() - 1;
        sc.close();

        int n = 15;
        char[][] b = new char[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(b[i], ',');
        }

        int a = 15; // 黒い部分の1辺の長さ
        for (int i = 0; i < n; i += 2) {
            for (int j = i; j < i + a; j++) {
                b[i][j] = '#'; // 上辺
                b[i + a - 1][j] = '#'; // 下辺
            }
            for (int j = i; j < i + a; j++) {
                b[j][i] = '#'; // 左辺
                b[j][i + a - 1] = '#'; // 右辺
            }
            a -= 4;
        }
//      for (int i = 0; i < n; i++) {
//          System.out.println(b[i]);
//      }

        System.out.println(b[r][c] == '#' ? "black" : "white");
    }
}

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


C - Matrix Reducing

問題
実装が下手そう。

思考過程
  1. 行と列それぞれについて、行列Aから残す部分をbit全探索する。
  2. 残す部分の行数・列数がBと同じ場合、Aから残す部分を元に行列Cを作成し、Bと一致するか調べる。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h1 = sc.nextInt();
        int w1 = sc.nextInt();
        int[][] a = new int[h1][w1];
        for (int i = 0; i < h1; i++) {
            for (int j = 0; j < w1; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        int h2 = sc.nextInt();
        int w2 = sc.nextInt();
        int[][] b = new int[h2][w2];
        for (int i = 0; i < h2; i++) {
            for (int j = 0; j < w2; j++) {
                b[i][j] = sc.nextInt();
            }
        }
        sc.close();

        int eh = 1 << h1;
        for (int ih = 0; ih < eh; ih++) {
            int ew = 1 << w1;
            int bh = Integer.bitCount(ih);
            if (bh != h2) {
                continue;
            }
            for (int iw = 0; iw < ew; iw++) {
                int bw = Integer.bitCount(iw);
                if (bw != w2) {
                    continue;
                }

                // 行列Aから一部の行・列を残した行列Cを作成
                int[][] c = new int[bh][bw];
                int ch = -1;
                for (int jh = 0; jh < h1; jh++) {
                    if ((ih >> jh & 1) == 1) {
                        ch++;
                        int cw = -1;
                        for (int jw = 0; jw < w1; jw++) {
                            if ((iw >> jw & 1) == 1) {
                                cw++;
                                c[ch][cw] = a[jh][jw];
                            }
                        }
                    }
                }

                // BとCが一致するか判定
                boolean ok = true;
                label:
                for (int i = 0; i < bh; i++) {
                    for (int j = 0; j < bw; j++) {
                        if (b[i][j] != c[i][j]) {
                            ok = false;
                            break label;
                        }
                    }
                }
                if (ok) {
                    System.out.println("Yes");
                    return;
                }
            }
        }
        System.out.println("No");
    }
}

ここまで17分45秒＋0ペナ。678位。


D - "redocta".swap(i,i+1)

問題

思考過程
  1. 'a'を1、't'を2、\cdots、'r'を7に置き換え、転倒数を求める。
import java.util.Scanner;

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

        int[] a = new int[s.length];
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'a') a[i] = 1;
            if (s[i] == 't') a[i] = 2;
            if (s[i] == 'c') a[i] = 3;
            if (s[i] == 'o') a[i] = 4;
            if (s[i] == 'd') a[i] = 5;
            if (s[i] == 'e') a[i] = 6;
            if (s[i] == 'r') a[i] = 7;
        }
        System.out.println(tentousuu(a));
    }

    // 以下ライブラリ

    static long tentousuu(int[] a) {
        int n = a.length;
        int min = Integer.MAX_VALUE;
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            min = Math.min(min, a[i]);
            max = Math.max(max, a[i]);
        }
        min--;
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = a[i] - min;
        }

        BIT bit = new BIT(max - min);
        long ret = 0;
        for (int i = 0; i < n; i++) {
            ret += i - bit.sum(b[i]);
            bit.add(b[i], 1);
        }
        return ret;
    }

    static class BIT {
        int n;
        long[] arr;

        public BIT(int n) {
            this.n = n;
            arr = new long[n + 1];
        }

        void add(int idx, long val) {
            for (int i = idx; i <= n; i += i & -i) {
                arr[i] += val;
            }
        }

        long sum(int idx) {
            long sum = 0;
            for (int i = idx; i > 0; i -= i & -i) {
                sum += arr[i];
            }
            return sum;
        }
    }
}

ここまで20分29秒＋0ペナ。416位。


E - Blackout 2

問題

思考過程
  1. だんだん辺が途切れていくような問題は、後ろからUnionFindっぽい。
  2. 毎回M個の頂点に対して連結成分のサイズを調べるとかはO(MQ)で駄目。
  3. 発電所は1個の頂点とみなしても同等であるため、その頂点を含む連結成分のサイズ-1を求めればよい。
  4. まずクエリに含まれていない辺のみを追加した後、クエリを後ろから処理していく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.HashSet;
import java.util.Set;

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 m = Integer.parseInt(sa[1]);
        int e = Integer.parseInt(sa[2]);
        int[] u = new int[e];
        int[] v = new int[e];
        for (int i = 0; i < e; i++) {
            sa = br.readLine().split(" ");
            u[i] = Math.min(Integer.parseInt(sa[0]) - 1, n);
            v[i] = Math.min(Integer.parseInt(sa[1]) - 1, n);
        }
        int q = Integer.parseInt(br.readLine());
        int[] x = new int[q];
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < q; i++) {
            x[i] = Integer.parseInt(br.readLine()) - 1;
            set.add(x[i]);
        }
        br.close();

        UnionFind uf = new UnionFind(n + 1);
        // クエリに含まれていない辺を追加
        for (int i = 0; i < e; i++) {
            if (!set.contains(i)) {
                uf.union(u[i], v[i]);
            }
        }

        // 後ろから処理
        int[] ans = new int[q];
        ans[q - 1] = uf.size(n) - 1;
        for (int i = q - 1; i > 0; i--) {
            uf.union(u[x[i]], v[x[i]]);
            ans[i - 1] = uf.size(n) - 1;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i : ans) {
            pw.println(i);
        }
        pw.flush();
    }

    // 以下ライブラリ

    static class UnionFind {
        int[] parent, size;
        int num = 0; // 連結成分の数

        UnionFind(int n) {
            parent = new int[n];
            size = new int[n];
            num = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                size[i] = 1;
            }
        }

        void union(int x, int y) {
            int px = find(x);
            int py = find(y);
            if (px != py) {
                parent[px] = py;
                size[py] += size[px];
                num--;
            }
        }

        int find(int x) {
            if (parent[x] == x) {
                return x;
            }
            parent[x] = find(parent[x]);
            return parent[x];
        }

        /**
         * xを含む連結成分のサイズ
         */
        int size(int x) {
            return size[find(x)];
        }
    }
}

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



Fはどう見てもDPだろうとDPを書き始めるが、延々と試行錯誤し続けて最終的に例１すら合わず。
残り時間25分ほどになってGもまともに問題を読むが、20分かそこらでできる気はせず、Fに集中していた。



最終結果：ABCDEの5完1500点、30分34秒、546位、パフォーマンス1781相当
レート変動：2052（Unrated）


はいはいどうせDPできませんよということでさっさとAHC013に戻る。