AGC 029
A
隣り合う要素をswapして数列をsortする最小回数は転倒数と呼ばれています
B
- 2で割れる回数でグループ分けして←いらない
- 大きい順にマッチしていく
という解法で解いた、1個目いらない
証明
xとマッチできる値たちのうち、x以下のものは1種類しかない、というのが本質
最大の値xとマッチできるyが存在しなかったらx消していい
存在したらx - yでマッチ作っていい(x - yを使わないマッチングがあったとしても、x - yを使うマッチングに変換できる、なぜならx - yを使わないならxはぼっちで、yはx以外の何かとマッチしている、よってy - 何かをばらしてx - yを足せばいい)
C
そもそもどういう文字列をつくっていけばいいか考える
二分探索をする
シミュレーション
D
E
実装を詰めなかったため、破滅
