https://atcoder.jp/contests/abc068/tasks/arc079_b

公式解説とは少しだけ違うやり方をしたので解説します。

問題

数列に対するある「操作」が定義されています。この操作は停止条件があります。

整数Kが与えられるので、ちょうどK回の操作で停止するような数列を作ってくださいという問題です。

難しいところ

操作自体はシンプルですが、K(操作回数)の最大値が0〜50*(10^16)とめちゃめちゃに大きくて、全体をシミュレーションすることはできないことが分かります。

解き方

まず、いちばん小さいNについて実際の数列を作って様子を見てみます。Nの最小値は2なので、長さ2の数列を考えます。停止条件は「全ての数が2未満」なので、例えば「1 1」は停止状態です。

1 1の前がどうなっていたか、を考えます。すると、2回おきに「2 2」「3 3」などゾロ目が出てくることに気づきます。

K=0  1 1
K=1  0 3
K=2  2 2
K=3  1 4
K=4  3 3
K=5  2 5
K=6  4 4

N=3のときも試してみると、3回おきにゾロ目が出てきます。

K=0  2 2 2
K=1  1 1 5
K=2  0 4 4
K=3  3 3 3
K=4  2 2 6
K=5  1 5 5
K=6  4 4 4

最大ケースを考える

次に、N=2やN=3でどこまで操作回数を伸ばせるのかを考えます。数列の要素aiは(10^16)+1000という最大値があるので、そのときの操作回数を考えます。

N=2のとき、「x x」というゾロ目が出てくるのはK=(x-1)*2のときです。

K=0  1 1
K=1  0 3
K=2  2 2
K=3  1 4
K=4  3 3
K=5  2 5
K=6  4 4
...
K=(x-1)*2  x x
...

ということはxが最大に近い(10^16)+1のとき、K=(10^16)*2 となります。これは最大入力にだいぶ近いですが、まだ足りませんね。Nを増やしましょう。

N=3のとき、「x x x」といゾロ目が出てくるのはK=(x-2)*3のときです。

N=50のとき、「x x x ... x」というゾロ目が出てくるのはK=(x-49)*50のときです。

ということはxが最大に近い(10^16)+49のとき、K=(10^16)*50となり、最大入力にも対応できることが分かりました。

N=50のときを考える

N=2のときは2個おき、N=3のときは3個おきにゾロ目が来るので、N=50のときは50個ごとにゾロ目が来ます。図にすると以下のようになります。

K=0  49 49 ... 49
...
K=50  50 50 ... 50
...
K=100  100 100 ... 100
...
...
K=(10^16)*50  (10^16)+49  (10^16)+49 ... (10^16)+49

やりたいのは与えられたKに対応する数列を返すことでした。上のような法則性により、Kが50で割り切れるときはゾロ目の数列を返せば良いことがわかります。

割り切れないときは、直近のゾロ目数列からスタートして手順を何回かシミュレーションします。ゾロ目は50個おきに存在するので、手順は多くとも49回やるだけです。これは十分に高速です。

回答

ということで私の回答(Ruby)です。

https://atcoder.jp/contests/abc068/submissions/4243975

K = gets.to_i

def sim(as, k)
  as.map.with_index{|a, i|
    i == k ? a-50 : a+1
  }
end

div, mod = K/50, K%50
x = 49 + div + 1
as = [x]*50
(50 - mod).times do |k|
  as = sim(as, k)
end

公式解説について

解説では「0 1 2 ... 49」という数列をK=0とすると、50個おきに「1 2 3 ... 50」「2 3 4 ... 51」のような階段状の並びが出てくるという性質を使っているようです。最初の数列が違うだけで、答えの出し方は同じですね。

どうも「全ての要素に1回ずつ操作を行うと全体が-1される」ということだったようです。なるほどなあ。https://www.hamayanhamayan.com/entry/2017/07/30/030601