Yandex.Algorithm 2014 Round 2 D問題 - Inversions

Source

Yandex.Algorithm 2014
Yandex.Algorithm 2014 Round 2
問題文

問題概要

置換(要素数 $n$ の置換は $1,2,\ldots,n$ をちょうど $1$ つずつ含む)の中で転倒数が $K$ であるものを求める問題.
ただし,複数存在するので,要素数最小のものの中で,辞書順最小のものを求める.
置換 $p$ の転倒数は,$p_i > p_j, \;\; i < j$ を満たすペア $(i, j)$ の個数.

解法

要素数 $m$ の置換において,転倒数の最大値は $m (m-1) / 2$ なので,それが $K$ 以上となるような最小の $n$ を求める.
$n = O(\sqrt(K))$ なので愚直に $1$ から順番に試して行っても良い.
転倒数が $K$ で,辞書順最小の長さ $n$ の置換は $1$ 文字目からgreedyに確定していけば良い.
具体的には,今決めようとしている部分より後ろが,全て逆順であると仮定して,更に必要な転倒数を計算して,残っている整数の中からその必要転倒数番目の整数を使えば良い.
Fenwich treeなどを用いれば,残った整数の中の $x$ 番目みたいなのは高速に計算できる.
実際には,転倒数 $K$ は長さ $N-1$ の置換では達成できないぐらい大きいことから,もっと簡単に計算できる(が,以下のコードは愚直).

C++によるスパゲッティなソースコード

#include<bits/stdc++.h>
using namespace std;

#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

#define mygc(c) (c)=getchar_unlocked()
#define mypc(c) putchar_unlocked(c)

void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void writer(int x, char c){int i,sz=0,m=0;char buf[10];if(x<0)m=1,x=-x;while(x)buf[sz++]=x%10,x/=10;if(!sz)buf[sz++]=0;if(m)mypc('-');while(sz--)mypc(buf[sz]+'0');mypc(c);}

typedef struct struct_intfenwick{
  int size, memory;
  int *data;
}intFenwickTree;

intFenwickTree intFenwickTreeNew(int memory){
  intFenwickTree res;
  res.memory=memory; res.data=(int*)malloc(memory*sizeof(int));
  return res;
}

void intFenwickTreeDelete(intFenwickTree *t){free(t->data);}
void intFenwickTreeInit(intFenwickTree *t, int size){int i; t->size=size; rep(i,size) t->data[i]=0;}
void intFenwickTreeAdd(intFenwickTree *t,int k,int add){while(k<t->size)t->data[k]+=add, k|=k+1;}
int intFenwickTreeGet(intFenwickTree *t,int k){int res=0; while(k>=0)res+=t->data[k],k=(k&(k+1))-1; return res;}
int intFenwickTreeRange(intFenwickTree *t,int a,int b){return intFenwickTreeGet(t,b)-intFenwickTreeGet(t,a-1);}

int intFenwickTreeNthElement(intFenwickTree *t,int n){
  int a=0,b=t->size-1,k,d;
  k=intFenwickTreeGet(t,b);
  if(k <= n) return -1;
  while(b>a){
    k=(a+b)/2;
    d=intFenwickTreeGet(t,k);
    if(d>n) b=k; else a=k+1;
  }
  return a;
}

int K, N;
int res[1000000];

int main(){
  int i, j, k, need;
  intFenwickTree t = intFenwickTreeNew(1000000);

  reader(&K);
  for(N=1;;N++) if(N*(N-1)/2 >= K) break;
  intFenwickTreeInit(&t, N+100);
  REP(i,1,N+1) intFenwickTreeAdd(&t, i, 1);

  rep(i,N){
    need = K - (N-1-i)*(N-2-i)/2;
    K -= need;
    res[i] = intFenwickTreeNthElement(&t, need);
    intFenwickTreeAdd(&t, res[i], -1);
  }

  writer(N,'\n');
  rep(i,N) writer(res[i],i==N-1?'\n':' ');

  return 0;
}

Current time: 2017年07月23日17時31分37秒
Last modified: 2014年08月06日01時09分20秒 (by laycrs)
Tags: Competitive_Programming Yandex_Algorithm Yandex_Algorithm_2014 Yandex_Algorithm_2014_Round2
トップページに戻る

Logged in as: unknown user (not login)

ログイン: