Supercon2011 TECHNO

TECHNO-algo.txt

いろいろなアルゴリズムを適用できるようになりそうなので、まずは問題で与えられているデータを
交差点 -> 頂点、道路 -> 辺
とした無向グラフと考えることにした。

データがグラフならば、最短路を求めるのにはダイクストラ法などのアルゴリズムを利用することができる。
今回の予選課題は、ダイクストラ法を元にした方法で解くことにした。


まずはプライオリティキューを実装した。
このキューは、
・その地点までのスタートからの距離
・その地点の座標
・直前の地点の座標
・キューに入れられたとき、何番目の最短路だったか（後述）
をまとめた構造体 POINT を入れることができ、
スタートからの距離が短いデータから順に出てくるようにしてある。

また、データを保存する配列として、
・dist[200+1][200+1] その交差点への現在のスタートからの距離
・num[200+1][200+1][200] その交差点のk番目の最短路の数
・count[200+1][200+1] 何番目の最短路まで見つけたか
を用意した。


次にキューにスタート地点の座標を入れ、キューが空になるまで次の操作を繰り返す
1.キューを1つ取り出す。

2.取り出したデータにある「その座標へのスタートからの距離」と、配列 dist を比較する。
値が等しい時、配列 num に経路数を足して、そのデータを捨てる。

3.もうその地点のk番目までの最短路が見つかっている場合、そのデータを捨てる。

4.取り出したデータにある「その座標へのスタートからの距離」が、配列 dist の値よりも大きいとき、もしくはその地点に初めて来たときに次の操作を行う。
まず dist の値を更新して、num に直前の座標のものを代入する。
次に count の値を1増やす。
最後に、その交差点に繋がっている、k番目よりも多い最短路が見つかっていない座標への経路を新しくキューに入れる。
このとき、例えば現在の座標が(x, y)で北に経路が繋がっているならば、キューに入れる距離は
現在までの距離 + D[x][y][0]
となる。


このループが終了したとき、
・dist[x][y] には (x, y) へのk番目の最短路の距離
・num[x][y][c] には (x, y) への(c-1)番目の経路の数
・count[x][y] には (x, y) の探索の回数
が入っている。（その地点に行けない場合はすべて0が入っている）
よって
answer_length = dist[m][n];
answer_number = num[m][n][k-1];
を代入すればよい。


ところで、構造体 POINT に、何番目の最短路だったか保存している理由は、
仮にそれを保存せずnum[200+1][200+1]として座標だけで経路数を管理していると、
実装したプライオリティキューの特性上、プライオリティキューにデータが入れられ、
取り出されるまでに配列 num の値が更新されてしまうことがあるからである。
そのため、num[200+1][200+1][200]として、何番目の時にキューに入れられたか保存するようにしている。



反省点
・まず、プライオリティキューの大きさに根拠がない。
今回はメモリの確保にかかる時間を節約するために、プライオリティキューをポインタを使った実装ではなく
配列を使った実装を行ったので、どうしてもプライオリティキューの大きさを予め指定しておく必要があった。
また今回の実装では、指定された大きさ以上要素を詰め込むとプライオリティキューが容易に壊れてしまうことが分かった。
とりあえず2^20個分確保したが、用意できたテストケースではせいぜい1000程度しか使わなかったため、
ただメモリの無駄使いをしているだけの可能性もある。


・経路数を保存する配列が m * n * k つまり 201 * 201 * 200 という大きさになってしまったので、
なんとしてでも削りたかった。
うまく実装すれば削ることができるはずだと思い検討したが、
結局うまくいく方法を見つけることができなかった。


・チームのメンバーにソースレベルでの高速化に詳しい者がおらず、細かな高速化が行えなかった。
ただ、これはコンテストの趣旨に沿っていないと思われるので、
するのであればアルゴリズムを考え直すのが先決であると思われる。



感想
・はじめのうちは問Bを幅優先探索で解こうと思い、実装していたが、
途中でメンバーの一人がダイクストラ法に似たアルゴリズムを思いつき、
そこからデータをグラフとして扱う方法に発展していった。
今までグラフの問題は既存のアルゴリズムをそのまま利用したことしかなかったが、
この予選への参加で特にダイクストラ法への理解を深めることができた。



参考資料
「プログラミングコンテストチャレンジブック」 著者：秋葉 拓哉、岩田 陽一、北川 宜稔 出版社：毎日コミュニケーションズ
「プログラミングの宝箱 アルゴリズムとデータ構造」 著者：紀平 拓男、春日 伸弥 出版社：ソフトバンククリエイティブ
「各種アルゴリズムの C++ による実装 k-最短路」 http://www.prefield.com/algorithm/graph/k_shortest_paths.html

TECHNO.c

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

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

/* ↓以下の範囲は変更可能 */
#define QUE_MAX (1<<20)

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

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();
  */

/* ↓以下の範囲は変更可能 */
  {
	  const int dx[4] = {0, 1, 0, -1}; /* 相対座標 */
	  const int dy[4] = {1, 0, -1, 0};

	  /* プライオリティキューのための構造体 */
	  typedef struct {
		  unsigned int min; /* スタートからの距離 */
		  unsigned int x, y; /* その交差点の座標 */
		  unsigned int px, py; /* 直前にいた交差点の座標 */
		  unsigned int c; /* キューを入れた時のカウントを記録 */
	  } POINT;

	  static POINT que[QUE_MAX]; /* プライオリティキュー */
	  static unsigned int dist[200+1][200+1], num[200+1+1][200+1][200]; /* 距離、経路数 */
	  static int count[200+1][200+1]; /* 何番目の最短路か */
	  int cnt = 0, j, q, cost, a, b;
	  unsigned int px, py, nx, ny, d, ox, oy;
	  POINT p, x;
	  /* 配列の全ての要素を0で初期化
	  memset(dist, 0, sizeof dist);
	  memset(count, 0, sizeof count);
	  memset(num, 0, sizeof num); */

	  num[201][0][0] = 1;
	  /* push */
	  {
		  j = cnt++;
		  while(j > 0) {
			  q = (j - 1) / 2;
			  if(que[q].min <= 0)
				  break;
			  que[j] = que[q];
			  j = q;
		  }
		  que[j].min = 0;
		  que[j].x = 0;
		  que[j].y = 0;
		  que[j].px = 201;
		  que[j].py = 0;
		  que[j].c = 1;
	  }

	  /* キューが空になるまで */
	  while(cnt) {
		  /* pop */
		  {
			  p = que[0];
			  x = que[--cnt];
			  j = 0;
			  while(j * 2 + 1 < cnt) {
				  a = j * 2 + 1;
				  b = j * 2 + 2;
				  if(b < cnt && que[b].min < que[a].min)
					  a = b;
				  if(que[a].min >= x.min)
					  break;
				  que[j] = que[a];
				  j = a;
			  }
			  que[j] = x;
		  }
		  d = p.min;
		  ox = p.x;
		  oy = p.y;
		  px = p.px;
		  py = p.py;

		  /* 距離が同じ場合、経路数を足す */
		  if(dist[ox][oy] == d && count[ox][oy]) {
			  num[ox][oy][count[ox][oy] - 1] += num[px][py][p.c - 1];
			  continue;
		  }
		  /* 新しい経路 or 初めて来た */
		  if(count[ox][oy] != k && (dist[ox][oy] < d || !count[ox][oy])) {
			  dist[ox][oy] = d;
			  /* 経路数は、直前の座標のもの */
			  num[ox][oy][count[ox][oy]] = num[px][py][p.c - 1];
			  /* 新しい経路が見つかったので、1足す */
			  count[ox][oy]++;
			  /* その交差点に繋がっている経路をキューに入れる */
			  for(i = 0; i < 4; ++i) {
				  cost = D[ox][oy][i];
				  if(!cost) continue;
				  nx = ox + dx[i];
				  ny = oy + dy[i];
				  if(count[nx][ny] < k) {
					  /* push */
					  j = cnt++;
					  while(j > 0) {
						  q = (j - 1) / 2;
						  if(que[q].min <= d + cost)
							  break;
						  que[j] = que[q];
						  j = q;
					  }
					  que[j].min = d + cost;
					  que[j].x = nx;
					  que[j].y = ny;
					  que[j].px = ox;
					  que[j].py = oy;
					  que[j].c = count[ox][oy];
				  }
			  }
		  }
	  }
	  answer_length = dist[m][n];
	  answer_number = num[m][n][k - 1];
  }

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


  /* 時間計測用（デバッグ等に使って下さい）
　　 提出時は削除しないで，このようにコメントアウトすること
  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;
}