result:ooo-----
rate:1828->1831
日本語解説がないと嘘解放かどうかすらわかんない。
色々下手。
■A. Integer Diversity
abs(x)で管理
2つ以上あれば、+2
1つしか無いなら+1
ただし0は例外
■B. Mirror in the String
基本的に減少する文字列になればいい
???aと???abなら
???aa???
???abba???となるため
???aと???aaなら？
???aa???
???aaaa???となるが前者のほうが辞書順で小さくなるのは
??? = aa....aのときのみ。
■C. Representative Edges
適当にごちゃごちゃすると
等差数列になる必要がある。
不変な要素２つを選択する。
ただしサンプルにもある通り少数になる可能性があるので
交差=(a[j]-a[i])/(j-i)をx/yのように保持して分母を払って比較すると誤差が発生しない。
■D. Keep the Average High
とりあえずa[i]-xとするのは典型
セグメント木を用いてdpをしようとしていたが、よく考えると前から貪欲でいいので
貪欲に行う。
■E. Lexicographically Small Enough
Dより簡単に思えた。
sawpの回数=転倒数
前から順番に決めていく
s[t]をt[i]と一致させるかt[i]より小さいものにするか
swap元のidxは適当にqueで管理
転倒数はbitで管理する。
例
012を210にswapで作るには3回かかる。
{0,1}の未使用数=2-({0,1}の使用数)=2-0=2
{0}の未使用数=1-({0}の使用数)=1-0=1
{}の未使用数=0-({}の使用数)=0-0=0
みたくする。
■以下未読
