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

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

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

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

問題へのリンク

問題概要

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;
}