AtCoder Beginner Contest 198(Rated範囲外)

コンテスト前のレート：2011
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：276位（1500点、57分24秒）

今回もひどかったのでもうあまりまともには書きません。

A - Div

問題

思考過程

1. ～の通り。

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

        System.out.println(n - 1);
    }
}

ここまで0分23秒＋0ペナ。40位。

B - Palindrome with leading zeros

問題

思考過程

1. 末尾が'0'でなくなるまで'0'を取り除く。
2. その結果が回文になっていれば"Yes"。

import java.util.Scanner;

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

        StringBuilder sb = new StringBuilder(s);
        while (sb.length() > 0) {
            if (sb.charAt(sb.length() - 1) == '0') {
                sb.deleteCharAt(sb.length() - 1);
            } else {
                break;
            }
        }

        boolean flg = true;
        for (int i = 0; i < sb.length(); i++) {
            if (sb.charAt(i) != sb.charAt(sb.length() - 1 - i)) {
                flg = false;
                break;
            }
        }
        if (flg) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
}

ここまで3分16秒＋0ペナ。280位。

C - Compass Walking

問題

思考過程

1. 行き過ぎの場合は適当に角度を付けて調節可能なので、を満たす最小のを求めたい。
2. を移行して平方根を取って、誤差が心配なので念のため付近を探索し直すなどする。　→3ケースWA
3. 平方根を正確に計算したり、答えは高々程度なのでから全部調べたりなど絶対に誤差が出なそうな方法に変えてみたりするが、変わらず。
4. となる場合、ぴったりならよいが、それより短い場合は回の移動が必要。

import java.util.Scanner;

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

        long g = x * x + y * y;
        long r2 = r * r;
        for (long i = 0; ; i++) {
            long v = i * i * r2;
            if (v == g) {
                System.out.println(i);
                return;
            } else if (v > g) {
                if (i == 1) {
                    System.out.println(2);
                } else {
                    System.out.println(i);
                }
                return;
            }
        }
    }
}

ここまで22分22秒＋5ペナ。1175位。

D - Send More Money

問題
順位表の様子を見たり、そもそも題意を理解するのに5分くらいかかったりしたので、先にEを解く。
その後戻ってきた後も解けず。せめて0抜きにしてくれればできたと思うのだが・・・。
残り時間はまだ少しあったが、Unratedだからと面倒になって放棄した。

思考過程

1. 登場する文字が種類以上の場合は不可。
2. 文字の割り当てを全探索するか、下の桁からDFSしていくかを思い付く。
3. 前者の方法を実装してみるも、手元で例５が15秒くらいかかる。
4. 後者の方法は実装が面倒になって途中で断念。

E - Unique Color

問題

思考過程

1. 現在通った色のSetを持ちながらDFSしたいが、それだと頂点の処理を終えて親に戻る時にをSetから抜いていいかどうかわからない気がする。（後から考えれば、元々入っていたかを調べておけばいいだけ）
2. SetではなくMap＜色、その色の頂点数＞で管理することにする。　→になった時にエントリを消し忘れて1回WA

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class Main {
    static int n;
    static int[] c;
    static List<List<Integer>> list;
    static List<Integer> ans;

    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(" ");
        c = new int[n];
        for (int i = 0; i < n; i++) {
            c[i] = 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 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();

        ans = new ArrayList<>();
        Map<Integer, Integer> map = new HashMap<>();
        dfs(0, -1, map);

        Collections.sort(ans);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i : ans) {
            pw.println(i + 1);
        }
        pw.flush();
    }

    static void dfs(int x, int p, Map<Integer, Integer> map) {
        if (!map.containsKey(c[x])) {
            ans.add(x);
        }
        for (int next : list.get(x)) {
            if (next != p) {
                map.put(c[x], map.getOrDefault(c[x], 0) + 1);
                dfs(next, x, map);
                map.put(c[x], map.get(c[x]) - 1);
                if (map.get(c[x]) == 0) {
                    map.remove(c[x]);
                }
            }
        }
    }
}

ABCEと解いた時点で31分42秒＋6ペナ。251位。

F問題は全然わからず。
とりあえず回転で何パターン増えるのかを洗い出そうとしてみるが、途中で断念。
一応断念しなければ、公式解説の解法2と方向性は同じだったらしいが、桁DP/行列累乗パートまでは全く考えられてなかった。

最終結果：ABCEの4完、61分42秒、1174位、パフォーマンス1364相当
レート変動：2011（Unrated）

今回はC問題で完全にハマり、E問題でケアレスミスし、D問題では実装が下手くそだった。
D問題はStreak材として、明日すんなり実装できることを目指す。