AtCoder Beginner Contest 213(Rated範囲外)

ABC

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

A - Bitwise Exclusive Or

問題

思考過程
  1. 3つの数A, B, Cがあり、A xor B=Cが成り立つなら、B xor C=AもC xor A=Bも成り立つ。
  2. よって、Cを求めたいならばA xor Bを求める。
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();
        sc.close();

        System.out.println(a ^ b);
    }
}

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


B - Booby Prize

問題

思考過程
  1. スコアではなく番号を答える必要があるので、オブジェクトを作ってソートを行う。
  2. スコアの昇順にソートし、後ろから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();
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.i = i;
            o.a = sc.nextInt();
            arr[i] = o;
        }
        sc.close();

        Arrays.sort(arr, (o1, o2) -> o1.a - o2.a); // aの昇順
        System.out.println(arr[n - 2].i + 1);
    }

    static class Obj {
        int i, a;
    }
}

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


C - Reorder Cards

問題

思考過程
  1. 行と列は独立しているので、それぞれ座標圧縮する。
import java.io.PrintWriter;
import java.util.Scanner;
import java.util.TreeMap;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int h = sc.nextInt();
        int w = sc.nextInt();
        int n = 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();

        a = zaatu(a);
        b = zaatu(b);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(a[i] + " " + b[i]);
        }
        pw.flush();
    }

    // 以下ライブラリ

    static int[] zaatu(int[] a) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 0; i < a.length; i++) {
            map.put(a[i], null);
        }
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        int cnt = 0;
        for (Integer i : arr) {
            cnt++;
            map.put(i, cnt);
        }
        int[] b = new int[a.length];
        for (int i = 0; i < a.length; i++) {
            b[i] = map.get(a[i]);
        }
        return b;
    }
}

ここまで4分39秒＋0ペナ。44位。


D - Takahashi Tour

問題

思考過程
  1. BFSやDFSの動きと似ている。戻る移動があるのでどちらかと言えばDFSっぽい。
  2. DFSをしながら適切なタイミングで答えのリストに都市番号を追加していけばできそう。
  3. 各都市に入ってきた時と出ていく時に追加する？
  4. 入ってきた時はよいが、出ていく時ではなく、次の都市から戻ってきた時なので、再帰呼び出しから戻った直後に追加する。
  5. 番号が小さい都市から移動するので、隣接リストをソートしておく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Main {
    static List<List<Integer>> list;
    static List<Integer> ans;

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

        ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Collections.sort(list.get(i)); // 5
        }
        dfs(0, -1);

        StringBuilder sb = new StringBuilder();
        for (int i : ans) {
            sb.append(i + 1).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static void dfs(int x, int p) {
        ans.add(x); // 3, 4
        for (int i : list.get(x)) {
            if (i != p) {
                dfs(i, x);
                ans.add(x); // 3, 4
            }
        }
    }
}

ここまで9分18秒＋0ペナ。67位。


E - Stronger Takahashi

問題
入力部分をミスっていて5分以上溶かした。
BufferedReader使う時は本当に気を付けないと・・・。

思考過程
  1. 道の区画に移動する場合は距離+0で移動しキューの先頭に追加、塀の区画に移動する場合は周囲9マスに距離+1で移動しキューの末尾に追加する01BFSをすればよさそうに見える。　が、サンプルが合わない。
  2. ダイクストラにした方が確実かと思い、書き換えてみる。　が、まだ合わない。
  3. わかりやすそうな例２でデバッグをして、入力部分のミスに気付く。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.PriorityQueue;

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]); // ここが0になっていた
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        int[] dx = {1, 0, -1, 0};
        int[] dy = {0, 1, 0, -1};
        int inf = 1000000007;

        int[] d = new int[h * w];
        Arrays.fill(d, inf);
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        Node first = new Node(0, 0);
        que.add(first);
        d[0] = 0;
        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.d > d[cur.v]) {
                continue;
            }
            int cx = cur.v / w;
            int cy = cur.v % w;
            for (int i = 0; i < 4; i++) {
                int nx = cx + dx[i];
                int ny = cy + dy[i];
                if (nx < 0 || h <= nx || ny < 0 || w <= ny) {
                    continue;
                }
                if (s[nx][ny] == '.') {
                    int next = nx * w + ny;
                    if (d[cur.v] < d[next]) {
                        d[next] = d[cur.v];
                        que.add(new Node(next, d[next]));
                    }
                } else {
                    int alt = d[cur.v] + 1;
                    for (int x = -1; x <= 1; x++) {
                        for (int y = -1; y <= 1; y++) {
                            int nx2 = nx + x;
                            int ny2 = ny + y;
                            if (nx2 < 0 || h <= nx2 || ny2 < 0 || w <= ny2) {
                                continue;
                            }
                            int next = nx2 * w + ny2;
                            if (alt < d[next]) {
                                d[next] = alt;
                                que.add(new Node(next, d[next]));
                            }
                        }
                    }
                }
            }
        }
        System.out.println(d[h * w - 1]);
    }

    static class Node implements Comparable<Node> {
        int v;
        int d;

        public Node(int v, int d) {
            this.v = v;
            this.d = d;
        }

        public int compareTo(Node o) {
            return d - o.d;
        }
    }
}

ここまで27分50秒＋0ペナ。131位。


F - Common Prefixes

問題
終了8分後に通った。
ACLの中でまだ自力で使った実績がないものを使えて良かった。

思考過程
  1. 比較したい文字列がsuffixであることや、"mississippi"というサンプルから、suffix_arrayが使えないかと、ACLの該当ドキュメントを読み直して、そもそもsuffix_arrayが何だったかからおさらいしつつ、とりあえず出力してみる。
  2. ついでにlcp_arrayというものが載っていたので、それも出力してみる。
    　
  3. そして、各部分文字列同士を比較した時に答えにどれだけ寄与するかを、以下の図のように書き出してみると、同じ部分文字列同士の箇所（背景黄色）から上下に向かって、lcp_arrayの累積minを取った形になっていそう。
    f:id:ks2m:20210809001955p:plain
    　
  4. あとは、累積minの総和を求めたい。
  5. これは、ランレングス圧縮したスタック情報を上手く更新していけばできそう。
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
import java.util.Scanner;
import java.util.function.Consumer;
import java.util.function.IntBinaryOperator;

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

        int[] sa = StringAC.suffixArray(s);
        int[] la = StringAC.lcpArray(s, sa);

        long[] ans = new long[n];

        // 黄色箇所より上の部分
        Deque<Obj> que = new ArrayDeque<>();
        long sum = 0;
        for (int i = 0; i < n - 1; i++) {
            // start
            if (que.isEmpty()) {
                // 最初の1個は単純に追加
                que.add(new Obj(la[i], 1));
                sum += la[i];
            } else {
                Obj o2 = new Obj(la[i], 1); // 追加要素
                sum += la[i];
                while (!que.isEmpty()) {
                    Obj o = que.peek();
                    if (o.val < la[i]) {
                        // 追加する値の方が大きい場合は下記★で追加するのみ
                        break;
                    } else if (o.val == la[i]) {
                        // 値が同じ場合、追加要素と先頭要素をマージ
                        // （先頭要素を消しておいて、追加要素に件数を加算）
                        que.poll();
                        o2.cnt += o.cnt;
                        break;
                    }
                    // 追加する値の方が小さい場合
                    // 先頭要素の値を追加する値に書き換えて追加要素とマージ
                    // （書き換えた分の差分計算）
                    sum -= (long) o.val * o.cnt;
                    sum += (long) o2.val * o.cnt;
                    // （先頭要素を消しておいて、追加要素に件数を加算）
                    que.poll();
                    o2.cnt += o.cnt;
                }
                que.addFirst(o2); // ★要素追加
            }
            // end
            ans[sa[i + 1]] += sum;
        }

        // 黄色箇所より下の部分
        que = new ArrayDeque<>();
        sum = 0;
        for (int i = n - 2; i >= 0; i--) {
            // （中略）上の方のstart～endと完全に同一
            ans[sa[i]] += sum;
        }

        // 黄色箇所
        for (int i = 0; i < n; i++) {
            ans[i] += n - i;
        }

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

    static class Obj {
        int val, cnt;

        public Obj(int val, int cnt) {
            this.val = val;
            this.cnt = cnt;
        }
    }
}

// 以下ACLを移植した文字列ライブラリ

提出



GとHは問題を読んだだけで何もわからず。



最終結果：ABCDEの5完1500点、27分50秒、253位、パフォーマンス2125相当
レート変動：2101（Unrated）


ABCで勝利（レート以上のパフォ）は203以来。
8問制になってさらに、知識がないとどうにもならない問題が多くなってきている気がする。

せっかくノーリスクで知識増やせるんだからちゃんと復習しないと・・・と今回も言い続けるけど、橙diffとかのやつはだいたい理解できる範囲を超えてて厳しい。