Entries
codechef February 2011 Challenge 4問目
Problem Statement
February 2011 Challengeの参加記録
n個 (10以下) の正整数 x[k] が与えられる.
ある数字Zがx[k]の和で表せれるとは,
Z = (x[1]+x[1]+…) + (x[2]+x[2]+…) + …
と書けること,つまり,非負整数y[k]が存在して
Z = Σx[k]*y[k]
となること,である.
この問題でやるべきことは以下の2つ.
x[k]の和でかけない最大の正整数を求めること.ただし存在しないならそれを指摘する.
10^7個以下の整数が与えられ,それらの内,何個がx[k]の和で書けるか調べること.
x[k]はそれぞれ10^7以下で,x[k]の中に少なくても1つは10^5以下のものが存在する.
最小のx[k]をXと書くことにする.
aがx[k]の和で表せるなら,a+Xも当然x[k]の和で表すことができる.
よって,a = 0, 1, ..., X-1 に対して,a+m*Xがx[k]の和で表すことのできる最小のmを求めることを考える.
Z = a+m*X
が表せるなら,
(Z+x[k]) mod X + floor( (Z+x[k])/X ) * X
も表せるので,ノードaからノード(Z+x[k]) mod Xにコストfloor( (X+z[k])/X ) - mの枝を張る.
こうしてできたグラフ上でダイクストラすることで,全てのaについて,a+m*Xが表すことのできる最小のmが求まる.
後は適当にやるだけだが,タイムリミットの設定が微妙に厳しめなので,できるだけ効率のよいコードを書くと良い.
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
typedef struct struct_kdyenbxjdashd{
int node, nodeMemory;
int *edgeSize, *edgeMemory;
int **edge, **cost;
}ListGraphIntCost;
ListGraphIntCost NewListGraphIntCost(int maxNode,int maxDegree){
int i; ListGraphIntCost res;
res.node=0; res.nodeMemory=maxNode;
res.edgeSize = (int*)malloc(maxNode*sizeof(int));
res.edgeMemory = (int*)malloc(maxNode*sizeof(int));
res.edge = (int**)malloc(maxNode*sizeof(int*));
res.cost = (int**)malloc(maxNode*sizeof(int*));
if(maxDegree){
rep(i,maxNode) res.edge[i]=(int*)malloc(maxDegree*sizeof(int));
rep(i,maxNode) res.cost[i]=(int*)malloc(maxDegree*sizeof(int));
}
rep(i,maxNode) res.edgeMemory[i]=maxDegree;
return res;
}
void DeleteListGraphIntCost(ListGraphIntCost g){
int i;
rep(i,g.nodeMemory) { if(g.edgeMemory[i]) free(g.edge[i]), free(g.cost[i]);}
free(g.edgeSize); free(g.edgeMemory); free(g.edge); free(g.cost);
}
void ListGraphIntCostSetEmpty(ListGraphIntCost *g,int node){
int i;
g->node = node;
rep(i,node) g->edgeSize[i]=0;
}
void ListGraphIntCostAddEdge(ListGraphIntCost *g,int node1,int node2,int cost){
int s1=g->edgeSize[node1]++;
g->edge[node1][s1]=node2; g->cost[node1][s1]=cost;
}
void ListGraphIntCostAddBidirectedEdge(ListGraphIntCost *g,int node1,int node2,int cost){
int s1,s2;
if(node1==node2){
s1=g->edgeSize[node1]++;
g->edge[node1][s1]=node2; g->cost[node1][s1]=cost;
} else {
s1=g->edgeSize[node1]++, s2=g->edgeSize[node2]++;
g->edge[node1][s1]=node2; g->cost[node1][s1]=cost;
g->edge[node2][s2]=node1; g->cost[node2][s2]=cost;
}
}
/* edgeMemory[k]=sizeに変更する.中身のデータは破壊される. */
/* fg=1 ならば,すでにedgeMemory[k]>=sizeの場合は何もしない */
void ListGraphIntCostOneEdgeReallocEasy(ListGraphIntCost *g,int k,int size,int fg){
if(fg==1 && g->edgeMemory[k]>=size) return;
if(g->edgeMemory[k]==size) return;
if(g->edgeMemory[k]){ free(g->edge[k]); free(g->cost[k]); }
g->edgeMemory[k]=size;
g->edge[k] = (int*)malloc(size*sizeof(int));
g->cost[k] = (int*)malloc(size*sizeof(int));
}
/* g.nodeは既に設定済み,edgeのメモリが足りてない場合は適当にメモリ確保するぜ */
void ListGraphIntCostSetDirectEdges(ListGraphIntCost *g,int from[],int to[],int cost[],int size){
int i,n=g->node;
rep(i,n) g->edgeSize[i]=0;
rep(i,size) g->edgeSize[from[i]]++;
rep(i,n) {ListGraphIntCostOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
rep(i,size) ListGraphIntCostAddEdge(g,from[i],to[i],cost[i]);
}
/* g.nodeは既に設定済み,edgeのメモリが足りてない場合は適当にメモリ確保するぜ */
void ListGraphIntCostSetBidirectEdges(ListGraphIntCost *g,int from[],int to[],int cost[],int size){
int i,n=g->node;
rep(i,n) g->edgeSize[i]=0;
rep(i,size) g->edgeSize[from[i]]++, g->edgeSize[to[i]]++;
rep(i,n) {ListGraphIntCostOneEdgeReallocEasy(g,i,g->edgeSize[i],1); g->edgeSize[i]=0;}
rep(i,size) ListGraphIntCostAddBidirectedEdge(g,from[i],to[i],cost[i]);
}
void intHeapGoUp(int n,int hp[],int hpi[],int d[]){
int k,m;
if(!n) return;
m=(n-1)/2;
if(d[hp[m]]<=d[hp[n]]) return;
k=hp[m]; hp[m]=hp[n]; hp[n]=k;
hpi[hp[m]]=m; hpi[hp[n]]=n;
intHeapGoUp(m,hp,hpi,d);
}
void intHeapGoDown(int n,int hp[],int hpi[],int hp_size,int d[]){
int k,m;
m=2*n+1; if(m>=hp_size) return;
if(hp_size>m+1 && d[hp[m]]>d[hp[m+1]]) m++;
if(d[hp[m]]>=d[hp[n]]) return;
k=hp[m]; hp[m]=hp[n]; hp[n]=k;
hpi[hp[m]]=m; hpi[hp[n]]=n;
intHeapGoDown(m,hp,hpi,hp_size,d);
}
void intHeapInsert(int n,int hp[],int hpi[],int *hp_size,int d[]){
hp[*hp_size]=n; hpi[n]=(*hp_size)++;
intHeapGoUp((*hp_size)-1,hp,hpi,d);
}
int intHeapDelete(int hp[],int hpi[],int *hp_size,int d[]){
int r=hp[0]; hpi[r]=-1;
if( *hp_size==1 ){(*hp_size)--; return r;}
hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
intHeapGoDown(0,hp,hpi,*hp_size,d);
return r;
}
int in[12],in_size;
/* INF=unreachable=1000000000 */
void ListGraphIntCostDijkstra(ListGraphIntCost g,int st,int ed,int res[],void *WorkMemory){
int i,j,k,n=g.node,hp_size=0,c;
int *hp, *hpi;
hp = (int*) WorkMemory; WorkMemory = (void*)( hp + n );
hpi = (int*) WorkMemory; WorkMemory = (void*)( hpi + n );
rep(i,n) hpi[i]=-1, res[i]=1000000000; res[st]=0;
intHeapInsert(st,hp,hpi,&hp_size,res);
while(hp_size){
i = intHeapDelete(hp,hpi,&hp_size,res);
REP(j,1,in_size){
k=(i+in[j])%n;
c=res[i]+(i+in[j])/n;
if(res[k] <= c) continue; res[k]=c;
if(hpi[k]<0) intHeapInsert(k,hp,hpi,&hp_size,res);
else intHeapGoUp(hpi[k],hp,hpi,res);
}
}
}
int GCD(int a,int b){int r; while(a){r=b; b=a; a=r%a;} return b;}
void intSort(int d[],int s){int i=-1,j=s,k,t;if(s<=1)return;k=(d[0]+d[s-1])/2;for(;;){while(d[++i]<k);while(d[--j]>k);if(i>=j)break;t=d[i];d[i]=d[j];d[j]=t;}intSort(d,i);intSort(d+j+1,s-j-1);}
int dist[100100];
int main(){
int i,j,k,l,m,n,q,gcd;
ListGraphIntCost g = NewListGraphIntCost(100100, 20);
ll res; int res1, res2;
ll a,b,c,val,chk;
void *mem = malloc(4000000);
int size;
scanf("%d",&size);
while(size--){
scanf("%d",&n);
rep(i,n) scanf("%d",in+i);
scanf("%d%lld%lld%lld",&q,&a,&b,&c);
a %= c; b %= c;
in_size=n;
intSort(in,n);
gcd = in[0]; REP(i,1,n) gcd = GCD(gcd,in[i]);
rep(i,n) in[i] /= gcd;
m = in[0];
ListGraphIntCostSetEmpty(&g,m);
ListGraphIntCostDijkstra(g,0,-1,dist,mem);
res = -1;
rep(i,m) if(res < i+(ll)dist[i]*m-m) res = i+(ll)dist[i]*m-m;
if(gcd==1) printf("%lld\n",res); else puts("-1");
res1 = res2 = 0;
val = b;
rep(i,q){
val += a;
if(val>=c) val -= c;
if(val%gcd){res2++; continue;}
chk = val / gcd;
if(chk > res){res1++; continue;}
if(dist[chk%m] <= chk/m) res1++; else res2++;
}
printf("%d %d\n",res2,res1);
}
return 0;
}
コメント
コメントの投稿
トラックバック
- トラックバック URL
- http://rsujskf.blog32.fc2.com/tb.php/1898-5253892e
- この記事にトラックバックする(FC2ブログユーザー)