C. Permutation Partitions (Codeforces Global Round 7)

問題

https://codeforces.com/contest/1326/problem/C

問題概要

長さnの順列pが与えられる。また1以上n以下の整数kが与えられる。与えられた順列をk個に分割した際、それぞれの区画の最大値の合計を最大化したい。

その合計値がいくつになるか答えよ。また、そうなるような分割の方法が何通りあるか答えよ。(で)

考察

k個に分けたそれぞれの区画に、順列の大きい方からk個の数値が別々に入るのが一番得で、これは該当する数値が出るたびに区切っていけば容易に達成可能です。この値は全体の合計から、上位k番目に入らない数の合計を引いたものなのでで求まります。

分割の仕方については、例えばk=2で{1, 5, 3, 2, 6, 4}という順列だったとして、5と3の間、3と2の間、2と6の間で区切ることが可能です。つまり上位k番目以内に入っている数に挟まれている部分のどこでも区切ることが可能で、この区切りがk-1個あってそれぞれの組み合わせになるので、それぞれの上位数同士の間隔をかけ合わせたものが実現可能な分割方法の個数になります。

#include <bits/stdc++.h>
using namespace std;

int main() {
    long long n, k;
    cin >> n >> k;
    long long p;
    vector<long long> q(k);
    int idx = 0;
    for (int i = 0; i < n; i++) {
        cin >> p;
        if (p > n - k) q[idx++] = i;
    }
    long long ans = 1;
    for (int i = 0; i < k - 1; i++) {
        ans *= q[i + 1] - q[i];
        ans %= 998244353;
    }
    cout << (n + 1) * n / 2 - (n - k) * (n - k + 1) / 2 << " " << ans << endl;
}

反省

最初、問題の意味が理解できなくて、飛ばしてDの考察に行ってしまったのでした。問題の意味さえわかってしまえば考察実装ともにとても楽というか、数え上げの基礎のような問題でした。そんなわけで、スコア的にとてももったいないことをしました。語学力よ・・・。