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$ の置換では達成できないぐらい大きいことから,もっと簡単に計算できる(が,以下のコードは愚直).
#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: 2024年03月19日14時51分40秒
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)