AtCoder Beginner Contest 187

コンテスト前のレート：1858
レート通りのパフォーマンスが得られる順位：449位（1500点、30分39秒）

A - Large Digits

問題
一旦数値で受け取るよう実装した後に文字列で受け取るように変えたりなどしていて微妙に時間ロス。

思考過程

1. 題意の通り実装するだけだが、各桁の値をどうやって取得するか。
2. で割った余りを取ってで割るのを繰り返すのも一瞬考えたが、文字ずつ'0'を引いて数値化することにした。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        char[] a = sc.next().toCharArray();
        char[] b = sc.next().toCharArray();
        sc.close();

        int aa = 0;
        for (int i = 0; i < a.length; i++) {
            aa += a[i] - '0';
        }
        int bb = 0;
        for (int i = 0; i < b.length; i++) {
            bb += b[i] - '0';
        }
        System.out.println(Math.max(aa, bb));
    }
}

ここまで1分31秒＋0ペナ。628位。

B - Gentle Pairs

問題
例３が合わなくて数分考えてやっと思考過程2にたどり着く。

思考過程

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

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int dx = x[j] - x[i];
                int dy = y[j] - y[i];
                if (dx > 0 && -dx <= dy && dy <= dx) {
                    ans++;
                }
                if (dx < 0 && -dx >= dy && dy >= dx) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで6分50秒＋0ペナ。1291位。

C - 1-SAT

問題

思考過程

1. '!'が付いていない文字列と、付いている文字列（の'!'抜き）を別々のSetに格納し、両方のSetに含まれている文字列を探す。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashSet;
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());
        String[] s = new String[n];
        for (int i = 0; i < n; i++) {
            s[i] = br.readLine();
        }
        br.close();

        Set<String> set = new HashSet<>();
        Set<String> set1 = new HashSet<>();
        for (int i = 0; i < n; i++) {
            if (s[i].startsWith("!")) {
                set1.add(s[i].substring(1));
            } else {
                set.add(s[i]);
            }
        }
        for (String str : set) {
            if (set1.contains(str)) {
                System.out.println(str);
                return;
            }
        }
        System.out.println("satisfiable");
    }
}

ここまで10分32秒＋0ペナ。512位。

D - Choose Me

問題
貪欲を考え始めたときに、過去問の解説で見たことがある考え方を思い出せた。

思考過程

1. 「：番目まで見て、票得るために演説を行う必要がある町の数」でできないかとか考えるが、制約が大きいのでとても無理。
2. DP的なことでは制約が大きくてどうにもならなそうなので、貪欲を考えてみる。
   　
3. まず一旦高橋氏が全く演説を行わないとする。
4. 高橋氏がある町で演説を行った場合、青木氏の票が減り、高橋氏の票が増える。
5. よって、ある町で演説を行った場合、票数の差はずつ縮んでいくので、でソートし、の合計が全の合計を上回るまでに必要な件数を求める。
6. はint型の範囲を超える可能性があるのでオーバーフローに注意。（これで1回WA出した）

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

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

        long ao = 0;
        long[] c = new long[n];
        for (int i = 0; i < n; i++) {
            c[i] = a[i] * 2L + b[i]; // Lがないとオーバーフロー
            ao += a[i];
        }
        Arrays.sort(c);
        reverse(c);

        long ta = 0;
        for (int i = 0; i < n; i++) {
            ta += c[i];
            if (ta > ao) {
                System.out.println(i + 1);
                return;
            }
        }
    }

    // 以下ライブラリ

    static void reverse(long[] a) {
        for (int i = 0; i < a.length / 2; i++) {
            long tmp = a[i];
            a[i] = a[a.length - 1 - i];
            a[a.length - 1 - i] = tmp;
        }
    }
}

ここまで21分12秒＋1ペナ。623位。

E - Through Path

問題
みんな解くの早すぎ。

思考過程

1. 単純にクエリごとにDFS/BFSするのは当然TLE。
2. 上手く合計値を管理しながらDFSというか木DPをすればできないか？と思うが、枝分かれした時に、番目以降の枝で取得してきた値を番目以前の枝部分に足せない問題がある。
3. 他の枝に反映したい値を取るためのDFSと、各ノードに反映していくためのDFSの回に分けることを考えていく。
   　
4. まず一度DFSを行い、根に足すことになるの合計を求める。
5. 上記4の値を持った状態から始め、今度は辺を通る度、以下のように現在値を管理しながらDFSを行う。
   • 行きがけ時は「根側に足す」を引き、「葉側に足す」を足す
   • 帰りがけ時は上記を元に戻す

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

public class Main {
    static int n;
    static List<List<Hen>> list;
    static long[] ans;
    static long now;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        list = new ArrayList<>(n);
        for (int i = 0; i < n; i++) {
            list.add(new ArrayList<>());
        }
        Hen[] arr = new Hen[n - 1];
        for (int i = 0; i < n - 1; i++) {
            String[] sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            Hen h = new Hen();
            h.a = a;
            h.b = b;
            list.get(a).add(h);
            list.get(b).add(h);
            arr[i] = h;
        }

        int q = Integer.parseInt(br.readLine());
        for (int i = 0; i < q; i++) {
            String[] sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int e = Integer.parseInt(sa[1]) - 1;
            int x = Integer.parseInt(sa[2]);
            if (t == 1) {
                arr[e].xa += x;
            } else {
                arr[e].xb += x;
            }
        }
        br.close();

        ans = new long[n];
        now = dfs(0, -1);
        dfs2(0, -1);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(ans[i]);
        }
        pw.flush();
    }

    static class Hen {
        int a, b;
        long xa, xb;
    }

    static long dfs(int x, int p) {
        long ret = 0;
        for (Hen h : list.get(x)) {
            int next = h.b;
            long val = h.xa;
            if (next == x) {
                next = h.a;
                val = h.xb;
            }
            if (next == p) {
                continue;
            }
            long res = dfs(next, x);
            val += res;
            ret += val;
        }
        return ret;
    }

    static void dfs2(int x, int p) {
        ans[x] = now;
        for (Hen h : list.get(x)) {
            int next = h.b;
            long val1 = h.xa;
            long val2 = h.xb;
            if (next == x) {
                next = h.a;
                val1 = h.xb;
                val2 = h.xa;
            }
            if (next == p) {
                continue;
            }
            now -= val1;
            now += val2;
            dfs2(next, x);
            now -= val2;
            now += val1;
        }
    }
}

ここまで63分56秒＋1ペナ。738位。

F - Close Group

問題
解けず。
最終的に外れ方針で頑張ってしまい、それを捨てて最初からやり直せたとしてもあと20分は必要だったか・・。
（以下はほぼその外れ方針）

思考過程

1. もらうDPを考えると、集合への遷移には、とを合わせた場合、とを合わせた場合、のように、通り程度の遷移を見ていく必要がありそうで、これではで駄目そう。
   　
2. 配るDPを考えると、集合を表す数値にどこかビットを足した値への遷移では、が完全グラフでなければ正しく遷移できない。
   が完全グラフつの集まりだったとすると、新しい頂点が、つの部分グラフいずれかに吸収して完全グラフになり得るか、いずれでも吸収できないかがわからない。
   　
3. 上記2を正しく遷移できるようにすることを考える。
4. 通りの集合全てについて、完全グラフかどうかを調べ、完全グラフである各集合を頂点とみなし、完全グラフと完全グラフから、それらを統合したに距離で遷移できるとする。
5. このようにすると、いずれかの完全グラフから全体への最短距離を求める、多点スタートのBFSとみなすことができる。
6. なお、これでは完全グラフである部分集合の数をとすると、であり、はなので、結局計算量は落ちていない。
   　
7. そして解説を見たら、上記1に戻って、はであり、これは無駄な遷移を調べなければになるというだけのことだった。

最終結果：ABCDEの5完、68分56秒、818位、パフォーマンス1569
レート変動：1858→1832（-26）

今回は十分に早かったのがC問題だけ。でもSetが想定解だと、元々若干有利なだけな気がする。

E問題はもうこの際解けただけでもマシだったかも。
実装にもそこそこ時間をかけてしまっているので、方針はすぐに立つくらいじゃないと勝負になってなさそう。

F問題は計算量改善していないけどなんか凝った方法が思いつけたから、考察力という面では収穫があったかなと思う。
をにできるのは知識としてはあるが、それを使って自力ACできた経験がまだないので、元々解けるかどうか微妙なところであった。
とりあえず後でちゃんとACしておくことにする。