fc2ブログ

Entries

February 2011 Challenge 4問目 - Glass Measurement (この記事を編集する[管理者用])

Source

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が求まる.
後は適当にやるだけだが,タイムリミットの設定が微妙に厳しめなので,できるだけ効率のよいコードを書くと良い.

C言語のスパゲッティなコード
#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ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)