マスターオブ場合の数を競プロで殴る その2「ヒツジ vs オオカミ」

企画の説明は 第1回のエントリー をご覧ください。

問題

オオカミとヒツジがそれぞれ $N$ 匹います。あなたの仕事はこれらの $2N$ 匹を $1$ つのオリの中に入れることです。注意すべきこととして、オリの中に $1$ 匹以上のヒツジがいるとき、オオカミの数がヒツジの数を上回ると、ヒツジは食べられてしまいます。ヒツジが食べられないように、この $2N$ 匹を $1$ 匹ずつすべてオリの中に入れる方法は、何通りありますか？ ただし、オオカミ $N$ 匹は区別せず、ヒツジ $N$ 匹も区別しません。

答えを $998244353$ で割ったあまりを求めてください。

制約

• $1 \leq N \leq 2 \times 10 ^ {5}$

『マスター・オブ・場合の数』P.12 §1-3. をもとに改題

例えば $N = 3$ のとき、ヒオヒヒオオ（ヒ＝ヒツジ、オ＝オオカミ）はOKですが、ヒヒオオオヒはNGです（5匹目の時点でヒツジ2匹に対してオオカミ3匹になるので食べられてしまう）。

クリックで解答を表示

解答

基本的に $($ ヒツジの頭数 $)-($ オオカミの頭数 $)$ がマイナスになった瞬間アウトなのですが、一つだけ例外があり、ヒツジが $\mathbf{0}$ 匹のときはオオカミを入れても $\mathbf{1}$ 匹までなら耐えます（ $2$ 匹以上入れるとヒツジを入れられなくなって詰む）。

このことに注意しつつ、横軸に時間、縦軸に $($ ヒツジの頭数 $)-($ オオカミの頭数 $)$ を取ったグラフを書くと、下図のようになります（下図は $N=3$ の場合）。

赤い線を踏んだ瞬間ゲームオーバーです。この図で赤い線を通らずにスタートからゴールへ向かう道順の個数を数えます。DPをすれば $O(N^{2})$ で解けますが、今回の制約では間に合いません。

上述した「例外」を表す緑色の線が出しゃばっていてどう見ても厄介なので、ひとまず緑色の道を通らない場合を考えてみましょう。

この経路数は有名問題で、カタラン数 $c_N$ になります。

カタラン数

$n$ 番目のカタラン数を $c_n$ とすると、 $$c_n = {}_{2n}\mathrm{C}_{n} - {}_{2n}\mathrm{C}_{n - 1}$$

なぜこの経路数がカタラン数になるのかについては、インターネット上に様々な解説がありますので、ググったりして自分に合うものを探してみてください。個人的オススメをいくつか貼っておきます。

• カタラン数の意味と漸化式 | 高校数学の美しい物語

• えびまさんの解説動画（カタラン数の話は1:10～3:00）

さて、本筋に戻ります。先程は緑色の道を無視した道順を考えたので、次は緑色の道を通る道順を考えます。

緑色の道を通り抜けると、スタートの $1$ つ右の地点に出て来ます。ここで、この地点からもう行けない道は消してしまいましょう。すると……

先程と同じ図が $1$ マス縮小されて出てきました！ よって、緑色の道を通る場合は $c_{N-1}$ 通りになります。

以上より、緑色の道を通る場合と通らない場合をあわせて $c_{N} + c_{N - 1}$ 通りが求める答えです。

実装例

from functools import reduce
MOD = 998244353

# nCrを求める関数
def comb(n, r):
    if not 0 <= r <= n: return 0
    if r == 0 or r == n: return 1
    numer = reduce(lambda x, y: x * y % MOD, (n - r + k + 1 for k in range(r)))
    denom = reduce(lambda x, y: x * y % MOD, (k + 1 for k in range(r)))
    return numer * pow(denom, MOD - 2, MOD) % MOD

# n番目のカタラン数を求める関数
def catalan(n):
    return (comb(2 * n, n) - comb(2 * n, n - 1)) % MOD

n = int(input())
print((catalan(n) + catalan(n - 1)) % MOD)

余談

競プロにおいては、括弧列の問題で同様の考え方が役立つようです。$N$ 組の括弧を正しく並べて括弧列にする方法の個数は、まさにカタラン数 $c_N$ 通りです。流石にそれを直接問う問題は少ないですが、今回のように道順問題っぽい図を書いて考えるのは括弧列問題において定石の一つみたいです。

括弧列問題の例

• ABC167F - Bracket Sequencing

マスターオブ場合の数を競プロで殴る その1「サイコロの積」

私の大きな弱点である数え上げを克服するために、『大学への数学』で有名な東京出版の『マスター・オブ・場合の数』第1章を解いていくことにしました。

もちろん紙とペンを使って解くこともしますが、競プロに最大限生かすため、手で解くだけに留めずプログラムでもぶん殴ってみよう！ という遊びを兼ね備えた精進、精進を兼ね備えた遊びです。

ただし、『マスター・オブ・場合の数』の問題は手で解くことを想定しているため、そのままプログラミングで殴ると多くの問題が全探索で通ってしまいます。そこで、問題を一般化して競プロっぽく改題し、それに対してできる限り大きい制約で解けるようチャレンジしていこうと思います。

「ここがおかしい！」や「もっと計算量落とせるよ！」などのご指摘は歓迎です！

問題

$1$ から $6$ の目が出るサイコロを $N$ 回振るとき、目の出方は $6^{N}$ 通りあります。このうち、出る目の積が $2^{M}$ の倍数となるような目の出方は何通りありますか？

答えを $998244353$ で割ったあまりを求めてください。

制約

• $1 \leq N \leq 3000$
• $1 \leq M \leq 3000$

『マスター・オブ・場合の数』P.12 §1-1. §1-2. をもとに改題

おそらく水diffぐらいの難易度だと思います。

クリックで解答を表示

解答

「出た目の積が $2^{M}$ の倍数」という条件は「 $2$ の素因数の個数が ${M}$ 個以上」と言い換えられます。

$1 \sim 6$ を素因数分解して、$2$ の素因数の個数を調べてみましょう。

• $1 = 2^{\mathbf{0}}$
• $2 = 2^{\mathbf{1}}$
• $3 = 2^{\mathbf{0}} \cdot 3^{1}$
• $4 = 2^{\mathbf{2}}$
• $5 = 2^{\mathbf{0}} \cdot 5^{1}$
• $6 = 2^{\mathbf{1}} \cdot 3^{1}$

$2$ の素因数の個数は $1, 3, 5$ が出たら $0$ 個、$2, 6$ が出たら $1$ 個、$4$ が出たら $2$ 個増えるということが分かりました。これを遷移とする以下のようなDPを行うことで、この問題を解くことができます。

DP配列の定義

$dp[i][j] =$ サイコロを $i$ 回ふって $2$ の素因数の個数がちょうど $j$ 個であるような場合の数 $\pmod{998244353}$

ただし $j \gt {M}$ の場合は $j={M}$ にまとめて扱うことにします。

初期値

• $dp[0][0] = 1$
• $dp[i][j] = 0\hskip2em (otherwise)$

遷移

$j \geq {M}$ の場合をまとめて扱う都合上、配るDPのほうが直感的に書けます。

• $dp[i + 1][j] \mathrel{{+}{=}} dp[i][j] \times 3$
• $dp[i + 1][\min(j+1, M)] \mathrel{{+}{=}} dp[i][j] \times 2$
• $dp[i + 1][\min(j+2, M)] \mathrel{{+}{=}} dp[i][j] \times 1$

貰うDPで書く場合は $j={M}$ のときの場合分けに注意が必要です。

• $dp[i + 1][j] = dp[i][j] \times 3 + dp[i][j - 1] \times 2 + dp[i][j - 2] \times 1 \hskip1em (j \lt M)$
• $dp[i + 1][j] = dp[i][j] \times 6 + dp[i][j - 1] \times 3 + dp[i][j - 2] \times 1 \hskip1em (j = M)$

更新順

小さい方からでOK。

このDP配列を埋めたとき、$dp[N][M]$ が求める答えです。計算量は $O(NM)$ です。

実装例

配るDPで実装した例です。

#include <iostream>
using namespace std;
constexpr int MOD = 998244353;

int dp[3001][3001];
int main() {
    // input
    int n, m;
    cin >> n >> m;

    // dp 配列の初期化
    for (int i = 0; i <= n; ++i)
        for (int j = 0; j <= m; ++j)
            dp[i][j] = 0;
    dp[0][0] = 1;
        
    // dp 遷移
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            dp[i + 1][j] += dp[i][j] * 3;
            dp[i + 1][min(j + 1, m)] += dp[i][j] * 2;
            dp[i + 1][min(j + 2, m)] += dp[i][j];

            dp[i + 1][j] %= MOD;
        }
    }

    if (dp[n][m] < 0) dp[n][m] += MOD;

    // output
    cout << dp[n][m] << endl;
}

貰うDPで書く場合は、DP遷移の部分が次のように変わります（他は同じです）。

    // dp 遷移
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j <= m; ++j) {
            if (j < m)
                dp[i + 1][j] += dp[i][j] * 3 + dp[i][j - 1] * 2 + dp[i][j - 2];
            else
                dp[i + 1][j] += dp[i][j] * 6 + dp[i][j - 1] * 3 + dp[i][j - 2];

            dp[i + 1][j] %= MOD;
        }
    }

余談

『マスター・オブ・場合の数』には、多項式の次数に置き換えて解く方法が紹介されていました。なぜこれが成り立つのかについては本を読んでいただくとして、この問題は次の問題に帰着できます。

$\sum^{\infty}_{k=M}[x^{k}](x^{2}+2x+3)^{N}$ を $998244353$ で割ったあまりを求めよ。 ただし $[x^{k}]f(x)$ は $f(x)$ の $k$ 次の係数を表す。

これを見ると繰り返し2乗法で効率的に解けそうな気がしてくるのですが、シグマを何とかする方法が思いつきませんでした。何かいい方法はあるのでしょうか。分かる人がいたら是非教えて下さい。

類題： TDPC D - サイコロ

サイコロを $N$ 回振ったとき、出た目の積が $D$ の倍数となる確率を求めよ。

制約

• $1 \leq N \leq 100$
• $1 \leq D \leq 10^{18}$

https://atcoder.jp/contests/tdpc/tasks/tdpc_dice

TDPCに似てる問題があったのでこちらも解いてみます。

クリックで解答を表示

解答

先程とほとんど同じ問題設定ですが、$2^{M}$ の倍数から $D$ の倍数へと条件が広がっています。$D$ を素因数分解できればさっきと同じ手順で解くことができるはずですが、 $1 \leq D \leq 10^{18}$ という制約では素因数分解ができません（素因数分解には通常 $O(\sqrt{D})$ かかるため）。

仕方ないので小さいケースで色々試していると、$D = 7$ のとき $N$ によらず答えが $0$ になることに気付きました。$D=11$ などでも同様です。

これを踏まえてよく考えてみると、$1 \sim 6$ に含まれる素因数は $2, 3, 5$ しかありえません。そのため、$\boldsymbol{D}$ に $\mathbf{2, 3, 5}$ 以外の素因数が含まれていたらその時点で確率は $\mathbf{0}$ になるのです。素因数が $2, 3, 5$ しかないと分かれば、ひたすらこれらの数で割っていくことで $O(\log{D})$ で素因数分解ができます。

$D=2^{A} \cdot 3^{B} \cdot 5^{C}$ の形に素因数分解できたら、あとは先程と同様です。

• $dp[i][a][b][c] =$ サイコロを $i$ 回ふって $2, 3, 5$ の素因数の個数がそれぞれ $a, b, c$ 個であるような確率 $\pmod{998244353}$

• $dp[0][0][0][0] = 1$

• $dp[i][a][b][c] = 0\hskip2em (otherwise)$

と定義し、$1 \sim 6$ が

• $1 = 2^{\mathbf{0}} \cdot 3^{\mathbf{0}} \cdot 5^{\mathbf{0}}$
• $2 = 2^{\mathbf{1}} \cdot 3^{\mathbf{0}} \cdot 5^{\mathbf{0}}$
• $3 = 2^{\mathbf{0}} \cdot 3^{\mathbf{1}} \cdot 5^{\mathbf{0}}$
• $4 = 2^{\mathbf{2}} \cdot 3^{\mathbf{0}} \cdot 5^{\mathbf{0}}$
• $5 = 2^{\mathbf{0}} \cdot 3^{\mathbf{0}} \cdot 5^{\mathbf{1}}$
• $6 = 2^{\mathbf{1}} \cdot 3^{\mathbf{1}} \cdot 5^{\mathbf{0}}$

と素因数分解されることから、DPの遷移は

• $dp[i+1][\min(a+0 ,A)][\min(b+0 ,B)][\min(c+0 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$
• $dp[i+1][\min(a+1 ,A)][\min(b+0 ,B)][\min(c+0 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$
• $dp[i+1][\min(a+0 ,A)][\min(b+1 ,B)][\min(c+0 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$
• $dp[i+1][\min(a+2 ,A)][\min(b+0 ,B)][\min(c+0 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$
• $dp[i+1][\min(a+0 ,A)][\min(b+0 ,B)][\min(c+1 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$
• $dp[i+1][\min(a+1 ,A)][\min(b+1 ,B)][\min(c+0 ,C)] \mathrel{{+}{=}} dp[i][a][b][c] / 6$

と書けます。添字が小さい順に埋めていって、$dp[N][A][B][C]$ が求める答えとなります。計算量は $O(NABC)$ つまり $O(N\log^{3}{D})$ となります。

ACコード(Python, 141ms)

WBC004 E - Link 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

時刻 にノード数 , リンク(無向辺)数 の単純・連結とは限らない(多重辺や自己ループを含む可能性がある)ネットワークを準備する。ノードには から の番号が振られているが、リンクは区別されない。このネットワークは、以下の制約を満たすネットワークを重複無く列挙し、その中から一様ランダムに つ選んだものである。ただし、 つのネットワークが異なるとはある が存在して、ノード とノード を結ぶリンクの本数が異なることとする。

• 次数が 以上のノードのうち番号が一番大きいものをノード として、任意の についてノード とノード を結ぶリンクが存在する。

この後、時刻 にひとつずつ、 本のリンクを持ったノードを追加していく。(これらのノードの番号は順に とする。)

すなわち、時刻 におけるネットワークの全ノード数と総リンク数はそれぞれ である。

時刻 に追加されるノードの持つ 本のリンクがノード と繋がる確率をそれぞれ とする。

1. 
2. 時刻 におけるノード の次数を として、

時刻 にネットワークが連結である確率を求めよ。

制約

• 点
• 点
• 
• 
• 
• 入力はすべて整数

解説

問題の整理

この問題、問題文の読解がとても大変ですよね（この問題は元ネタからこんな調子だったので仕方ないところがあるのですが）。こういうときは、絵を描きながら１文ずつ読んでいくと理解の助けになると思います。グラフ問題は特に絵を書くことの恩恵を受けやすいです。この問題の内容を絵で表すとこんな感じになります。まずは問題文前半で説明されている初期状態です。

要するに、頂点数 , 辺数 で、連結なカタマリが1つだけあるグラフなのですね。ただし、図では明示できていない条件として連結なカタマリの中では隣り合う数字が辺でつながれていなければなりません（つまり、1-2, 2-3, 3-4, ...という辺がないといけない）。

次に、毎時発生する遷移の様子です。

毎時、腕を 本持った新しい頂点が飛んできます。それぞれの腕がどの頂点とつながるかについては、問題文のゴツい数式に気圧されそうですが、落ち着いて読んでみると単に確率を (場合の数) / (総数) という形で表しているに過ぎず、片方の腕は「接続先の次数に比例した確率」、もう片方の腕は「等確率」で各頂点につながるということが読み取れます。

そして、以上のルールをもとに我々が最終的に答えなければいけないものが、初期状態としてありえるものからランダムに つピックアップし、 回の遷移を行ったあと、グラフ全体が連結になっている確率です。難解な問題文からシンプル?な問題設定が露わになりました。

全体の方針

初期状態と遷移の仕方が定められているあたりがとてもDPっぽいですね。ある時刻の状態（ここでは状態＝確率分布）から次の時刻の状態が一意に定まるので、時間を添字に持つDPを用いることを考えます。また、制約が なので、単なる時間の1次元DPにとどまらず添字を増やしていく余裕はあるということを頭の隅に置いておきます。察するに、おそらく連結成分の大きさを表す も添え字に持ってDPするのでしょうね。

まずは遷移を掘り下げていきます。我々にとって興味があるのは「時刻 で全体が連結かどうか」なので、「連結」という視点を念頭に置いておきます。

遷移の確率を考える

「接続先の次数に比例した確率でくっつく」というのが明らかに意味深な問題設定なので、その意味するところを考えてみましょう。

もったいぶらずに言ってしまうと、「次数で結合先を選ぶ腕」は次数が の頂点、つまり孤立した頂点にはつながらないということです。逆に、すでに連結になっているカタマリにしかつながらないとも言えます。

となると、遷移の結果を左右する権利を握っているのは「等確率で全頂点につながるもう片方の腕」です。これが連結成分内の頂点にくっついた場合は何も起きないに等しいのですが、その一方、孤立した頂点にくっついた場合は連結成分に新たに1つ頂点が加わることになります。

それぞれの事象が発生する確率は、連結した頂点数と孤立した頂点数を数えてそれぞれ全頂点数で割ることで と求まります。時刻 における全頂点数を とおいています。また、 は上で述べたように、今現在の連結成分の大きさを表しています（問題文の とは異なるものであることに注意してください）。

初期状態を計算する

さぁ数え上げです！ 私はここで一生つまずいていました……

最初に載せた画像を再掲します。

この条件を満たす辺の張り方の数を連結成分の大きさ ごとに数え上げたいです。なお、頂点は区別して辺は区別しません。

まず、1-2, 2-3, 3-4, ...の辺は絶対に必要なので先に張ってしまいましょう。これで、 本の辺を消費します（植木算注意！）。

残った 本の辺を多重辺自己ループなんでもありで張っていきます。この際、下手な数え方をすると重複の処理で爆死するので気をつけてください。

上手な数え方としては、張れる辺 (1-1, 1-2, 1-3, ...) を列挙し、それぞれに 本の辺を分配するというやり方があります。これは数え上げ典型問題であるところの「箱にボール分ける問題（箱区別してボール区別しないで空箱許すバージョン）」に帰着できます。知ってる人には「重複組合せ」「 」で通じるやつです。

これをこの問題に応用すると、まず張れる辺の種類は 頂点から重複を許して 頂点を選んでその間に辺を張るため 種類となり、その中で 本の辺を分配するので、求める場合の数は

となります。

DPに落とし込む

DP配列の定義

時刻 時点で連結成分内の頂点 が であるような確率

初期値

(確率に直すためにあとで総和で割ります)

漸化式

もらうDPです。左の項は孤立していた頂点が選ばれて連結成分に1つ加わる場合、右の項は連結成分が選ばれて変わらない場合の遷移です。

更新順序

素直に添字が小さい順で問題ありません。

実装例

from math import comb

def solve():
    # input
    n, m, l = map(int, input().split())

    # DP配列の生成
    dp = [[0] * (n + 10) for _ in range(l + 10)]

    # 初期値の設定
    dp[0] = [0] * (n + 10)
    for k in range(min(n + 1, m + 2)): # nかm+1で打ち止め
        dp[0][k] = comb(k * (k - 1) // 2 + m, m - k + 1)
    init_sum = sum(dp[0])
    dp[0] = [x / init_sum for x in dp[0]]

    # DPの更新
    for t in range(l):
        for k in range(n):
            dp[t + 1][k + 1] = dp[t][k] * (n - k) / (n + t) + dp[t][k + 1] * (t + k + 1) / (n + t)
    
    # output
    print(f"{dp[l][n]:.15f}") # 桁数を固定しないと指数表記になってWAを食らうことがある


t = int(input())
for _ in range(t): solve()

ひとこと

数え上げ地力が足りない

WBC004 D - Photosynthesis 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)さん主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

ナエムラー(閲覧注意)はレベル で「こうごうせい 」という技を覚えます。 「こうごうせい」で利用される光の波長は です。この区間を 等分したとき、「こうごうせい 」で吸収できるのは 番目の区間の光のみです。しかし、この技を繰り返し使用していると と技のレベルが上がっていきます。

「こうごうせい 」 は のエネルギーを消費する代わりに、区間 を含む連続した 個の区間の光を吸収できます。 区間 の光を吸収すると、 のエネルギーが得られます。

あなたはチャンピオンに挑むため、技のレベルと吸収できる光の波長を最適にしておかなければなりません。 回の「こうごうせい」(技のレベルは問わない)で得られる正味のエネルギー の最大値を求めてください。

制約

• 
• 
• 
• 
• 入力はすべて整数

解説

連続した 個の区間の光を吸収してエネルギーを得る際に のエネルギーを消費するので、あらかじめ、区間 から得られるエネルギー から を引いておきましょう。これを とおくと、次の問題に帰着できます。

数列 が与えられます。 番目の項を含む任意の区間和を取るとき、その最大値を求めてください。

これは典型問題で、方針としては累積和を上手く使うことがカギです。

普通に累積和を使って の区間和を求めるとき、第 項までの累積和テーブルを として として求めますね。これを最大化したいので、 が を含む範囲で はできるだけ大きく、 はできるだけ小さくます。よって、それぞれ の右側の最大値, 左側の最小値を取って来ればOKです。

他にも色々やり方は考えられます。 を始点に左右に2つ累積和を伸ばし、それぞれの最大値を取ってきて足すという方法もポピュラーだと思います。本質的にはさっきのと同じことをしています。

実装例

from itertools import accumulate

def solve():
    # input
    n, k, c = map(int, input().split())
    e = list(map(int, input().split()))
    
    # solve    
    f = [x - c for x in e]
    e = list(accumulate(f, initial=0))
    ans = max(e[k:]) - min(e[:k])

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

ひとこと

この「左右に分けて累積和を取る」っていうのをセグ木みたいにいっぱい積み込むと、構築 でお好きな区間和取り放題になるデータ構造Disjoint Sparse Tableができます。裏を返せば、Disjoint Sparse Tableを持っていればこの問題は一発だったかもしれません。

WBC004 C - Blurred Numbers 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

文字列 が与えられます。 の各文字は、ローマ数字の記号 (I, V, X, L, C, D, M) または ? です。

? をローマ数字の記号に置き換えてできる文字列のうち、文字列全体を通してローマ数字として成り立つものは何通りあるでしょうか？

しかし、東京大学には「優３割規定」というルールがあります。「優３割規定」とは、『 点以上の成績がつく学生の人数は受講者全体の 以下でなければならない』というルールです。このルールに違反すると、怒られが発生します。

怒られるのは嫌なので、あなたは「優３割規定」に違反しないように成績をつけ直すことにしました。あなたは任意の学生の点数を 点に変えることができます。最低で何人の学生の点数を 点に変えれば「優３割規定」をみたすことができるか求めてください。

制約

• はローマ数字の記号 (I, V, X, L, C, D, M) と ? からなる
• 

解説

桁DPはしません。この問題、メチャクチャ見掛け倒しです。

作れるローマ数字は 以上 以下のたった 通りなので、ローマ数字のほうを全部生成して文字列 に一致するものがいくつあるか数えればよいです。

計算量は として です。

実装例

def int_to_roman(n):
    """
    1～3999のアラビア数字を入れるとそれに対応するローマ数字を返す関数
    """
    assert 1 <= n <= 3999

    res = ""

    # 1000の位
    d, n = divmod(n, 1000)
    res += ["", "M", "MM", "MMM"][d]

    # 100の位
    d, n = divmod(n, 100)
    res += ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"][d]

    # 10の位
    d, n = divmod(n, 10)
    res += ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"][d]

    # 1の位
    res += ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"][n]

    return res

def is_match(s, target):
    """
    与えられた文字列Sが目的のローマ数字を表せるか判定する関数
    """
    # 長さが違ったらダメ
    if len(s) != len(target):
        return False
        
    # 1文字ずつ見ていって食い違いがあったらダメ
    for sl, tl in zip(s, target):
        if sl != tl and sl != "?":
            return False
    return True

def solve():
    s = input()
    print(sum(is_match(s, int_to_roman(n)) for n in range(1, 4000)))
    
t = int(input())
for _ in range(t): solve()

ひとこと

最近、ABCのCにもこういう問題多いですよね。

WBC004 B - Linear Code 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

線形符号を構成する長さ の符号語 が与えられるので、異なる つの符号語間のハミング距離の最小値を求めてください。

線形符号

同じ長さのビット列の集合を として、任意の について を満たすとき を線形符号とする。

制約

• 部分点点
• 
• は整数
• は0と1からなる文字列
• はすべて異なる
• 

解説 (部分点)

そもそも「ハミング距離」とは何でしょうか。Wikipediaの解説を見てみましょう。

ハミング距離（ハミングきょり、英: Hamming distance）とは、等しい文字数を持つ二つの文字列の中で、対応する位置にある異なった文字の個数である。

ハミング距離の例： 1011101 と 1001001 の間のハミング距離は 2 である。

ハミング距離 - Wikipedia

要するに、同じ位置にある違う文字の個数がハミング距離なのですね。

問題文はハミング距離の最小値を求めろと言っているので、言われた通りに与えられたビット列の全ペアについてハミング距離を計算して、その最小値を答えとすればよいです。

計算量は 通りのペアに対して で文字を一つ一つ見比べてハミング距離を求めるので、全体で になります。部分点の制約は なので、十分間に合います。

実装例 (部分点)

INF = float("inf")

def solve():
    # input
    n, l = map(int, input().split())
    c = [input() for _ in range(n)]

    # 答えを十分大きい値で初期化
    ans = INF

    # 異なるi, jの組に対して
    for i in range(n):
        for j in range(i):
            # ハミング距離を求める
            cnt = 0
            for k in range(l):
                if c[i][k] != c[j][k]:
                    cnt += 1
            # 暫定の答えより小さければ更新
            if ans > cnt:
                ans = cnt
    
    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

これで部分点 点をゲットできます。

解説

結論から述べると、線形符号のハミング距離の最小値は、 以外のビット列のpopcountの最小値に一致します。 どのようにしてこの結論に至るのか考えてみましょう。

上で書いた愚直解から計算量を落としていきましょう。i, jの2重ループを何とかするのは現段階では難しそうなので、まずはハミング距離を効率的に求める方法を模索するところから始めます。ハミング距離とは、同じ位置にある違う文字の個数でした。これだけでは文字を全部見比べることしかできないように思えます。

しかし、今回は見比べたい文字が 進数という重要な制約があります。 進数のもとで異なる文字を探すなら、ビット演算が役に立ちそうですね？

……そうです！ まさに が、ビット列間の異なる文字を求める演算なのです！

2進数のハミング距離

ビット列 と の異なる部分は で求められる。 よって、ビット列 と のハミング距離は、 のpopcount ( 進数で表したときの の個数) に一致する。

したがって、この問題は次の問題に帰着できます。

線形符号を構成する長さ の符号語 が与えられるので、異なる つの符号語間の のpopcountの最小値 を求めてください。

まだ計算量は落ちていませんが、 の演算で表せると嬉しい気分になることがあります。ここで線形符号の定義をもう一度見てみましょう。

線形符号

同じ長さのビット列の集合を として、任意の について を満たすとき を線形符号とする。

ここにもドンピシャで が出てきています！

”任意の について を満たす” ことから、先程帰着された問題の「異なる つの符号語間の 」は、すべて「 」に入っていることになります。

よって、 のpopcountの最小値を求めれば、それが答えです……と言いたいところですが、それは嘘で、 が含まれていると、 のpopcountは なので最小値が になって終了してしまいます。

というのも、「異なる つの符号語間の 」が になることはないのです。そもそも の性質から となるのは のときだけですが、”集合内の異なる つの符号語間” なので とはならず、 によって が出てくることはありません。

逆に、 のうち 以外の要素は全て出てきます。 だからです。

以上より、元の問題は以下の問題に帰着することができました。この問題は計算量 で解くことができます。

線形符号を構成する長さ の符号語 が与えられるので、 のうち 以外の要素のpopcountの最小値 を求めてください。

実装例

def solve():
    n, l = map(int, input().split())
    print(min(filter(lambda x: x > 0, (input().count("1") for _ in range(n)))))

t = int(input())
for _ in range(t): solve()

ひとこと

Testerとして解けなかった問題三銃士の一角です。最初は部分点なんてなかったのですが、Bにこれが置かれてるのやばいだろと思って愚直解が通るような部分点を設置してもらうよう申し立てたという裏話があります。

WBC004 A - 79 Good 解説

2021年3月18日に開かれたウインドベル(@Twi_Stamp)主催の競プロ有志コンテストWind Bel Contest 004 – Good Bye 2A Day 2の解説です。

問題文

あなたは東京大学の教員です。あなたが開講した科目では、 人の学生が受講し、学生 の成績は 点 でした。

しかし、東京大学には「優３割規定」というルールがあります。「優３割規定」とは、『 点以上の成績がつく学生の人数は受講者全体の 以下でなければならない』というルールです。このルールに違反すると、怒られが発生します。

怒られるのは嫌なので、あなたは「優３割規定」に違反しないように成績をつけ直すことにしました。あなたは任意の学生の点数を 点に変えることができます。最低で何人の学生の点数を 点に変えれば「優３割規定」をみたすことができるか求めてください。

制約

• 
• 
• 入力はすべて整数

解説

「あなた」の目的は、「優３割規定」を満たすこと──つまり、 点以上の人数を全体の 以下に抑えることです。

点以上の人数は、 の数字をforループなどで全部見て数えればよいです。

上限人数は、全体の人数の なので、 です。このままだと「 人」のように小数になってしまって扱いづらいので、小数点以下を切り捨てて としておくとよいでしょう。

こうして求めた結果が 点以上の人数上限人数 となっていたら、最初から「優３割規定」を満たしているので何もする必要はなく、答えは になります。

問題は 点以上の人数上限人数 のときです。「優３割規定」を守るためには、 点以上の人数 を何とかして減らさなければなりません。ここで、学生の点数を 点に変える能力の出番です。このアビリティをある学生に使ったとき何が起きるのか、学生の元の点数に着目して考えてみましょう。

• 点以下：何も起こらない
• 点以上： 点以上の人数が 人減る

よって、この問題は「点以上の学生を好きなだけ減らすことができる。何人減らせば上限人数以下になるか」という問題であることが分かりました。これは 点以上の人数上限人数 で計算できます。

実装例

解説通りの実装例

import math

def solve():
    # input
    n = int(input())
    a = list(map(int, input().split()))

    # 80点以上の人数
    yu_cnt = 0
    for score in a:
        if score >= 80:
            yu_cnt += 1

    # 上限人数
    yu_max = math.floor(0.3 * n)

    # 答えの計算
    if yu_cnt <= yu_max:
        ans = 0
    else:
        ans = yu_cnt - yu_max

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

慣れた人向けの実装例

def solve():
    # input
    n = int(input())
    a = list(map(int, input().split()))

    yu_cnt = sum(x >= 80 for x in a)
    yu_max = n * 3 // 10

    ans = max(yu_cnt - yu_max, 0)

    # output
    print(ans)

t = int(input())
for _ in range(t): solve()

ちなみに、math.floor(0.3 * n) でぞわぞわする方もいるかもしれませんが、今回の制約で誤差は出ません。

ひとこと

原案でした。時期的にもセンシティブな「優３割規定」というテーマで問題を作ってしまい非常に申し訳ないと思っています。