AtCoder Beginner Contest 245(Rated範囲外)

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

A - Good morning

問題

思考過程

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();

        if (a < c || a == c && b <= d) {
            System.out.println("Takahashi");
        } else {
            System.out.println("Aoki");
        }
    }
}

ここまで1分54秒＋0ペナ。421位。

B - Mex

問題

思考過程

1. 二重ループでも間に合う制約だが、やっぱりはSetで持っておくことにする。
2. から順に調べていき、最初にSetに含まれていない値が答え。

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();
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            set.add(sc.nextInt());
        }
        sc.close();

        for (int i = 0; i <= n; i++) {
            if (!set.contains(i)) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで3分05秒＋0ペナ。276位。

C - Choose Elements

問題

思考過程

1. 前から順に番目まで調べた時に、としてを選んでいることがあり得るか、を選んでいることがあり得るかを記録していく。
2. 以下のいずれかを満たす場合、を選ぶことが可能。（についても同様）
   • が可能かつ
   • が可能かつ
3. の少なくとも一方が可能なら"Yes"。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        boolean[] ba = new boolean[n];
        boolean[] bb = new boolean[n];
        ba[0] = true;
        bb[0] = true;
        for (int i = 1; i < n; i++) {
            if (ba[i - 1] && Math.abs(a[i] - a[i - 1]) <= k ||
                    bb[i - 1] && Math.abs(a[i] - b[i - 1]) <= k) {
                ba[i] = true;
            }
            if (ba[i - 1] && Math.abs(b[i] - a[i - 1]) <= k ||
                    bb[i - 1] && Math.abs(b[i] - b[i - 1]) <= k) {
                bb[i] = true;
            }
        }

        if (ba[n - 1] || bb[n - 1]) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで6分53秒＋0ペナ。159位。

D - Polynomial division

問題

思考過程

1. のグリッドの上から番目、左から番目のマスにを記入するとした場合に、と斜め（が同じであるライン）の合計だけわかっている状態からを求める問題。
   　
2. これは、が小さい順か大きい順かでグリッド内の値を順番に特定していくことができる。
3. 小さい順の方が実装が混乱しなそうなので小さい順にやってみることにする。
   • 
   • 
   • 
   • 
   • 
     　
4. これではの場合に除算が発生してREだった。
5. が大きい順にやっていくことで各ステップで最後に割る値がとなり、制約よりなので除算が発生しないようにできる。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        int[] b = new int[n + m + 1];
        for (int i = 0; i <= m; i++) {
            int val = 0;
            for (int j = 0; j < i; j++) {
                if (0 <= n - i + j) {
                    val += a[n - i + j] * b[m - j];
                }
            }
            b[m - i] = (c[n + m - i] - val) / a[n];
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i <= m; i++) {
            sb.append(b[i]).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }
}

ここまで31分28秒＋1ペナ。746位。

E - Wrapping Chocolate

問題

思考過程

1. 縦が短い順に調べていくことで、であることは考慮対象に入っているかどうかで担保し、考慮対象内でを満たす中で最も無駄が少ない組合せを貪欲に選択していくことができる。
   　
2. 実装はあらかじめチョコレートと箱をそれぞれ縦が短い順にソートした上、箱をベースにループを回すとできそう。
3. ある箱について調べる時、まず縦の長さが箱以下であるチョコレートを全て考慮対象に追加する。
4. その後考慮対象内で横の長さが箱以下の中で最大のチョコレートを選択する。
5. 全ての箱を調べ終わった後、考慮対象内にチョコレートが残っていなければ"Yes"。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.TreeMap;

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]);
        Obj[] a = readArray(br, n);
        Obj[] b = readArray(br, m);
        br.close();

        Arrays.sort(a);
        Arrays.sort(b);
        // キー：横の長さ　値：個数
        TreeMap<Integer, Integer> map = new TreeMap<>();
        int x = 0;
        for (Obj o : b) {
            // 3
            while (x < n) {
                Obj o2 = a[x];
                if (o2.a <= o.a) {
                    map.put(o2.b, map.getOrDefault(o2.b, 0) + 1);
                    x++;
                } else {
                    break;
                }
            }
            // 4
            Integer key = map.floorKey(o.b);
            if (key != null) {
                int v = map.get(key) - 1;
                if (v > 0) {
                    map.put(key, v);
                } else {
                    map.remove(key);
                }
            }
        }
        // 5
        if (x == n && map.isEmpty()) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    static Obj[] readArray(BufferedReader br, int n) throws Exception {
        Obj[] arr = new Obj[n];
        String[] sa = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            Obj o = new Obj();
            o.a = Integer.parseInt(sa[i]);
            arr[i] = o;
        }
        sa = br.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i].b = Integer.parseInt(sa[i]);
        }
        return arr;
    }

    static class Obj implements Comparable<Obj> {
        int a, b;

        @Override
        public int compareTo(Obj o) {
            if (a != o.a) {
                return a - o.a;
            }
            return b - o.b;
        }
    }
}

ここまで46分31秒＋1ペナ。402位。

F - Endless Walk

問題

思考過程

1. とりあえずACLを貼って強連結成分分解をする。
2. 要素数以上の強連結成分（以下「良い強連結成分」と呼ぶ）内の頂点は条件を満たす。
3. あとは上記2.の強連結成分に到達できる頂点も条件を満たすが、それをどうやって求めるか。ACLはトポロジカル順で返してくれはするが、最後の良い強連結成分より前が全てそこに繋がっているとは限らない。
   　
4. 良い強連結成分外の未訪問頂点からDFSして良い強連結成分に到達できた頂点はOKとする？
5. ルートが枝分かれしていた時に計算量を悪化させずに判定をするのが難しそう。
   　
6. 辺を逆向きにし、良い強連結成分の全頂点を始点としてBFSを行い、到達できた頂点をOKとすればよい。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.List;
import java.util.Queue;

public class Main {
    static List<List<Integer>> list;
    static int[] b;

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

        int[][] g = scc.scc();

        Queue<Integer> que = new ArrayDeque<>();
        b = new int[n];
        for (int i = g.length - 1; i >= 0; i--) {
            if (g[i].length >= 2) {
                for (int e : g[i]) {
                    b[e] = 1;
                    que.add(e);
                }
            }
        }

        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (b[next] == 0) {
                    que.add(next);
                    b[next] = 1;
                }
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (b[i] == 1) {
                ans++;
            }
        }
        System.out.println(ans);
    }
}

// 以下ACLを移植したSCC（強連結成分分解）

提出
ここまで64分27秒＋1ペナ。326位。

G - Foreign Friends

問題
FはBFSに気付くのに、D, E, Gは実装に時間かかり過ぎで、時間内には解けず。
下記思考過程を終えた時点でまだ15分くらいは残っていたと思うが、実装にもデバッグにも時間がかかって7分ほど遅れてAC。

思考過程

1. 回ダイクストラをやりたいが、それは当然TLE。
2. 始点を個にして同時にダイクストラをやればどうか？
3. 上手く枝刈りするとしても、の配列を用意してしまったりしては駄目。
4. 人の各人について、異なる国由来の人気者上位人からのコストだけ保持しておけば、そのどちらかは条件を満たすので十分。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
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]);
//      int k = Integer.parseInt(sa[2]);
        int l = Integer.parseInt(sa[3]);

        sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[l];
        for (int i = 0; i < l; i++) {
            b[i] = Integer.parseInt(sa[i]) - 1;
        }

        List<List<Hen>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            int u = Integer.parseInt(sa[0]) - 1;
            int v = Integer.parseInt(sa[1]) - 1;
            int c = Integer.parseInt(sa[2]);

            list.get(u).add(new Hen(v, c));
            list.get(v).add(new Hen(u, c));
        }
        br.close();

        long[] d = new long[n];  // 最小コスト1位
        long[] d2 = new long[n]; // 最小コスト2位
        int[] da = new int[n];   // 最小コスト1位の所属国
        int[] da2 = new int[n];  // 最小コスト2位の所属国
        Arrays.fill(d, Long.MAX_VALUE);
        Arrays.fill(d2, Long.MAX_VALUE);
        PriorityQueue<Node> que = new PriorityQueue<Node>();
        for (int i = 0; i < l; i++) {
            que.add(new Node(b[i], 0, a[b[i]]));
            d[b[i]] = 0;
            da[b[i]] = a[b[i]];
        }

        while (!que.isEmpty()) {
            Node cur = que.poll();
            if (cur.a == da[cur.v] && cur.d > d[cur.v]) {
                continue;
            }
            if (cur.a == da2[cur.v] && cur.d > d2[cur.v]) {
                continue;
            }
            for (Hen hen : list.get(cur.v)) {
                long alt = cur.d + hen.c;
                if (alt < d[hen.v]) {
                    if (da[hen.v] != cur.a) {
                        d2[hen.v] = d[hen.v];
                        da2[hen.v] = da[hen.v];
                    }
                    d[hen.v] = alt;
                    da[hen.v] = cur.a;
                    que.add(new Node(hen.v, alt, cur.a));
                } else if (alt < d2[hen.v] && da[hen.v] != cur.a) {
                    d2[hen.v] = alt;
                    da2[hen.v] = cur.a;
                    que.add(new Node(hen.v, alt, cur.a));
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            long ans = Long.MAX_VALUE;
            if (da[i] != a[i]) {
                ans = d[i];
            } else {
                ans = d2[i];
            }
            if (ans == Long.MAX_VALUE) {
                ans = -1;
            }
            sb.append(ans).append(' ');
        }
        sb.deleteCharAt(sb.length() - 1);
        System.out.println(sb.toString());
    }

    static class Hen {
        int v, c;

        public Hen(int v, int c) {
            this.v = v;
            this.c = c;
        }
    }

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

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

        public int compareTo(Node o) {
            return Long.compare(d, o.d);
        }
    }
}

ここまで107分06秒＋1ペナ。

最終結果：ABCDEFの6完2000点、69分27秒、357位、パフォーマンス1969相当
レート変動：2017（Unrated）

2600点105分ならほぼパフォ2400でABCトーナメントも勝てていたので惜しかった。
D問題で下からやろうとしていなければあるいは・・・。