けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

キーエンス プログラミング コンテスト 2020 C - Subarray Sum (茶色, 400 点)

AtCoder AtCoder400点 気付き系 構築 パズル 茶色diff 制約条件:ちょうどK個

結構ギャグ要素強めな問題だった

問題へのリンク

問題概要

3 つの整数 N, K, S が与えられる。
長さ N の整数列 A_{0}, \dots, A_{N-1} であって、以下の条件を満たすものを構築せよ:

  • 1 \le A_{i} \le 10^{9}
  • A_{l} + \dots, A_{r} = S を満たすような (l, r) の組がちょうど K 個ある

制約

  • 1 \le N \le 10^{5}
  • 0 \le K \le N
  • 1 \le S \le 10^{9}

考えたこと

とりあえず一つ思うこととして、 A_{i} は全部 1 以上なので、 A の区間の左端を l で固定したとき、

  • A_{l} + \dots, A_{r} = S

を満たすような r は、もし存在するならば、ただ一通りだけ、ということがわかる。複数の r に対して A_{l} + \dots, A_{r} が同じ値になることはありえない。

ということで、そういう r が存在するような l がちょうど K 個になるようにすればいいんだ、ということになる。その最も簡単な場合というのは

  • A[0] = S (r = 0)
  • A[1] = S (r = 1)
  • ...
  • A[K-1] = S (r = K-1)

というような場合。こうしたとき、 l \ge K に対しては区間和が S にならないようにする必要があるので、残りは S+1 とかで埋めておくと安心できる。

ただし、 S = 1000000000 のときは S+1 は 10^{9} を超えてしまうので、その場合だけ 1 にすれば OK。

まとめると、以下の感じで OK。

  • S \lt 1000000000 のとき、 S, S, \dots, S, S+1, \dots, S+1　( S が K 個)

  • S = 1000000000 のとき、 S, S, \dots, S, 1, \dots, 1　( S が K 個)

#include <iostream>
using namespace std;

int main() {
    int N, K, S;
    cin >> N >> K >> S;
    int rem = S+1;
    if (rem > 1000000000) rem = 1;
    for (int i = 0; i < K; ++i) cout << S << " ";
    for (int i = K; i < N; ++i) cout << rem << " ";
    cout << endl;
}