エクサウィザーズプログラミングコンテスト2021（AtCoder Beginner Contest 222）(Rated範囲外)

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

A - Four Digits

問題
本当はJavaで"+"を使った文字列の連結は良くないけど文字数も少ないので手抜き。

思考過程

1. 入力を文字列で受け取り、文字になるまでを付け足す。

import java.util.Scanner;

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

        while (n.length() < 4) {
            n = "0" + n;
        }
        System.out.println(n);
    }
}

ここまで0分43秒＋0ペナ。188位。

B - Failing Grade

問題
過去最も簡単なB問題候補なのではないだろうか。

思考過程

1. のものをカウントしていく。
2. 一旦入力を配列に入れるほどでもないので、入力を受け取りながら上記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();
        int p = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            if (a < p) {
                ans++;
            }
        }
        sc.close();

        System.out.println(ans);
    }
}

ここまで1分29秒＋0ペナ。89位。

C - Swiss-System Tournament

問題

思考過程

1. 勝数と番号の組をソートできるよう、オブジェクトの配列を作成しておく。
2. 各ラウンドでは、配列の前から要素ずつ見ていき、じゃんけんの結果を反映してソートし直す。

なお、下記コード中の★1であいこを除外するならば、★2はelseだけでも十分だった。

import java.util.Arrays;
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 m = sc.nextInt();
        int n2 = n * 2;
        char[][] a = new char[n2][m];
        for (int i = 0; i < n2; i++) {
            a[i] = sc.next().toCharArray();
        }
        sc.close();

        Obj[] arr = new Obj[n2];
        for (int i = 0; i < n2; i++) {
            Obj o = new Obj();
            o.i = i;
            arr[i] = o;
        }

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n2; j += 2) {
                Obj o1 = arr[j];
                Obj o2 = arr[j + 1];
                char g1 = a[o1.i][i];
                char g2 = a[o2.i][i];
                if (g1 != g2) { // ★1
                    if ((g1 == 'G' && g2 == 'C') ||
                            (g1 == 'C' && g2 == 'P') ||
                            (g1 == 'P' && g2 == 'G')) {
                        o1.w++;
                    } else if ((g2 == 'G' && g1 == 'C') || // ★2
                            (g2 == 'C' && g1 == 'P') ||
                            (g2 == 'P' && g1 == 'G')) {
                        o2.w++;
                    }
                }
            }
            Arrays.sort(arr, (o1, o2) -> {
                if (o1.w != o2.w) {
                    return o2.w - o1.w;
                }
                return o1.i - o2.i;
            });
        }

        for (Obj o : arr) {
            System.out.println(o.i + 1);
        }
    }

    static class Obj {
        int w, i;
    }
}

ここまで9分36秒＋0ペナ。90位。

D - Between Two Arrays

問題

思考過程

1. 「番目までで最後がの場合の通り数」を定義し、の遷移を考える。
2. への遷移は、～の和となるので、が小さい方から順に処理していけば、ならしで遷移できる。
   　
3. の範囲しか集計しないか、の範囲しか値を入れないかすることで、の条件を満たす通り数のみ数えることができる。
4. 上記3.の後者で処理するため、の合計を求めてから、その先についてはつずつ合計に加算して代入を繰り返すようにする。
   　
5. 答えは～の和。この範囲しか値を入れていないので、について全て足してもよい。

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

        int mod = 998244353;
        int m = 3001;
        long[][] dp = new long[n][m];
        for (int i = a[0]; i <= b[0]; i++) {
            dp[0][i] = 1;
        }
        for (int i = 1; i < n; i++) {
            long sum = 0;
            // a[i]未満の範囲は合計のみ求める
            for (int j = 0; j < a[i]; j++) {
                sum += dp[i - 1][j];
            }
            // a[i]～b[i]の範囲は合計への加算と結果の設定
            for (int j = a[i]; j <= b[i]; j++) {
                sum += dp[i - 1][j];
                sum %= mod;
                dp[i][j] = sum;
            }
        }
        // 5
        long ans = 0;
        for (int j = a[n - 1]; j <= b[n - 1]; j++) {
            ans += dp[n - 1][j];
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで16分31秒＋0ペナ。117位。

E - Red and Blue Tree

問題

思考過程

1. 例１では、辺を通る回数の合計（とする）が回あるのを、回ずつになるように塗り分ける必要がある。
2. これは、各辺を通る回数がわかっていれば、「数列から任意の要素を選んで合計が特定の値になる通り数」を求めることになるので、DPで解ける。
   　
3. 制約が小さいので、各辺を通る回数は回DFSをしてで求められる。
   　
4. 上記2.の「特定の値」はまたはとして考えられる値であり、の両辺にを足して変形すると、となる。
5. 上記4.のが負数や奇数の場合は。
   　
6. あとは上記2.のDPをすると計算量がなので、の最大値がどれくらいになるかだが、はで、は。

import java.util.ArrayList;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int n, m, k;
    static int[] a;
    static List<List<Hen>> list;

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        k = sc.nextInt();
        a = new int[m];
        for (int i = 0; i < m; i++) {
            a[i] = sc.nextInt() - 1;
        }
        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++) {
            Hen h = new Hen();
            h.u = sc.nextInt() - 1;
            h.v = sc.nextInt() - 1;
            list.get(h.u).add(h);
            list.get(h.v).add(h);
            arr[i] = h;
        }
        sc.close();

        // 3
        for (int i = 1; i < m; i++) {
            dfs(a[i - 1], -1, a[i], new LinkedHashSet<>());
        }

        // 4
        int total = 0;
        for (Hen h : arr) {
            total += h.cnt;
        }
        // r + b = k + 2b
        // total - k = 2b;
        total -= k;
        // 5
        if (total < 0 || total % 2 != 0) {
            System.out.println(0);
            return;
        }
        int b = total / 2;

        int mod = 998244353;
        long[] dp = new long[b + 1];
        dp[0] = 1;
        for (Hen h : arr) {
            long[] wk = new long[b + 1];
            for (int i = 0; i <= b; i++) {
                int next = i + h.cnt;
                if (next <= b) {
                    wk[next] += dp[i];
                }
                wk[i] += dp[i];
                wk[i] %= mod;
            }
            dp = wk;
        }
        System.out.println(dp[b]);
    }

    static class Hen {
        int u, v, cnt;
    }

    static boolean dfs(int x, int p, int g, LinkedHashSet<Hen> his) {
        if (x == g) {
            for (Hen h : his) {
                h.cnt++;
            }
            return true;
        }
        for (Hen h : list.get(x)) {
            int i = h.u;
            if (i == x) {
                i = h.v;
            }
            if (i != p) {
                his.add(h);
                if (dfs(i, x, g, his)) {
                    return true;
                }
                his.remove(h);
            }
        }
        return false;
    }
}

ここまで36分46秒＋0ペナ。116位。

残り時間はほとんどF問題に費やしたが解けず。
全方位木DPライブラリを使いにくいかと思って自力で頑張っていたら、終了数分前に考慮漏れに気付いて修正が間に合わず。
とはいえ、終了数分後に提出したものもACのケース数がほとんど変わっていないまま。何が悪いのかはすぐにはわかりそうにない。

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

Eで時間かかってしまったかと思ったら意外と早かったのはよかったが、Fでおおよその解法がわかるまではそんなに時間かかっていないのに詰め切れていないのが・・・。