AtCoder Beginner Contest 246(Rated範囲外)

ABC

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

A - Four Points

問題

思考過程
  1. x, yそれぞれ1回登場する値と2回登場する値の2種類があり、1回登場する値の方を答えればよい。
  2. 実装は大げさ過ぎる気もしたが、Map＜値、個数＞の形で入力を受け取って調べることにする。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        Map<Integer, Integer> mapx = new HashMap<>();
        Map<Integer, Integer> mapy = new HashMap<>();
        for (int i = 0; i < 3; i++) {
            int a = sc.nextInt();
            mapx.put(a, mapx.getOrDefault(a, 0) + 1);
            int b = sc.nextInt();
            mapy.put(b, mapy.getOrDefault(b, 0) + 1);
        }
        sc.close();

        int x = 0;
        for (int a : mapx.keySet()) {
            if (mapx.get(a) == 1) {
                x = a;
            }
        }
        int y = 0;
        for (int a : mapy.keySet()) {
            if (mapy.get(a) == 1) {
                y = a;
            }
        }
        System.out.println(x + " " + y);
    }
}

ここまで3分17秒＋0ペナ。1385位。


B - Get Closer

問題

思考過程
  1. \frac{A}{A+B}と\frac{B}{A+B}？とか一瞬考えたりするが、全然違う。（例１をよく見れば、3:4:5の直角三角形から\frac{A}{\sqrt{A^2+B^2}}が出てきてもよさそうなものだったが・・・。）
    　
  2. 距離が1ということは、角度がわかればcos \thetaとsin \thetaになる。
  3. 角度はatan2メソッドを使えば求められる。
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();

        double r = Math.atan2(b, a);
        System.out.println(Math.cos(r) + " " + Math.sin(r));
    }
}

ここまで6分26秒＋0ペナ。1027位。


C - Coupon

問題

思考過程
  1. Kが大きいため、PriorityQueueを使ってK回減算するような愚直シミュレーションは間に合わない。d回分まとめて引くようなことをする必要がある。
    　
  2. まず、Xを引いてマイナスにならない範囲で使えるだけ使う。
  3. それでまだクーポンが余っている場合、A_iの大きい順（この時点ではA_i \% Xの大きい順）に1枚ずつ使っていく。
import java.util.Collections;
import java.util.PriorityQueue;
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 k = sc.nextInt();
        int x = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        for (int i = 0; i < n; i++) {
            int d = Math.min(a[i] / x, k);
            a[i] -= x * d;
            k -= d;
        }

        PriorityQueue<Integer> que = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < n; i++) {
            que.add(a[i]);
        }

        long ans = 0;
        while (!que.isEmpty()) {
            int b = que.poll();
            if (k > 0) {
                b = 0;
                k--;
            }
            ans += b;
        }
        System.out.println(ans);
    }
}

ここまで12分14秒＋0ペナ。579位。


D - 2-variable Function

問題
実装が下手くそで時間かかった。

思考過程
  1. 因数分解してみたら(a+b)(a^2+b^2)となるが、特に何も見えてこない。
  2. a \geq bとして、まずa=bの場合のX=4a^3 \geq Nとなる最小のaを求め、以降aを1増やすごとにbをaから（2回目以降は前回の続きから）減らせるところまで減らしていくようにすれば、計算量は(10^6)^2ではなく10^6 \times 2くらいで済みそう。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        long n = sc.nextLong();
        sc.close();

        long b = 0;
        long ans = Long.MAX_VALUE;
        boolean f = true;
        for (long a = 0; a <= n; a++) {
            long x = a * a * a;
            // b＝0でもn以上なら終了
            if (x >= n) {
                ans = Math.min(ans, x);
                break;
            }
            x *= 4;
            if (x >= n) {
                // 初めて4a^3≧nとなった場合、bの初期値を設定
                if (f) {
                    f = false;
                    b = a;
                    ans = x;
                }
                while (b >= 0) {
                    long y = a*a*a + a*a*b + a*b*b + b*b*b;
                    if (y >= n) {
                        ans = Math.min(ans, y);
                        b--;
                    } else {
                        break;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで31分49秒＋0ペナ。582位。


E - Bishop 2

問題

思考過程
  1. ABC170-Fを距離無制限にして斜めにしたような問題。
  2. この手の問題は、普通に4方向に進めるだけ進むBFSをしようとすると、訪問済みのマスから先には進まないようにすればもっと先の方にある未訪問マスに行き損ねる場合があり、必ず壁にたどり着くまで調べていては計算量オーバーとなってしまう。
    　
  3. 訪問したマスの情報を保持しておく配列を左上-右下方向と左下-右上方向の2つ用意し、最後に該当する方向の移動によってたどり着く場合の最小手数を設定するようにする。
  4. このようにすれば、訪問済みのマスに当たった時点でその先を調べなくてよくなる。
    　
  5. 未訪問判定する配列を間違えたり、打ち切る処理を入れていなかったり、2方向のみ調べるべきなのに4方向調べていて配列を分けた意味がなくなっていたりしていたので直す。
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Queue;
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 ax = sc.nextInt() - 1;
        int ay = sc.nextInt() - 1;
        int bx = sc.nextInt() - 1;
        int by = sc.nextInt() - 1;
        char[][] g = new char[n][n];
        for (int i = 0; i < n; i++) {
            g[i] = sc.next().toCharArray();
        }
        sc.close();

        int[] dx = {1, -1, 1, -1};
        int[] dy = {1, -1, -1, 1};
        int f = 1000000000;

        int[][] d = new int[n][n];
        int[][] d2 = new int[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(d[i], -1);
            Arrays.fill(d2[i], -1);
        }
        d[ax][ay] = 0;
        d2[ax][ay] = 0;

        Queue<Integer> que = new ArrayDeque<>();
        int s = ax * n + ay;
        que.add(s);
        que.add(s + f);
        while (!que.isEmpty()) {
            int cur = que.poll();
            int cz = cur / f;
            cur %= f;
            int cx = cur / n;
            int cy = cur % n;

            int start = 0;
            int end = 2;
            if (cz == 1) {
                start = 2;
                end = 4;
            }
            for (int i = start; i < end; i++) {
                for (int j = 1; j < n; j++) {
                    int nx = cx + dx[i] * j;
                    int ny = cy + dy[i] * j;
                    if (nx < 0 || n <= nx || ny < 0 || n <= ny ||
                            g[nx][ny] == '#') {
                        break;
                    }
                    int next = nx * n + ny;
                    if (cz == 0) {
                        if (d2[nx][ny] == -1) {
                            que.add(next + f);
                            d2[nx][ny] = d[cx][cy] + 1;
                        } else {
                            break;
                        }
                    } else {
                        if (d[nx][ny] == -1) {
                            que.add(next);
                            d[nx][ny] = d2[cx][cy] + 1;
                        } else {
                            break;
                        }
                    }
                }
            }
        }

        if (d[bx][by] == -1) {
            if (d2[bx][by] == -1) {
                System.out.println(-1);
            } else {
                System.out.println(d2[bx][by]);
            }
        } else {
            if (d2[bx][by] == -1) {
                System.out.println(d[bx][by]);
            } else {
                System.out.println(Math.min(d[bx][by], d2[bx][by]));
            }
        }
    }
}

ここまで65分59秒＋3ペナ。598位。



一応まずはFを見たが、すぐにはわからず、とりあえずGも見る。
並行して考えている間にFは既に500人程度に解かれていたので、今更解いても順位はほとんど上がらないと見てGに賭けることにする。


G - Game on Tree 3

問題
答えの二分探索をするところまではやれていたが、判定問題が解けておらず、例３が合わないまま終了。
以下はただの解説ACコード。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;

public class Main {
    static int n;
    static int[] a, dp;
    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 - 1; i++) {
            a[i + 1] = 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();

        int ok = 0;
        int ng = 1000000001;
        while (Math.abs(ok - ng) > 1) {
            int mid = (ok + ng) / 2;
            if (dfs(0, -1, mid) > 0) {
                ok = mid;
            } else {
                ng = mid;
            }
        }
        System.out.println(ok);
    }

    static int dfs(int x, int p, int v) {
        int ret = 0;
        for (int c : list.get(x)) {
            if (c != p) {
                int res = dfs(c, x, v);
                ret += res;
            }
        }
        if (ret > 0) {
            ret--;
        }
        if (a[x] >= v) {
            ret++;
        }
        return ret;
    }
}

　


最終結果：ABCDEの5完1500点、80分59秒、793位、パフォーマンス1599相当
レート変動：2017（Unrated）


自分のレートがちょうど1色低ければAだけが遅かったという感じだが、レート2000基準で考えたらDとEをもっと早く通してFとGに時間を残せないと駄目なのだと思う。
Eは最終的に34分かかったが、初回提出までなら19分だったのだが・・・。
時間に追われてGの木DP部分がちゃんと考えられずになんとなくになっていたのが失敗。

なお、2000点最下位ならパフォ1730ほどで、2100点最下位なら2340ほどだったので、130を捨てて740を取りに行ったと思えば戦略は間違ってなかったかなと思う。
自分にとって解ける可能性はどちらも似たようなものだったし。