xo— 246th.
A問題がアになってunrated.
B. Mister B and PR Shifts
問題概要
長さ の distinct な数列 が与えられる.
数列を任意の回数循環シフトできる.
数列の偏差 の最小値を求めよ.
解法
偏差の式を眺めていると最初に に変換したくなる. このとき偏差は .
ここで 回ずつ循環シフトしていく. この 回分の変化を数えて, 現在の偏差を動かす方針.
今までに 回シフトしたとする.
回シフトは, 全体に を加えて 番目に を加える操作だということが分かる.
をすると, 現在の が 以下の個数だけ正に動き 以上の個数だけ負に動く. しかしこれだと現在の の更新に かかってしまう.
全体に する操作は, 基準を していると思ってもよい. すると最初の が 以下の個数だけ正に動き 以上の個数だけ負に動くということがわかる. この個数は簡単に数えることが出来るため, えいできる.
ソース
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; }
けわしいなあ