codeforces #212 div2 C. Insertion Sort
問題ページ
Problem - C - Codeforces
概要
n要素の順列が与えられる。この順列に挿入ソートを行う。
この順列のどこか2要素をswapすることで挿入ソートでの交換回数を最小化しろ。
考えたこと
- ようするに転倒数を最小化すればいい
- i,j (i<j)を交換したとき転倒数はどう変化するか
- 区間[i+1,j-1]の数に対し影響する
- a[i]より大きい数の個数の分swap回数がプラス
- a[i]より小さい数の個数の分swap回数がマイナス
- a[j]より大きい数の個数の分swap回数がマイナス
- a[j]より小さい数の個数の分swap回数がプラス
- a[i]<a[j] ならswap回数が+1、a[i]>a[j]なら-1
- ある区間[l,r]でa[l]、a[r]より大きい数の個数を知りたい
- 転倒数と同様にBITでやれば出来そうだけどO(n^2logn)は通らなさそうな制約
- dp[l][r] = (区間[l,r]でa[l]より大きい数の個数) を前計算しておく
- 区間をずらしつつ条件を満たす数の個数を数えるとO(n^2)で実装でき通る
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; using VVI = vector<VI>; using PII = pair<int, int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) #define ALL(x) x.begin(), x.end() #define PB push_back const ll LLINF = (1LL<<60); const int INF = (1LL<<30); const int MOD = 1000000007; int dp[5010][5010]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); int n; cin >> n; VI a(n); REP(i, n) cin >> a[i]; int ret = n*(n-1)/2; REP(i, n) { FOR(j, i+1, n) { if(a[j] > a[i]) dp[i][j] = 1; } FOR(j, i+1, n) { dp[i][j] += dp[i][j-1]; } ret -= dp[i][n-1]; } int mi = INF, cnt = 1; REP(r, n) { int small = 0, big = 0; for(int l=r-1; l>=0; --l) { // vのうちa[l]より大きい数の個数 int tmp = 0; tmp += dp[l][r]; tmp -= r-l-1 - dp[l][r]; // vのうちa[r]より大きい数の個数 tmp += small; tmp -= big; if(a[l] > a[r]) tmp--; else tmp++; if(a[r] < a[l]) big++; else small++; if(mi > tmp) { mi = tmp; cnt = 1; } else if(mi == tmp) { cnt++; } } } cout << ret + mi << " " << cnt << endl; return 0; }