スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Facebook Hacker Cup 2012 Round 2 C : Sequence Slicing

昔解けなかったやつ



数列 S[0...N-1] が与えられる。
これを用いて数列 MS[0...] を
MS[k] := S[k mod N] + N・floor(k/N)
と定義する。

区間 [0, R] に含まれる整数を一様ランダムに 2 つ選ぶ。( a, b とする )
MS[min(a,b)], MS[min(a,b)+1], .., MS[max(a,b)] に含まれる数の種類が K 種類以上になる確率はいくらか?
既約分数で求めよ。

・ 1 ≦ N ≦ 2000
・ 1 ≦ K ≦ R ≦ 10^9
・ 1 ≦ S[i] ≦ 10^5

解答

解けなかったので TopCoder のフォーラムに書かれていた解法を参考にした。

i = 0, 1, 2, ..., R に対して、
S[i...j] に含まれる数がちょうど K 種類となるような最小の jf(i) とおく。

この f を用いると、答えは
Σi=0, ..., R (R - f(i) + 1)
と書ける。

S の定義から明らかに
f(i+N) = f(i) + N
なので、
f(0), f(1), ..., f(N-1)
が計算できればいい。

j = f(i) は、
g(i,k) := S[i...k] に含まれる数の種類数
という関数を用意して、j について二分探索すれば求められる。
g は S[0], S[1], ..., S[N-1] を mod N で分類すれば、複数の区間の和集合の長さを求める問題と同じなので、O(N log N) で計算できる。

計算量は O(N^2 log N log R + R)。
+R は少し考えれば消せる。

ソースコード

#include<cstdio>
#include<algorithm>

#define rep(i,n) for(int i=0;i<(n);i++)

using namespace std;

typedef long long ll;

template<class T>
struct interval{
T a,b;
interval(){}
interval(const T &a,const T &b):a(a),b(b){}
bool operator<(const interval &I)const{ return a<I.a || a==I.a && b<I.b; }
};

ll gcd(ll a,ll b){ return b?gcd(b,a%b):a; }

// a[i..j] に含まれる異なる数の個数
ll calc(int n,int *a,int i,ll j){
int sz[2000]={};
static interval<ll> I[2000][2000];
rep(k,n){
ll left =i/n+(i%n<=k?0:1);
ll right=j/n-(k<=j%n?0:1);
int ofs=a[k]/n;
int idx=a[k]%n;
I[idx][sz[idx]++]=interval<ll>(left+ofs,right+ofs);
}

ll res=0;
rep(k,n){
sort(I[k],I[k]+sz[k]);

ll pre=0;
rep(l,sz[k]){
ll a=I[k][l].a,b=I[k][l].b;
pre=max(pre,a);
if(pre<=b){
res+=b-pre+1;
pre=b+1;
}
}
}
return res;
}

ll solve(int n,int K,int R,int *a){
if(K==1){
return (ll)(R+1)*(R+1);
}

ll ans=0;
rep(i,n){
ll lo=i,hi=R+1;
while(lo<hi){
ll mi=(lo+hi)/2;
if(calc(n,a,i,mi)<K) lo=mi+1; else hi=mi;
}

ll j=lo;
while(j<=R){
ans+=R-j+1;
j+=n;
}
}
ans*=2; // a と b を入れ替える分の重複度

return ans;
}

int main(){
int T; scanf("%d",&T);
for(int cas=1;cas<=T;cas++){
int n,K,R; scanf("%d%d%d",&n,&K,&R);
int a[2000];
rep(i,n) scanf("%d",a+i);

ll p=solve(n,K,R,a);
ll q=(ll)(R+1)*(R+1);
ll g=gcd(p,q);
printf("Case #%d: %lld/%lld\n",cas,p/g,q/g);
}

return 0;
}

スポンサーサイト

コメントの投稿

非公開コメント

プロフィール

fura2

Author : fura2
数学・コンピュータを中心に、考えたこと・やったことを書いていきます。

誤植等を含め、間違いはご指摘いただければ幸いです。

FC2カウンター
検索フォーム
最新記事
最新コメント
最新トラックバック
月別アーカイブ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。