AtCoder Beginner Contest 218(Rated範囲外)

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

A - Weather Forecast

問題

思考過程
  1. SN文字目が'o'かどうかを判定する。
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();
        char[] s = sc.next().toCharArray();
        sc.close();

        if (s[n - 1] == 'o') {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで0分48秒+0ペナ。103位。


B - qwerty

問題

思考過程
  1. 'a'から(P_i-1)文字後ろの文字(例:'a'の2文字後ろは'c')を出力していく。
  2. 今のAtCoderの仕様では不要だとは思うが、念のため最後に改行しておく。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int[] p = new int[26];
        for (int i = 0; i < 26; i++) {
            p[i] = sc.nextInt() - 1; // 1
        }
        sc.close();

        for (int i = 0; i < 26; i++) {
            System.out.print((char) ('a' + p[i])); // 1
        }
        System.out.println(); // 2
    }
}

ここまで2分13秒+0ペナ。182位。


C - Shapes

問題
実装が大変そうという以前に、最初は下記思考過程1~2.で詰まって、一旦飛ばしてDを先にやることにする。
下記5.のようなリスト化を思い付くのが難しくて、それがわかれば実装量は多いが実装難易度はそれほどではなく、実装がめんどくさいと敬遠するほどではなかったと思う。

と油断していたら下記7.でJava特有の罠にハマって1ペナ。
Integer同士になることが結構レアなので、本当によく見落とす。(確か前回もミスってる)

思考過程
  1. Sを平行移動させたときの左上の位置を全探索で二重ループ、Sの左上の位置を決めたときのTとの一致を調べる二重ループで合わせて四重ループを書きかけて、はみ出している判定なども含めたらループの内部をどう実装すればよいかよくわからなくなる。
  2. 周囲の余白を削れば少しやりやすくなる?気もするが、それだけでも実装大変そう。
     
  3. 下記4~6.を90度回転させながら4回行う。
  4. S, Tそれぞれ、左上の位置('#'が1つ以上存在する最初の行と列)を求める。
  5. S, Tそれぞれ、各'#'マスについて左上からの相対位置を数値化したもの(xN+y)をリストに追加していく。
  6. 2つのリストをソート後、完全に一致するかどうかを調べる。
     
  7. Integer同士を「!=」で比較していたためWA。equalsメソッドに直す。
import java.util.ArrayList;
import java.util.Collections;
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);
        int n = sc.nextInt();
        char[][] s = new char[n][n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        char[][] t = new char[n][n];
        for (int i = 0; i < n; i++) {
            t[i] = sc.next().toCharArray();
        }
        sc.close();

        for (int k = 0; k < 4; k++) {
            // 4
            int sx = n;
            int sy = n;
            int tx = n;
            int ty = n;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (s[i][j] == '#') {
                        sx = Math.min(sx, i);
                        sy = Math.min(sy, j);
                    }
                    if (t[i][j] == '#') {
                        tx = Math.min(tx, i);
                        ty = Math.min(ty, j);
                    }
                }
            }

            // 5
            List<Integer> ls = new ArrayList<>();
            List<Integer> lt = new ArrayList<>();
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (s[i][j] == '#') {
                        ls.add((i - sx) * n + j - sy);
                    }
                    if (t[i][j] == '#') {
                        lt.add((i - tx) * n + j - ty);
                    }
                }
            }
            if (ls.size() != lt.size()) {
                System.out.println("No");
                return;
            }

            // 6
            Collections.sort(ls);
            Collections.sort(lt);
            boolean flg = true;
            for (int i = 0; i < ls.size(); i++) {
                if (!ls.get(i).equals(lt.get(i))) { // 7
                    flg = false;
                    break;
                }
            }
            if (flg) {
                System.out.println("Yes");
                return;
            }

            // 90度回転
            s = turnRight(s);
        }
        System.out.println("No");
    }

    // 以下ライブラリ

    static char[][] turnRight(char[][] a) {
        int h = a.length;
        int w = a[0].length;
        int h1 = h - 1;
        char[][] b = new char[w][h];
        for (int i = 0; i < w; i++) {
            for (int j = 0; j < h; j++) {
                b[i][j] = a[h1 - j][i];
            }
        }
        return b;
    }
}

ABEDCと解いた時点で61分41秒+3ペナ。842位。


D - Rectangles

問題
下記思考過程3.で2ペナ。
何が悪いのか全くわからず、ここまでで30分もかかっていたが一旦飛ばしてEへ。
Eの後なんとかこれを通し、Cに戻る。

思考過程
  1. 点をx座標ごとにまとめ、Map<x座標、y座標の集合>を作る。
  2. y座標の集合」を、「y座標2点の組の集合」に作り直す。
  3. x座標2つの組を全探索し、それぞれの上記2.の集合を比較して同一要素の個数を答えに足していく。 →15/29ケースWA
     
  4. 本質的には変わらないはずだと思うのだが、上記2.の作り直しを行わず、x座標2つの組を全探索し、その中でさらにx_iに対応するy座標2つの組を全探索し、x_jに対応するy座標の集合内に2つとも含まれていればカウントするようにしてみてAC。

なお、これを書いている間もWAの理由は全くわからなかったのだが、書き終えて公開する寸前にやっとわかった。
上記2.で作り直しをする前に、集合をソートするのが漏れていた。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]);
            y[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        // 1
        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Set<Integer> list = map.get(x[i]);
            if (list == null) {
                list = new HashSet<>();
                map.put(x[i], list);
            }
            list.add(y[i]);
        }

        int ans = 0;
        Integer[] arr = map.keySet().toArray(new Integer[0]);
        // x[i]とx[j]の組を全探索
        for (int i = 0; i < arr.length; i++) {
            Set<Integer> set1 = map.get(arr[i]);
            Integer[] arr1 = set1.toArray(new Integer[0]);
            for (int j = i + 1; j < arr.length; j++) {
                Set<Integer> set2 = map.get(arr[j]);

                // x[i]内のy[a]とy[b]の組を全探索
                for (int a = 0; a < arr1.length; a++) {
                    for (int b = a + 1; b < arr1.length; b++) {
                        if (set2.contains(arr1[a]) && set2.contains(arr1[b])) {
                            ans++;
                        }
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ABEDと解いた時点で48分30秒+2ペナ。1017位。


E - Destruction

問題
CやDよりもはるかに簡単に解けた。

思考過程
  1. 辺を取り除くのではなく、C \le 0の辺を優先的に追加していって最小全域木を作れば、残った辺から報酬を得られる。
  2. 基本的にはクラスカル法をすればよいが、C \le 0の辺は、既に同じ連結成分になっている頂点同士を繋ぐことになる場合でも使い切る。
import java.io.BufferedReader;
import java.io.InputStreamReader;
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 n = Integer.parseInt(sa[0]);
        int m = Integer.parseInt(sa[1]);
        // cの昇順
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> o1.c - o2.c);
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[0]) - 1;
            o.b = Integer.parseInt(sa[1]) - 1;
            o.c = Integer.parseInt(sa[2]);
            que.add(o);
        }
        br.close();

        long ans = 0;
        UnionFind uf = new UnionFind(n);
        while (!que.isEmpty()) {
            Obj o = que.poll();
            if (o.c <= 0) {
                uf.union(o.a, o.b);
            } else {
                if (!uf.same(o.a, o.b)) {
                    uf.union(o.a, o.b);
                } else {
                    ans += o.c;
                }
            }
        }
        System.out.println(ans);
    }

    static class Obj {
        int a, b, c;
    }

    // 以下ライブラリ

    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とyが同一連結成分か
         */
        boolean same(int x, int y) {
            return find(x) == find(y);
        }

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

ABEと解いた時点で41分15秒+0ペナ。1114位。


F - Blocked Roads

問題
Cまで戻った後、残り40分足らずでFとGの2問とも解くのは厳しいと思い、配点が高いGに行きかけたが、一応思い付いたことは試しておくことにし、結果AC。

思考過程
  1. M回BFSしたのでは、O(M^2)かかってしまう。
  2. 最短経路に関わる辺はO(N)本しかないので、そのケースだけBFSして、それ以外は辺を削除しない場合の最短距離を出力することにすれば、O(MN)になり、間に合いそう。
  3. 最初にワーシャルフロイド法を行い、辺を削除しない場合の最短距離と、各辺が最短距離に関わっているかを判定できるようにしておく。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Queue;

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 inf = 1000000000;
        int[][] d = new int[n][n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    d[i][j] = inf;
                }
            }
        }

        List<List<Integer>> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        Obj[] arr = new Obj[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            d[a][b] = 1;

            list.get(a).add(b);

            Obj o = new Obj();
            o.s = a;
            o.t = b;
            arr[i] = o;
        }
        br.close();

        // ワーシャルフロイド法
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (d[i][k] != inf && d[k][j] != inf) {
                        d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);
                    }
                }
            }
        }

        int n1 = n - 1;
        PrintWriter pw = new PrintWriter(System.out);
        for (Obj o : arr) {
            if (d[0][n1] == inf) {
                pw.println(-1);
            } else {
                if (d[0][n1] == d[0][o.s] + d[o.t][n1] + 1) {
                    Queue<Integer> que = new ArrayDeque<>();
                    que.add(0);
                    int[] e = new int[n];
                    Arrays.fill(e, -1);
                    e[0] = 0;
                    while (!que.isEmpty()) {
                        int cur = que.poll();
                        for (int next : list.get(cur)) {
                            if (e[next] == -1) {
                                // 通れない辺の場合
                                if (cur == o.s && next == o.t) {
                                    continue;
                                }
                                que.add(next);
                                e[next] = e[cur] + 1;
                            }
                        }
                    }
                    pw.println(e[n1]);
                } else {
                    pw.println(d[0][n1]);
                }
            }
        }
        pw.flush();
    }

    static class Obj {
        int s, t;
    }
}

ここまで87分57秒+3ペナ。464位。


G - Game on Tree 2

問題
案の定時間が足りず、下記思考過程2.までで時間切れ。
コンテスト直後に解説をチラ見し、翌日に30~40分ほどかけてAC。

思考過程
  1. 葉から木DPを行い、深さの偶奇に応じて、子からの戻り値の最小値または最大値を元に処理して親へ戻っていく流れを考える。
  2. それぞれ下半分と上半分を持つためのPriorityQueue2本を用意して、親へ戻る時に自分を追加していって・・・と思ったが、子ごとに要素数が異なるので、根から自分までの要素も持っておかないと、どの子が最小または最大か判断できない?
     
  3. 親へ戻る時に追加するのではなく、普通に根から自分までの履歴を下半分と上半分に分けて持つようにし、各葉まで達した時の中央値を先に求めておく。
  4. ただし、親に戻っていく時に履歴から自分を取り除くのにO(N)かけては駄目なので、PriorityQueueではなく、TreeSetを同じ要素を複数持てるように改造したものを使う。
  5. あとは上記1.の通りの木DPをする。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.TreeMap;

public class Main {
    static int n;
    static int[] a, med;
    static List<List<Integer>> list;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        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 u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            list.get(u).add(v);
            list.get(v).add(u);
        }
        br.close();

        med = new int[n];
        dfs(0, -1, new MultiTreeSet<>(), new MultiTreeSet<>());
        int ans = dfs2(0, -1, 0);
        System.out.println(ans);
    }

    // 各葉の中央値を求めるDFS
    static void dfs(int x, int p, MultiTreeSet<Integer> low, MultiTreeSet<Integer> high) {
        low.add(a[x]);
        high.add(a[x]);
        Integer l = null;
        Integer h = null;
        if (low.last().compareTo(high.first()) > 0) {
            l = low.pollLast();
            h = high.pollFirst();
            low.add(h);
            high.add(l);
        }
        med[x] = (low.last() + high.first()) / 2;

        for (int c : list.get(x)) {
            if (c != p) {
                dfs(c, x, low, high);
            }
        }

        if (l != null) {
            low.remove(h);
            high.remove(l);
            low.add(l);
            high.add(h);
        }
        low.remove(a[x]);
        high.remove(a[x]);
    }

    // 答えを求める木DP
    static int dfs2(int x, int p, int dep) {
        int ret = 0;
        if (dep % 2 == 1) {
            ret = 1000000007; // inf
        }
        boolean leaf = true;
        for (int c : list.get(x)) {
            if (c != p) {
                leaf = false;
                int res = dfs2(c, x, dep + 1);
                if (dep % 2 == 0) {
                    ret = Math.max(ret, res);
                } else {
                    ret = Math.min(ret, res);
                }
            }
        }
        if (leaf) {
            return med[x];
        }
        return ret;
    }

    // 以下ライブラリ

    static class MultiTreeSet<T> {
        TreeMap<T, Integer> map = new TreeMap<>();
        int size = 0;

        void add(T e) {
            map.put(e, map.getOrDefault(e, 0) + 1);
            size++;
        }

        void remove(T e) {
            if (e != null && map.containsKey(e)) {
                int val = map.get(e);
                if (val == 1) {
                    map.remove(e);
                } else {
                    map.put(e, val - 1);
                }
                size--;
            }
        }

        int sizeAll() {
            return size;
        }

        int sizeUnq() {
            return map.size();
        }

        boolean contains(T e) {
            return map.containsKey(e);
        }

        boolean isEmpty() {
            return size == 0;
        }

        T lower(T e) {
            return map.lowerKey(e);
        }

        T floor(T e) {
            return map.floorKey(e);
        }

        T higher(T e) {
            return map.higherKey(e);
        }

        T ceiling(T e) {
            return map.ceilingKey(e);
        }

        T first() {
            return map.firstKey();
        }

        T last() {
            return map.lastKey();
        }

        T pollFirst() {
            T e = map.firstKey();
            remove(e);
            return e;
        }

        T pollLast() {
            T e = map.lastKey();
            remove(e);
            return e;
        }

        @SuppressWarnings("unchecked")
        T[] toArrayUnq() {
            Object[] arr = map.keySet().toArray();
            return (T[]) arr;
        }

        @SuppressWarnings("unchecked")
        T[] toArrayAll() {
            Object[] arr = new Object[size];
            int idx = 0;
            for (T e : map.keySet()) {
                int num = map.get(e);
                for (int i = 0; i < num; i++) {
                    arr[idx] = e;
                    idx++;
                }
            }
            return (T[]) arr;
        }
    }
}

 



終結果:ABCDEFの6完2000点、102分57秒、521位、パフォーマンス1824相当
レート変動:2034(Unrated)


今回は最初CもDも解けず、3問目をACするまでに40分以上もかかっており、一時は2完灰パフォで終わるのではないかと思った。
2完300点、2分13秒で終わった場合のパフォは632だったが。

なんだかんだでFまでは通せたので、一応青diff以下はできたということでまあ。
CとDで全く詰まらなければ、Gが解けたか惜しいところまでいったかくらいにはなったかも。

Gが絶対に解けない難易度ではなかったのに十分な時間を残せなかったのはもったいなかったが、CやDは解法自体がわかるのにも時間がかかったし、その上非常に気付きにくいミスまで犯していたので、これらを落とさなかっただけでもホッとした。