ferinの競プロ帳

競プロについてのメモ

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;
}