UNICORNプログラミングコンテスト2022(AtCoder Beginner Contest 269)(Rated範囲外)

コンテスト前のレート:2023
(Ratedだとしたら)レート通りのパフォーマンスが得られる順位:295位(2000点、63分12秒)


AHC014の最中なので手短に。

A - Anyway Takahashi

問題

思考過程
  1. 式の意味など何も考えずに問題文の通り計算と出力を行う。
import java.util.Scanner;

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

        System.out.println((a + b) * (c - d));
        System.out.println("Takahashi");
    }
}

ここまで0分40秒+0ペナ。92位。


B - Rectangle Detection

問題

思考過程
  1. S_{ij}が'#'であるijの最小値と最大値を求める。
import java.util.Scanner;

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

        int a = n;
        int b = 0;
        int c = n;
        int d = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (s[i][j] == '#') {
                    a = Math.min(a, i);
                    b = Math.max(b, i);
                    c = Math.min(c, j);
                    d = Math.max(d, j);
                }
            }
        }
        a++;
        b++;
        c++;
        d++;
        System.out.println(a + " " + b);
        System.out.println(c + " " + d);
    }
}

ここまで3分24秒+0ペナ。100位。


C - Submask

問題

思考過程
  1. 部分集合の全探索ができるループの回し方があるのでそれをやる。
  2. これだと答えは大きい順に得られるので逆順に出力する。
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

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

        List<Long> list = new ArrayList<>();
        for (long i = x; i > 0; i = (i - 1) & x) {
            list.add(i);
        }
        list.add(0L);

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = list.size() -1; i >= 0; i--) {
            pw.println(list.get(i));
        }
        pw.flush();
    }
}

ここまで7分36秒+0ペナ。217位。


D - Do use hexagon grid

問題

思考過程
  1. UnionFindを使う。
  2. _NC_2通りの組み合わせについて隣接しているか判定し、隣接しているなら結合を行う。
  3. 隣接判定は深く考えずに問題文の6点を使えばいい。
  4. 判定を半分で済ますため、_NP_2通りを調べることにする。i=jをスキップする必要もないため、単純な二重ループになる。
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 = 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();

        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                int xi = x[i];
                int yi = y[i];
                int xj = x[j];
                int yj = y[j];
                if (xi - 1 == xj && yi - 1 == yj ||
                        xi - 1 == xj && yi == yj ||
                        xi == xj && yi - 1 == yj) {
                    uf.union(i, j);
                }
            }
        }
        System.out.println(uf.num);
    }

    // 以下ライブラリ

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

ここまで12分06秒+0ペナ。143位。


E - Last Rook

問題

思考過程
  1. logN回程度で特定しなければならない。
  2. 行と列を分ければちょうど10回ずつ。
  3. 上手く二分探索していきたい感じ。
  4. 1~midの間に空きがあるかないかを元に判定ができる。空きがない場合T=midとなるので、そうならない最小値を求める。
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 ok = n; // ok:空きが1つある
        int ng = 0; // ng:空きがない
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            System.out.println("? 1 " + mid + " 1 " + n);
            int t = sc.nextInt();
            if (t == mid) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
        int x = ok;

        ok = n;
        ng = 0;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            System.out.println("? 1 " + n + " 1 " + mid);
            int t = sc.nextInt();
            if (t == mid) {
                ng = mid;
            } else {
                ok = mid;
            }
        }
        int y = ok;

        System.out.println("! " + x + " " + y);
        sc.close();
    }
}

ここまで19分20秒+0ペナ。80位。


F - Numbered Checker

問題

思考過程
  1. 二次元累積和の要領で、左上から(X, Y)までの長方形領域の合計をf(X, Y)で求められるとすると、f(B, D)-f(A-1, D)-f(B, C-1)+f(A-1, C-1)を求めればよい。
  2. f(X, Y)はいくつかの要素に分解して1つずつ地道に求めていく(下記コード内コメント参照)。0化されている部分は、偶数\times偶数の領域に限れば\div 2をすれば合う。
  3. とりあえず上記2.の計算を行うことに集中し、あとからmodを必要な箇所に追加する。(例2や3に救われた)
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

public class Main {
    static int n, m;
    static int mod = 998244353;

    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]);
        m = Integer.parseInt(sa[1]);
        int q = Integer.parseInt(br.readLine());

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]);
            int c = Integer.parseInt(sa[2]) - 1;
            int d = Integer.parseInt(sa[3]);

            long ans = f(b, d) - f(a, d) - f(b, c) + f(a, c) + mod * 2;
            ans %= mod;
            pw.println(ans);
        }
        pw.flush();
        br.close();
    }

    static long f(long x, long y) {
        // 奇数の場合最後の1行を除いた行数を取得する
        long x2 = x / 2 * 2;
        long y2 = y / 2 * 2;

        // 偶数×偶数部分の計算その1
        // 何列目かに依存する部分の合計
        // 1~y2の和がx2個。0化部分を考慮して÷2
        long v1 = y2 * (y2 + 1) / 2 % mod;
        long v12 = v1 * x2 / 2 % mod;

        // 偶数×偶数部分の計算その2
        // 何行目かに依存する部分の合計
        // 0~(x2-1) * mの和がy2個。0化部分を考慮して÷2
        long v2 = x2 * (x2 - 1) / 2 % mod;
        long v22 = v2 * y2 / 2 % mod * m % mod;

        // 行数が奇数の場合、最後の行の分
        long a = x2 * m + 1;
        long b = x2 * m + y2 - 1;
        long v3 = (a + b) / 2 % mod * y2 / 2 % mod;

        // 列数が奇数の場合、最後の列の分
        long c = y;
        long d = (x2 - 2) * m + y;
        long v4 = (c + d) / 2 % mod * x2 / 2 % mod;

        // 行列共に奇数の場合、(x, y)の分
        long v5 = (x - 1) * m + y;
        v5 %= mod;

        long val = v12 + v22;
        if (x % 2 == 1) {
            val += v3;
        }
        if (y % 2 == 1) {
            val += v4;
        }
        if (x % 2 == 1 && y % 2 == 1) {
            val += v5;
        }
        val %= mod;
        return val;
    }
}

ここまで61分03秒+0ペナ。247位。



GとExは2乗が許されればどちらも解けそうな気もしないでもなかった。

Gは状態数が増えにくそうな順番にすればいけないかと、A+Bが小さいものを先にしたり0を先にしたりと小細工してみたがTLE。
だが方向性は合っていたらしい。



終結果:ABCDEFの6完2000点、61分03秒、266位、パフォーマンス2059相当
レート変動:2023(Unrated)


Eまで早かったのは良かったが、まさかFの早解きも要求されるとは。
38分なら2400で、そこから23分遅れで300以上も下がっている。
算数めんどくさいなとか思っていてなかなか手が動かなかった時間が無駄だった。
すぐに手を動かしていればあと5分10分早かったかも。