AtCoder Beginner Contest 226(Rated範囲外)

A - Round decimals
- 思考過程
B - Counting Arrays
- 思考過程
C - Martial artist
- 思考過程
D - Teleportation
- 思考過程
E - Just one
- 思考過程
G - The baggage
- 思考過程

コンテスト前のレート：2018
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：305位（1600点、110分48秒）

A - Round decimals

思考過程

整数部と小数部を分けたり、小数第一位を取得したりするのが面倒な気がして、BigDecimalの力を借りることにする。
精度と丸めモードを指定することで好きな桁での四捨五入ができる。

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

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

        x = x.setScale(0, RoundingMode.HALF_UP);
        System.out.println(x.toPlainString());
    }
}

ここまで1分28秒＋0ペナ。516位。

B - Counting Arrays

問題
B問題としてはかなり難しい方だと思う。

思考過程

$N$ 個の配列同士を自力で比較してソートするなり、配列をSetに入れられるようにequalsとhashcodeを実装したラッパークラスを用意するなりしないと・・・？
後者に近い方法で、配列の各要素をハイフン区切りで連結して文字列化すればSetが使える。
$100$ 万文字くらいの後ろの方しか異ならない文字列を $10$ 万個入れてTLEになったりしないかと不安だったが、通ったのでヨシ。

なお、そもそも入力を行ごと文字列として読み込んでも、ハイフン区切りがスペース区切りになるだけなので同じだった。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.TreeSet;

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());
        TreeSet<String> set = new TreeSet<>();
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            int l = Integer.parseInt(sa[0]);
            StringBuilder sb = new StringBuilder();
            for (int j = 1; j <= l; j++) {
                int a = Integer.parseInt(sa[j]);
                sb.append(a).append('-');
            }
            set.add(sb.toString());
        }
        br.close();

        System.out.println(set.size());
    }
}

ここまで4分30秒＋0ペナ。415位。

C - Martial artist

問題
これもいつものC問題より難しい。まあC問題はぎりぎり茶diffくらいはあってほしいけど。
ついでにこれあの問題とほぼ同じ（完全に同じ？）構造をしているけど、今回出てきて問題なかったのかな。

思考過程

$N$ の習得に必要なもの、さらにその習得に必要なもの、 $\cdots$ とBFSで辿っていくと、必要な技の集合が求められる。
それらの技を習得する以外に時間ロスをするようなことはないので、それらの $T$ の合計を求めればよい。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Queue;
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[] t = new int[n];
        int[] k = new int[n];
        List<List<Integer>> list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            t[i] = Integer.parseInt(sa[0]);
            k[i] = Integer.parseInt(sa[1]);
            List<Integer> list2 = new ArrayList<>(k[i]);
            for (int j = 0; j < k[i]; j++) {
                int a = Integer.parseInt(sa[j + 2]) - 1;
                list2.add(a);
            }
            list.add(list2);
        }
        br.close();

        Set<Integer> set = new HashSet<>();
        Queue<Integer> que = new ArrayDeque<>();
        que.add(n - 1);
        set.add(n - 1);
        while (!que.isEmpty()) {
            int cur = que.poll();
            for (int next : list.get(cur)) {
                if (!set.contains(next)) {
                    que.add(next);
                    set.add(next);
                }
            }
        }
        long ans = 0;
        for (int i : set) {
            ans += t[i];
        }
        System.out.println(ans);
    }
}

ここまで10分21秒＋0ペナ。151位。

D - Teleportation

問題

思考過程

$3$ 点が同一直線上にあるような組み合わせが存在する場合に限り、 $N(N-1)$ 通りよりも減る感じ。
$2$ 点を通る直線の傾きの数が答えになる。
傾きが同じ直線を同一視するためには、 $x$ 座標の差と $y$ 座標の差のGCDを取ったペアをSetに入れていく形にしたい。
　
負の数の%が意図しない動きをすることを警戒し、絶対値のGCDを求めるようにしたり、ペアのSetを実現するのにMapを使ったり頑張る。

以下のコードは終了後に多少簡単にしたものだが、本番時はさらに $x$ 座標の差が $0$ かどうかで場合分けまでしていたり、かなり冗長なことをしていた。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
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[] x = new int[n];
        int[] y = new int[n];
        for (int i = 0; i < n; i++) {
            String[] sa = br.readLine().split(" ");
            x[i] = Integer.parseInt(sa[0]);
            y[i] = Integer.parseInt(sa[1]);
        }
        br.close();

        Map<Integer, Set<Integer>> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i != j) {
                    int a = x[j] - x[i];
                    int b = y[j] - y[i];
                    int g = gcd(Math.abs(a), Math.abs(b));
                    a /= g;
                    b /= g;
                    Set<Integer> set = map.get(a);
                    if (set == null) {
                        set = new HashSet<>();
                        map.put(a, set);
                    }
                    set.add(b);
                }
            }
        }
        int ans = 0;
        for (Set<Integer> set : map.values()) {
            ans += set.size();
        }
        System.out.println(ans);
    }

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

ここまで20分39秒＋0ペナ。277位。

E - Just one

問題

思考過程

連結成分ごとの通り数を掛け算する。以下 $1$ つの連結成分について考える。
　
次数が $1$ の頂点は、その辺の始点になるしかない。
次数が $2$ 以上の頂点はどうすればいいのかぱっとはわからないが、そもそも構築可能であるためには、頂点数＝辺数でなければならない。
つまり、木よりも辺が $1$ 本だけ多く、サイクルが $1$ つだけ存在する形になる。
サイクル部分については、サンプルを見ると時計回りと反時計回りの $2$ 通り。
結局、サイクル部分が $2$ 通りで他の辺は選択の余地はないので、各連結成分は $0$ 通りか $2$ 通り。
　
頂点数＝辺数かどうかは、UnionFindで既に同一連結成分である頂点同士を連結しようとした回数をメモしておき、同一連結成分内の頂点についての回数の合計が $1$ であるかどうかで調べられる。

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

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

        DSU uf = new DSU(n);
        int[] cnt = new int[n];
        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;
            if (uf.same(u, v)) {
                cnt[u]++;
            }
            uf.merge(u, v);
        }
        br.close();

        int mod = 998244353;
        long ans = 1;
        List<List<Integer>> gs = uf.groups();
        for (List<Integer> g : gs) {
            int sum = 0;
            for (int e : g) {
                sum += cnt[e];
            }
            if (sum != 1) {
                System.out.println(0);
                return;
            }
            ans *= 2;
            ans %= mod;
        }
        System.out.println(ans);
    }
}

// 以下ACLを移植したDSU

提出
ここまで34分21秒＋0ペナ。152位。

Fはぱっと見どうすればいいのかさっぱりだったのでとりあえずGも見る。
Gがとても簡単そうな見た目をしていたので先にそっちをやってから戻ってくる。
その後40分ほどあったが、誤読していて例３が合わず終了。
自分の体感より正解者数多くて辛い。

G - The baggage

問題
ARC126-Aみたいな貪欲では？と思って損しなそうな手順を考えてやってみたら通った。
Fと比べて正解者数少なすぎなのは問題の並び順のせいなのか、雑な貪欲をしてハマった人が多いのか。
touristの所要時間が他の7問合計＜この1問っぽいし、自分も通せはしたけど自信があったわけではなかったし、難しいは難しいんだろうけど。

思考過程

とりあえず、重さ＝体力である組み合わせについては、割り当ててよさそう。
例えば $A_3$ を減らすのに $B_3$ ではなく $B_4$ を使うと、 $2+2$ の組み合わせに使える可能性が減ってしまうなどしそう。
　
重い方が選択の余地が少ないので、 $A_5$ から順に処理していく。
上記1.の割り当てを行った後、 $A_5$ が残っていたらアウト。
$B_5$ が余っていて $A_4$ が残っていたら、まず $A_4$ の残りには $B_5$ を割り当てるしかない。割り当てた $B_5$ は $B_1$ に追加する。
$A_3$ が残っている場合、 $A_4$ や $A_5$ が余っていたらどちらを使っても $A_2$ や $A_1$ を割り当てる選択肢の幅が狭まることはない。
　
以上のようなことを整理したら、ベタで $1$ つ $1$ つ書かなくても、繰り返し処理で書けそう。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        PrintWriter pw = new PrintWriter(System.out);
        label:
        for (int z = 0; z < t; z++) {
            String[] sa = br.readLine().split(" ");
            long[] a = new long[6];
            for (int i = 0; i < 5; i++) {
                a[i + 1] = Long.parseLong(sa[i]);
            }
            sa = br.readLine().split(" ");
            long[] b = new long[6];
            for (int i = 0; i < 5; i++) {
                b[i + 1] = Long.parseLong(sa[i]);
            }

            // 重さ＝体力の割り当て
            for (int i = 1; i <= 5; i++) {
                long min = Math.min(a[i], b[i]);
                a[i] -= min;
                b[i] -= min;
            }

            int y = 5;
            for (int x = 5; x > 0; x--) {
                while (y > 0 && b[y] == 0) {
                    y--;
                }
                // 体力が大きいものからa[x]に割り当て
                while (a[x] > 0 && y >= x) {
                    long min = Math.min(a[x], b[y]);
                    a[x] -= min;
                    b[y] -= min;
                    b[y - x] += min;
                    if (b[y] == 0) {
                        y--;
                    }
                }
                // 体力x以上を使い切っても重さxが残っていたらアウト
                if (a[x] > 0) {
                    pw.println("No");
                    continue label;
                }
            }
            pw.println("Yes");
        }
        pw.flush();
        br.close();
    }
}

ここまで59分33秒＋0ペナ。18位。

最終結果：ABCDEGの6完2100点、59分33秒、94位、パフォーマンス2400相当
レート変動：2018（Unrated）

G問題が当たったおかげで黄色になった時以来の2400範囲内。
Eまではそれなりにスムーズに解けることが多いけどFが解けている率が低いのをなんとかしていきたい。