AtCoder Beginner Contest 165 C - Many Requirements

解法

得点の計算方法が面倒で、賢い解き方はなかなか思い浮かびません。制約が小さいことに注目して全探索の方針を考えます。

制約上の最大値である $N=M=10$ で考えます。数列 $A$ としてあり得るものは、単純に見積もると $1$ 以上 $M$ 以下の整数が $N$ 個なので $M^{N} = 10^{10}$ 通り、これを全探索するのは厳しいです。ですが広義単調増加、つまり $A_{1} \le A_{2} \le \cdots \le A_{N}$ という条件によってこれがなんと $92378$ 通り であると計算できます。これなら全探索ができます。

その計算方法として、まず1つは後で「実装」のところで書くようなコードを実際に書いてしまってその個数を出力してみる、という方法があります。事前に見積もれていなくても、ダメ元で最大ケースを調べてみるのは良い戦略です。試しに計算してみてめちゃくちゃ多いようだったら別の方針に行けば良いので。

もう1つは数え上げの考え方を使います。以下の図にまとめました。

f:id:betrue12:20200502231759p:plain

このような考え方で、あり得る数列の個数は $_{N+M-1}C_{N}$ であることが分かります。手計算はつらいので Wolfram|Alpha に投げましょう。 $_{19}C_{10} = 92378$ であると計算してくれます。

実装

実際に $_{N+M-1}C_{N}$ 通りの数列を列挙する方法ですが、再帰で作ったり長さの小さいものから順番に作ったり、色々実装方針があります。私の実装を以下に貼ります。これは長さの小さいものから順番に作っていく方法です。

C++

// V[k] : 長さkである単調増加数列たち
vector<vector<int>> V[11];

// 初期値として長さ1のものを入れる
for(int i=1; i<=M; i++) V[1].push_back({i});

// V[k] から V[k+1] を作る
for(int i=1; i<N; i++) for(auto& v : V[i]){
    // 単調増加なので、末尾の値以上であるものを全て試す
    int b = v.back();
    for(int a=b; a<=M; a++){
        auto v2 = v;
        v2.push_back(a);
        V[i+1].push_back(v2);
    }
}
// V[N] に求めたいものが入っている

Python

# V[k] : 長さkである単調増加数列たち
V = [[] for _ in range(N+1)]

# 初期値として長さ1のものを入れる
for i in range(1, M+1):
    V[1].append([i])

# V[k] から V[k+1] を作る
for i in range(1, N):
    for v in V[i]:
        # 単調増加なので、末尾の値以上であるものを全て試す
        b = v[-1]
        for a in range(b, M+1):
            v2 = v + [a]
            V[i+1].append(v2)
# V[N] に求めたいものが入っている