京セラプログラミングコンテスト2021（AtCoder Beginner Contest 200）(Rated範囲外)

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

最初にD問題の問題文だけ読んでみて、すぐに解けそうにないので普通に前から解く。

A - Century

問題

思考過程

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() - 1;
        sc.close();

        System.out.println(n / 100 + 1);
    }
}

ここまで1分15秒＋0ペナ。1139位。

B - 200th ABC-200

問題

思考過程

1. 深く考えずに問題文の通り実装する。
2. 後ろに文字列としてを付け加えるのは、倍してを足せば文字列に変換しなくてもできる。
3. 答えはintに収まらないと書いてあるのでlong型にする。を付け加えた後はで割れるので、多分longには収まるのだろう。

import java.util.Scanner;

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

        for (int i = 0; i < k; i++) {
            if (n % 200 == 0) {
                n /= 200;
            } else {
                n = n * 1000 + 200;
            }
        }
        System.out.println(n);
    }
}

ここまで2分56秒＋0ペナ。507位。

C - Ringo's Favorite Numbers 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[] c = new int[200];
        for (int i = 0; i < n; i++) {
            c[sc.nextInt() % 200]++;
        }
        sc.close();

        long ans = 0;
        for (int i = 0; i < c.length; i++) {
            ans += (long) c[i] * (c[i] - 1) / 2;
        }
        System.out.println(ans);
    }
}

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

D - Happy Birthday! 2

問題
DPの復元をするのにひたすら手間取った。
最終的に、下記4.の判定を入れるなら、3.はいらなかった。

思考過程

1. 「番目まで見て個以上選んだ時の和の余りがになる選び方の数」をして、となる箇所があるかどうか調べる。なければ"No"。
2. あとは、条件を満たしたところから、最後にを選んだ場合の遷移と、を選ばなかった場合の遷移を起点として、DPテーブルを逆から辿って復元する。
3. なお、答えの数列が空ではいけないことから、は起点の範囲から除外する。（の場合に、とならないように）
   　
4. WAが出てしまったので、明らかに駄目である、を選ばなかった方の数列が空になった場合や、復元時ににたどり着かなかった場合を除外してみたらAC。これで本当に穴がないかどうかは知らない。　→（2021/5/10追記）after_contestで1ケースWA。

import java.util.ArrayList;
import java.util.List;
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 = 200;
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt() % m;
        }
        sc.close();

        int[][] dp = new int[n + 1][m];
        dp[0][0] = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                dp[i + 1][j] += dp[i][j];
                dp[i + 1][(j + a[i]) % m] += dp[i][j];
            }
            if (i > 0) {
                for (int j = 0; j < m; j++) {
                    if (dp[i + 1][j] >= 2) {
                        // 最後にa[i]を選んだ遷移の復元
                        List<Integer> b = new ArrayList<>();
                        b.add(i + 1);
                        int now = (j - a[i] + m) % m;
                        for (int k = i - 1; k >= 0; k--) {
                            int next = (now - a[k] + m) % m;
                            if (dp[k][next] > 0) {
                                now = next;
                                b.add(k + 1);
                            }
                            if (now == 0) {
                                break;
                            }
                        }
                        if (now != 0) {
                            continue;
                        }

                        // 最後にa[i]を選ばなかった遷移の復元
                        List<Integer> c = new ArrayList<>();
                        now = j;
                        for (int k = i - 1; k >= 0; k--) {
                            int next = (now - a[k] + m) % m;
                            if (dp[k][next] > 0) {
                                now = next;
                                c.add(k + 1);
                            }
                            if (now == 0) {
                                break;
                            }
                        }
                        if (now != 0 || c.size() == 0) {
                            continue;
                        }

                        System.out.println("Yes");
                        System.out.print(b.size());
                        for (int k = b.size() - 1; k >= 0; k--) {
                            System.out.print(" " + b.get(k));
                        }
                        System.out.println();
                        System.out.print(c.size());
                        for (int k = c.size() - 1; k >= 0; k--) {
                            System.out.print(" " + c.get(k));
                        }
                        System.out.println();
                        return;
                    }
                }
            }
        }
        System.out.println("No");
    }
}

ここまで40分45秒＋2ペナ。532位。

EとFは解けず。
モチベがあまりなく、時間いっぱいまで粘らず離脱しようかとも思ったが、一応最後までF問題をゆるく解こうとはしていた。

一応、各文字について、前の文字と異なることが何回あるかを数える方針でやってはいたが、細かくは詰め切れず。

最終結果：ABCDの4完、50分45秒、802位、パフォーマンス1626相当
レート変動：2008（Unrated）

とりあえず明日のARCはちゃんと頑張れるようにしたい。