ABC068D - Strorkisのブログ

長さ $N$ の数列において、最大値の値を $N$ 減らすという操作を $K$ 回行うことにより、最大値が $N-1$ になるような数列を求めよという問題です。

$a_i$ に厳しめの制約がある為、 $N=50$ の場合を考えます。

私は、 $K$ が変化した場合に何を変化させれば良いのかを $K=0$ から順に考えました。

特に記述がない限り、 $a_i = 0$ とします。

$K=0$ の場合、 $a_0 = 49$ です。
最初から最大値が $N-1$ である必要があります。

$K=1$ の場合、 $a_0 = 99$ 、または、 $50 \leq a_0 < 99$ かつ $a_1 = 48$ です。
$a_0 = 99$ の場合は、 $a_0 - N$ によって最大値が $N-1$ になります。
$50 \leq a_0 < 99$ かつ $a_1 = 48$ の場合は、 $a_1 + 1$ によって最大値が $N-1$ になります。
$a_i$ の制約を考えると、後者の方が良さそうです。

同じように考えると、 $K=2$ の場合、 $a_0 = 50, a_1 = 49, a_2 = 47$ であれば良いことがわかります。

つまりは、49から0までの数列を作っておき、左側からKの値だけインクリメントして行けば良さそうです。

では、一番右まで行ってしまった場合、つまり $K=51$ の場合はどうすれば良いでしょうか。

結論としては、 $K=50$ の時点で、 $a_0=a_0-N+(N-1)$ となっているため、 $a_0$ をインクリメントすれば良いです。

つまりは、一番左に戻れば良いという事ですね。

ただ、1ずつインクリメントするのは明らかにTLEするので、実装では各 $a_i$ において、 $K \div N$ を足した後、 $K\ mod\ N$ だけ左側からインクリメントしています。

/* typedef long long ll; */

  ll k; cin >> k;
  int n = 50;
  vector<ll> a(n);
  for (int i = 0; i < n; i++) a[i] = n - 1 - i + k / n;
  for (int i = 0; i < k % n; i++) a[i]++;

  cout << n << endl << a.front();
  for (int i = 1; i < n; i++) cout << " " << a[i];
  cout << endl;

説明難しい。