SuperCon2013予選

いまごろですが、通過していました。
西日本のsakataで出場します。
よろしくお願いしますー。
コードと解説をはっておきます

コード

#include <stdio.h>
#include <string.h>
#include "sc13.h"

#define N 30
#define INF 1000000

int a[N];
int path[N], best, n, path_[N];
int visited[N];
void solve(int p, int x, int sum, int rest){
	int i;
	int q;
	if(sum + rest <= best){ return; }
	if(p == N - 1){
		if(best < sum){
			path_[x] = N - 1;
			n = x + 1;
			memcpy(path, path_, sizeof(int) * n);
			best = sum;
		}
		return;
	}
	q = (p + a[p]) % N;
	if(visited[q] == 0){
		path_[x + 1] = q;
		visited[q] = 1;
		solve(q, x + 1, sum + a[p], rest - a[p]);
		visited[q] = 0;
	}
	q = (p + N - a[p]) % N;
	if(visited[q] == 0){
		path_[x + 1] = q;
		visited[q] = 1;
		solve(q, x + 1, sum - a[p], rest - a[p]);
		visited[q] = 0;
	}
	return;
}

int d[N];
int dfs(int v, int dist){
	d[v] = dist;
	int u, ret = a[v];
	u = (v + a[v]) % N;
	if(d[u] == -INF){
		ret += dfs(u, dist + a[v]);
	}
	u = (v + N - a[v]) % N;
	if(d[u] == -INF){
		ret += dfs(u, dist - a[v]);
	}
	return ret;
}
int main(){
	int t;
	for(t = 0; t < 5; t++){
		int i;
		int SUM = 0;
		for(i = 0; i < N; i++){
			scanf("%d", &a[i]);
		}
		for(i = 0; i < N; i++)
			d[i] = -INF;
		SUM = dfs(0, 0);
		best = d[N - 1] - 1;
		if(best == -INF - 1){
			sc_output(0, path);
			continue;
		}
		visited[0] = 1;
		solve(0, 0, 0, SUM);
		sc_output(n, path);
	}
	return 0;
}

提出した解説

アルゴリズム解説

問題のすごろくゲームをグラフの問題に変形した.

マスv に 数字a が書かれているとき, u1, u2 をそれぞれ
u1 ≡ v + a (mod N)
u2 ≡ v - a (mod N) を満たす最小の非負整数とすると
マスv から右回りでマスu1, 左まわりでマスu2 に到達することができるので,グラフの頂点と辺に対応させて
頂点v から 頂点u1 へ 重みa の辺をはり
頂点v から 頂点u2 へ 重み-a の辺をはる
とすることができる.

このときすごろくの問題は,与えられた重み付き有向グラフにおける最長単純路を求めることに言い換えることができる.
このようにして作られたグラフには負閉路が含まれる可能性があるためBellman-Ford法やDijkstra法を用いることができない.
インターネットで調べると負閉路が存在する有向グラフの最長単純路問題はNP困難であることがわかった.
（参考文献 http://www.orsj.or.jp/~archive/pdf/a_a/1999A_202.pdf)

そこで,今回用いた解法では全探索をしつつ,明らかに探索する必要のない部分の探索をやめる枝刈りをすることで高速化した。

(1)解のない例への対処
解のない例に対してそのまま全探索すると探索範囲が広く時間がかかりがちになる.
そこで最初に,グラフで深さ優先探索をしてスタートからゴールまでの経路が存在するかどうかを確認する.
深さ優先探索はO(N)でできるので解のない例に対して,高速に対処できる.
また,この深さ優先探索の実行時に,スタートからゴールまでのある単純路の重みの和W（最適とは限らない）と,
スタートから到達できるマスにかかれている数字の和Sを求めておく.

(2)探索する必要のない状態の枝刈り
再帰関数で全探索しているとき,スタートから現在までの使用した辺の重みの和をsとし,
使用していない正の値を持つ辺の重みの和をrとする.現在求まっている最長単純路の候補の路長をbestとすると,
s + r <= best
が成り立つとき,この状態より先を探索してもbestよりよい解はないので枝刈りする.
またbestの初期値として(1)のWを用いる.rは(1)のSを利用して計算する.

以上の解法を実装した.