AtCoder Beginner Contest 259

コンテスト前のレート:1976
レート通りのパフォーマンスが得られる順位:355位(2000点、105分35秒)

A - Growth Record

問題
問題を読むのが遅くて辛い。

思考過程
  1. とりあえずM \leq Xかそうでないかで場合分け。
  2. M \gt Xの場合はT
  3. M \leq Xの場合はM \times D?と思ったが、例2を見ると0歳の時0ではないらしく、T - (X-M) \times Dのように逆算が必要であった。
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();
        int m = sc.nextInt();
        int x = sc.nextInt();
        int t = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        if (m <= x) {
            System.out.println(t - (x - m) * d);
        } else {
            System.out.println(t);
        }
    }
}

ここまで3分28秒+0ペナ。763位。


B - Counterclockwise Rotation

問題
度とラジアンの変換メソッドはMathクラスにあったらしい。知らなかった。

思考過程
  1. 半径rと角度\thetaがわかれば、x=r \cos \thetay=r \sin \thetaで求められる。
  2. r=\sqrt{a^2+b^2}であり、これはMath.hypotを使って求められる。
  3. 角度の方は、元の角度(ラジアン単位)をMath.atan2で求め、それにdラジアンに換算したものを足す。
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 d = sc.nextInt();
        sc.close();

        // 2
        double r = Math.hypot(a, b);
        // 3
        double rad = Math.atan2(b, a);
        rad += Math.PI * 2 * d / 360; // Math.toRadians(d)でよかった
        // 1
        double x = r * Math.cos(rad);
        double y = r * Math.sin(rad);
        System.out.println(x + " " + y);
    }
}

ここまで7分23秒+0ペナ。408位。


C - XX to XXX

問題

思考過程
  1. STの各文字を上手く対応付けていくことを考えようとするが大変そう。
  2. ランレングス圧縮すれば判定しやすくなりそう。
     
  3. S, Tそれぞれについて、文字の並び順のリストと各文字が連続する回数のリストを作る。戻り値が2つになるのでメソッド化しにくく、ベタで2回書いてしまう。
     
  4. リストのi番目の比較に際しては、まず文字が異なれば"No"。
  5. 回数の方は、Sの方が多いか、Sの方が少なく増やせない場合"No"。
import java.util.ArrayList;
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);
        char[] s = sc.next().toCharArray();
        char[] t = sc.next().toCharArray();
        sc.close();

        // Sをランレングス圧縮
        List<Character> lsc = new ArrayList<>();
        List<Integer> lsn = new ArrayList<>();
        char a = s[0];
        int n = 1;
        for (int i = 1; i < s.length; i++) {
            if (s[i] == a) {
                n++;
            } else {
                lsc.add(a);
                lsn.add(n);
                a = s[i];
                n = 1;
            }
        }
        lsc.add(a);
        lsn.add(n);

        // Tをランレングス圧縮
        List<Character> ltc = new ArrayList<>();
        List<Integer> ltn = new ArrayList<>();
        a = t[0];
        n = 1;
        for (int i = 1; i < t.length; i++) {
            if (t[i] == a) {
                n++;
            } else {
                ltc.add(a);
                ltn.add(n);
                a = t[i];
                n = 1;
            }
        }
        ltc.add(a);
        ltn.add(n);

        if (lsc.size() != ltc.size()) {
            System.out.println("No");
            return;
        }

        for (int i = 0; i < lsc.size(); i++) {
            // 4
            char cs = lsc.get(i);
            char ct = ltc.get(i);
            if (cs != ct) {
                System.out.println("No");
                return;
            }

            // 5
            int ns = lsn.get(i);
            int nt = ltn.get(i);
            if (ns > nt) {
                System.out.println("No");
                return;
            }
            if (ns < nt && ns < 2) {
                System.out.println("No");
                return;
            }
        }
        System.out.println("Yes");
    }
}

ここまで15分44秒+0ペナ。346位。


D - Circumferences

問題
幾何ライブラリ何も用意できていなくて辛い。

思考過程
  1. 各円を頂点とし、円同士が交わるか接する場合に辺を張ったグラフを考え、sがある円とtがある円が連結かどうかを判定する。
  2. O(N^2α)で問題ない制約なので、UnionFindを使って_NC_2通り全組合せについて連結できるか判定する。
     
  3. 円同士が交わるか接するかの判定については、完全に離れる場合と含まれる場合をNGとすることを思い浮べながら実装してみるもWA。
  4. 検索して、「半径の差\leq中心同士の距離\leq半径の和」(※実際には整数で扱うためこれらの2乗で比較)という判定式を得る。
     
  5. s, tがある円は、全ての円を見ていき、中心と点との距離が半径と一致しているかを判定して特定する。
import java.util.Scanner;

public class Main {
    static int[] x, y, r;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int sx = sc.nextInt();
        int sy = sc.nextInt();
        int tx = sc.nextInt();
        int ty = sc.nextInt();
        x = new int[n];
        y = new int[n];
        r = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = sc.nextInt();
            y[i] = sc.nextInt();
            r[i] = sc.nextInt();
        }
        sc.close();

        // 2
        UnionFind uf = new UnionFind(n);
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (cross(i, j)) {
                    uf.union(i, j);
                }
            }
        }

        // 5
        int s = 0;
        int t = 0;
        for (int i = 0; i < n; i++) {
            long dx = sx - x[i];
            long dy = sy - y[i];
            if (dx * dx + dy * dy == (long) r[i] * r[i]) {
                s = i;
            }
            dx = tx - x[i];
            dy = ty - y[i];
            if (dx * dx + dy * dy == (long) r[i] * r[i]) {
                t = i;
            }
        }
        // 1
        if (uf.same(s, t)) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }

    static boolean cross(int i, int j) {
        long d1 = r[i] - r[j];
        long d2 = r[i] + r[j];
        long dx = x[i] - x[j];
        long dy = y[i] - y[j];
        long d12 = d1 * d1;
        long d22 = d2 * d2;
        long dx2 = dx * dx;
        long dy2 = dy * dy;
        // 4
        if (d12 <= dx2 + dy2 && dx2 + dy2 <= d22) {
            return true;
        }
        return false;
    }

    // 以下ライブラリ

    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)];
        }
    }
}

ここまで37分16秒+1ペナ。611位。


E - LCM on Whiteboard

問題

思考過程
  1. 1に書き換えるということは、その数を除いたN-1個の最小公倍数になるということ。
  2. a_iを書き換えた時に書き換え前と最小公倍数が異なるためには、1つ以上の素因数についてa_1a_Nの中でa_iの次数が単独で最大である必要がある。
  3. ひとまず、Map<素因数、{最大、次点}>を作っておく。
     
  4. a_ia_jで同じ最小公倍数に変化する可能性があるかないかよくわからなかったので(実際その可能性はなかったが)、上記2.の条件を満たす素因数を連結した文字列をSetに入れて要素数を答えることにする。
  5. 単独最大であるものしかSetには入らないので、Setに入る要素の長さの合計はO(\sum m_i)に収まるはず。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
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[] m = new int[n];
        List<List<Integer>> pl = new ArrayList<>(n);
        List<List<Integer>> el = new ArrayList<>(n);
        Map<Integer, PriorityQueue<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            m[i] = Integer.parseInt(br.readLine());
            List<Integer> pi = new ArrayList<>(m[i]);
            List<Integer> ei = new ArrayList<>(m[i]);
            for (int j = 0; j < m[i]; j++) {
                String[] sa = br.readLine().split(" ");
                int p = Integer.parseInt(sa[0]);
                int e = Integer.parseInt(sa[1]);
                pi.add(p);
                ei.add(e);
                PriorityQueue<Integer> q = map.get(p);
                if (q == null) {
                    q = new PriorityQueue<Integer>();
                    map.put(p, q);
                }
                q.add(e);
                if (q.size() > 2) {
                    q.poll();
                }
            }
            pl.add(pi);
            el.add(ei);
        }
        br.close();

        // 3
        Map<Integer, int[]> map2 = new HashMap<>();
        for (Integer k : map.keySet()) {
            PriorityQueue<Integer> q = map.get(k);
            int[] a = new int[2];
            if (q.size() == 2) {
                a[1] = q.poll();
                a[0] = q.poll();
            } else {
                a[0] = q.poll();
            }
            map2.put(k, a);
        }

        // 4
        Set<String> set = new HashSet<>();
        for (int i = 0; i < n; i++) {
            StringBuilder sb = new StringBuilder();
            List<Integer> pi = pl.get(i);
            List<Integer> ei = el.get(i);
            sb.append('-');
            for (int j = 0; j < m[i]; j++) {
                int p = pi.get(j);
                int[] a = map2.get(p);
                if (a[0] != a[1] && ei.get(j) == a[0]) {
                    sb.append(p).append('-');
                }
            }
            set.add(sb.toString());
        }
        System.out.println(set.size());
    }
}

ここまで59分35秒+1ペナ。512位。


F - Select Edges

問題

思考過程
  1. wの大きい順に貪欲に選ぶのは駄目そう。(1-2-3-4の場合に2-3ではなく1-2と3-4を選ばなければならないとかがある)
  2. 葉から木DPをすることを考えると、子を全部処理した時点で「dp0:=使い切っている(親と繋がる辺を選べない)場合の最大値」と「dp1:=1本残している(親と繋がる辺を選べる)場合の最大値」を保持しておくのを思い付く。
     
  3. 頂点xについて処理する際、d_xまたはd_x-1本をどのように選べばよいかが問題だが、これは各子について辺を選ぶとどれだけ得するか(辺を選ぶ場合-選ばない場合)を求めてその大きい順に貪欲に選べばよい。
  4. 辺を選んだ場合に得する子がd_x個より少ない場合や、d_x=0の場合に注意する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {
    static int[] d;
    static List<List<Hen>> list;
    static long[] dp0, dp1;

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

            list.get(a).add(new Hen(b, c));
            list.get(b).add(new Hen(a, c));
        }
        br.close();

        dp0 = new long[n];
        dp1 = new long[n];
        dfs(0, -1);
        System.out.println(Math.max(dp0[0], dp1[0]));
    }

    static void dfs(int x, int p) {
        PriorityQueue<Obj> que = new PriorityQueue<>((o1, o2) -> Long.compare(o2.d, o1.d));
        for (Hen h : list.get(x)) {
            if (h.v != p) {
                dfs(h.v, x);
                Obj o = new Obj();
                o.v0 = dp0[h.v];
                o.v1 = dp1[h.v] + h.c;
                o.d = o.v1 - o.v0;
                que.add(o);
            }
        }
        int cnt = 0;
        while (!que.isEmpty()) {
            Obj o = que.poll();
            long max = Math.max(o.v0, o.v1);
            if (cnt < d[x] - 1) {
                dp0[x] += max;
                dp1[x] += max;
            } else if (cnt < d[x]) {
                dp0[x] += max;
                dp1[x] += o.v0;
            } else {
                dp0[x] += o.v0;
                dp1[x] += o.v0;
            }
            cnt++;
        }
        if (d[x] == 0) {
            dp1[x] = -100000000000L;
        }
    }

    static class Obj {
        long v0, v1, d;
    }

    static class Hen {
        int v, c;

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

ここまで85分47秒+1ペナ。257位。



GもExも100人ほど解いていてどちらをやるか迷う。
一応両方問題読んだが、どちらもすぐにはわからず。
Gはフローっぽさだけ感じており、Exは4乗から落とす方法わからんとか思っている間に残り5分を切って諦め。



終結果:ABCDEFの6完2000点、90分47秒、282位、パフォーマンス2079
レート変動:1976→1987(+11)


6完時点で15分だけ残っても中途半端で損した感じ。30分くらいはないと解ける可能性を感じないのでもう少し前半をスムーズに解きたい。

こればっかりはどうしようもないが、まず問題を読むのが遅くて出遅れ気味だった。
Dはすぐに調べに行くべきだった。
EとFはあまり自信なかったので通せただけでも助かったが、やっぱりDPの実装が遅い。