ver.)2019-02-12Techhttps://atcoder.jp/contests/abc068/tasks/arc079_b公式解説とは少しだけ違うやり方をしたので解説します。数列に対するある「操作」が定義されています。この操作は停止条件があります。整数Kが与えられるので、ちょうどK回の操作で停止するような数列を作ってくださいという問題です。難しいところ操作自体はシンプルですが、K(操作回数)の最大値が0〜50*(10^16)とめちゃめちゃに大きくて、全体をシミュレーションすることはできないことが分かります。解き方まず、いちばん小さいNについて実際の数列を作って様子を見てみます。Nの最小値は2なので、長さ2の数列を考えます。1の前がどうなっていたか、を考えます。3」などゾロ目が出てくることに気づきます。4N=3のときも試してみると、3回おきにゾロ目が出てきます。4最大ケースを考える次に、N=2やN=3でどこまで操作回数を伸ばせるのかを考えます。数列の要素aiは(10^16)+1000という最大値があるので、そのときの操作回数を考えます。x」というゾロ目が出てくるのはK=(x-1)*2のときです。これは最大入力にだいぶ近いですが、まだ足りませんね。x」といゾロ目が出てくるのはK=(x-2)*3のときです。x」というゾロ目が出てくるのはK=(x-49)*50のときです。いうことはxが最大に近い(10^16)+49のとき、K=(10^16)*50となり、最大入力にも対応できることが分かりました。N=50のときを考えるN=2のときは2個おき、N=3のときは3個おきにゾロ目が来るので、N=50のときは50個ごとにゾロ目が来ます。図にすると以下のようになります。(10^16)+49やりたいのは与えられたKに対応する数列を返すことでした。上のような法則性により、Kが50で割り切れるときはゾロ目の数列を返せば良いことがわかります。割り切れないときは、直近のゾロ目数列からスタートして手順を何回かシミュレーションします。ゾロ目は50個おきに存在するので、手順は多くとも49回やるだけです。これは十分に高速です。回答ということで私の回答(Ruby)です。51」のような階段状の並びが出てくるという性質を使っているようです。最初の数列が違うだけで、答えの出し方は同じですね。「全ての要素に1回ずつ操作を行うと全体が-1される」ということだったようです。authorTwitterGitHub。