AtCoder Beginner Contest 185

コンテスト前のレート：1882
レート通りのパフォーマンスが得られる順位：410位（2100点、58分54秒）

A - ABC Preparation

問題

思考過程

1. ～の最小値を出力する。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int[] a = new int[4];
        for (int i = 0; i < 4; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int ans = a[0];
        for (int i = 0; i < 4; i++) {
            ans = Math.min(ans, a[i]);
        }
        System.out.println(ans);
    }
}

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

B - Smartphone Addiction

問題

思考過程

1. 順に処理していくことを考える。
2. 現在時刻からまでの間に、だけバッテリー残量が減る。
3. 減った結果、残量が以下ならば"No"。
4. 時刻からまでの間に、だけ残量が増える。
5. 増えた結果、残量が以上ならばとする。
6. 現在時刻をとして上記2に戻る。
   　
7. 最後に、上記2のをに読み替えてもう一度減らす判定をする。
8. ここまで通り抜ければ"Yes"。

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

        long r = n;
        long now = 0;
        for (int i = 0; i < m; i++) {
            r -= a[i] - now; // 2
            // 3
            if (r <= 0) {
                System.out.println("No");
                return;
            }
            r += b[i] - a[i]; // 4
            r = Math.min(r, n); // 5
            now = b[i]; // 6
        }
        // 7
        r -= t - now;
        if (r <= 0) {
            System.out.println("No");
            return;
        }
        System.out.println("Yes"); // 8
    }
}

ここまで5分55秒＋0ペナ。291位。

C - Duodecim Ferra

問題
ただのコンビネーションなのに全然気付かず、遠回りをした。

思考過程

1. 「：番目の切れ目まで見て、その内の箇所を切断した場合の通り数」を考える。
2. とりあえず配列の長さ分のループを回す。
3. 切断しない場合と切断する場合の遷移を実装する。
4. が答えかと思ったが合わない。
5. デバッグ出力してみると、っぽかったのでそのようにした。切れ目の数がだからということなんだろうと納得することにした。（雑）

import java.util.Scanner;

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

        long[][] dp = new long[l + 1][12];
        dp[0][0] = 1;
        for (int i = 0; i < l; i++) {
            for (int j = 0; j < 12; j++) {
                dp[i + 1][j] += dp[i][j]; // 切断しない場合
                if (j < 11) {
                    dp[i + 1][j + 1] += dp[i][j]; // 切断する場合
                }
            }
        }
        System.out.println(dp[l - 1][11]);
    }
}

ここまで11分31秒＋0ペナ。362位。

D - Stamp

問題

思考過程

1. は、青色マス同士の間のマス数の最小値。
2. ただし、間がマスの箇所は無視する。
3. 両端欄外のマスとも青色であるとしておく。
4. の総和を求める。

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

        // 思考過程3
        a[m] = 0;
        a[m + 1] = n + 1;
        Arrays.sort(a);

        // 思考過程1
        int k = n;
        for (int i = 1; i < a.length; i++) {
            int d = a[i] - a[i - 1] - 1;
            // 思考過程2
            if (d > 0) {
                k = Math.min(k, d);
            }
        }

        // 思考過程4
        int ans = 0;
        for (int i = 1; i < a.length; i++) {
            int d = a[i] - a[i - 1] - 1;
            int v = (d + k - 1) / k;
            ans += v;
        }
        System.out.println(ans);
    }
}

ここまで17分22秒＋0ペナ。183位。

E - Sequence Matching

問題
問題文を読みつつ一応順位表を見たら、F問題の方が倍くらい解かれていたので、F問題を先に見ることに。
戻ってきた後、サンプルが通る程度のものは10分ほどで書けたが、凡ミスやら遷移がおかしいやらでWA連発。

思考過程

1. 「：までとまでを突き合わせたときの答え」とし、LCS（最長共通部分列）を求めるのと似たような感じでできないかを考える。
2. 上、左、左上からの遷移をするので、配列外参照を気にしなくていいように1-indexedにする。
3. 片方が文字の場合は全部消すしかないので、初期化は以下のようにする。
4. 上記2の通り方向からの遷移を調べ、その内の最小値を採用していく。
5. 具体的な各方向からの遷移時の計算は、なら遷移元と同じ（新しい要素は消さず、不一致も増えない）、そうでなければ遷移元（消したら手増え、消さなければ不一致がつ増えるので後者を採用）。　→9ケースWA
   　
6. 例１のデバッグ出力を見ると、の場合に最低個は消すはずなのにになっていたりなどする。
7. 計算結果と、との差分とのmaxを取ってみる。　→6ケースWA
   　
8. 上記6を手掛かりにすると、で既に対応が取られているのに、でしていないのが問題。
9. 対応付けられている要素数（LCS）を管理するDPテーブルを別に用意し、いずれかが全て対応付け済みならすることにする。

結局、公式解説を読んだら、上と左からの遷移時は必ずすればいいだけで、最後の計算は、値が過大になる方におかしかったので結果的に通ってしまった。

import java.io.BufferedReader;
import java.io.InputStreamReader;

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

        // 思考過程2
        int[][] dp = new int[n + 1][m + 1];
        int[][] dp1 = new int[n + 1][m + 1];
        // 思考過程3
        for (int i = 0; i <= n; i++) {
            dp[i][0] = i;
        }
        for (int i = 0; i <= m; i++) {
            dp[0][i] = i;
        }

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                // 思考過程4, 5
                int v1 = dp[i - 1][j];
                int v2 = dp[i][j - 1];
                int v3 = dp[i - 1][j - 1];
                if (a[i] != b[j]) {
                    v1++;
                    v2++;
                    v3++;
                } else {
                    // 思考過程9
                    if (dp1[i - 1][j] >= j) {
                        v1++;
                    }
                    if (dp1[i][j - 1] >= i) {
                        v2++;
                    }
                }
                dp[i][j] = Math.min(Math.min(v1, v2), v3); // 思考過程4
                dp1[i][j] = i + j - dp[i][j]; // ※この計算はおかしい
            }
        }
        System.out.println(dp[n][m]);
    }
}

ABCDFEと解いた時点で75分46秒＋4ペナ。680位。

F - Range Xor Query

問題
ただSegTreeを貼るだけにしか見えなかったので、E問題を中断して先にやることに。
実際貼るだけだった。

思考過程

1. SegTreeを貼る。
2. 型はInteger、単位元は、二項演算はxor。
3. クエリは問題文の通りに処理する。

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.function.BinaryOperator;
import java.util.function.Predicate;

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

        SegTree<Integer> st = new SegTree<>(a, 0, (v1, v2) -> v1 ^ v2);
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < q; i++) {
            sa = br.readLine().split(" ");
            int t = Integer.parseInt(sa[0]);
            int x = Integer.parseInt(sa[1]) - 1;
            int y = Integer.parseInt(sa[2]);
            if (t == 1) {
                st.set(x, st.get(x) ^ y);
            } else {
                int ans = st.prod(x, y);
                pw.println(ans);
            }
        }
        pw.flush();
        br.close();
    }
}

// 以下ACLのSegTree

提出
ABCDFと解いた時点で26分01秒＋0ペナ。123位。

最終結果：ABCDEFの全完、95分46秒、786位、パフォーマンス1576
レート変動：1882→1855（-27）

やっぱりDPがまだまだ安定感に欠けるのと、解法詰められていないところに実装ミスが重なってペナルティを量産することになったのが痛かった。

それにしても、セグ木貼るだけの問題は2000人も解けるのか・・・。
分母（コンテスト参加人数）も、ピーク時の12000人ほどではなく、7500人ほどしかいないのに。
ACLがきっかけでできるようになった人がどれくらいいるんだろう。