Supercomputing Contest 2011/予選・認定問題

SuperCon 2011 予選問題および認定問題 †

• 印刷用PDF版
• 雛形プログラム
• 入力データのサンプル

経路総数の計算: 経路計算は,カーナビやウェブの経路探索サービスなどで,最近では一般にも身近な計算問題でしょう.単に一つの最適経路を求めるだけでなく,同様に良い経路をすべて求めておくことも避難計画などに重要です.今回の予選課題は,最短経路長(もしくは準最短経路長)となる経路の総数を求める問題です. 具体的には,図 1 のような (n + 1) × (m + 1) の格子状に表わされた道路網において,座標 (0,0) のスタート格子点 S から,座標 (m, n) のゴール格子点 T までの最短経路長(もしくは準最短経 路長)を達成する経路の個数を求める問題です.(注:便宜上,各格子点を (0, 0) から (m, n) まで の座標で表わしますが,この数字は辺の長さとは無関係です.また,どの問題例でもスタート頂点Sは座標 (0, 0)の点で,ゴール頂点は座標 (m, n) の点とします.)

下の格子図が問題例の一つ.各格子点が交差点を表わし, 辺が交差点間の道路を表わしている.各辺が表わす道路の長さは一定ではない.この例では,各辺の上に書かれている 整数が道路長である(縦の辺はすべて長さ 1 とする).道 路長 0 は通行できないことを意味している. 経路を考える際,交差点ではどちらに進んでもよい.この問題例では,スタート格子点 (0, 0) からゴール格子点 (5, 4) までの最短経路長は 9.その長さとなる経路の取り方は太線の矢印を含め 2 通り.

以下のすべての問いにおいて,m, n ≤ 200,各辺の長さは 0 ∼ 20 の整数とします(問Aのみ,辺 の長さは 0 または 1 に限る).問題例の与え方は次のページ以降の詳細説明で述べます.また,すべての問いにおいて,答えるべき経路の総数は intに収まると仮定して構いません.

問A (スーパーコン3級認定問題　2011年度版) †

• 与えられる問題例の各辺の長さは 0(通行不可)もしくは 1 だけとします.この場合に,長さ m+n の経路長となる経路の総数を求めるプログラムを作成してください.
  • ヒント:長さ m + n の経路 は(もしあれば)最短経路です.無い場合は答えは 0 です.スタート格子点に近い各格子点 (i, j) から順に,そこまでに至る長さ i + j の経路の総数を求める戦略がよいでしょう.

問B (スーパーコン2級認定問題　2011年度版) †

• 与えられた問題例に対して,最短経路長とその最短経路を達成する経路の総数を求めるプログラムを作成してください.

問C (スーパーコン予選問題 兼 1級認定問題　2011年度版) †

• 問題例として,格子状道路図の他に整数 k (1 ≤ k ≤ 200) が与えられます.この問題例に対して, 最短経路長,次に長い経路長,と順に考えていったときの k 番目の経路長を求め,その長さを達 成する経路の総数を求めるプログラムを作成して下さい.たとえば,図 1 の例では,最短経路長 の次の長さの経路長は 10 で,その経路長を達成する経路の個数は6なので,この格子状道路図 と k = 2 に対する答えは10と6です.

注意 †

• 作成するプログラム
  • プログラムは入出力の部分を規定した雛形プログラムをもとに,その一部を修正する形で 作って下さい.作成の際には「変更可能」とコメントされている範囲以外は変更・削除しな いようにして下さい.したがって,ここで指定された入力,出力以外のものを期待したプロ グラムは審査対象から除外されます.その他は適宜変更や追加して構いません.また,標準 ライブラリ関数等を宣言して使用しても構いません.
  • 提出するプログラムは指定したファイル名の単一ファイルとして下さい.
  • プログラムは C 言語で記述して下さい.詳細は以下の通りです.
    • プログラムは C 言語規格(ANSI C や C99 など)に準拠する C 言語で記述して下さい. (インラインアセンブラの使用は禁止します.)
    • int は 32 ビット,long long は 64 ビットを仮定します.long のビット幅は環境により 異なるので,64 ビットデータを扱いたい場合は long ではなく long long を使って下さい. (<stdint.h> をインクルードして使える int64 t などを使うとさらに確実です.)
    • Linux 上の gcc ver 3.3.3 を使用してコンパイルし,Linux 上で実行します.この Linux は 64 ビット x86 64 版です. ・移植性の問題(例えばエンディアンの違い)によるトラブルには対処しません.

• 審査方法(スーパーコン認定に関して)
  • 応募プログラムをコンパイルし,5 題程度の問題例に対して各々 1 分間の制限時間で実行 し,すべての問題例で制限時間内に正確な答えを出している場合に合格とします.
  • スーパーコン認定に使用する問題例ではm,n≤50(問Cの場合にはk≤50)とします.
  • 審査環境におけるメモリはおよそ 4 ギガバイトです.*1

• 審査方法(予選選抜に関して)
  • 応募プログラムをコンパイルし,10 題程度の問題例に対して各々 2 分間の制限時間で実行します.
  • 予選選抜で使用する問題例では m, n, k ≤ 200 とします.
  • 審査環境におけるメモリはおよそ 4 ギガバイトです. *2
  • 制限時間内に正確な答えを出している問題例の個数順をもとに順位を決めます.
  • 同順位のチームに対しては,正解を出した計算の計算時間の合計を用いて順位を決めます. (万が一,合計計算時間に優位差の無い場合には,合わせて提出されるプログラムの説明をもとに工夫度を評価して順位を決めます.)
  • 以上の順位付けのもとで,上位 10 チームを本選出場候補チームとして選びます.ただし, 1 校からは最大 1 チームしか本戦出場できません.本選出場候補チームには,同時にスーパーコン 1 級も授与します.

詳細説明 †

問題例の与え方 †

問題例は以下のように与えられます(ただし,k は問Cのみ).

たとえば右図の格子状道路網に対する問Bのプログラムに対する入力は次のようになります.

雛形プログラムについて †

雛形プログラムでは,上記の入力問題例の辺長のデータを,次のような配列 D[m + 1][n + 1][4] に 格納するまで行います.それを用いて計算してください.

改訂履歴 †

• 問Ｃの記述中の「最短経路長 の次の長さの経路長は 10 で,その経路長を達成 する経路の個数は4なので」の中の「4」を「6」に修正．
• 問題例の与え方の記述中の「たとえば右図の格子状道路網に対する問Aのプロ グラムに対する入力は」の中の「問A」を「問B」に修正．