どうして...
66:54 2完 + 1ペナ 980位
A Max Mod Min
直感的にはあまりをとるとかなり早いスピードで収束していきそうです
300点だし、とりあえず出すか！の精神でシミュレーションすると通ります
(AC 7:57)
B Swap to Sort
すべての元凶
こういう設定自体はよく見る問題で、操作Bではindexの偶奇が変わらないので、操作Aを最小限に使ってindexの偶奇を合わせるとよさそうです
たとえば{2,1,3,4}だと、2と1のindexがあっていないのでここを操作Aでswapさせればよさそうです
最終形を考えると、indexが{奇数,偶数,奇数 ... }となっていくことはわかります
つまり、「もしindexが違うなら、swapをすることで貪欲に直していく」ことがいいかなと思います
たとえば{1,5,3,7,8,6,2,4}なら、{1,8,5,6,3,2,7,4}という形を目指して
7を右に3回、3を右に2回、5を右に1回動かすといった具合です
が、これは嘘です
実は操作Bを使って{1,6,3,4,8,5,2,7}とした後に、8と5・2と7をswapすると操作Aが2回で終わります
偶奇が一致していないダメなやつをどこかに固めておき、そこをswapして1セットずつつぶしていくのが最善手となります
解説にもありましたが、「もしうまくできたとしてもK回かかる」というところを考えて、とりあえずその達成手段を考えた方がよかったのかもしれません
今回だと、1回のswapで偶奇がずれている2つを打ち消せるので、それが達成できるように検証するべきでした
偶奇がなおってしまえば、後は貪欲に操作Bでswapしていけばよいです
(AC 66:54)
C Min Sum Diff
思ったより解かれているので困ります
最適解がどのような形をするか考えます
要素がN個あるとして、そのうちN-1個を固定します
残った要素が左からN/2番目以下なら、できるだけ右に寄せるのがよさそうです
なぜなら、右に1ずらすと(右にある個数) - (左にある個数)だけコストが減少するからです
同様に考えると、真ん中にできるだけ集めるのが最善になりそうです
ということで、真ん中=Xを固定して考えます
その時のコストを以下の3つに分けて整理します
1. Xより左にあるものが、Xにあるものに対してかかるコスト
2. Xより右にあるものが、Xにあるものに対してかかるコスト
3. Xより左にあるものとXより右にあるもののコスト
これらは「左にあるものの個数」「左にあるものの座標の総和」「右にあるものの個数」「右にあるものの座標の総和」があると計算できるので、これを逐一差分計算していきます
実装が結構しんどいですが、こんな感じになります
デバッグやってたら間に合わなかった...
(AC 126:26)
総括
もう一回修行し直します
