2011/06/22

Supercon2011 参加記録

後輩と一緒にSupercon2011に参加しました。私は高校生ではないので、予選(認定問題)にしか応募資格がありません。認定証問題は3週間かけることが出来るのですが、忙しかったので全ては解けず、問題A,Bを解いたのみです。

問題はこちら(日本語です)。

簡単には、最短路問題です。したがって、ダイクストラ法を用いれば容易に解ける問題です。もしもう少し忙しくなく時間があれば問題Cを考え、アルゴリズムを改良するのですが、それができなかったのが心残りです。
A:パスカルの三角形の計算と同じことです。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main(int argc, char** argv) {
  int answer = -1; 
  int m, n;
  int D[200+1][200+1][4];
  char* problem_file;
  clock_t start, end;
  FILE* fp;

  int i, x, y;
  char buf[0xffff];
  char* p;

  if (argc <= 1) {
    fprintf(stderr, "Enter the input file.¥n");
    exit(EXIT_FAILURE);
  }

  problem_file = argv[1];
  fp = fopen(problem_file, "r");
  if (fp == NULL) {
    fprintf(stderr, "Cannot open %s.¥n", problem_file);
    exit(EXIT_FAILURE);
  }

  p = fgets(buf, 0xffff, fp);
  assert(p != 0);

  m = atoi(strtok(buf, ", ¥n"));
  n = atoi(strtok(NULL, ", ¥n"));
  assert(m > 0 && m <= 200);
  assert(n > 0 && n <= 200);
  for (y = 0; y <= n; y++) {
    p = fgets(buf, 0xffff, fp);
    assert(p != 0);
    p = strtok(buf, ", ¥n");
    for (i = 0; i < m; i++) {
      int length = atoi(p);
      assert(length >= 0 && length <= 1);
      D[i][y][1] = length;
      D[i+1][y][3] = length;
      p = strtok(NULL, ", ¥n");
    }
    D[0][y][3] = 0;
    D[m][y][1] = 0;
  }
  for (x = 0; x <= m; x++) {
    p = fgets(buf, 0xffff, fp);
    assert(p != 0);
    p = strtok(buf, ", ¥n");
    for (i = 0; i < n; i++) {
      int length = atoi(p);
      assert(length >= 0 && length <= 1);
      D[x][i][0] = length;
      D[x][i+1][2] = length;
      p = strtok(NULL, ", ¥n");
    }
    D[x][0][2] = 0;
    D[x][n][0] = 0;
  }

  fclose(fp);

   unsigned int data[51][51];
  int j;
  memset(data,0,sizeof(data));
  for(i=0;i<=m;i++){
    for(j=0;j<=n;j++){
      if(i==0 && j==0){
data[i][j]=1;
continue;
      }
      if(i!=0) data[i][j]+=D[i][j][3]*data[i-1][j];
      if(j!=0) data[i][j]+=D[i][j][2]*data[i][j-1];
    }
  }
  answer=data[m][n];
  
  printf("%s, %d¥n", problem_file, answer);
  return 0;
}


B:オーソドックスな最短路問題です。
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

int main(int argc, char** argv) {
  int answer_length = -1;
  int answer_number = -1;
  int m, n;
  int D[200+1][200+1][4];
  char* problem_file;
  clock_t start, end;
  FILE* fp;

  int i, x, y;
  char buf[0xffff];
  char* p;

  if (argc <= 1) {
    fprintf(stderr, "Enter the input file.¥n");
    exit(EXIT_FAILURE);
  }

  problem_file = argv[1];
  fp = fopen(problem_file, "r");
  if (fp == NULL) {
    fprintf(stderr, "Cannot open %s.¥n", problem_file);
    exit(EXIT_FAILURE);
  }

  p = fgets(buf, 0xffff, fp);
  assert(p != 0);

  m = atoi(strtok(buf, ", ¥n"));
  n = atoi(strtok(NULL, ", ¥n"));
  assert(m > 0 && m <= 200);
  assert(n > 0 && n <= 200);
  for (y = 0; y <= n; y++) {
    p = fgets(buf, 0xffff, fp);
    assert(p != 0);
    p = strtok(buf, ", ¥n");
    for (i = 0; i < m; i++) {
      int length = atoi(p);
      assert(length >= 0 && length <= 20);
      D[i][y][1] = length;
      D[i+1][y][3] = length;
      p = strtok(NULL, ", ¥n");
    }
    D[0][y][3] = 0;
    D[m][y][1] = 0;
  }
  for (x = 0; x <= m; x++) {
    p = fgets(buf, 0xffff, fp);
    assert(p != 0);
    p = strtok(buf, ", ¥n");
    for (i = 0; i < n; i++) {
      int length = atoi(p);
      assert(length >= 0 && length <= 20);
      D[x][i][0] = length;
      D[x][i+1][2] = length;
      p = strtok(NULL, ", ¥n");
    }
    D[x][0][2] = 0;
    D[x][n][0] = 0;
  }

  fclose(fp);

 struct{
    unsigned int dis;
    unsigned int num;
  } data[201][201];
  int j,k,l,flg;
  unsigned int mind,mink,minm,minn;
  
  memset(data,0,sizeof(data));
  data[0][0].dis=0;
  data[0][0].num=1;

  for(i=0;data[m][n].dis!=0 || i<=(m+1)*(n+1);i++){
    mind=2000000000;
    flg=0;
    for(j=0;j<=m;j++){
      for(k=0;k<=n;k++){
if(data[j][k].dis==0 && j+k!=0) continue;
for(l=0;l<=3;l++){
  if(D[j][k][l]==0) continue;
  if(data[j-(l-2)*(l%2)][k-(l-1)*((l+1)%2)].num!=0) continue;
  if(mind>D[j][k][l]+data[j][k].dis){
    mind=D[j][k][l]+data[j][k].dis;
    mink=data[j][k].num;
    minm=j-(l-2)*(l%2);
    minn=k-(l-1)*((l+1)%2);
    flg=1;
  }else if(mind==D[j][k][l]+data[j][k].dis){
    if(minm==j-(l-2)*(l%2) && minn==k-(l-1)*((l+1)%2)) mink+=data[j][k].num;
  }
}
      }
    }
    if(flg==0) break;
    data[minm][minn].dis=mind;
    data[minm][minn].num=mink;
  }
  
  answer_length=data[m][n].dis;
  answer_number=data[m][n].num;

  printf("%s, %d, %d¥n", problem_file, answer_length, answer_number);
  return 0;
}

0 件のコメント:

コメントを投稿