Kyo_s_s Homepage

第2回緑以下コン Writer記

競技プログラミング

コンテストページ: https://yukicoder.me/contests/471

D, K を作問しました。

D A_1 < A_2 < … < A_N

問題: A_1 < A_2 < … < A_N

正整数 $N, X$ が与えられます。 $N$ 個の正整数からなる数列 $A_1, A_2, \ldots, A_N$ であって、次の条件:

$0 < A_1 < A_2 < \cdots < A_{N-1} < A_N$
$\displaystyle \sum_{i=1}^N A_i = X$

をすべて満たすものが存在するか判定してください。存在するなら辞書順最小のものを1つ出力してください。 $T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

$1 \le T \le 10^5$
$1 \le N \le 2 \times 10^5$
$1 \le X \le 10^{18}$
1つのテストケースについて、それらの $N$ の総和は $2 \times 10^5$ 以下

灰diffの問題を作るのにあたり、

マルチテストケースに慣れてもらう
数列の辞書順というのを知ってもらう

ということを目的として考えた結果、この問題が生まれました。「先頭 $N - 1$ 個は $1, 2, ...$ で、最後は余ったもの」とすればよいです。灰diffでちょうどよいかなと思っています。

マルチテストケースの問題は、

int main() {
    int t;
    cin >> t;
    while (t--) {
        // solve
    }
}

として解くより、

void solve() {
    // solve
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
}

として解く方が // solve のインデントが浅くなり良い書き方だと思います。

K A_1 > A_2 > … > A_N

問題: A_1 > A_2 > … > A_N

正整数 $N, X$ が与えられます。 $N$ 個の正整数からなる数列 $A_1, A_2, \ldots, A_N$ であって、次の条件:

$A_1 > A_2 > \cdots > A_{N-1} > A_N > 0$
$\displaystyle \sum_{i=1}^N A_i = X$

$1 \le T \le 10^5$
$1 \le N \le 2 \times 10^5$
$1 \le X \le 10^{18}$
1つのテストケースについて、それらの $N$ の総和は $2 \times 10^5$ 以下

D問題の不等号逆verです。こういう制約が少し変わったものが後ろに置かれるのが個人的に好きなのですが、今回のセットで実現できてよかったです。

Dが先に作問されてから、Kの制約で解ける？みたいな話になり、無事解けて難易度も良い感じだったので Kに置かれました。

個人的には割とこういう問題は苦手意識があるのですが、この問題は小さいケースの愚直を書くと答えの構成が分かりそうだなと思います。

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

vector<int> solve5(int x) {
    for (int a1 = 1; a1 < x; a1++)  {
        for (int a2 = 1; a2 < a1; a2++) {
            for (int a3 = 1; a3 < a2; a3++) {
                for (int a4 = 1; a4 < a3; a4++) {
                    for (int a5 = 1; a5 < a4; a5++) {
                        if (a1 + a2 + a3 + a4 + a5 == x) {
                            return {a1, a2, a3, a4, a5};
                        }
                    }
                }
            }
        }
    }
    return {-1};
}

int main() {

    for (int x = 13; x <= 25; x++) {
        auto ans = solve5(x);
        cout << x << "\t: ";
        for (auto a: ans) cout << a << " ";
        cout << endl;
    }

}

13      : -1
14      : -1
15      : 5 4 3 2 1
16      : 6 4 3 2 1
17      : 6 5 3 2 1
18      : 6 5 4 2 1
19      : 6 5 4 3 1
20      : 6 5 4 3 2
21      : 7 5 4 3 2
22      : 7 6 4 3 2
23      : 7 6 5 3 2
24      : 7 6 5 4 2
25      : 7 6 5 4 3

この増え方からなんとなく推測するとよいなぁというのが想定です。実際これで良いことが証明できます、頑張って証明しました。

にぶたんでも解けるらしいです(解いていません)。

おわりに

いろいろなタスクを他の運営の方に投げてしまい、解説を書くのも他の問題に対して一番遅くなってしまったりで申し訳ありませんでした。もし第三回が開催されるなら(!?) もっといろいろタスクをこなしたいです。

Clarが飛んでこなかったのは良かったのですが、想定より多くの人が通していてびっくりです (Dを解いた後Kを見に行った人が一定数いたっぽい？)。難易度推定は難しいですね。

オンサイトの運営にかかわるのは初めてでしたが、無事多くの人に楽しんでもらえたようで良かったです。運営の皆さん、緑以下コンに参加してくれた方々ありがとうございました！