PG BATTLE 2023参加記録

Published on 2023-10-23
Last Modified 2023-10-23

Table Of Contents

始まりは突然に

10月9日に、やきとりさん(@yktr_drm06)からPG BATTLEに誘われて、私、やきとりさん、ryotaさん(@95s7k84695a)のチームで参加することになりました。

このコンテストの存在は知っていたものの、学内に競技プログラミングをしている知り合いが存在しないため、どうしようか迷っていました。(最悪電通大競プロサークルのDiscordで募集かけようかと思っていた。)

そんな時にお誘いいただいたので、ぜひ！ということで参加させていただきました。メンバーが私よりも強い方なので、ラッキーだなとか思っていました(すいません。)

PG BATTLEについて

普段はAtCoderのコンテスト及び類似のコンテストしか出ていないので、PG BATTLEのルールはちょっと新鮮でした。要点は以下の通りです。

3人1チーム
ひとりひとり解く問題が違う(配点は1/3ずつ)
チーム内相談禁止
提出は一回のみ
総得点及び解答提出時間で勝負

ICPCですら提出は何回かできるので、プログラミングコンテストとしてはかなり珍しい方だなと思います。問題は、ましゅまろ/せんべい/かつおぶしの三種類あり、誰がどの問題を解くかは事前に決めることができます。私は二番目に簡単なせんべいを担当しました。

せんべい雑振り返り

すべての問題はここで公開されています。

難易度2 積の符号

ちょっと前にTwitterで話題になっていた、注意力を要求するB問題みたいな雰囲気のする問題です。符号を当てればよいので、全部掛け算する必要はなく、0があるかどうかで場合分けをすればよいです。

0がなければ、-の要素が偶数個か奇数個かでACできます。

import std;

void main () {
    int N = readln.chomp.to!int;
    int[] A = readln.split.to!(int[]);

    int minus = false;

    A.sort;
    foreach (i; 0..N) {
        if (A[i] == 0) { writeln(0); return; }
        if (A[i] < 0) minus++;
    }

    if (minus % 2 == 0) {
        writeln("+");
    } else {
        writeln("-");
    }
}

難易度3 ABCの個数

期待値を求める系の問題は大体よくわかってないので、苦手問題来たーって思って身構えました。

ググって何とかならないかなーと思って、「期待値の線形性」というキーワードで出てきたこのサイトを見ていたら、応用例2がまさにこの問題でした。ラッキー！

どうやら各部分で"ABC"が作れる確率を足し合わせればよいようです。

期待値の線形性ってこうやって使うんだなぁと勉強になったような気がします。ただ、数学的理解が怪しいのでうーんという感じです。

import std;

void main () {
    string S = readln.chomp;

    solve(S);
}

void solve (string S) {
    /* 期待値の線形性を使う */
    /* 場所iをスタートにしてABCができる確率X_iとすると、解はE[Σ(X_i)] */
    double ans = 0;
    foreach (i; 0..S.length) {
        if (S.length <= i+2) continue;
        if ((S[i] != '?' && S[i] != 'A') || (S[i+1] != '?' && S[i+1] != 'B') || (S[i+2] != '?' && S[i+2] != 'C')) continue; /* 確率0 */
        int UnComfirmed = 0;
        for (int j = 0; j < 3; j++) if (S[i+j] == '?') UnComfirmed++;
        ans += 1./(3^^UnComfirmed);
    }

    writefln("%.10f", ans);
}

難易度4 距離K

これは割とすぐ解法が見えました。まずは数列を次のようにK個のグループに分けます。 $$\mathrm{group}[i] \coloneqq \{ A[x] \mid \forall j, ~ x = i+jK \}$$ 実は、操作によって入れ替わることができるのは同一グループに属する要素だけです。

簡単のため、ある一つのグループ以外を固定して考えます。この時、数列Aは操作できるグループの「同じものを含む順列」通り数になります。同様の議論をすべてのグループに適用することで、数列Aの変化先の総数は、すべてのグループについての「同じものを含む順列」の総積であることが分かります。

式におこしましょう。$\mathrm{group}[i]$が要素$x[j]$を$y[j]$個持つとすると、求める値は $$ \prod_{i} \frac{\left( \sum_{j} y[j] \right)!}{\prod_j (y[j]!)} $$ となります。$\sum_{j}y[j] \leq N$なので、 Nまでの階乗及びその逆元をを空間/時間$O(N)$で先に求めておけば、上の式を高速に求めることができます。

import std;

void main () {
    int N, K; readln.read(N, K);
    int[] A = readln.split.to!(int[]);

    solve(N, K, A);
}

void solve (int N, int K, int[] A) {
    const long MOD = 998244353;

    /* 階乗前計算 */
    long[] fact = new long[](N+1);
    long[] factInv = new long[](N+1);
    fact[0] = factInv[0] = 1;

    for (int i = 1; i <= N; i++) {
        fact[i] = i*fact[i-1] % MOD;
        factInv[i] = modInv(fact[i], MOD);
    }

    int[][] ModuloKGroups = new int[][](K, 0);

    foreach (i; 0..K) {
        if (N <= i) continue;
        int pos = i;
        while (pos < N) {
            ModuloKGroups[i] ~= A[pos];
            pos += K;
        }
    }

    /* 最後にprodの総積をとる */
    long[] prod = new long[](K);

    int[int] count;
    foreach (i; 0..K) {
        int ElemSize = cast(int) ModuloKGroups[i].length;
        foreach (m; ModuloKGroups[i]) count[m]++;

        prod[i] = fact[ElemSize];
        foreach (key, val; count) {
            prod[i] *= factInv[val];
            prod[i] %= MOD;
        }
        count.clear;
    }

    long ans = 1;
    foreach (i; 0..K) {
        ans *= prod[i];
        ans %= MOD;
    }

    writeln(ans);
}

void read(T...)(string S, ref T args) {
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}

long modPow (long a, long x, const int MOD) {
    // assertion
    assert(0 <= x);
    assert(1 <= MOD);

    // normalize
    a %= MOD; a += MOD; a %= MOD;

    // simple case
    if (MOD == 1) {
        return 0L;
    }

    if (x == 0) {
        return 1L;
    }

    if (x == 1) {
        return a;
    }

    // calculate
    long res = 1L;
    long base = a % MOD;
    while (x != 0) {
        if ((x&1) != 0) {
            res *= base;
            res %= MOD;
        }
        base = base*base; base %= MOD;
        x >>= 1;
    }

    return res;
}

long modInv (long x, const int MOD) {
    import std.exception;
    enforce(1 <= MOD, format("Line : %s, MOD must be greater than 1. Your input = %s", __LINE__, MOD));
    return modPow(x, MOD-2, MOD);
}