AtCoder Beginner Contest 220(Rated範囲外)

コンテスト前のレート：2005
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：323位（2000点、72分53秒）

A - Find Multiple

問題

思考過程

1. 制約が緩いので、計算することを考えるより、思考停止で全探索する。
2. を全部調べていって、以上以下となるものがあればそれを出力する。
3. を超えても見つからなければ。

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 c = sc.nextInt();
        sc.close();

        for (int i = c; i <= b; i += c) {
            if (a <= i) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(-1);
    }
}

ここまで1分00秒＋0ペナ。254位。

B - Base K

問題

思考過程

1. をそれぞれ頑張って進法表記から進法表記に直す。（右から桁目についてを求める）
2. を出力する。

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();
        char[] a = sc.next().toCharArray();
        char[] b = sc.next().toCharArray();
        sc.close();

        long aa = 0;
        long k2 = 1;
        for (int i = a.length - 1; i >= 0; i--) {
            aa += (a[i] - '0') * k2;
            k2 *= k;
        }

        long bb = 0;
        k2 = 1;
        for (int i = b.length - 1; i >= 0; i--) {
            bb += (b[i] - '0') * k2;
            k2 *= k;
        }

        System.out.println(aa * bb);
    }
}

ここまで5分35秒＋0ペナ。1141位。

なお、そもそもJavaでは以下のように第2引数に基数を指定して文字列を数値に変換することができる。
滅多に使わないので完全に忘れていた。

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();
        long a = Long.parseLong(sc.next(), k);
        long b = Long.parseLong(sc.next(), k);
        sc.close();

        System.out.println(a * b);
    }
}

C - Long Sequence

問題

思考過程

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

        long sum = 0;
        for (int i = 0; i < n; i++) {
            sum += a[i];
        }

        long ans = x / sum * n;
        x %= sum;
        for (int i = 0; i < n; i++) {
            x -= a[i];
            ans++;
            if (x < 0) {
                break;
            }
        }
        System.out.println(ans);
    }
}

ここまで8分35秒＋0ペナ。400位。

D - FG operation

問題

思考過程

1. 「番目まで操作後、一番左がである通り数」を定義し、（0-indexedで）初め一番左はなので、で初期化する。
2. 問題文の操作の通りの遷移を行う。
3. DP配列を何故かint型にしてしまっていたため、オーバーフローで1ペナ。longに直してAC。

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

        int mod = 998244353;
        long[][] dp = new long[n][10];
        dp[0][a[0]] = 1;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < 10; j++) {
                int nx1 = (j + a[i]) % 10;
                dp[i][nx1] += dp[i - 1][j];
                int nx2 = (j * a[i]) % 10;
                dp[i][nx2] += dp[i - 1][j];
            }
            for (int j = 0; j < 10; j++) {
                dp[i][j] %= mod;
            }
        }
        for (int i = 0; i < 10; i++) {
            System.out.println(dp[n - 1][i]);
        }
    }
}

ここまで14分43秒＋1ペナ。335位。

E - Distance on Large Perfect Binary Tree

問題

思考過程

1. くらいの範囲で実験する。
2. 実験結果としては、頂点を深さの点としたとき、頂点の候補としては、深さの種類の深さの点がそれぞれ個ある。（最初にが個多くて、がない以外は～が並んでいる）
   　
3. の場合は上記2.の個数列の後ろの方を使えなくなるので、上記2.の深さ列が未満に収まっているところまでの個数列を採用するように帳尻を合わせる。
4. の時はのみ、の時はのみといったように、の時は上記2.の個数列の後ろから番目までのみを採用できる。
   　
5. 各について、上記3. 4.を満たす範囲の個数列の和を求め、深さの点の個数（）倍したものを答えに足していく。
6. 範囲の和を高速に求められるように、累積和を取っておく。
   　
7. 例２が合わなかったが、何ケースくらい通るか試すために一度提出し、半分くらい通る。
8. 上記3. 4.の大小関係を調べていなかったのを直してAC。

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 d = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long[] p = new long[d + 1];
        p[0] = 1;
        for (int i = 1; i < p.length; i++) {
            p[i] = p[i - 1] * 2 % mod;
        }
        p[d - 1] = p[d]; // 2^(d-1)を捨てる

        // 6
        long[] q = new long[p.length];
        for (int i = 1; i < q.length; i++) {
            q[i] = q[i - 1] + p[i - 1];
            q[i] %= mod;
        }

        long ans = 0;
        long b = 1;
        for (int i = 0; i < n; i++) {
            // 3
            int r = i + d;
            int r2 = (Math.max(r - n + 1, 0) + 1) / 2;
            int r3 = d - r2;
            // 4
            int l = Math.max(d - i - 1, -1);
            if (l < r3) { // 8
                long v1 = q[r3];
                if (l == -1) {
                    v1++; // 最初の1個多い1の分
                } else {
                    v1 -= q[l];
                    v1 %= mod;
                    if (v1 < 0) {
                        v1 += mod;
                    }
                }
                // 5
                long val = v1 * b % mod;
                ans += val;
            }
            b = b * 2 % mod;
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで71分34秒＋2ペナ。1041位。

F - Distance Sums 2

問題
下記思考過程3.にたどり着いたのが終了数秒前で、提出できたのが22:40ちょうどで1秒遅れ。（間に合っていても結局WAだったが）
終了数分後に再提出してAC。

思考過程

1. とりあえず全方位木DPを貼る。
2. 各ラムダ式内をガチャガチャやる。頂点数sizeの方はさすがに大丈夫なはずなので、答えvalの方をそれらしくいじる。
3. サンプルの実行結果がだけ多くなったような感じになったのでを引いてみる。
4. 1ケースだけWAになったので、オーバーフローを疑ってとりあえずlongにしてみてAC。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;
import java.util.function.BiFunction;

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

        // 2
        Rerooting3<Obj> r = new Rerooting3<>(n, edges, new Obj(), 
                (o, i) -> {
                    return o;
                },
                (o1, o2) -> {
                    Obj ret = new Obj();
                    ret.size = o1.size + o2.size;
                    ret.val = o1.val + o2.val;
                    return ret;
                },
                (o, i) -> {
                    Obj ret = new Obj();
                    ret.size = o.size + 1;
                    ret.val = o.val;
                    ret.val += ret.size;
                    return ret;
                });

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            pw.println(r.query(i).val - n); // 3
        }
        pw.flush();
    }

    static class Obj {
        long val, size; // 4
    }

    // 以下ライブラリ

    static class Rerooting3<T> {
        public int nodeCnt;
        private T identity;
        private BiFunction<T, Integer, T> beforeMerge;
        private BiFunction<T, T, T> merge;
        private BiFunction<T, Integer, T> afterMerge;
        private List<List<Integer>> adjacents;
        private List<List<Integer>> indexForAdjacent;
        private Object[][] dp;
        private Object[] res;

        /**
         * 初期化
         * @param nodeCnt 頂点数（≧1）
         * @param edges 木構造の辺の配列  例：{{0,1},{0,2},{1,3}}
         * @param identity 単位元
         * @param beforeMerge 指定頂点（部分木の子）を計算する関数（何もしない場合以外戻り値は新規オブジェクト）
         * @param merge 部分木のマージ関数（戻り値は新規オブジェクト）
         * @param afterMerge 指定頂点（部分木の根）の分を計算する関数（何もしない場合以外戻り値は新規オブジェクト）
         */
        public Rerooting3(int nodeCnt, int[][] edges, T identity, BiFunction<T, Integer, T> beforeMerge,
                BiFunction<T, T, T> merge, BiFunction<T, Integer, T> afterMerge) {
            this.nodeCnt = nodeCnt;
            this.identity = identity;
            this.beforeMerge = beforeMerge;
            this.merge = merge;
            this.afterMerge = afterMerge;

            adjacents = new ArrayList<>(nodeCnt);
            indexForAdjacent = new ArrayList<>(nodeCnt);
            for (int i = 0; i < nodeCnt; i++) {
                adjacents.add(new ArrayList<>());
                indexForAdjacent.add(new ArrayList<>());
            }
            for (int i = 0; i < edges.length; i++) {
                int[] edge = edges[i];
                indexForAdjacent.get(edge[0]).add(adjacents.get(edge[1]).size());
                indexForAdjacent.get(edge[1]).add(adjacents.get(edge[0]).size());
                adjacents.get(edge[0]).add(edge[1]);
                adjacents.get(edge[1]).add(edge[0]);
            }

            dp = new Object[nodeCnt][];
            res = new Object[nodeCnt];
            for (int i = 0; i < nodeCnt; i++) {
                dp[i] = new Object[adjacents.get(i).size()];
            }
            if (nodeCnt == 1) {
                res[0] = afterMerge.apply(identity, 0);
            } else {
                initialize();
            }
        }

        @SuppressWarnings("unchecked")
        public T query(int node) {
            return (T) res[node];
        }

        @SuppressWarnings("unchecked")
        private void initialize() {
            int[] parents = new int[nodeCnt];
            int[] order = new int[nodeCnt];

            // InitOrderedTree
            int index = 0;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.addFirst(0);
            parents[0] = -1;
            while (!stack.isEmpty()) {
                int current = stack.pollFirst();
                order[index++] = current;
                for (int adjacent : adjacents.get(current)) {
                    if (adjacent == parents[current]) continue;
                    stack.addFirst(adjacent);
                    parents[adjacent] = current;
                }
            }

            // FromLeaf
            for (int i = order.length - 1; i >= 1; i--) {
                int node = order[i];
                int parent = parents[node];
                T accum = identity;
                int parentIndex = -1;
                for (int j = 0; j < adjacents.get(node).size(); j++) {
                    if (adjacents.get(node).get(j) == parent) {
                        parentIndex = j;
                        continue;
                    }
                    accum = merge.apply(accum, beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
                }
                dp[parent][indexForAdjacent.get(node).get(parentIndex)] = afterMerge.apply(accum, node);
            }

            // ToLeaf
            for (int node : order) {
                T accum = identity;
                Object[] accumsFromTail = new Object[adjacents.get(node).size()];
                accumsFromTail[accumsFromTail.length - 1] = identity;
                for (int j = accumsFromTail.length - 1; j >= 1; j--) {
                    accumsFromTail[j - 1] = merge.apply(
                            (T) accumsFromTail[j],
                            beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
                }
                for (int j = 0; j < accumsFromTail.length; j++) {
                    dp[adjacents.get(node).get(j)][indexForAdjacent.get(node).get(j)] =
                            afterMerge.apply(merge.apply(accum, (T) accumsFromTail[j]), node);
                    accum = merge.apply(accum, beforeMerge.apply((T) dp[node][j], adjacents.get(node).get(j)));
                }
                res[node] = afterMerge.apply(accum, node);
            }
        }
    }
}

最終結果：ABCDEの5完1500点、81分34秒、1190位、パフォーマンス1377相当
レート変動：2005（Unrated）

ちなみにこの前日のARC127は記事も書いていないが、不参加というわけではなく、単に1問も提出に値するコードを書けるに至らず、結果としてNoSub撤退となっていた。

ARC127をNoSub撤退してなかったら、多分今回のABCで一気にレート1900も切っていたと思う。

レート黄色を維持するには青diffまでを高確率で通せればよいが、最近は青どころか緑～水diffすらも落としまくってるので救いようがない。
黄diffは稀にしか解けなくてもいいから、青diffまではちゃんと解きたいんだけど、一体どうすれば。
やっぱりくじかつの後半で面倒な問題が出てきたらあっさり放棄してるのがいけないのかな。