PG BATTLE 2023に参加して飛び賞をゲットした話

ソフトウェアエンジニアの@tobisatisより、競プロ部の活動報告をお届けします。

2023年10月21日に開催されたPG BATTLE 2023に参加しました。PG BATTLEは、同じ会社内や学校内の3人を1チームとして出場する競技プログラミングの団体戦です。2021年の大会から数えて3度目の参加となりました。

チーム結成

部員数が増えたこともあり、今回は6人で2チームを編成できました。アンケートに回答し、参加意欲の高い順、参加意欲が同じなら提出が早い順で、上から3の倍数人を集めるという手順でメンバーを決めました。チーム名とAtCoder（日本最大の競技プログラミングのサービス）での各メンバーの最高レベル（色）は次の通りです。

チーム1「モノグサでいこう」黄、黄、青
チーム2「Monoxer Blues」青、青、青

結果

両チームとも240点を記録し、企業の部184位中「モノグサでいこう」が14位、「Monoxer Blues」が20位でした。企業の部では130位までの10位ごと13チームにスポンサー賞が与えられ、「Monoxer Blues」が「国際ソフトウェア賞」を獲得しました。

「Monoxer Blues」、左からscrblbug、tamura2004、konayuki

国際ソフトウェア株式会社様、ありがとうございました！部員一同、この場にて御礼申し上げます。

問題の感想

問題と詳しい解説は、PG Battleの公式サイトに掲載されています。

ましゅまろ

「モノグサでいこう」のましゅまろで参加しました。言語はC#です。

1問目、コイントス

(1/2)^Nを求めます。Nが小さいので、1.0をN回2で割ることで十分小さい誤差の値を得られます。

2問目、微分

x^で文字列を分割して数値を得て、問題文にある通りに計算をすればよいです。オーバーフローに注意しましょう。

3問目、2進数と10進数

BigIntegerを使ってBを2進数から10進数に変換し、適当にゼロ埋めを行って文字列で比較しました。組み込みの文字列比較で正しい答えを得られるのですが、1度しか提出できない緊張感のため、本番では上の文字から1文字ずつ比較しました。

4問目、ダンス

「L番目からR番目の人をすべて取り除く操作の数」という小問題を再帰的に解いていくことで求まります。小問題は、左端の人を誰とペアにするかを決めていくことでより小さい問題に帰着させます。状態数O(N²)、遷移O(N)よりO(N³)で解けます。やはり緊張しましたが、入出力例の4が大きいケースだったので、ある程度安心して提出できました。

本番提出コードの一部を掲載します。（NとSの入力、ライブラリを省略）

var v = new bool[n + 1, n + 1];
var f = new ModInt[n + 1, n + 1];
ModInt F(int x, int y)
{
    if (x >= y)
    {
        return 1;
    }
    if (v[x, y]) return f[x, y];
    ModInt res = 0;
    for (var i = x + 1; i < y; i += 2)
    {
        if (s[x] == s[i]) continue;
        var l1 = (i - x - 1) / 2;
        var l2 = (y - 1 - i) / 2;
        var w = F(x + 1, i) * F(i + 1, y);
        var h = (l2 + 1).H(l1 + 1);
        res += w * h;
    }
    v[x, y] = true;
    f[x, y] = res;
    return res;
}
var ans = F(0, n);
return ans;