AtCoder Beginner Contest 275

ABC

コンテスト前のレート：1957
レート通りのパフォーマンスが得られる順位：307位（2000点、63分56秒）

A - Find Takahashi

問題

思考過程
  1. 最大値とその時のindexを保持しておく変数を用意し、より大きい値が出てきた時にそれらを更新しながらH_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();
        int[] h = new int[n];
        for (int i = 0; i < n; i++) {
            h[i] = sc.nextInt();
        }
        sc.close();

        int max = 0;
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (h[i] > max) {
                max = h[i];
                ans = i;
            }
        }
        System.out.println(ans + 1);
    }
}

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


B - ABC-DEF

問題

思考過程
  1. 掛け算を1回やるだけでオーバーフローしてしまうので、タイピング量が増えてしまうけど何も考えずにBigIntegerを使うのが楽？
  2. いや、入力をmod取った上、掛け算の度にmod取れば大丈夫。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int mod = 998244353;
        long a = sc.nextLong() % mod;
        long b = sc.nextLong() % mod;
        long c = sc.nextLong() % mod;
        long d = sc.nextLong() % mod;
        long e = sc.nextLong() % mod;
        long f = sc.nextLong() % mod;
        sc.close();

        long abc = a * b % mod * c % mod;
        long def = d * e % mod * f % mod;
        long ans = abc - def + mod;
        ans %= mod;
        System.out.println(ans);
    }
}

ここまで2分55秒＋0ペナ。322位。


C - Counting Squares

問題

思考過程
  1. 正方形の内の1頂点目の座標を全探索し、そこから2頂点目へのベクトルを全探索することを考える。残りの2点は例１を見ながら適当にベクトルの縦横を入れ替えたり符号を入れ替えたりして帳尻を合わせて求められる。
  2. 1頂点目の座標は9 \times 9箇所調べればよい。
  3. 2頂点目へのベクトルは縦方向に+1～+8、横方向には-8～+8？　と思ったが例１が3になる。
  4. 負の範囲も調べないと漏れそうな気がしたが、やっぱり横方向は0～+8で足りていそう。
import java.util.Scanner;

public class Main {
    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = 9;
        char[][] s = new char[n][n];
        for (int i = 0; i < n; i++) {
            s[i] = sc.next().toCharArray();
        }
        sc.close();

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                for (int x = 1; x < 9; x++) {
                    for (int y = 0; y < 9; y++) {
                        if (s[i][j] == '.') {
                            continue;
                        }

                        int i2 = i + x;
                        int j2 = j + y;
                        if (i2 < 0 || n <= i2 || j2 < 0 || n <= j2 || s[i2][j2] == '.') {
                            continue;
                        }

                        i2 = i - y;
                        j2 = j + x;
                        if (i2 < 0 || n <= i2 || j2 < 0 || n <= j2 || s[i2][j2] == '.') {
                            continue;
                        }

                        i2 = i + x - y;
                        j2 = j + x + y;
                        if (i2 < 0 || n <= i2 || j2 < 0 || n <= j2 || s[i2][j2] == '.') {
                            continue;
                        }
                        ans++;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで11分58秒＋0ペナ。195位。


D - Yet Another Recursive Function

問題

思考過程
  1. メモ化再帰やるだけ。
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static Map<Long, Long> map;

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

        map = new HashMap<>();
        long ans = dfs(n);
        System.out.println(ans);
    }

    static long dfs(long k) {
        if (map.containsKey(k)) {
            return map.get(k);
        }
        if (k == 0) {
            return 1;
        }

        long ret = dfs(k / 2) + dfs(k / 3);
        map.put(k, ret);
        return ret;
    }
}

ここまで14分54秒＋0ペナ。82位。


E - Sugoroku 4

問題

思考過程
  1. O(NK)で問題ない制約なので、「dp[i][j]:=ルーレットをi回回してマスjにいる確率」を考える。
  2. 全体でO(NKM)でもまだ大丈夫なので、遷移は双六の操作に従ってjから(j+1)～(j+M)に確率\frac{1}{M}で移動するのをO(M)で処理すればよい。
  3. 1回回す度にNの部分を答えに足していき、Nを超えた部分は折り返して加算する。
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 k = sc.nextInt();
        sc.close();

        int mod = 998244353;
        long mi = modinv(m, mod);

        long ans = 0;
        long[] dp = new long[n + 15];
        dp[0] = 1;
        for (int i = 0; i < k; i++) {
            long[] wk = new long[n + 15];
            for (int j = 0; j < n; j++) {
                for (int x = 1; x <= m; x++) {
                    wk[j + x] += dp[j] * mi;
                    wk[j + x] %= mod;
                }
            }
            // 折り返し部分
            for (int x = 1; x <= m; x++) {
                wk[n - x] += wk[n + x];
                wk[n - x] %= mod;
            }
            ans += wk[n];
            wk[n] = 0;
            dp = wk;
        }
        ans %= mod;
        System.out.println(ans);
    }

    // 以下ライブラリ

    static long modinv(long a, int m) {
        long b = m;
        long u = 1;
        long v = 0;
        long tmp = 0;

        while (b > 0) {
            long t = a / b;
            a -= t * b;
            tmp = a;
            a = b;
            b = tmp;

            u -= t * v;
            tmp = u;
            u = v;
            v = tmp;
        }

        u %= m;
        if (u < 0) u += m;
        return u;
    }
}

ここまで23分51秒＋0ペナ。81位。


F - Erase Subarrays

問題

思考過程
  1. 1回だけ削除する方法がO(N^2)通りあって、そこから2回目3回目と考えると全然できる気がしない。
  2. 「dp[i][j][k]:=i番目まで見て削除する要素の総和がjでk=最後の要素を削除しているかどうか」とすると遷移もちゃんと書けそうだが、これだとjがO(Na)、全体でO(N^2a)となり間に合わない。
  3. 削除する要素ではなく残す要素の総和でもほとんど同じ遷移で、これならj \gt M部分の情報は捨てることで全体でO(NM)だった。
import java.io.PrintWriter;
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[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = sc.nextInt();
        }
        sc.close();

        int inf = 100000000;
        int[][] dp0 = new int[n + 1][m + 1]; // 最後を選んでいない
        int[][] dp1 = new int[n + 1][m + 1]; // 最後を選んでいる
        for (int i = 0; i <= n; i++) {
            Arrays.fill(dp0[i], inf);
            Arrays.fill(dp1[i], inf);
        }
        dp0[0][0] = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= m; j++) {
                // i番目を削除する
                // 新しい部分列
                dp1[i + 1][j] = Math.min(dp1[i + 1][j], dp0[i][j] + 1);
                // 前から続いている部分列
                dp1[i + 1][j] = Math.min(dp1[i + 1][j], dp1[i][j]);

                // i番目を削除しない（残す要素の合計がj→njに増える）
                int nj = j + a[i];
                if (nj <= m) {
                    dp0[i + 1][nj] = Math.min(dp0[i + 1][nj], dp0[i][j]);
                    dp0[i + 1][nj] = Math.min(dp0[i + 1][nj], dp1[i][j]);
                }
            }
        }

        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 1; i <= m; i++) {
            int ans = Math.min(dp0[n][i], dp1[n][i]);
            if (ans == inf) {
                ans = -1;
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

ここまで41分24秒＋0ペナ。103位。



Gは正当な方法は何も思い浮かばず、記念に乱択山登りをしてみたが少ししか通らず。
山登りの近傍は、A \gt Bの中から1つ追加、A \lt Bの中から1つ追加、両方から1つずつ追加、の3種類。（コスパ良いものが選ばれる確率を適当に高くする）
除外する操作も入れたり焼きなましにしたりしたらどうだったんだろうか。



最終結果：ABCDEFの6完2000点、41分24秒、139位、パフォーマンス2329
レート変動：1957→2000（+43）


ARC151で-42を喰らった時は黄色に戻るまで結構な回数かかりそうだと思ったが、それからまさかの2回で+71で一気に2000まで回復。無事9回目の入黄を果たした。

レート2000以上になるパフォのボーダーが2322くらいで、Fまで解いた時点からしばらくの間は2400になるかどうかのちょうど境目付近にいたのでまあそこまでは落ちないだろうと思っていたが、最後の20分でみるみる落ちてギリギリだった。
1990台からジャンプできる可能性があるのとどちらが良いのか微妙なところだが。