AtCoder Beginner Contest 207(Rated範囲外)

ABC

コンテスト前のレート：2074
（Ratedだとしたら）レート通りのパフォーマンスが得られる順位：268位（1100点、52分14秒）

A - Repression

問題

思考過程
  1. max(A+B, A+C, B+C)を求める。
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();

        int ans = a + b;
        ans = Math.max(ans, a + c);
        ans = Math.max(ans, b + c);
        System.out.println(ans);
    }
}

ここまで0分47秒＋0ペナ。296位。


B - Hydrate

問題

思考過程
  1. 愚直にシミュレーションしても、だいたい10^5回以内くらいには終わりそうな雰囲気を感じる。
  2. ただし、達成不可能な場合は無限ループになるので先に判定しておく必要がある。
  3. \frac{B}{C} \geq Dの場合は-1。
  4. 一応最悪ケースを調べておこうかとも思ったが、すぐにできそうになかったのでとりあえず提出。
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();
        int d = sc.nextInt();
        sc.close();

        if (b >= c * d) {
            System.out.println(-1);
            return;
        }

        long w = a;
        long r = 0;
        for (int i = 1; ; i++) {
            w += b;
            r += c;
            if (w <= r * d) {
                System.out.println(i);
                return;
            }
        }
    }
}

ここまで5分05秒＋0ペナ。351位。


C - Many Segments

問題

思考過程
  1. 全部半開区間か閉区間かにすることを考える。
  2. 閉区間に揃えてみることにし、左側が開区間(t=3, 4)なら+1、右側が開区間(t=2, 4)なら-1してみるが、例１すら合わない。
  3. 例１で(i, j)=(2, 3)の場合、[2, 2]と[3, 3]のため共通部分なしとなっていた。
  4. +1と-1ではなく、+0.1と-0.1とし、[2, 2.9]と[2.1, 3.9]の判定になるようにする。
    　
  5. 共通部分があるかどうかの判定は、区間iが左にある場合（r_i \lt l_j）と区間jが左にある場合（r_j \lt l_i）以外の場合に共通部分ありとする。
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();
        double[] l = new double[n];
        double[] r = new double[n];
        for (int i = 0; i < n; i++) {
            int t = sc.nextInt();
            l[i] = sc.nextInt();
            r[i] = sc.nextInt();
            if (t > 2) {
                l[i] += 0.1;
            }
            if (t % 2 == 0) {
                r[i] -= 0.1;
            }
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (r[i] < l[j] || r[j] < l[i]) {
                } else {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで14分33秒＋0ペナ。303位。



D問題は解けず。
a_1に対応付けるc_kをN通り、回転を90度単位に4通り試したら11/64WA。


E - Mod i

問題
残り1分で提出してなんとかAC。
結果がわかる頃にはもう時間切れになっているし、残り1分足らずではできることもないだろうと、採点が進んでいくのを見守っていたが、ぎりぎりTLEになった場合を想定して、longをintに変える定数倍高速化を用意しておくくらいはやりようがあったかもしれない。
と気が付いた時には残り30秒足らずだったので、結局そのまま見守った。
そして1975ms。見守ったことを後悔せずに済んだ。

思考過程
  1. とりあえず「dp[i][j]:=i番目まで見て区間をj個作っている場合の通り数」を考えてみる。
  2. 例１や例２のDPテーブルを手作りしてみつつ、遷移を考える。
  3. dp[i][j]への遷移は、dp[j - 1][j - 1]～dp[i - 1][j - 1]を調べて求める必要がある。
  4. 愚直にやっていたら、DPテーブルがO(N^2)で遷移がO(N)なので、O(N^3)かかってしまう。なんとか累積和などで遷移をO(1)にしたい。
    　
  5. dp[x][j - 1]について、mod jごとに合計を保持しておくMapを用意し、それを逐次更新していくようにする。
  6. 個数無制限ナップサック状態になったのでループを逆順にしたり、下記ソース中の変数cに入れる値などを散々間違えながら直したりして、ようやくDPテーブルが手作りのものと一致し、サンプルが合ったので提出。
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
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();
        long[] a = new long[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextLong();
        }
        sc.close();

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

        int mod = 1000000007;
        long[][] dp = new long[n + 1][n + 1];
        dp[0][0] = 1;

        List<Map<Long, Long>> list = new ArrayList<>(n + 1);
        Map<Long, Long> fm = new HashMap<>();
        fm.put(0L, 1L);
        list.add(fm);

        for (int i = 1; i <= n; i++) {
            for (int j = i; j >= 1; j--) {
                Map<Long, Long> map = list.get(j - 1);
                long c = b[i] - b[j - 1];
                c %= j;
                if (c < 0) {
                    c += j;
                }
                dp[i][j] = map.getOrDefault(c, 0L) % mod;

                long e = b[i] - b[j];
                e %= j + 1;
                Map<Long, Long> map2 = null;
                if (j == i) {
                    map2 = new HashMap<>();
                    list.add(map2);
                } else {
                    map2 = list.get(j);
                }
                map2.put(e, map2.getOrDefault(e, 0L) + dp[i][j]);
            }
        }
        long ans = 0;
        for (int i = 1; i <= n; i++) {
            ans += dp[n][i];
        }
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで98分47秒＋0ペナ。464位。



Fは問題を読むこともできず。



最終結果：ABCEの4完1100点、98分47秒、466位、パフォーマンス1808相当
レート変動：2074（Unrated）


今回は令和ABC-Dで過去最難だったらしいとはいえ、最近D問題を落とす率が馬鹿にならない。
直近10回中4回も落としている（それより前は40回近く連続で通しているが）。俺は本当に黄色なのだろうか。

Eの方針が割とすぐに出てきたことだけは良かった。