Entries

スポンサーサイト (この記事を編集する[管理者用])

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

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1754-1ec3cb3f
この記事にトラックバックする(FC2ブログユーザー)

December 2010 Challenge (この記事を編集する[管理者用])

2010年12月01日18時から10日間,6問.(1問はマラソン形式)
[LINK]

アルゴリズム問題を4問解いて,マラソン問題は適当にサブミット.
以下,大体の行動.

まずはざっと問題を眺める.
 A String Gameはすぐ解ける.
 Byteknights and Byteknavesは辞書順最小を求めるのが怪しいが多分解ける.
 Delivering Breadはマラソン問題.後回しでOK.
 Even Coefficientsはわからない.
 Odd Binomial Coefficientsもわからない.
 The Hungry Bearは解けそうだが,よくわからない.
まぁ,書いてみようか.
 A String GameはGrundy数求めるだけ.書く.Accept.
 The Hungry Bearも,x座標の範囲はO(n^2)で全部調べるとして,あとは尺取メソッドで行けることに気づく.
  書く.Accept.
 Byteknights and Byteknavesは…,segment treeを使えば,辞書順最小をO(n log n)で求めれることに気づいた.
  書く.TLE.えー.
  ローカルで実行するとたしかに時間かかる….
  答えが少ないときは,全部愚直に調べてみる.Accept.えー.
  答えが少なくない時も全部愚直に調べる.O(n^2).Accept.しかもさっきより早い.えーえーえー.
  まぁ,通ったからいいか….
すぐ解けそうなのは終わった.
Odd Binomial Coefficientsを考える.
 うーん.問題サイズ的には包除原理っぽいんだが.
 そもそも,項の数が1個の時の答えがわからない.
 調べる.
 ほう.
 どうやら,べきを2進数で表したときの1のビット数をXとして,2^Xが答えなのか.
 で,さらに調べると….
 2個の項が合ったとして,両方共,奇数になる項の数は,べきを2進数でANDを取った時の1のビット数をXとして,2^X.
 綺麗過ぎる.
 じゃ,包除原理で行ける.
 書く.TLE.えーえーえーえーえー.
 なんでcodechefってこんなにタイムリミット厳しいの….
 DPして,オーダーを1つ落とす.Accept.
Even Coefficientsがわからないので,Delivering Breadを適当にサブミット.
これも,微妙にタイムリミットが厳しいし,うまい方法もわからない.
まぁ,Even Coefficientsが解けない限り,Delivering Breadを解いても大して意味はないので,とりあえず保留.
なんかリジャッジが来た!
 Byteknights and Byteknavesが全部TLEになってる….
 まぁ,O(n^2)が通ったらそれはそれでダメな気がするし.
 うーん.とりあえず,どうやって辞書順最小を求めるのか,が問題.
 segment treeじゃなくて,Fenwick treeでできないかな…?
 できそうな気がしてきた.書いた.駄目じゃんこれ最悪でO(n^2 log n)じゃん.却下.
 うーん.
 リスト構造みたいなのを作って頑張る.
 オーダー見積もれないけど速そう.サブミット.Accept.
Even Coefficientsは….
 うーん,適当に変数に何か代入してすべて偶数になるかどうかを調べれば….
 と思ったら,サンプルの1個目が反例.
 わからなかった.

A String Gameの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 N 100

int is_same(char a[],char b[],int len){
  int i;
  rep(i,len) if(a[i]!=b[i]) return 0;
  return 1;
}

int get_len(char a[]){
  int i;
  for(i=0;;i++) if(a[i]<' ') break;
  return i;
}

int n;
char in[40]; int len;
char dic[40][40]; int dic_len[40];
int dp[40][40];

int solve(int st,int ed){
  int i,j,k;
  int a,b;
  int ar[N];

  if(st>ed) return 0;
  if(dp[st][ed]>=0) return dp[st][ed];
  
  rep(i,N) ar[i]=0;

  rep(k,n) REP(i,st,ed-dic_len[k]+2) if(is_same(in+i,dic[k],dic_len[k])){
    a = solve(st,i-1);
    b = solve(i+dic_len[k],ed);
    a ^= b;
    if(a<N) ar[a]=1;
  }

  rep(i,N) if(ar[i]==0) break;
  return dp[st][ed]=i;
}

int main(){
  int i,j,k,l,m;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%s%d",in,&n);
    rep(i,n) scanf("%s",dic[i]);
    len = get_len(in);
    rep(i,n) dic_len[i] = get_len(dic[i]);

    rep(i,len) rep(j,len) dp[i][j]=-1;
    k = solve(0,len-1);
    if(!k) puts("Tracy"); else puts("Teddy");
  }

  return 0;
}
Byteknights and Byteknavesの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)

int ok[51000], next[51000];

int get_next(int a){
  int res;
  if(next[a] == a) return a;

  res = get_next(next[a]);
  return next[a] = res;
}

void go_del(int a){
  ok[a] = 0; next[a] = next[a+1];
}

int main(){
  int i,j,k,l,m,n,res,gogo;
  int a[51000], b[51000], add[51000];
  char go[51000], tmp[51000];
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    rep(i,n) scanf("%d%d",a+i,b+i);

    rep(i,n+1) add[i] = 0;
    rep(i,n) add[a[i]]++, add[b[i]+1]--;

    k = 0;
    rep(i,n+1){
      k += add[i];
      if(i==k) ok[i]=1; else ok[i]=0;
    }

    res=0;
    rep(i,n+1) res += ok[i];
    printf("%d\n",res);

    if(res<0){
      rep(i,n) go[i]=1;
      rep(k,n+1) if(ok[k]){
        gogo=0;
        rep(i,n){
          if(a[i]<=k && k<=b[i]) tmp[i]=1; else tmp[i]=0;
          if(gogo==0 && tmp[i]>go[i]){gogo=-1; break;}
          if(gogo==0 && tmp[i]<go[i]) gogo=1;
        }
        if(gogo==1) rep(i,n) go[i]=tmp[i];
      }
    } else {
      next[n+1] = n+1;
      for(i=n;i>=0;i--){
        next[i] = next[i+1];
        if(ok[i]) next[i] = i;
      }
      rep(i,n){
        k = get_next(0); l = get_next(b[i]+1);
        if(k>=a[i] && l==n+1){
          go[i] = 1;
        } else {
          go[i] = 0; k = get_next(a[i]);
          while(a[i]<=k && k<=b[i]){
            go_del(k); k = get_next(k);
          }
        }
      }
    }
    rep(i,n) go[i]+='0'; go[n]='\0';
    puts(go);
  }
  
  return 0;
}
Delivering Breadの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 RAND (rand()/(RAND_MAX+1.0))
#define ll long long

typedef struct struct_kdyenbxjdashd{
  int node, nodeMemory;
  int *edgeSize, *edgeMemory;
  int **edge; int **cost;
}ListGraphLlCost;


ListGraphLlCost NewListGraphLlCost(int maxNode,int maxDegree){
  int i; ListGraphLlCost 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(ll*));
  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 DeleteListGraphLlCost(ListGraphLlCost 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 ListGraphLlCostSetEmpty(ListGraphLlCost *g,int node){
  int i;
  g->node = node;
  rep(i,node) g->edgeSize[i]=0;
}

void ListGraphLlCostAddEdge(ListGraphLlCost *g,int node1,int node2,int cost){
  int s1=g->edgeSize[node1]++;
  g->edge[node1][s1]=node2; g->cost[node1][s1]=cost;
}

void ListGraphLlCostAddBidirectedEdge(ListGraphLlCost *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;
  }
}

void llHeapGoUp(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;
  llHeapGoUp(m,hp,hpi,d);
}

void llHeapGoDown(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;
  llHeapGoDown(m,hp,hpi,hp_size,d);
}

void llHeapInsert(int n,int hp[],int hpi[],int *hp_size,int d[]){
  hp[*hp_size]=n; hpi[n]=(*hp_size)++;
  llHeapGoUp((*hp_size)-1,hp,hpi,d);
}

ll llHeapDelete(int hp[],int hpi[],int *hp_size,int d[]){
  ll r=hp[0]; hpi[r]=-1;
  if( *hp_size==1 ){(*hp_size)--; return r;}
  hp[0]=hp[--(*hp_size)]; hpi[hp[0]]=0;
  llHeapGoDown(0,hp,hpi,*hp_size,d);
  return r;
}


int n, LIM;

/* INF=unreachable=1000000000000000000LL */
void ListGraphLlCostDijkstra(ListGraphLlCost g,int st,int res[],int back[],void *WorkMemory){
  int i,j,k,n=g.node,hp_size=0; int c, cnt=0;
  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]=LIM+1; res[st]=0;
  llHeapInsert(st,hp,hpi,&hp_size,res);
  while(hp_size){
    i = llHeapDelete(hp,hpi,&hp_size,res);
    rep(j,g.edgeSize[i]){
      k=g.edge[i][j]; c=res[i]+g.cost[i][j];
      if(res[k] <= c) continue;
      res[k]=c; back[k]=i;
      if(hpi[k]<0) llHeapInsert(k,hp,hpi,&hp_size,res);
      else         llHeapGoUp(hpi[k],hp,hpi,res);
    }
  }
}

void intIntSort(int d[],int m[],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;t=m[i];m[i]=m[j];m[j]=t;}intIntSort(d,m,i);intIntSort(d+j+1,m+j+1,s-j-1);}


#define INF 1000000001

int total_score = 0;

int dist[301][301]; int route[301][301][301], route_size[301][301];
int res[100000], res_size, res_score;
int now[100000], now_size, use[301], now_score;
int cnt;

int val[301][301], ind[301][301], stc[301][301];

void score_renew(){
  int i;
  if(res_score >= now_score) return;
  res_score = now_score;
  res_size  = now_size;
  rep(i,res_size) res[i] = now[i];
}

void solve(int node, int tm){
  int i,j,k;
  int sz, bef, stt, iid;

  if(cnt++ > 400){
    score_renew();
    return;
  }

  bef = now_size;
  sz = 0;
  
  rep(i,n) if(!use[i]){
    if(tm + dist[node][i] > LIM) continue;
    val[now_score][sz] = dist[node][i], ind[now_score][sz] = i, sz++;
  }
  intIntSort(val[now_score],ind[now_score],sz);

  if(sz==0){
    score_renew();
    return;
  }

  if(sz>3) sz=3;
  k = (int) (RAND * sz);
  k = (int) (RAND * k );
  k = ind[now_score][k];

  iid = now_score; stt = 0;
  rep(i,route_size[node][k]){
    j = route[node][k][i];
    now[now_size++] = j;
    if(use[j]==0) use[j]=1, now_score++, stc[iid][stt++]=j;
  }

  solve(k, tm+dist[node][k]);

  rep(i,stt) use[stc[iid][i]]=0, now_score--;
  now_size = bef;
}

int main(){
  int i,j,k,l,m,loop;
  int cost[301]; int back[301];
  void *mem = malloc(9000000);
  int size;

  ListGraphLlCost g = NewListGraphLlCost(310, 310);
  srand(time(NULL));

  scanf("%d",&size);
  while(size--){
    scanf("%d%d%d",&n,&m,&LIM);
    ListGraphLlCostSetEmpty(&g,n);
    while(m--){
      scanf("%d%d%d",&i,&j,&k);
      ListGraphLlCostAddEdge(&g,j,i,k);
    }

    rep(i,n) rep(j,n) dist[i][j] = INF;
    rep(i,n){
      ListGraphLlCostDijkstra(g,i,cost,back,mem);
      rep(j,n) if(j!=i){
        if(cost[j] > LIM) continue;
        dist[j][i] = cost[j];
        route_size[j][i] = 0;
        k = j;
        while(k!=i){
          k = back[k];
          route[j][i][route_size[j][i]++]=k;
        }
      }
    }

    res_size = 0; res_score = 1;

    rep(loop,8){
      cnt = 0;
      now_size = 0; now_score = 1;
      rep(i,n) use[i]=0; use[0]=1;
      solve(0, 0);
    }

    if(res_size >= 10000) res_size = 9999;
    rep(i,res_size) printf("%d ",res[i]); puts("-1");
    total_score += res_score;
  }

/*  printf("---- total score = %d\n",total_score);*/

  return 0;
}
Odd Binomial Coefficientsの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

int bit_count(ll a){
  int res=0;
  while(a) res++, a&=(a-1);
  return res;
}

int main(){
  int i,j,k,l,m,n;
  ll in[16], res, go;
  int bc[100000];
  ll cof[16], comb[20][20];
  ll dp[100000];
  int inv[100000], bt;
  int size;

  bc[0]=0;
  REP(i,1,1<<16) bc[i]=bc[i&(i-1)]+1;
  rep(i,16) inv[1<<i]=i;

  comb[0][0]=1; REP(j,1,20) comb[0][j]=0;
  REP(i,1,20){
    comb[i][0]=1; REP(j,1,20) comb[i][j]=(comb[i-1][j-1]+comb[i-1][j]);
  }

  cof[0]=cof[1]=1;
  REP(i,2,16){
    go = 0;
    REP(j,1,i) go += cof[j] * comb[i][j];
    if(i%2) res=1; else res=0;
    cof[i] = res-go;
  }

  scanf("%d",&size);
  while(size--){
    scanf("%d",&n);
    rep(i,n) scanf("%lld",in+i);

    rep(i,n) dp[1<<i] = in[i];
    REP(k,1,1<<n) if(bc[k]>=2){
      m = k; bt = (m&(-m)); m ^= bt; dp[k] = in[inv[bt]];
      dp[k] &= dp[m];
    }
    
    res=0;
    REP(k,1,1<<n){
      m = bit_count(dp[k]);
      res += (1LL<<m) * cof[bc[k]];
    }

    printf("%lld\n",res);
  }

  return 0;
}
The Hungry Bearの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)

int x,y,k;
char mp[310][310];
int res[310][310];
int ar[310];

int main(){
  int i,j,l,m,n,q;
  int st,ed;
  int a,b;

  scanf("%d%d%d",&x,&y,&k);
  rep(i,x) scanf("%s",mp[i]);

  rep(i,x+1) rep(j,y+1) res[i][j]=0;

  rep(st,x){
    rep(i,y) ar[i]=0;
    REP(ed,st,x){
      rep(i,y) if(mp[ed][i]=='H') ar[i]++;
      a=0; b=0; m=0;
      for(;;){
        while(m<k && b<y) m+=ar[b], b++;
        if(m<k) break;
        res[ed-st+1][b-a]++;
        res[ed-st+1][y-a+1]--;
        m-=ar[a]; a++;
      }
    }
  }

  rep(i,x+1) REP(j,1,y+1) res[i][j]+=res[i][j-1];
  rep(i,x+1) REP(j,1,y+1) res[i][j]+=res[i][j-1];
  REP(i,1,x+1) rep(j,y+1) res[i][j]+=res[i-1][j];

  scanf("%d",&q);
  while(q--){
    scanf("%d%d",&i,&j);
    printf("%d\n",res[i][j]);
  }

  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1754-1ec3cb3f
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。