ei1333の日記

ぺこい

Codeforces Round #421 (Div. 1)

xo— 246th.

A問題がアになってunrated.

B. Mister B and PR Shifts

codeforces.com

問題概要

長さ  {n(2 \le n \le 10^6)} の distinct な数列  {p_i(1 \le p_i \le n)} が与えられる.

数列を任意の回数循環シフトできる.

数列の偏差  {\sum_{i=1}^{n} |p_i - i|} の最小値を求めよ.

解法

偏差の式を眺めていると最初に  {t_i = p_i - i} に変換したくなる. このとき偏差は  {\sum_{i=1}^{n} |t_i|}.

ここで  {1} 回ずつ循環シフトしていく. この  {1} 回分の変化を数えて, 現在の偏差を動かす方針.

今までに  {k} 回シフトしたとする.

 {1} 回シフトは,  {t_i} 全体に  {-1} を加えて  {n-k} 番目に  {n+1} を加える操作だということが分かる.

 {-1} をすると, 現在の  {t_i} {0} 以下の個数だけ正に動き  {1} 以上の個数だけ負に動く. しかしこれだと現在の  {t_i} の更新に  {O(n)} かかってしまう.

全体に  {-1} する操作は, 基準を  {+1} していると思ってもよい. すると最初 {t_i} {i} 以下の個数だけ正に動き  {i+1} 以上の個数だけ負に動くということがわかる. この個数は簡単に数えることが出来るため, えいできる.

ソース

set 使って正負を管理していたら実装が出来ずにうし生終了したので, BIT使ったら簡単だった(実装前に実装の方針をつめて).

#include <bits/stdc++.h>

using namespace std;

typedef long long int64;

template< class T >
struct BinaryIndexedTree
{
  vector< T > data;

  BinaryIndexedTree(int sz)
  {
    data.assign(++sz, 0);
  }

  T sum(int k)
  {
    T ret = 0;
    for(++k; k > 0; k -= k & -k) ret += data[k];
    return (ret);
  }

  void add(int k, T x)
  {
    for(++k; k < data.size(); k += k & -k) data[k] += x;
  }
};


int main()
{
  int N, P[1000000];
  scanf("%d", &N);
  for(int i = 0; i < N; i++) scanf("%d", &P[i]), --P[i];

  int T[1000000];
  for(int i = 0; i < N; i++) T[i] = P[i] - i;


  int64 ret = numeric_limits< int64 >::max();
  int id;

  int64 now = 0LL;
  for(int i = 0; i < N; i++) now += abs(T[i]);

  BinaryIndexedTree< int > bit(N + N + N+1);
  for(int i = 0; i < N; i++) T[i] += N;

  for(int i = 0; i < N; i++) bit.add(T[i], 1);

  for(int i = 0; i < N; i++) {

    if(ret > now) {
      ret = now;
      id = i;
    }
    int base_line = i + N + 1;
    now += bit.sum(base_line - 1);
    now -= bit.sum(N + N + N) - bit.sum(base_line - 1);
    int get = T[N - i - 1];
    bit.add(get, -1);
    now -= abs(get - base_line);
    bit.add(get + N, 1);
    now += abs(N + get - base_line);
  }

  cout << ret << " " << id << endl;
}

けわしいなあ