保存されている過去のバージョンの一覧

2015年01月16日07時16分10秒

Codeforces Round #285 DIV1 B問題/DIV2 D問題 - Misha and Permutations Summation

Source

Codeforces Round #285 DIV1 B問題
Codeforces Round #285 DIV2 D問題
Problem description

問題概要

この問題では，要素数 $N$ の，$0$ から $N-1$ の置換を考える．
辞書順で $k$ 番目（$0$ オリジン，つまり最初は $0$ 番目）の置換を $P(k)$ と書き，置換 $p$ に対して，置換が辞書順で何番目かというのを $O(p)$ と書く．
（つまり，$O(P(k))=k, P(O(p)) = p$．例は問題原文参照）
$2$ つの置換 $A, B$ が与えられるので，$P((O(A)+O(B))\ {\rm mod}\ N!)$ を求める問題．

解法

まず，$O(A), \;\; A=A_0,A_1,\ldots,A_{N-1}$ の値を考える．
それぞれの最初の値 $A_0$ に対して，残りの部分の並び替え方は $(N-1)!$ 通りあるから，$O(A) = A_0 \times (N-1)! + {}$ 先頭を除いた残りの部分だけ考えた時に住所順で何番目か，となる．
それを再帰的に考えていくと，最初の要素から見ていってあげて，$A_k$ が $A_k,A_{k+1},\ldots,A_{N-1}$ の中で何番目（$0$ オリジン）かというのを $a_k$ とすると，$O(A) = a_0 (N-1)! + a_1 (N-2)! + \cdots + a_{N-1} 0!$ となる．
逆に，$O(A)$ の値から $A$ を作りたければ，先頭から見て行って，残っている整数の中で $a_k$ 番目の整数を $A_k$ に割り当てるということをすれば良い．
$O(A)$ の値を求めることと，$O(A)$ の値から $A$ を構成するのは，例えば，Fenwick treeなどを用いれば高速に行うことができる．
$O(A)+O(B)$ の値を求めるには，単純に桁ごとに足してあげて，$(k-1)!$ の桁が $k$ 以上になったら繰り上がりを行えば良い．
時間計算量は $O(N \log N)$ 程度（以下の実装は手抜きで $O(N (\log N)^2)$ になっている）．

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 READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}

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 s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
template<class T> void writerArr(T x[], int n){int i;if(!n){mypc('\n');return;}rep(i,n-1)writer(x[i],' ');writer(x[n-1],'\n');}

template<class T>
struct fenwick{
  int size, memory; T *data;
  void malloc(int mem){memory=mem;data=(T*)std::malloc(sizeof(T)*mem);}
  void *malloc(int mem, void *workMemory){memory=mem;data=(T*)workMemory;return (void*)(data+mem);}
  void free(void){memory=0;free(data);}
  void init(int N){size=N;memset(data,0,sizeof(T)*N);}
  void add(int k, T val){while(k<size)data[k]+=val,k|=k+1;}
  T get(int k){T res=0;while(k>=0)res+=data[k],k=(k&(k+1))-1;return res;}
  T range(int a, int b){if(b==-1)b=size-1;return get(b)-get(a-1);}
  int kth(T k){int i=0,j=size,c;T v;while(i<j){c=(i+j)/2;v=get(c);if(v<=k)i=c+1;else j=c;}return i==size?-1:i;}
};

int N;
int P[222222], Q[222222];

int res[222222];
int cnt[222222];

int main(){
  int i, j, k;
  void *mem = malloc(70000000);
  fenwick<int> t;

  reader(&N);
  rep(i,N) reader(P+i);
  rep(i,N) reader(Q+i);

  t.malloc(N);
  
  t.init(N);
  rep(i,N) t.add(i,1);
  rep(i,N){
    k = t.get(P[i]-1);
    cnt[N-1-i] += k;
    t.add(P[i], -1);
  }

  t.init(N);
  rep(i,N) t.add(i,1);
  rep(i,N){
    k = t.get(Q[i]-1);
    cnt[N-1-i] += k;
    t.add(Q[i], -1);
  }

  REP(i,1,N){
    cnt[i+1] += cnt[i] / (i+1);
    cnt[i] %= (i+1);
  }

  t.init(N);
  rep(i,N) t.add(i,1);
  rep(i,N){
    k = t.kth(cnt[N-i-1]);
    res[i] = k;
    t.add(k,-1);
  }

  writerArr(res,N);

  myed;
  return 0;
}

Current time: 2024年04月25日09時58分07秒
Last modified: 2015年01月16日07時16分10秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF285 CF_Div1_B CF_Div2_D
トップページに戻る

Logged in as: unknown user (not login)

ログイン：