ferinの競プロ帳

競プロについてのメモ

speedrun001 FからL

F-見える数

読解が難しかったけど質問を見たらわかった。a[i]以前の最大の数がa[i]より小さければそのa[i]は見える。なので最大の数を保持して全てのa[i]を見ればできる。

G-あまり

10のa[i]の長さ乗を掛けたあとa[i]を足すを繰り返す。MODの取り忘れに注意。

H-LIS

LISでググってください。O(nlogn)で解ける。

I-和がNの区間

尺取り。今見ている区間の合計がn未満ならr+1, 今見ている区間の合計がnより大きければl+1する。

J-転倒数

転倒数でググってください。BITを使うとO(nlogn)で解ける。

K-辞書順で何番目?

a[i]の位置にa[i]未満の数が来るものの個数を合計すればいい。(a[i]より前で使っていないa[i]未満の数の個数) * (N-i-1)! を全てのa[i]について足し上げる。a[i]未満の数の個数はBITを使えばO(logN)で取得できる。

L-N回スワップ

1が1番目にいなかった場合、1と1番目の数を直接交換する以外1を1番目に持っていく方法はない。したがってiがi番目になければ適切な位置に持っていくのを繰り返すのが最適になる。 同じ位置について2回交換すれば元の位置関係に戻すことが出来、1回交換すると元の位置関係とは違うものになる。したがって最適な方法で交換したあとに、2の倍数回交換することができれば"YES"、そうでなければ"NO"となる。