Codeforces Round #672 感想
D解きたかった…
コンテスト前の話
動画見てたらコンテスト登録締め切り3分前だった。時間を勘違いしていたらしい。大急ぎでパソコンを起動してログインして参加登録した
Problem A
隣り合う要素のswapをn(n-1)/2-1回までしかできないとき、数列をソートできますか？
考察
- サンプルでは 2 1 ができないみたい
- swapが1回もできないからそれはそうだけど、これは逆順ソートされた数列
- 逆順ソートされてると不利そう
- よく考えたらバブルソートだね
- バブルソートの最悪交換回数はn(n-1)/2
- ようは最悪交換回数になりますかを判定する
- 最悪なのは完全に逆順にソートされている時
- それは数列が単調に減少しているときのみ
な場所があればYES
はソートされているとみなせるのでこれもYES側
- でなければNO
Problem B
以下の条件を満たす(i,j)のペアはいくつか
条件：i < jかつ
考察
- 後ろの条件意味不
- 小さい数を手元で実験して性質を調べる
- 2進数にした時の桁数が一致している時のみ条件が成立
- BITで殴ると
- いやそんなことないやろ（ぼく使えないし）
- 桁数ごとに個数を調べてnC2の総和
Problem C1
数列aの（連続でなくてよい）部分列bをとってb1-b2+b3-...を最大化せよ
考察
- まあDPでしょう
- dp1[i] = i番目まで見て最後にプラスしたときの最大
- dp2[i] = i番目まで見て最後にマイナスしたときの最大
- 更新は1個前と反対側の1個前±a[i]のmax
- なんかバグった、dp1はa[i]そのものがベストなことがある（そこがb1）
Problem D
n個のランプがある。時間[Li,Ri]の間ついている。同時に全部つくタイミングがあるランプk個の組合せはいくつあるか
考察
- 2項係数は前計算して高速に求められる前提
- 座圧してついてるランプの個数をimosで管理して時間を前から見ていく
- 多重にカウントすることがないようにランプが1個以上ついたタイミングのみに着目
- imosにその瞬間ついたランプの個数の情報も載せる（ここで計算量ミスがあった、後述）
- 各時刻で、ついているランプの数と今まさについたランプの数がわかってる
- ついているランプからk個選ぶ方法を数える、ただし今まさについたランプを1個以上使うもののみ
- 余事象をつかう
- nCk(ついてるランプ,k) - nCk(さっきからついてるランプ,k) の総和
計算量ミスについて
vector vについてcount(v.begin(),v.end(),x)はO(v.size())、これはsortを前提としていないためでsortしてても一緒
正解はsortしてequal_range
か、multisetでcount
