AtCoder Regular Contest 104

ARC

コンテスト前のレート：1755
レート通りのパフォーマンスが得られる順位：661位（500点、5分55秒）

A - Plus Minus

問題
連立方程式を解けばいいが、思考停止で全探索した。

思考過程
  1. -200 \leq X, Y \leq 200の間で全探索し、条件を満たしたところで出力して終了。
  2. 探索範囲は、足し算と引き算しかしないのだから、AとBの範囲の2倍取っておけば大丈夫だろうと思った。
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();
        sc.close();

        for (int x = -200; x <= 200; x++) {
            for (int y = -200; y <= 200; y++) {
                if (x + y == a && x - y == b) {
                    System.out.println(x + " " + y);
                    return;
                }
            }
        }
    }
}

ここまで1分22秒＋0ペナ。875位。


B - DNA Sequence

問題
問題理解に時間がかかった。
また、解説の実装に比べて回りくどいことをした。

思考過程
  1. O(N^2)が間に合いそうなので、全ての部分文字列を1つずつ判定することを考える。
  2. 部分文字列に含まれるAとT、CとGの数が同じであれば答えにカウントしていく。
  3. 部分文字列（元の文字列の一部区間）に含まれる各文字の数は、累積和を使ってO(1)で求める。
  4. 実装上、T→B、G→Dに変換しておけば、A～D→0～3にでき、配列やループで扱いやすくなる。
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();
        char[] s = sc.next().replaceAll("T", "B").replaceAll("G", "D").toCharArray();
        sc.close();

        int[][] sum = new int[4][n];
        for (int i = 0; i < n; i++) {
            int c = s[i] - 'A';
            sum[c][i]++;
        }
        for (int k = 0; k < 4; k++) {
            for (int i = 1; i < n; i++) {
                sum[k][i] += sum[k][i - 1];
            }
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                int[] cnt = new int[4];
                for (int k = 0; k < 4; k++) {
                    cnt[k] = sum[k][j];
                    if (i > 0) {
                        cnt[k] -= sum[k][i - 1];
                    }
                }
                if (cnt[0] == cnt[1] && cnt[2] == cnt[3]) {
                    ans++;
                }
            }
        }
        System.out.println(ans);
    }
}

ここまで10分35秒＋0ペナ。1074位。

まあ普通のペースかなと思いつつ順位表を見たら、予想した倍以上の順位で水パフォ見込みで愕然としていた。
5分55秒時点だと、多分やっと問題を理解した頃だと思う。


C - Fair Elevator

問題
15分ほど考えてDへ。Dが解けた後再び20分費やしたが解けず。
「区間が被っていない or Cが同じ」の2-SATのように見えていたが、それをtrue/falseで表すのは無理そうなどと思ったりしていた。


D - Multiset Mean

問題
方針は比較的すぐに出てきたので、この問題に集中することにし、結果的に成功した。

思考過程
  1. 平均に関する問題なので、c_xを求めるときは(1-x)～(N-x)がK個ずつあるものとして、平均が0になる個数を求めることを考える。
  2. まず、0だけ使うパターンがK通り。
  3. -1を1個使う場合は、+1も1個使う。
  4. -1を2個使う場合は、+1を2個か、+2を1個使う。
  5. つまり、マイナス側とプラス側の合計値が同じになる集合を作るパターンが何通りかを求めたい。
    　
  6. 「dp[i][j]：xとの差の絶対値がi以下の数のみを使用し、合計値がjになる通り数」を求められるか考える。
  7. jのサイズをいくつにすればよいかだが、これは1～(N-1)の和のK倍。iのサイズNも含めてDPテーブルのサイズは5000万くらい。遷移がO(1)ならいける気がしてくる。
    　
  8. DPの遷移は、iを0個使う場合からK個使う場合までの和になるため、dp[i][j] = \sum_{a=0}^K dp[i - 1][j - ai]となる。
  9. これは、mod iごとに和を記憶しておくことでO(K)をO(1)にできる。（毎回dp[i - 1][j]を足してdp[i - 1][j - i (K+1)]を引く）
    　
  10. 答えは、各jについて、dp[x-1][j]（マイナス側）とdp[n-x][j]（プラス側）を掛け合わせ、さらに0～K個の0を任意に付け足せるため、(K+1)倍する。
  11. j=0の場合のみ、空集合はNGのため、K通り。

※実際は、上記10で、dp[min(x-1, n-x)][j]^2とか、dp[x-1][j]のところを\sum_{a=1}^{x-1}dp[a][j]とかやったりしてもっと迷走していた。

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 k = sc.nextInt();
        int m = sc.nextInt();
        sc.close();

        int total = n * (n - 1) / 2 * k;
        long[][] dp = new long[n][total + 1];
        dp[0][0] = 1;
        for (int i = 1; i < n; i++) {
            int i1 = i - 1;
            long[] sum = new long[i];
            for (int j = 0; j <= total; j++) {
                int ji = j % i;
                sum[ji] += dp[i1][j];
                int d = j - i * (k + 1);
                if (d >= 0) {
                    sum[ji] -= dp[i1][d];
                    sum[ji] += m;
                }
                sum[ji] %= m;
                dp[i][j] += sum[ji];
                dp[i][j] %= m;
            }
        }

        for (int x = 1; x <= n; x++) {
            int l = x - 1;
            int r = n - x;
            long ans = 0;
            for (int j = 1; j <= total; j++) {
                ans += dp[l][j] * dp[r][j] % m;
                ans %= m;
            }
            ans *= k + 1;
            ans += k;
            ans %= m;
            System.out.println(ans);
        }
    }
}

ここまで98分41秒＋0ペナ。190位。



最終結果：ABDの3完、98分41秒、223位、パフォーマンス2249
レート変動：1755→1815（+60）


D問題を通したことで、2完早解きからも3完早解きからも逃れられて大成功。（1200点のパフォーマンス範囲は2183～2360で、時間による差は誤差みたいなもの）
C問題でDPできそうにないなとすぐに切り捨てていたのは反省。