AtCoder Beginner Contest 165 C - Many Requirements

C - Many Requirements

解説

単調増加列の数え上げですが、以下の考え方がわかりやすいです。

• maspyさん

単調増加数列の数え上げは、

・1 <= x < y < z <= N
binom(N,3) それはそう

・1 <= a <= b <= c <= N
x=a, y=b+1, z=c+2 とおくと、1<=x<y<z<=N+2 に対応
binom(N+2,3)

とやる方が好み。

— maspy (@maspy_stars) 2020年5月3日

• Ganmodokix さん

きのうのC pic.twitter.com/NRAoyZg0Tg

— Ganmodokix (@AprilGanmo) 2020年5月3日

• てんぷらさん

昨日のCの数の見積もり、｢単調増加のことを無視すると10^10だけど単調増加にしようと思うと(全部異なるなら)1/10!くらいになってこれなら3000しかない、等しいのがあるからそこまでは減らないけどかといって100万とかまでは増えへんやろ｣くらいが踏みやすい考察だと思っています

— てんぷら (@tempura_cpp) 2020年5月3日

とにかく、広義単調増加列を全て試していいことがわかるので、DFS等で列挙しましょう。

実装

int N, M, Q;
vector<ll> v;
vector<ll> a, b, c, d;
ll ans = 0;

ll solve(vector<ll> &x) {
    ll res = 0;
    rep(i, Q) {
        if (x[b[i]] - x[a[i]] == c[i]) {
            res += d[i];
        }
    }
    return res;
}

void dfs(int pre = 0) {
    if ((int) v.size() == N) {
        chmax(ans, solve(v));
        return;
    }
    for (int i = pre; i < M; i++) {
        v.push_back(i);
        dfs(i);
        v.pop_back();
    }
}

int main() {
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);
    cin >> N >> M >> Q;
    a.resize(Q);
    b.resize(Q);
    c.resize(Q);
    d.resize(Q);
    rep(i, Q) {
        cin >> a[i] >> b[i] >> c[i] >> d[i];
        a[i]--;
        b[i]--;
    }
    dfs();
    cout << ans << endl;
}