読者です 読者をやめる 読者になる 読者になる

よすぽコン2解説

よすぽコン2 解説

お疲れ様でした。

A 数列swap

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

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

  • 左のほうが大きい -> 反転数は-1
  • 要素の大きさは同じ -> 反転数は変化なし
  • 右のほうが大きい -> 反転数は+1

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

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

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

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

B LCM-Card

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

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

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

もっと高速化します

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

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

C 今日の典型データ構造

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

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

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

D チェックディギット

筋肉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回で通すことも可能です