AtCoder Beginner Contest 168

ABC

コンテスト前のレート：1769
レート通りのパフォーマンスが得られる順位：573位

A - ∴ (Therefore)

問題
if文とswitch分どっちの方が早く書けるんだろう。

問題概要

以下の通り出力せよ。

  • Nの1の位が2, 4, 5, 7, 9のとき 'hon'
  • Nの1の位が0, 1, 6, 8のとき 'pon'
  • Nの1の位が3のとき 'bon'
  • Nは999以下の正の整数
思考過程
  1. 1の位は\% 10で求まる。
  2. 条件が一番多いやつをelseにする。
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();
        sc.close();

        n %= 10;
        if (n == 3) {
            System.out.println("bon");
        } else if (n == 0 || n == 1 || n == 6 || n == 8) {
            System.out.println("pon");
        } else {
            System.out.println("hon");
        }
    }
}

ここまで1分36秒＋0ペナ。282位。


B - ... (Triple Dots)

問題
'...' が半角ピリオドではなく三点リーダだったりしたら嫌だと思ったので念のためコピペした。

問題概要

英小文字からなる文字列Sの長さがK以下であればSをそのまま出力、そうでなければ先頭K文字に '...' を付加して出力せよ。

  • 1 \leq K, |S| \leq 100
思考過程
  1. K以下かどうかで場合分けする。
  2. 先頭K文字はsubstringで取得できる。
import java.util.Scanner;

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

        if (s.length() <= k) {
            System.out.println(s);
        } else {
            System.out.println(s.substring(0, k) + "...");
        }
    }
}

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


C - : (Colon)

問題
数学っぽくて時間かかりそうで見た瞬間うげっと思った。
先にD問題をやることも考えたが、完全に手が止まるまでは頑張ることにした。
それにしても、正解者数多すぎでは？　高校生大学生辺りだとできなければまずいのかもしれないけど。

問題概要

時針と分針の長さがそれぞれA、Bであるアナログ時計がある。
H時M分時点での2本の針の先端の距離を求めよ。

  • 入力は全て整数
  • 1 \leq A, B \leq 1000
  • 0 \leq H \leq 11
  • 0 \leq M \leq 59
思考過程
  1. 三角関数関連かベクトル関連か何かの公式で求められそうな形をしているが、そんなものはとっくに忘れたので、それぞれの座標を求めて三平方することにする。
  2. まずは角度（1周を1とした割合）を求める。
  3. sinメソッドやcosメソッドの引数はラジアン単位なので、360ではなく2\piを掛ける。
  4. x座標はcos、y座標はsinで求まる。
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 h = sc.nextInt();
		int m = sc.nextInt();
		sc.close();

		double r1 = h / 12.0 + m / (12.0 * 60);
		r1 *=  Math.PI * 2;
		double x1 = a * Math.cos(r1);
		double y1 = a * Math.sin(r1);

		double r2 = m / 60.0 * Math.PI * 2;
		double x2 = b * Math.cos(r2);
		double y2 = b * Math.sin(r2);

		System.out.println(Math.hypot(x1 - x2, y1 - y2));
	}
}

ここまで12分19秒＋0ペナ。542位。
最初2\piではなく\piにしてたりして、2分ほど遅れた。


D - .. (Double Dots)

問題
数学よりただのBFSの方がはるかに簡単だと思うのは、経験値なのかな・・・。

問題概要

N頂点M辺の単純無向連結グラフがある。
頂点1以外の各頂点に、直接つながっているいずれかの頂点を指す道しるべを置く。
各頂点から、道しるべをたどって最短の移動回数で頂点1にたどり着けるようにしたい。
そのような道しるべの配置が存在するか判定し、存在するならばそのような配置を1つ出力せよ。

  • 2 \leq N \leq 10^5
  • 1 \leq M \leq 2 \times 10^5
思考過程
  1. 連結なので必ず 'Yes'。サンプルにも 'No' のケースがない。
  2. 最短距離で辺の重みもないので普通のBFSをしたくなる。
  3. 頂点1からのBFSで、距離ではなく遷移元を記録していけばよい。
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]);
        List<List<Integer>> 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;
            list.get(a).add(b);
            list.get(b).add(a);
        }
        br.close();

        int[] ans = new int[n];
        Arrays.fill(ans, -1); // 未訪問を-1とする
        Queue<Integer> que = new ArrayDeque<>();
        que.add(0);
        ans[0] = 0; // [0]は出力しないが、未訪問と区別するため適当な値
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (ans[next] == -1) {
                    que.add(next);
                    ans[next] = cur;
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        pw.println("Yes");
        for (int i = 1; i < n; i++) {
            pw.println(ans[i] + 1);
        }
        pw.flush();
    }
}

ここまで17分23秒＋0ペナ。186位。
一気に浮上できてひとまず安心を得る。


E - ∙ (Bullet)、F - . (Single Dot)

E問題　F問題
ここから先は解けていないので省略。
後で解けて気が向いたら追記するかもしれません。

E問題は、A_i/B_i=-B_j/A_jであるものが仲が悪く、A/Bでソートすれば件数をカウントできそうくらいまでは考えたが、本当に割り算したのでは精度が足りないと思い、整数のまま上手く管理するのも大変そうと思ってひとまずF問題を確認しに行く。

F問題はまず、座標範囲が10^9で、1 \leq N, M \leq 1000という制約が、見るからに座標圧縮っぽいと思った。
座標圧縮後にBFSすればO((N+M)^2)くらいでいけそうなのだが、実装が150行ほどになってしまい、最後までバグが取れず終了。
コンテスト後に明らかにミスっぽいのは直したと思うのだが、それでもACケースが2割→7割くらいで、まだ何か見落としがあるのかどうか・・・。


最終結果：ABCDの4完、17分23秒、547位、パフォーマンス1789
レート変動：1769→1771

4完で冷えなかったのいつ以来だろう。


E - ∙ (Bullet)　※5/19追記

問題
解説見て解いたので追記。思考過程は解説の影響を受けています。

問題概要

N匹のイワシがおり、i匹目のイワシには2つの属性値A_i、B_iがある。
この中から、選んだどの2匹についても以下の条件を満たさないように1匹以上を選んで1つの箱に入れる選び方は何通りあるか。

  • A_i \cdot A_j+B_i \cdot B_j=0 (i \neq j)

1000000007で割った余りを求めよ。

  • 入力は全て整数
  • 1 \leq N \leq 2 \times 10^5
  • -10^{18} \leq A_i, B_i \leq 10^{18}
思考過程
  1. iとjが混在しない形に式変形すると、A_i/B_i=-B_j/A_jとなる。
  2. これをソートでもできれば、条件を満たしてしまう組み合わせを突き合わせやすそう？　でも小数にしてしまうと誤差で死にそう。
  3. 実際に割るのではなく、AとBの値のペアをキーとして突き合わせたい。
  4. AとBをフィールドに持ったクラスに、equalsとhashCodeを実装すれば、HashMapのキーにすることができ、そうすれば1要素当たりO(1)で突き合わせができ、全体でO(N)で集計ができそう（実際には累乗の計算などでlogが付くが）。
  5. (A, B)=(3, -5), (-9, 15)といった2要素はA_i/B_iが同じであり、同一視したいので、下準備として、最大公約数で割った上、A \geq 0となるように符号も調整する。一方が0の場合は他方を1に統一する。
  6. 下準備の結果キー(A, B)が同じになったものごとに件数をカウント。
  7. 各キー(A, B)に対し、同時に選択できないNGキー(B, -A)を生成し、それに該当する件数を取得する。キーの生成にあたっては、Bが負になったり、(0, -1)になったりしないように注意。
  8. 上記のキーk1とNGキーk2の組ごとに、両方を同時に選択しない場合の数を計算し、組の数分掛け合わせる。
  9. 1組内での場合の数は、k1に該当する件数をv1、k2に該当する件数をv2とすると、k1側を自由に選んでk2側を0匹とするケースが2^{v1}、その逆が2^{v2}、両方とも0匹のケースが重複するため1ケース引いて、2^{v1}+2^{v2}-1となる。
  10. 全体で1匹以上選ぶ必要があるため、全ての(k1, k2)の組で0匹の場合の1ケースを引く。
  11. (A, B)=(0, 0)の場合は、その1匹のみしか選ぶことができない（他の全てのイワシがNGキーとなる）ため、その件数のみ別途カウントしておき、最後に足す。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.Map;

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());
        Obj[] arr = new Obj[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            Obj o = new Obj();
            o.a = Long.parseLong(sa[0]);
            o.b = Long.parseLong(sa[1]);
            arr[i] = o;
        }
        br.close();

        // 思考過程5
        for (Obj o : arr) {
            if (o.a != 0 || o.b != 0) {
                long gcd = gcd(o.a, o.b);
                o.a /= gcd;
                o.b /= gcd;
                if (o.a < 0) {
                    o.a *= -1;
                    o.b *= -1;
                }
            }
        }

        // 思考過程6、11
        int zero = 0;
        Map<Obj, Integer> map = new HashMap<>();
        for (Obj o : arr) {
            if (o.a == 0 && o.b == 0) {
                zero++;
            } else {
                if (map.containsKey(o)) {
                    map.put(o, map.get(o) + 1);
                } else {
                    map.put(o, 1);
                }
            }
        }

        int mod = 1000000007;
        long ans = 1;
        Obj[] keys = map.keySet().toArray(new Obj[0]);
        for (Obj k : keys) {
            if (!map.containsKey(k)) {
                continue;
            }
            // 思考過程9 k1側
            int v1 = map.get(k);
            long a = power(2, v1, mod);

            // 思考過程7 NGキー生成
            Obj k2 = new Obj();
            if (k.b > 0) {
                k2.a = k.b;
                k2.b = -k.a;
            } else if (k.b == 0) {
                k2.b = 1;
            } else {
                k2.a = -k.b;
                k2.b = k.a;
            }
            // 思考過程9 k2側
            Integer v2 = map.get(k2);
            if (v2 != null) {
                long a2 = power(2, v2, mod) - 1;
                a += a2;
                map.remove(k2); // 二重カウント防止
            }

            // 思考過程8
            ans *= a;
            ans %= mod;
        }
        ans--; // 思考過程10
        ans += zero + mod; // 思考過程11
        ans %= mod;
        System.out.println(ans);
    }

    static class Obj {
        long a, b;

        @Override
        public boolean equals(Object o) {
            Obj o2 = (Obj) o;
            if (a == o2.a && b == o2.b) {
                return true;
            }
            return false;
        }

        @Override
        public int hashCode() {
            // 適当な計算をしておけばとりあえず動きはする
            return (int) (31 * a + b);
        }
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }

    static long gcd(long a, long b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

　

F - . (Single Dot)　※5/19追記

問題
コンテスト本番中、時間切れ寸前に投げたコードから、ほんの数箇所直したらAC。（下記ソースにコメント）
あとほんの少しの実装力があればパフォ2400・・・。

問題概要

縦にX軸、横にY軸を取る無限に広がる二次元平面がある。
N本の縦線とM本の横線が引かれており、i本目の縦線は点(A_i, C_i)と点(B_i, C_i)を結ぶ線分、j本目の横線は点(D_j, E_j)と点(D_j, F_j)を結ぶ線分である。
点(0, 0)からスタートし、線分（端点含む）を通らないで動ける範囲の面積を求めよ。
無限大の場合は 'INF' と出力せよ。

  • 入力は全て整数
  • 1 \leq N, M \leq 1000
  • -10^9 \leq A_i, B_i, C_i, D_j, E_j, F_j \leq 10^9
  • A_i \lt B_i
  • E_j \lt F_j
  • 点(0, 0)はどの線分上にも位置しない
思考過程
  1. 要素の値はあからさまに大きいが要素数は少ない場合、値が計算量に影響しない（か影響したとしても対数オーダーの）解法を考える。　とりあえずA～Fの値に注目して座標圧縮する。
  2. 座標圧縮後、線分がある範囲の座標は高々3000^2程度のため、全体を二次元配列で表せる。
  3. 点(0, 0)はマスではなく交点のため、適当に周囲4マスのどこかからスタートする。　4方向に移動していく（線分の部分は移動不可の）BFSで到達可能マスが漏れなくわかりそう。
  4. 座標圧縮部分やBFSの遷移部分で似たような実装を量産してしまい、ソースがどんどん長くなる・・・。
  5. 到達可能マスの辺の長さを座標圧縮前に戻して面積を計算する。
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.Queue;
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]);
        int[] a = new int[n];
        int[] b = new int[n];
        int[] c = new int[n];
        for (int i = 0; i < n; i++) {
            sa = br.readLine().split(" ");
            a[i] = Integer.parseInt(sa[0]);
            b[i] = Integer.parseInt(sa[1]);
            c[i] = Integer.parseInt(sa[2]);
        }
        int[] d = new int[m];
        int[] e = new int[m];
        int[] f = new int[m];
        for (int i = 0; i < m; i++) {
            sa = br.readLine().split(" ");
            d[i] = Integer.parseInt(sa[0]);
            e[i] = Integer.parseInt(sa[1]);
            f[i] = Integer.parseInt(sa[2]);
        }
        br.close();

        // キー：圧縮前のX座標、値：圧縮後のX座標
        TreeMap<Integer, Integer> mapx = new TreeMap<>();
        mapx.put(0, null);
        for (int i = 0; i < n; i++) {
            mapx.put(a[i], null);
            mapx.put(b[i], null);
        }
        for (int i = 0; i < m; i++) {
            mapx.put(d[i], null);
        }
        Integer[] arr = mapx.keySet().toArray(new Integer[0]);
        int cnt = 0;
        for (Integer i : arr) {
            mapx.put(i, cnt);
            cnt++;
        }
        // index：圧縮後のX座標、値：圧縮前のX座標
        int[] tox = new int[mapx.size()];
        for (Integer key : mapx.keySet()) {
            tox[mapx.get(key)] = key;
        }

        // キー：圧縮前のY座標、値：圧縮後のY座標
        TreeMap<Integer, Integer> mapy = new TreeMap<>();
        mapy.put(0, null);
        for (int i = 0; i < n; i++) {
            mapy.put(c[i], null);
        }
        for (int i = 0; i < m; i++) {
            mapy.put(e[i], null);
            mapy.put(f[i], null);
        }
        arr = mapy.keySet().toArray(new Integer[0]);
        cnt = 0;
        for (Integer i : arr) {
            mapy.put(i, cnt);
            cnt++;
        }
        // index：圧縮後のY座標、値：圧縮前のY座標
        int[] toy = new int[mapy.size()];
        for (Integer key : mapy.keySet()) {
            toy[mapy.get(key)] = key;
        }


        // Y軸（横）方向に移動できない部分
        // ngy[x][y] == trueの場合、(x, y-1)と(x, y)の間は移動不可
        boolean[][] ngy = new boolean[tox.length + 1][toy.length + 1];
        for (int i = 0; i < n; i++) {
            int x1 = mapx.get(a[i]);
            int x2 = mapx.get(b[i]);
            int y = mapy.get(c[i]);
            for (int j = x1 + 1; j <= x2; j++) {
                ngy[j][y] = true;
            }
        }

        // X軸（縦）方向に移動できない部分
        // ngx[x][y] == trueの場合、(x-1, y)と(x, y)の間は移動不可
        boolean[][] ngx = new boolean[tox.length + 1][toy.length + 1];
        for (int i = 0; i < m; i++) {
            int x = mapx.get(d[i]);
            int y1 = mapy.get(e[i]);
            int y2 = mapy.get(f[i]);
            for (int j = y1 + 1; j <= y2; j++) {
                ngx[x][j] = true;
            }
        }


        // 到達可能マス記録用
        boolean[][] visit = new boolean[tox.length + 1][toy.length + 1];
        int fx = mapx.get(0);
        int fy = mapy.get(0); // バグ：mapxになっていた
        // 最初から端の場合
        if (fx == 0 || fx == tox.length - 1 || fy == 0 || fy == toy.length - 1) {
            System.out.println("INF");
            return;
        }

        Queue<Integer> que = new ArrayDeque<>();
        que.add(fx * 10000 + fy);
        visit[fx][fy] = true;
        while (!que.isEmpty()) {
            int cur = que.poll();
            int cx = cur / 10000;
            int cy = cur % 10000;
            // 上
            int nx = cx - 1;
            int ny = cy;
            if (!ngx[nx][ny] && !visit[nx][ny]) { // 通れるかつ未訪問
                if (nx == 0) { // 端に達した場合
                    System.out.println("INF");
                    return;
                }
                que.add(nx * 10000 + ny);
                visit[nx][ny] = true;
            }
            // 下
            nx = cx + 1;
            ny = cy;
            if (!ngx[cx][ny] && !visit[nx][ny]) {
                if (nx == tox.length) {
                    System.out.println("INF");
                    return;
                }
                que.add(nx * 10000 + ny);
                visit[nx][ny] = true;
            }
            // 左
            nx = cx;
            ny = cy - 1;
            if (!ngy[nx][ny] && !visit[nx][ny]) {
                if (ny == 0) {
                    System.out.println("INF");
                    return;
                }
                que.add(nx * 10000 + ny);
                visit[nx][ny] = true;
            }
            // 右
            nx = cx;
            ny = cy + 1;
            if (!ngy[nx][cy] && !visit[nx][ny]) {
                if (ny == toy.length) {
                    System.out.println("INF");
                    return;
                }
                que.add(nx * 10000 + ny);
                visit[nx][ny] = true;
            }
        }

        long ans = 0;
        for (int i = 1; i < tox.length; i++) { // バグ：tox.length - 1になっていた
            for (int j = 1; j < toy.length; j++) { // バグ：toy.length - 1になっていた
                if (visit[i][j]) {
                    long dx = tox[i] - tox[i - 1]; // バグ：tox[i + 1] - tox[i]になっていた
                    long dy = toy[j] - toy[j - 1]; // バグ：toy[i + 1] - toy[i]になっていた
                    ans += dx * dy;
                }
            }
        }
        System.out.println(ans);
    }
}

二次元配列の中身は適宜デバッグ出力して確認した方が、急がば回れで結局早く解決できたかもしれない。
コピペ後の直し漏れは本当によくない。焦って重複に近いコードを量産した天罰か・・・。