ばっちぃのは嫌！！！
汚いのは良くないですよね．不衛生は良くない．ほんとにね．
Typoraでインライン数式が使えません．だれか助けて
先に言っておきます．俺は解説を書いていない．
AGC053 A- >_<again
[良い非負整数列,整数列の分解]
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit...
WA
><again
submit
UWA!!!!!!!!!!!!!!!!!!
AC
まず，長さN+１の良い数列が渡されるから，それの大小関係を維持したまま，できるだけ多くの数列に分解してケロっていう問題ぺこ．
とりあえず，6 8 っていう良い数列(S は <)短い数列を考えたとき，<っていう条件を満たす一番ちっせえのは0<1ってなる．
で，B_0 = {0,1}にしてみると，数列Aの残りは{6,7}．B_1 = {0,1}にすると，数列Aの残りは{6,6}こうなると，もう良い数列は作れないから，B_0 = {0,1}, B_1 = {6,7}かあ．．．ってなった．
で，なんか
$$
X_i < X{i+1}
$$
っていう関係を満たす数列Bを一個作ったときに，数列Aの残りを見るとX_iとX_i+1の差は必ず縮まって，X_i = X_i+1になっちゃうと，これ以上は分解出来ない（っていうか，そうなった時点でアウトだから，厳密？には，X_i = X_i+1になる直前までしか分解出来ない).
$$
\begin {align}
&k = min(\abs {A_i - A{i+1}}) （0 \leqq i \leqq n-1)\
&数式あってるかな\
&まあなんか，隣合う2つの数の差の中で一番小さいもの個のBが作れるぜ！！みたいな感じ．
\end {align}
$$
俺は悪い競プロerだから証明はしないぜ
で，はいまぁ，良い非負整数列Aは，k個に分けれることがわかりました！！やった〜〜〜！！
で，こっからは答えを知っている俺がお話するんだけど…
int nokori = k; for(int i = 0; i < k; i++){ // B_i を出力する for(int j = 0; j <= n; j++){ //B_i[j]の出力 cout << A[i]/nokori << " "; A[i] -= A[i]/nokori; } cout << endl; nokori--; }
こんな感じで，分け分けしながら(A[i]/kのことを言っている)出力して行くと，うまく行くタピな．（たぴちゃん)
nokoriっていうのは，後何個B_iを出力するかってやつ(k個出力するから，最初はnokori k個出力するよ〜ってことでk)
- 良い非負整数列Aの要素n+1個を全て同じ数(nokori)で割ったものも良い非負整数列であるってマジ？
- A[i]/nokoriの切り捨てごねごねで条件(< や >)を満たせなくなっちゃわない？大丈夫?どっかでB_i[j] == B_i[j+1]になっちゃうんじゃないの？？
こんな感じなことが気になっちゃうと思うので(俺が今気になった )，そのへんがどうなのか考えながら書きなぐっていきます．
じゃあまず．1個目
良い非負整数列Aの要素n+1個を全て同じ数(nokori)で割ったものも良い非負整数列であるってマジ？
とりあえず前提？知識
$$
\begin {align}
& A < B &(A,Bは非負整数)\
& \Leftrightarrow \frac {A} {k} < \frac {B} {k} &(kは1以上の自然数)\&0が自然数かどうかはわしゃ知らん
\end {align}
$$
こういう大小関係あるじゃん，だから，まぁ，大小関係はいじできてるよねえ！！！って言いたい．言いたいけど，わかるよ，君ら（いや，俺）が気になってること.
$$
\begin {align}
& \frac {A} {k} = \frac{4}{3}は1.3だけど切り捨てられて1になる \
& \frac {B} {k} = \frac{5}{3}は1.6だけど切り捨てられて1になる．
\end {align}
$$
こんなときにA<Bの大小関係がA/k とB/kに当てはまらないよねえ．みたいな．こういうの気になるよね．
ちょっとAとかBとかｋって言うのが，問題文と一致していないから，問題文と一致させるね. $$ \begin{align} & A{i} < A{i+1} \ & \Leftrightarrow\frac {A{i}}{nokori} < \frac {A{i+1}}{nokori} \end{align} $$ そう．こんな感じで，良い整数列を同じ値で割っても大小変わらんよ．みたいなことを言いたいのね．
で，で，切り捨てで一緒になっちゃわない？大丈夫？って話なんだけど，まあ，「 ならない」んですよね．
最初のnokoriって言うのはk（Aがk個に分けれるよ〜のｋ)わけなんですが，このkっていう数字がそもそも何だったかっていうと
$$
\begin {align}
&k = min(\abs {A_i - A_{i+1}}) （0 \leqq i \leqq n-1)\
&これです．これ
\end {align}
$$
そう．これ．２つの項の差の最小値がkなわけなんです．
つまり，隣接する2項について，差はk以上あることが保証されている．ってことは，kで割った値が隣接する2項で一致するわけがない．
わかりますか？AとA+kをkで割ったときの商は一致しますか？しませんね！
そういうノリ．
次 nokori = k - 1になったときもうまく行くのか
どうなんでしょうね…
こっからは僕も声を小さくして数学者から隠れながらブログを投稿します
まぁ，多分，最初Aの中で，隣接する2項の差の最小値はkだったじゃん．で，今nokoriが1減ってk-1になったことで，隣接する2項の差の最小値はk-1になったと思うんよ．っていうか，そういう操作をしていないと，k個の答えの数列Bを出力出来ないしな．
で，答えを出力する過程は，下の感じ
- Aiをそれぞれnokoriで割ったものをBiとして出力
- Aiから出力したBiを引く（新しいAができる感じ)
- iを0~nまでやったらnokoriを-1
- 1に戻る
こんな感じ
nokori = k -1 になったときにうまくいくかっていうのは，「新しいAで，隣接する2項の差の最小値がk-1以上」であればいい．それは，さっき説明したAとA+kをｋで割った商が一致しないっていうのと同じ話．
まず，差がkだったところをA_iとA_{i+1}だとして見てみよう．(A_i < A_{i+1}っていう関係だったっていうていで話を聞いてね)
このとき，B_i + 1 = B_{i+1}になってます．だから，新しいA_i(上の２の手順のところ)とA_{i+1}の差は，kから1引いたk-1になってる．
よし，最初差が最小だったところについては，「新しいAで，隣接する２項の差がk-1以上」であることがわかった．
他に，A_iとA_{i+1}の差がkよりも大きいところを見てみよう．２項の差をKってしとくよ．
このときB_i + d = B_{i+1} みたいな関係が成り立っていることであろう．(dは1以上)．
新しいAはA_i -= B_i , A_{i+1} -= B_{i+1} ってなってるなあ…
A_{i+1}の右をちょっとばらしてみようか
A_{i+1} -= B_i + d
ふんふん，なるほど，A_{i+1}は新しくなる過程で，A_iよりもdだけ多く引かれているらしい．もともとの２項の差はKだったから，新しいAの２項の差はK-dになっているね．
このK-dが「k-1」よりも大きければ良い．で，このdっていうのがどうやって決まるかって言うと，BiはAiをnokori(今回はk)で割った値で決まる．A_iとA_{i+1}にkから2k-1の差があればd=1，2kから3k-1の差ならd=2って感じだよね.
ここまで言えば，隣接する２項の差がkより大きいやつは，新しいAで差がk-1以上だって言うことがなんとなくわかったんじゃないだろうか
これ以上ちゃんと伝えるのは俺の日本語力と俺自身の数学力と俺の論理的思考力的に無理だ．
