読者です 読者をやめる 読者になる 読者になる

supercon 2011

programming

最短距離と経路の数を別々にやってる人が多いっぽい?
自分は同時にやった。


ソース

/* SuperCon 2011 予選問題C用テンプレート
   ・解答プログラムはこのテンプレートに従って作成すること.
  ・解答プログラムは1つのファイルで,チーム名.c という名前にすること.
  ・入力の方式は,あらかじめ入力ファイル(例:input_sample.txt)を作っ
   ておき,実行時にファイル名を指定する方式です.
*/

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

/* ↓以下の範囲は変更可能 */

#define MAX_M 200
#define MAX_N 200
#define MAX_K 200
#define MAX_DIS 21      //20+1
#define MAX_PO 40401    //(M+1)*(N+1)

struct route{
	int dis, sz;
	unsigned char vx[MAX_PO], vy[MAX_PO];
}rlen[MAX_DIS];

struct point{
	int th, kdis;
	int pdis[MAX_DIS] ,pat[MAX_DIS];
}po[MAX_M+1][MAX_N+1];


const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0};


int ri, M2, N2;
char used[MAX_M+1][MAX_N+1];


char dfs(int x, int y, int D[201][201][4]){
	if(x == M2 && y == N2) return 1;
	
	used[x][y] = 0;
	int i;
	for(i = 0; i < 4; i++){
		if(D[x][y][i] && used[x+dx[i]][y+dy[i]]) if( dfs(x+dx[i],y+dy[i],D) ) return 1;
	}
	
	return 0;
}

/* ↑上記の範囲は変更可能 */

int main(int argc, char** argv) {
  int answer_length = -1; /* この変数に k 番目に長い経路の長さを代入してください */
  int answer_number = -1; /* この変数に k 番目に長い経路の総数を代入してください */
  int m, n, k;
  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"));
  k = atoi(strtok(NULL, ", \n"));
  assert(m > 0 && m <= 200);
  assert(n > 0 && n <= 200);
  assert(k > 0 && k <= 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);

  /* 入力した情報を画面に出力する(デバッグ等に使って下さい)
   提出時は削除しないで,このようにコメントアウトすること
  printf("The input graph\n");
  for (i = 2*n; i >= 0; i--) {
    y = i / 2;
    if (i % 2 == 0) {
      printf("+");
      for (x = 0; x < m; x++) {
        assert(D[x][y][1] == D[x+1][y][3]);
        printf("%d+", D[x][y][1]);
      }
      assert(D[0][y][3] == 0);
      assert(D[m][y][1] == 0);
    } else if (i > 0) {
      for (x = 0; x <= m; x++) {
        assert(D[x][y][0] == D[x][y+1][2]);
        assert(y != n-1 || D[x][y+1][0] == 0);
        printf("%d ", D[x][y][0]);
      }
    } else {
      for (x = 0; x <= m; x++) {
        assert(D[x][y][2] == 0);
      }
    }
    printf("\n");
  }
  printf("\n");
  */

  /* 時間計測用(デバッグ等に使って下さい)
   提出時は削除しないで,このようにコメントアウトすること
  start = clock();
  */

/* ↓以下の範囲は変更可能 */
	
	int j, h, nx, ny, ni, cnt;
	
	M2 = m; N2 = n;
	for(x = 0; x <= m; x++) for(y = 0; y <= n; y++) used[x][y] = 1;
	if( dfs(0,0,D) ){
		
		for(i = 0; i < MAX_DIS; i++){ rlen[i].dis = i; rlen[i].sz = 0;}
		for(x = 0; x <= m; x++) for(y = 0; y <= n; y++){
			po[x][y].th = 0;
			po[x][y].kdis = -1;
			for(i = 0; i < MAX_DIS; i++) po[x][y].pdis[i] = -1;
		}
		ri = 0;
		rlen[0].sz = 1; rlen[0].vx[0] = 0; rlen[0].vy[0] = 0;
		po[0][0].pat[0] = 1;
		cnt = 0;
		
		
		while(cnt < MAX_DIS){
			
			if(rlen[ri].sz){
				cnt = 0;
				
				for(i = 0; i < rlen[ri].sz; i++){
					x = rlen[ri].vx[i]; y = rlen[ri].vy[i];
					
					for(j = 0; j < 4; j++){
						
						if(D[x][y][j]){
							nx = x+dx[j]; ny = y+dy[j]; ni = (ri+D[x][y][j]) % MAX_DIS;
							
							if(po[nx][ny].pdis[ni] == rlen[ni].dis){
								
								po[nx][ny].pat[ni] += po[x][y].pat[ri];
								
							} else {
								
								if(po[nx][ny].th < k || rlen[ni].dis < po[nx][ny].kdis){
									po[nx][ny].th ++;
									po[nx][ny].pdis[ni] = rlen[ni].dis;
									po[nx][ny].pat[ni] = po[x][y].pat[ri];
									
									if(po[nx][ny].th == k) po[nx][ny].kdis = rlen[ni].dis;
									if(po[nx][ny].th > k){
										for(h = po[nx][ny].kdis-1;;h--){
											if(po[nx][ny].pdis[h%MAX_DIS] == h){ po[nx][ny].kdis = h; break;}
											//if(h <= po[nx][ny].kdis-MAX_DIS){puts("Error."); return -1;}
										}
									}
									
									rlen[ni].vx[rlen[ni].sz] = nx;
									rlen[ni].vy[rlen[ni].sz] = ny;
									rlen[ni].sz ++;
								}
							}
						}
					}
				}
			} else {
				cnt++;
			}
			
			
			rlen[ri].dis += MAX_DIS; rlen[ri].sz = 0; ri = (ri+1) % MAX_DIS;
		}
		
		
		if(po[m][n].th >= k){
			answer_length = po[m][n].kdis;
			answer_number = po[m][n].pat[po[m][n].kdis % MAX_DIS];
		} else {
			answer_length = 0;
			answer_number = 0;
		}
		
	} else {
		
		answer_length = 0;
		answer_number = 0;
	}
	
/* ↑上記の範囲は変更可能 */


  /* 時間計測用(デバッグ等に使って下さい)
   提出時は削除しないで,このようにコメントアウトすること
  end = clock();
  printf("%s, %f, %d, %d\n", problem_file, (double)(end - start) / CLOCKS_PER_SEC, answer_length, answer_number);
  */

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


説明

【基本方針】

・スタート地点から各交点までの、短い方から数えてk番目までの経路の長さ・個数を順に求めていく。

・経路の長さは単調増加なので、スタート地点からの距離を0から始めて1ずつ増やしていき、それに該当する交点に関して処理を行う。


【工夫点】

・メモリ
 道路の長さは20以下であるから、スタート地点からの距離lに関する処理をしているときには
 l+20より大きい距離に関する更新は起こらないので、配列(rlen)の要素数は21で良い。

・実行時間
 サイズが大きく経路がない入力データではムダな探索が行われるので、あらかじめ経路の有無を確認する。

・データ構造
 特に特殊なデータ構造を使う必要は無かった。


【注意点】

・探索打ち切りのタイミングについて
 ・21回連続で更新が無ければ終了。
 ・各交点に関して、短い方から数えてk番目より長い経路は必要がないので切り捨てる。

・短い方から数えてk番目の経路
 ・k番目より長い経路がk番目の経路よりも先に更新されることがあるため、条件判断を
  「記録した経路がk種類未満 もしくは k番目の経路(暫定)よりも短い」
  とし、データの更新を行わなければならない。


【変数】

rlen  : 現在調べているの経路長の経路のデータ。 構造体はroute(後述)
po    : 交点のデータ。 構造体はpoint(後述)
dx,dy : 上下左右の処理をシンプルに書くための配列。
ri    : rlenの添字。 現在探索している長さ mod 21
M2,N2 : DFS内でも使えるようにするために、m,nを代入する。
used  : DFS用で、すでに調べた交点は0、まだ調べていない交点は1。
j,h   : for分で使う変数。
nx,ny : 次に調べる交点の座標
ni    : 次に調べる経路の長さ mod 21
cnt   : 連続で更新が行われなかった回数。 21以上になれば探索は終了。


【構造体】

・route 経路に関する構造体
  dis   : スタート地点からの距離
  sz    : vx,vyのデータ数
  vx,vy : スタート地点からの距離がdisである交点の座標

・point 交点に関する構造体
  th    : 今までに記録した経路の種類の数
  kdis  : 短い方から数えてk番目の経路長
  pdis  : 経路長を記録する。 経路長が同じ経路かどうかを判別するために使う。
  pat   : 経路長がpdisの経路のパターン数