キーエンスプログラミングコンテスト 2021

A - Two Sequences 2
- 思考過程
B - Mex Boxes
- 思考過程
C - Robot on Grid
- 思考過程
D - Choosing Up Sides
- 思考過程

コンテスト前のレート：1863
レート通りのパフォーマンスが得られる順位：486位（1200点、42分00秒）

A - Two Sequences 2

問題
とにかく時間かかりすぎて辛い。

思考過程

とりあえず現時点での最大値を達成したときの $a_i$ （以下 $ma$ ）と $b_j$ （以下 $mb$ ）を保持しながら、前から $c_n$ を求めていくことを考える。
　
$b_n \gt mb$ の場合、 $ma \times b_n$ はそれまでの最大値より大きい。
$a_n \gt ma$ の場合、 $a_n$ を採用する場合は $b_n$ しか取れないので、 $a_n \times b_n$ がそれまでの最大値より大きいかどうかを調べる。
これだと、例２の $3$ 行目以降が合わない。 $n=3$ の時、答えは $a_2 \times b_3$ だが、 $a_3 \times b_3$ となってしまう。
　
$b_n$ を採用する場合、 $a$ の方は $a_1$ ～ $a_n$ のどれでも取れるので、 $ma$ は単にこれまでの最大値を保持するものとする。「 $a_n \gt ma$ の場合」とか余計な条件は付けずに、 $ma \times b_n$ が大きいかどうかを必ず調べても害はない。
結局、上記2とかは無駄かも・・・とは思いつつも、害はない処理であり、ソースを整える時間ももったいないのでそのまま提出。

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] sa = br.readLine().split(" ");
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = Integer.parseInt(sa[i]);
        }
        sa = br.readLine().split(" ");
        int[] b = new int[n];
        for (int i = 0; i < n; i++) {
            b[i] = Integer.parseInt(sa[i]);
        }
        br.close();

        long ans = 0;
        long ma = 0;
        long mb = 0;
        PrintWriter pw = new PrintWriter(System.out);
        for (int i = 0; i < n; i++) {
            ma = Math.max(ma, a[i]);
            // 思考過程2（このifブロックは消しても通る）
            if (b[i] > mb) {
                mb = b[i];
                ans = ma * mb;
            }
            long val = ma * b[i];
            if (val > ans) {
                mb = b[i];
                ans = ma * mb;
            }
            pw.println(ans);
        }
        pw.flush();
    }
}

ここまで20分40秒＋0ペナ。1905位。
486位以上になるためには5～6分程度で通す必要があったので、滅茶苦茶遅い。

B - Mex Boxes

問題

思考過程

一旦 $K$ を無視して考えると、同じ値のボールは全部別の箱に入れるのが最適。
値 $i$ のボールが $c_i$ 個あるとすると、答えに寄与するボールの数は $c_i$ の累積 $min$ を取った形になる。
答えは、値 $i$ が書かれた蓋の数を計算していくと $i \times (c_{i-1} - c_i)$ となるが、よく考えればそもそもボールを $1$ 個追加する度に答えは $+1$ か $+0$ なので、答えに寄与するボールの数がそのまま答えになる。
整理すると、 $c_i$ の累積 $min$ の総和を求めればよい。
　
ここで忘れていた $K$ を思い出す。
$c_i$ は $K$ との $min$ を取る必要がある。　→WA
for文の中でやったせいで、先頭だけ $min$ を取れていなかった。むしろ先頭だけ $min$ 取れば十分だった。

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

        c[0] = Math.min(c[0], k); // これがなくてWA
        for (int i = 1; i < n; i++) {
            c[i] = Math.min(c[i], c[i - 1]);
            c[i] = Math.min(c[i], k); // 不要
        }

        int ans = 0;
        for (int i = 0; i < n; i++) {
            ans += c[i];
        }
        System.out.println(ans);
    }
}

ここまで30分24秒＋1ペナ。1500位。

C - Robot on Grid

問題
ガチャガチャやりやすい例２と、強いケースの例３のおかげで解けた。

思考過程

とりあえず、'R'の場合右のみに、'D'の場合下のみに、'X'の場合両方に、いずれでもない場合 $3$ 種類を総合して右と下に $2$ 倍ずつ遷移するDPを書いてみる。　→例１が3にしかならない。
$(2, 1)$ → $(2, 2)$ が $1$ 通り、 $(1, 2)$ → $(2, 2)$ が $2$ 通りになっているが、前者を $3$ 通りにして、 $3+2=5$ にしたい感じ。
今見ているマスに関係ない空白マスの数を $X$ として、 $3^X$ 倍する感じか？と思うが、例２で遷移の度に $3^3$ 倍とかしてたら $150$ なんて大幅に超えてしまっていて何かがおかしい。
　
例２を色々ガチャガチャやって辻褄を合わせようとする。
まず $(1, 1)$ から $(1, 2)$ と $(2, 1)$ へは、無関係の空白マスが $3$ 個あるので $3^3=27$ 倍、 $(1, 1)$ を埋める $3$ 通りの内、右へ行くのも下へ行くのも $2$ 通りあるのでどちらも $2$ 倍し、どちらも $54$ 通り。
空きマスでない部分は通常のDPの通り遷移していくと、下図までは埋まる。
X D
D D
R
1 54 54
54 54 54＋左からの遷移
54 54＋上からの遷移
$(3, 2)$ の「上からの遷移」がいくつになるのか考える。
$(2, 2)$ までの遷移は、 $(1, 1)$ が'X'か'R'の $2$ 通り、 $(2, 2), (3, 2), (3, 3)$ が $3^3$ 通りで $54$ 通りとなっているが、 $(2, 2)$ → $(3, 2)$ まで行こうとした時点で、 $(2, 2)$ は'X'か'D'の $2$ 通りとなり、 $36$ 通りに減りそう。 $\frac{2}{3}$ 倍？
　
以下のように当てはめてみたら辻褄が合った。
$3^4=81$ $81 \times \frac{2}{3} = 54$ $54$
$81 \times \frac{2}{3} = 54$ $54$ $54 + 54 \times \frac{2}{3} = 90$
$54$ $54 + 54 \times \frac{2}{3} = 90$ $90 + 90 \times \frac{2}{3} = 150$
$\frac{2}{3}$ 倍するために、 $3$ の逆元を求めておく。
例３もこれで合ったので提出。

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 h = Integer.parseInt(sa[0]);
        int w = Integer.parseInt(sa[1]);
        int k = Integer.parseInt(sa[2]);
        char[][] s = new char[h][w];
        for (int i = 0; i < k; i++) {
            sa = br.readLine().split(" ");
            int a = Integer.parseInt(sa[0]) - 1;
            int b = Integer.parseInt(sa[1]) - 1;
            char c = sa[2].charAt(0);
            s[a][b] = c;
        }
        br.close();

        int mod = 998244353;
        long m3 = modinv(3, mod);
        long[][] dp = new long[h + 1][w + 1];
        dp[0][0] = power(3, h * w - k, mod);
        for (int i = 0; i < h; i++) {
            for (int j = 0; j < w; j++) {
                if (s[i][j] == 'R') {
                    dp[i][j + 1] += dp[i][j];

                } else if (s[i][j] == 'D') {
                    dp[i + 1][j] += dp[i][j];

                } else if (s[i][j] == 'X') {
                    dp[i][j + 1] += dp[i][j];
                    dp[i + 1][j] += dp[i][j];

                } else {
                    dp[i][j + 1] += dp[i][j] * 2 * m3;
                    dp[i + 1][j] += dp[i][j] * 2 * m3;
                }
                dp[i][j + 1] %= mod;
                dp[i + 1][j] %= mod;
            }
        }
        System.out.println(dp[h - 1][w - 1]);
    }

    // 以下ライブラリ

    static long power(long x, long n, int m) {
        if (n == 0) {
            return 1;
        }
        long val = power(x, n / 2, m);
        val = val * val % m;
        if (n % 2 == 1) {
            val = val * x % m;
        }
        return val;
    }

    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;
    }
}

ここまで55分54秒＋1ペナ。508位。
だいぶ盛り返せたが、あと1問解かなければレートプラスにはならない状況。

D - Choosing Up Sides

問題
Eも問題は読んだが全く方針が立ちそうもなかったので、残り時間はほぼDに費した。
だが解けず。

思考過程

$_{2^N}C_{2^{N-1}}$ 通り全列挙するだけでは？　→TLE
頭の中が $_{N}C_{N-1}$ になっていていけそうな気がしていたが、全然違った。
　
$N=3$ の場合で考える。
人 $1$ をAチーム固定とすると、Aチームは残りの $7$ 人中 $3$ 人。
$7$ 人が同じ回数ずつ $A$ チームになる必要があるので、 $3$ と $7$ の最小公倍数が操作回数最小ではないかと当たりを付ける。 $N=8$ の場合でも数万行 $\times 256$ 文字の出力をすればよいのでそれっぽい。
　
あとは条件を満たすように上手く配分できる方法を構築するだけ。これが手作業ならできて、ある程度規則性のある並びにもなっているのだが、簡単に実装できそうにない。できないまま時間切れ。

公式解説を見て、 $i$ 回目の操作で人 $j$ を $popcount(i \& j)$ の偶奇で分けるとあるが、どうやったらこんなのが出てくるのかさっぱり。
$popcount(i)=2^{N-1}-1$ となる $i$ を探してどうにかならないかくらいの発想しかなかった。

最終結果：ABCの3完、60分54秒、619位、パフォーマンス1730
レート変動：1863→1850（-13）

A問題が絶望的に遅かった割には浅い傷で済んだのでまあ・・。
Aが6分で解けてBのしょうもないペナルティがなければちょうど42分くらいなので、順当な結果かと思う。

$3^4=81$	$81 \times \frac{2}{3} = 54$	$54$
$81 \times \frac{2}{3} = 54$	$54$	$54 + 54 \times \frac{2}{3} = 90$
$54$	$54 + 54 \times \frac{2}{3} = 90$	$90 + 90 \times \frac{2}{3} = 150$

1	54	54
54	54	54＋左からの遷移
54	54＋上からの遷移