AtCoder Beginner Contest 191

コンテスト前のレート：1937
レート通りのパフォーマンスが得られる順位：409位（1100点、28分50秒）

A - Vanishing Pitch

問題
いつものAより難しめ。
参加者全体でAよりBの方が正解者数多いの珍しい気がする。

思考過程

1. ボールは秒後にはメートル、秒後にはメートル離れた場所まで移動するので、ならば"No"。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int v = sc.nextInt();
        int t = sc.nextInt();
        int s = sc.nextInt();
        int d = sc.nextInt();
        sc.close();

        int v1 = v * t;
        int v2 = v * s;
        if (v1 <= d && d <= v2) {
            System.out.println("No");
        } else {
            System.out.println("Yes");
        }
    }
}

ここまで1分27秒＋0ペナ。226位。

B - Remove It

問題

思考過程

1. 前から見ていき、と等しくない要素を答えの文字列に追加していく。
2. 要素が個以上ある場合は末尾の半角スペースを取り除きたいが、個も追加していない場合は空文字列のまま何もしない。

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 x = sc.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) {
            if (a[i] != x) {
                sb.append(a[i]).append(' ');
            }
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb.toString());
    }
}

ここまで2分57秒＋0ペナ。298位。

C - Digital Graffiti

問題
初めは問題の意味がよくわからず。
なんとなくわかってからも簡単に解ける気がせず、一旦飛ばしてD問題を見る。
Dもなんか大変そうなのでEを見たら、簡単だったのでEを解く。
Fも一応見て簡単にはわかりそうになかったので、Cに戻ってくる。

思考過程

1. まずは問題理解から。自己交叉とは何かを調べる。
2. はっきりはわからなかったが、多分【多角形 - Wikipedia】の一番右の茶色の図形のように、重なっているような部分がないということ？
3. 例１のも'#'にして分銅のような形にしてみると、角形になりそう。'#'が個だけの場合は角形と解釈しそう。
   　
4. 適当な'#'から始めて多角形の周に沿うようにDFS/BFS？　と一瞬思うが、できる気がしない。
5. では辺に当たる部分をDFS/BFS？　それも大変そう。
6. では頂点に当たる部分に注目したら？
7. 上記3.のような分銅型を眺めると、頂点になるのは折れ曲がっている箇所で、'.'と'#'が直線で分けられるような部分は辺になる。
   　
8. 結局、例１の説明にあるような座標系で、基本的には点の周囲の'#'の数が個か個であれば頂点とカウントできる。（個なら完全に多角形の外、平行に個なら辺、個なら多角形の内部）
9. ただし、対角に個ある場合は、個分とカウントされる。（と勘違いした。そのようになるのは多角形の中に空洞ができる場合で、白に塗られた任意のマスは互いに到達可能って書いてあった。）

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        char[][] s = new char[h][w];
        for (int i = 0; i < h; i++) {
            s[i] = br.readLine().toCharArray();
        }
        br.close();

        int ans = 0;
        for (int i = 1; i < h; i++) {
            for (int j = 1; j < w; j++) {
                int cnt = 0;
                if (s[i - 1][j - 1] == '#') cnt++;
                if (s[i - 1][j] == '#') cnt++;
                if (s[i][j - 1] == '#') cnt++;
                if (s[i][j] == '#') cnt++;
                // '#'が1個か3個の場合
                if (cnt % 2 == 1) {
                    ans++;
                } else if (cnt == 2) {
                    // '#'が対角に2個の場合（このケースは不要）
                    if (s[i - 1][j - 1] == s[i][j]) {
                        ans += 2;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ABECと解いた時点で25分01秒＋0ペナ。54位。

D - Circle Lattice Points

問題
下記6.から8.にたどり着くまで20分かかったが、ぎりぎりでAC。

思考過程

1. まず、小数で扱うと誤差が心配なので、整数で扱えないかを考える。
2. 入力を倍したら、となり、後々乗したりしてもオーバーフローの心配はなさそう。
   　
3. 格子点をつずつ円の内部かどうか判定して数えたのでは、最大で例３の通り個くらいになってしまうので間に合わない。
4. 下図のように、座標をと固定すると、円の内部となる座標の範囲を二分探索（三平方の定理で境界判定）で求めることができ、それをで行えば、全体でとなる。
   
5. 左右それぞれについて二分探索を行い、よくある～の範囲で当てはまる数を求めたい場合にとするような計算をするだけなのだが、なかなか例３が合わない。
6. 図内のok1、ng1、ok2、ng2は実際には単位ではなく単位で求めてしまっているので、単位に切り捨てか切り上げをしなければならないが、そのやり方が値の正負によって変わることに注意する必要があった。　→3ケースWA
   　
7. 想定外のことが起こっていないかREを仕込んだりもするが空振り。いくら見直しても、forループ内に問題がある箇所はなさそうに思える。
8. の丸め方も、正負で場合分けが必要だった。（円の範囲外を調べたときにになるように実装できていれば、は広めにすればよかったが、上記6.を直す内にそうならなくなってしまった）

import java.math.BigDecimal;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        BigDecimal bd = BigDecimal.valueOf(10000);
        long x = sc.nextBigDecimal().multiply(bd).longValue();
        long y = sc.nextBigDecimal().multiply(bd).longValue();
        long r = sc.nextBigDecimal().multiply(bd).longValue();
        sc.close();

        long ans = 0;
        long r2 = r * r;
        long s = y - r;
        // 切り上げ（値が大きくなる方に丸める）
        if (s >= 0) {
            s = (s + 9999) / 10000 * 10000;
        } else {
            s = s / 10000 * 10000;
        }
        long t = y + r;
        // 切り捨て（値が小さくなる方に丸める）
        if (t >= 0) {
            t = t / 10000 * 10000;
        } else {
            t = (t - 9999) / 10000 * 10000;
        }

        for (long i = s; i <= t; i += 10000) {
            long a = y - i;
            long a2 = a * a;

            long ok1 = x;
            long ng1 = x - r - 1;
            while (Math.abs(ok1 - ng1) > 1) {
                long mid = (ok1 + ng1) / 2;
                long b = x - mid;
                long b2 = b * b;
                if (a2 + b2 <= r2) {
                    ok1 = mid;
                } else {
                    ng1 = mid;
                }
            }

            long ok2 = x;
            long ng2 = x + r + 1;
            while (Math.abs(ok2 - ng2) > 1) {
                long mid = (ok2 + ng2) / 2;
                long b = x - mid;
                long b2 = b * b;
                if (a2 + b2 <= r2) {
                    ok2 = mid;
                } else {
                    ng2 = mid;
                }
            }

            if (ok2 >= 0) {
                ans += ok2 / 10000;
                if (ok1 <= 0) {
                    // x=0をまたぐ場合
                    // 正側と負側と0を足す
                    ans -= ok1 / 10000;
                    ans++;
                } else {
                    // 完全に正の範囲の場合
                    // f(R) - f(L-1)のイメージ
                    ans -= ng1 / 10000;
                }
            } else {
                // 完全に負の範囲の場合
                // - (f(L) - f(R+1))のイメージ
                ans -= ok1 / 10000;
                ans += ng2 / 10000;
            }
        }
        System.out.println(ans);
    }
}

ABECDと解いた時点で99分15秒＋4ペナ。301位。

E - Come Back Quickly

問題

思考過程

1. 始点を固定すればほぼただのダイクストラだが制約は・・・乗が間に合いそうな制約なので、本当にただ回ダイクストラするだけ。
2. ただし、始点に戻ってこられるように少し工夫が必要。
3. 通常、距離がより短くなれば値を更新してキューにも入れるところを、次の頂点が始点の場合は値の更新だけ行い、そこで終わりなのでキューに入れないようにすればよさそう。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
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]);
        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 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));
            // b→aの辺はなし
        }
        br.close();

        PrintWriter pw = new PrintWriter(System.out);
        for (int s = 0; s < n; s++) {
            long ans = Long.MAX_VALUE;
            long[] d = new long[list.size()];
            Arrays.fill(d, Long.MAX_VALUE);
            d[s] = 0;
            PriorityQueue<Node> que = new PriorityQueue<Node>();
            Node first = new Node(s, 0);
            que.add(first);

            while (!que.isEmpty()) {
                Node cur = que.poll();
                if (cur.d > d[cur.v]) {
                    continue;
                }
                for (Hen hen : list.get(cur.v)) {
                    long alt = d[cur.v] + hen.c;
                    // 通常のダイクストラにこのif文だけ追加
                    if (hen.v == s) {
                        ans = Math.min(ans, alt);
                    }

                    if (alt < d[hen.v]) {
                        d[hen.v] = alt;
                        que.add(new Node(hen.v, alt));
                    }
                }
            }

            if (ans == Long.MAX_VALUE) {
                ans = -1;
            }
            pw.println(ans);
        }
        pw.flush();
    }

    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;
        long d;

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

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

ABEと解いた時点で15分23秒＋0ペナ。24位。

F - GCD or MIN

問題
Dに時間がかかりすぎたのもあり、この問題にかけたのは10～15分ほど。そして解けず。

思考過程

1. minしか取らないことで、は残せる。
2. gcdはmin以下にしかならないので、より大きい値は残せない。
3. 任意の回数gcdを取って作れる、以下の値の個数を求める問題になった。
   　
4. 適当なことをしたらTLEしそうな予感がし、下手に前から順にやったら取りこぼしがありそうで、どうすればいいのかよくわからず。
5. 素因数分解して何かわかったりしないか考えたりもするが、まとまらず。

最終結果：ABCDEの5完、119分15秒、302位、パフォーマンス2064
レート変動：1937→1950（+13）

D問題粘って最終的に解消できたのはよかった。
もっとすんなり気付いて5完90分くらいならパフォ2200近く、解けずに終われば1940程度でぎりぎりノルマクリアといったところだった。
パフォ100くらいは上がっているので、ぎりぎりでも通せた意味はあった。

これで次回2370以上で黄色に届くようになり、可能性が出てきたかもしれない。
今回は大丈夫だったが、そもそもまだ1900維持できる実力があると思っていないので、爆死しないようにしていきたい。

ABCトーナメント2回戦は、レート以上の結果は出したのだから、負けても仕方ない。