エイシングプログラミングコンテスト2022（AtCoder Beginner Contest 255）(Rated範囲外)

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

A - You should output ARC, though this is ABC.

問題

思考過程

1. 行列しかなく無駄感はあるが、を二次元配列で用意し、for文を使って入力を受け取り、を出力する。

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;
        int[][] a = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        sc.close();

        System.out.println(a[r][c]);
    }
}

ここまで1分11秒＋0ペナ。523位。

B - Light It Up

問題

思考過程

1. 明かりを持っていない各人について、明かりを持っている中で最も近い人との距離を求める。
2. 明かりを持っているか持っていないかは、明かりを持っている人の集合をSetで持っておけば、で判定できる。（後から思えば、持っているListと持っていないListに分けてもよかった）
3. 上記1.の中の最大値を求める。

import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < k; i++) {
            set.add(sc.nextInt() - 1);
        }
        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();

        double ans = 0;
        for (int i = 0; i < n; i++) {
            if (!set.contains(i)) {
                double min = 1e18;
                for (int j = 0; j < n; j++) {
                    if (set.contains(j)) {
                        double d = Math.hypot(x[i] - x[j], y[i] - y[j]);
                        min = Math.min(min, d);
                    }
                }
                ans = Math.max(ans, min);
            }
        }
        System.out.println(ans);
    }
}

ここまで7分31秒＋0ペナ。391位。

C - ±1 Operation 1

問題

思考過程

1. なるべく扱いやすくするため、まず、に置き換える。
2. が等差数列の範囲を外れている場合はの先頭または末尾との差を求めればよいが、交差がマイナスの場合もあったため、その場合はの符号を反転させておく。
3. が等差数列の最小値～最大値の範囲内の場合は、との小さい方が答えとなる。
   　
4. の計算で除算が発生したため対処する。
5. の最大値がとなっていてWA。に修正する。

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();
        long a = sc.nextLong();
        long d = sc.nextLong();
        long n = sc.nextLong();
        sc.close();

        // 1
        long v = x - a;
        // 2
        if (d < 0) {
            d = -d;
            v = -v;
        }
        // 5
        n--;
        if (v < 0) {
            System.out.println(-v);
        } else if (v > d * n || d == 0) { // 4
            System.out.println(v - d * n);
        } else {
            // 3
            v %= d;
            System.out.println(Math.min(v, d - v));
        }
    }
}

ここまで14分23秒＋1ペナ。212位。

D - ±1 Operation 2

問題

思考過程

1. 上図の③⑥が求めたい答え。これを定数や対数オーダーで求める方法はないか。
2. ①～③部分の累積和と④～⑥部分の累積和を前計算しておけば、二分探索で赤点線の位置を見つけてあとは適宜②や⑤を求めて差し引きすることが可能。
3. 頭の中で図をイメージしつつそれらしく計算してみたら、答えがマイナスになったが絶対値は合っていたので、気持ちは悪いがとりあえず符号反転だけさせて提出。

後からよく見たら、⑤⑥⑤をしていたつもりが、①①⑥に相当する計算をしていた。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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 n = Integer.parseInt(sa[0]);
        int q = Integer.parseInt(sa[1]);
        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        int[] x = new int[q];
        for (int i = 0; i < q; i++) {
            x[i] = Integer.parseInt(br.readLine());
        }
        br.close();

        Arrays.sort(a);
        // 1～3部分の累積和
        long[] l = new long[n + 1];
        for (int i = 0; i < n; i++) {
            l[i + 1] = l[i] + a[i];
        }
        // 4～6部分の累積和
        long[] r = new long[n + 1];
        for (int i = n - 1; i >= 0; i--) {
            r[i] = r[i + 1] + 1000000000 - a[i];
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            int idx = binarySearch(a, x[i]);
            // 4 - (3+4)
            long v1 = r[idx] - (1000000000L - x[i]) * (n - idx);
            // 1 - (1+6)
            long v2 = l[idx] - (long) x[i] * idx;
            pw.println(-v1 - v2);
        }
        pw.flush();
    }

    // arrayの中で値がval以上である最小のindex
    static int binarySearch(int[] array, long val) {
        int ok = array.length;
        int ng = -1;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (array[mid] >= val) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        return ok;
    }
}

ここまで24分27秒＋1ペナ。313位。

E - Lucky Numbers

問題
以下0-indexedで記載。

思考過程

1. を決めれば残りも全部決まる。
2. をとの差で表したときに、として出現する値とその個数をMapで持っておくと、の候補に対して各が何個ずつあるかをで求められる。
3. はの累積和で求められるような気がしたが、きちんと考えたら違った。。
4. 偶数番目はを増やすとその分増え、奇数番目はその分減る形のため、上記2.のMapも偶数番目と奇数番目で分けて管理する。
   　
5. あとは、とが同じ値になるようなの決め方を全て試す。全体で。
6. Mapから個数を取り出すところで、を足して取得すればいいのか引いて取得すればいいのか混乱したので両方試すことにした。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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

        // 3
        long[] a = new long[n];
        for (int i = 1; i < n; i++) {
            a[i] = s[i - 1] - a[i - 1];
        }
        // 4
        Map<Long, Integer> map1 = new HashMap<>();
        Map<Long, Integer> map2 = new HashMap<>();
        for (int i = 0; i < n; i++) {
            if (i % 2 == 0) {
                map1.put(a[i], map1.getOrDefault(a[i], 0) + 1);
            } else {
                map2.put(a[i], map2.getOrDefault(a[i], 0) + 1);
            }
        }

        // 5
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                // 2
                long a0 = a[i] - x[j];
                int v1 = 0;
                int v2 = 0;
                for (int i2 = 0; i2 < m; i2++) {
                    // 6
                    v1 += map1.getOrDefault(x[i2] + a0, 0);
                    v1 += map2.getOrDefault(x[i2] - a0, 0);
                    v2 += map1.getOrDefault(x[i2] - a0, 0);
                    v2 += map2.getOrDefault(x[i2] + a0, 0);
                }
                ans = Math.max(ans, v1);
                ans = Math.max(ans, v2);
            }
        }
        System.out.println(ans);
    }
}

ここまで59分16秒＋1ペナ。411位。

F - Pre-order and In-order

問題

思考過程

1. を元にDFSをやってみてしまえば、最後まで行ければその過程で構築ができているし、途中で矛盾が生じれば不可能とできる。
2. まず行きがけ順は、頂点に到達した時に次がでなければNG。
   　
3. 通りがけ順で次がの場合は、それ以上左の子はいない。そうでなければいるはずなので、行きがけ順の次の頂点を左の子とする。
4. 左の子を処理してに戻ってきた時、通りがけ順で次がでなければNG。
5. 右の子がいるかどうかは、通りがけ順の次がでない場合いると判定できる？と思ったが、通りがけ順の次がの祖先にいない場合だった。通りがけ順の次がの祖先の場合は、少なくともそこまで戻ってそこから右の子に行くかさらに戻るかになる。
6. あと配列外参照をしたので対策する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.LinkedHashSet;

public class Main {
    static int n, ip, ic;
    static int[] p, c, l, r;

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

        l = new int[n + 1];
        r = new int[n + 1];
        boolean res = dfs(1, new LinkedHashSet<>());
        if (!res) {
            System.out.println(-1);
            return;
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= n; i++) {
            pw.println(l[i] + " " + r[i]);
        }
        pw.flush();
    }

    static boolean dfs(int x, LinkedHashSet<Integer> his) {
        // 2
        if (p[ip] != x) return false;
        ip++;

        // 3
        if (c[ic] != x) {
            l[x] = p[ip];
            his.add(x);
            boolean res = dfs(l[x], his);
            his.remove(x);
            if (!res) return false;
        }

        // 4
        if (c[ic] != x) return false;
        ic++;

        // 5, 6
        if (ic < n && !his.contains(c[ic])) {
            r[x] = p[ip];
            his.add(x);
            boolean res = dfs(r[x], his);
            his.remove(x);
            if (!res) return false;
        }

        return true;
    }
}

ここまで82分25秒＋1ペナ。218位。

順位表を見たらGよりExの方が解かれていたのでとりあえず両方見る。
Gは何もわからず、Exは解けるかはさておき頑張ることはできそう。だが時間が足りそうにないので諦め。
EとFの片方しか解いていない人が多かったのか、Fの正解者数が400人以上いた割には高めの順位だったのでもういいやと思った。

最終結果：ABCDEFの6完2000点、87分25秒、239位、パフォーマンス2117相当
レート変動：2019（Unrated）

直近5回のABCでは青diffを落としていなくてまずまずの出来。
黄diffはABC227を最後に全く解けていないが。