トヨタシステムズプログラミングコンテスト2022(AtCoder Beginner Contest 279)

ABC

コンテスト前のレート：1996
レート通りのパフォーマンスが得られる順位：292位（2000点、85分47秒）

A - wwwvvvvvv

問題

思考過程
  1. Sの各文字を調べていき、'v'なら+1、'w'なら+2する。
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 ans = 0;
        for (int i = 0; i < s.length; i++) {
            if (s[i] == 'v') {
                ans++;
            } else {
                ans += 2;
            }
        }
        System.out.println(ans);
    }
}

ここまで0分55秒＋0ペナ。361位。


B - LOOKUP

問題

思考過程
  1. StringのindexOfを使って判定できる。
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.indexOf(t) == -1) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

ここまで2分07秒＋0ペナ。187位。


C - RANDOM

問題

思考過程
  1. S, Tそれぞれについて、縦読みした文字列をW個作る。
  2. それぞれをソートした結果が一致するかを調べる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        char[][] t = new char[h][w];
        for (int i = 0; i < h; i++) {
            t[i] = br.readLine().toCharArray();
        }
        br.close();

        String[] s2 = new String[w];
        String[] t2 = new String[w];
        for (int i = 0; i < w; i++) {
            StringBuilder sbs = new StringBuilder();
            StringBuilder sbt = new StringBuilder();
            for (int j = 0; j < h; j++) {
                sbs.append(s[j][i]);
                sbt.append(t[j][i]);
            }
            s2[i] = sbs.toString();
            t2[i] = sbt.toString();
        }
        Arrays.sort(s2);
        Arrays.sort(t2);

        for (int i = 0; i < w; i++) {
            if (!s2[i].equals(t2[i])) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで6分34秒＋0ペナ。249位。


D - Freefall

問題
コードの最後の方の平方根を取るところで+1が足りないことに気付くのに時間がかかった。

思考過程
  1. D問題で三分探索？と思ったが他に思い付かないのでやる。
  2. 整数でやっていると左右の幅が1にならないことがあるので、その範囲は全探索する。
import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {
    static long a, b;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] sa = br.readLine().split(" ");
        a = Long.parseLong(sa[0]);
        b = Long.parseLong(sa[1]);
        br.close();

        long l = 0;
        long r = a / b;
        while (r - l > 3) {
            long m1 = (l * 2 + r) / 3;
            long m2 = (l + r * 2) / 3;
            double v1 = calc(m1);
            double v2 = calc(m2);
            if (v1 <= v2) {
                r = m2;
            } else {
                l = m1;
            }
        }
        double ans = a;
        for (long i = l; i <= r; i++) {
            ans = Math.min(ans, calc(i));
        }
        System.out.println(ans);
    }

    // ※引数は問題文中のgではなく操作回数
    static double calc(long g) {
        return a / Math.sqrt(g + 1) + b * g;
    }
}

ここまで18分30秒＋0ペナ。228位。


E - Cheating Amidakuji

問題

思考過程
  1. とりあえずA_kの操作をスキップしないとして全部操作した場合にBがどうなるかをシミュレーションする。
  2. スキップする操作については、A_kを行うと0の位置が入れ替わる場合は入れ替わる相方の値の最終的な位置を求めればよいため、相方の値が何であるかをメモしておく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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

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

        int[] c = new int[m]; // 何の値の位置を答えればよいか
        for (int i = 0; i < m; i++) {
            int t = b[a[i]];
            b[a[i]] = b[a[i] + 1];
            b[a[i] + 1] = t;
            if (b[a[i]] == 0) {
                c[i] = b[a[i] + 1];
            } else if (b[a[i] + 1] == 0) {
                c[i] = b[a[i]];
            } else {
                c[i] = 0;
            }
        }

        // 値から位置を求める用
        int[] p = new int[n];
        for (int i = 0; i < n; i++) {
            p[b[i]] = i;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < m; i++) {
            pw.println(p[c[i]] + 1);
        }
        pw.flush();
    }
}

ここまで38分11秒＋0ペナ。191位。


F - BOX

問題

思考過程
  1. Map＜箱番号、中身の集合＞ではなく、Map＜中身の集合、箱番号＞がほしいイメージ。
  2. 集合の管理にUnionFindを使うと、Map＜集合の代表、箱番号＞にすることができる。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;

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

        UnionFind uf = new UnionFind(n + q);
        int[] a = new int[n + q]; // a[i]: iが含まれる集合の代表が入っている箱番号
        int[] b = new int[n];     // b[i]: 箱iの代表
        for (int i = 0; i < n; i++) {
            a[i] = i;
            b[i] = i;
        }
        for (int i = n; i < n + q; i++) {
            a[i] = -1;
        }
        int k = n;

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int x = Integer.parseInt(sa[1]) - 1;
            if (t == 1) {
                int y = Integer.parseInt(sa[2]) - 1;
                int x2 = Math.min(b[x], b[y]);
                int y2 = Math.max(b[x], b[y]);
                if (x2 == -1) {
                    if (y2 != -1) {
                        // 片方が空の場合
                        int l = uf.find(y2);
                        a[l] = x;
                        b[x] = l;
                        b[y] = -1;
                    }
                    // 両方空の場合何もしない
                } else {
                    uf.union(x2, y2);
                    int l = uf.find(x2);
                    a[l] = x;
                    b[x] = l;
                    b[y] = -1;
                }

            } else if (t == 2) {
                if (b[x] == -1) {
                    // 空箱にkを入れる場合
                    a[k] = x;
                    b[x] = k;
                } else {
                    uf.union(b[x], k);
                    int l = uf.find(k);
                    a[l] = x;
                    b[x] = l;
                }
                k++;

            } else {
                pw.println(a[uf.find(x)] + 1);
            }
        }
        pw.flush();
        br.close();
    }

    // 以下ライブラリ

    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[py] = px;
                size[px] += size[py];
                num--;
            }
        }

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

ここまで67分57秒＋0ペナ。157位。



Gは「i番目まで見てi番目と異なる色を最後にj番目で使っている」といった2乗のDPを累積和で高速化するような形かなとそれらしく実装してみたが、サンプルも合わずおかしいところを探している間に時間切れ。



最終結果：ABCDEFの6完2000点、67分57秒、183位、パフォーマンス2218
レート変動：1996→2020（+24）


前回のARCで微減してABCがRatedになってそれ以上に稼ぐことに成功。
ARC147で大きくプラスになって以来、完全にABCでプラス、ARCでマイナスの流れになっている。
ABCで黄パフォ安定するなら青に落ちても簡単に黄色に戻れるので楽ではあるのだが、元々ARCの方がABCより得意だと思っていた身としてはあまりうれしい傾向ではないかも。

競プロを惰性で続けていて、自分の中で典型になったものはすぐできるけど面倒なのは考える気がしないというのが表れてきている感じが・・・。