よすぽコン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回で通すことも可能です
