よすぽコン2解説 - よすぽの日記

お疲れ様でした。

最初の数列の反転数をXとすると答えは max(X-K, 0) です

隣り合う要素を交換する時

となりますまた、全ての隣り合う要素について

右のほうが大きい or 要素の大きさは同じ

となるとき、その数列はソートされていますなので当然反転数は0です

以上より, 反転数が0でなければ操作ごとに反転数を-1出来るため、答えは max(X-K, 0) です

dp[i][j][x] = i枚目まで考えている, j枚引いていて, それらのlcmがxである

という動的計画法を高速化します

xはXの約数だけ考えればOKです。これで多分通るかなぁ

もっと高速化します

Xの素因数の種類はO(logX)個です具体的に計算すると最大で13種類です

xとXは、素因数の種類ごとに同じ個数あるかどうかだけ保存すればOKですこれでxの種類は2^{素因数の種類}に落ちます

適当にTLE決めたら厳しかったっぽいですねあとジャッジキューを破壊した

想定解放はO(Nsqrt(N))です

行ごとに0でない要素数を数えて, sqrt(N)を超えたら行だけは個別に計算すればOKです

筋肉FA:antaさん No筋肉FA:sugim

下5桁の数字についてA_1,A_2,A_3,A_4,A_5とすると

(A_1 * 3 + A_2 * 4 + A_3 * 5 + A_4 * 6 + A_5 * 7) % 11 % 10

らしいです

%11は気づきませんね

ちなみに表には入ってないけど去年第五類という人の学籍番号が1つだけ入っています

なので規則を知らなくても期待値5回で通すことも可能です