SuperCon2012予選結果

予選通過しました。
西日本勢なので大阪大学に行きます。

↓送ったコード

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

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

/* ↓以下の範囲は変更可能 */
#include <string.h>
#define INF 0x7F7F7F7F
int max(int a, int b){ return (a > b)?a:b; }

int memo[1000][10001];
void init(int N){
	int i, j;
	for(i = 0; i < N; i++){
		for(j = 0; j < 10 * N + 1; j++){
			memo[i][j] = INF;
		}
	}
}
int solve(int p, int l, int N, int v[1000], char w[1000][11], char W[10001]){
	int i, t, ans;
	int k; /* strncmpの結果 */
	int len = strlen(&w[p][0]);
	if(p == N){
		return 0;
	}
	if(memo[p][l] != INF){
		return memo[p][l];
	}
	k = strncmp(&w[p][0], W + l, len);
	ans = solve(p + 1, l, N, v, w, W);
	if(k == 0){
		ans = max(ans, solve(p + 1, l + len, N, v, w, W) + v[p]); 
	}else if(k < 0){
		t = v[p];
		for(i = p + 1; i < N; i++){
			if(v[i] > 0){
				t += v[i];
			}
		}
		ans = max(ans, t);
	}
	memo[p][l] = ans;
	return ans;
}

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

int main(int argc, char** argv){
	int answer = -1; /* この変数に答（Vの最大値）を代入してください */
	int N;
	static int v[1000];
	static char w[1000][10+1];
	static char W[10000+1];
	char* problem_file;
	clock_t start, end;
	FILE* fp;

	int i;
	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);

	N = atoi(strtok(buf, " \n"));
	assert(1 <= N && N <= 1000);

	p = fgets(buf, 0xffff, fp);
	assert(p != 0);
	p = strtok(buf, " \n");
	strcpy(W, p);
	assert(1 <= strlen(W) && strlen(W) <= 10000);
	for(p = W; *p; ++p){
		assert(islower(*p));
	}

	for(i = 0; i < N; ++i){
		p = fgets(buf, 0xffff, fp);
		assert(p != 0);
		v[i] = atoi(strtok(buf, " "));
		assert(-1000000 <= v[i] && v[i] <= 1000000);
		p = strtok(NULL, " \n");
		strcpy(w[i], p);
		assert(1 <= strlen(w[i]) && strlen(w[i]) <= 10);
		for(p = w[i]; *p; ++p){
			assert(islower(*p));
		}
	}

	fclose(fp);

	start = clock();

/* ↓以下の範囲は変更可能 */
	init(N);
	answer = solve(0, 0, N, v, w, W);
/* ↑上記の範囲は変更可能 */

	end = clock();
	printf("%s, %f, %d\n", problem_file, (double)(end - start) / CLOCKS_PER_SEC, answer);

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

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

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

↓アルゴリズム説明(日本語が少し変)

アルゴリズム説明

文字列A = w_{S_0} + w_{S_1} +...+ w_{S_i} (S_i < N)
文字列B = w_(S_i + 1)
とする.

Aが,Wの先頭から|A|文字目までの文字列と等しいとき

AにBを加えようとするとき
(1)A+B <= W で, A+B は (Wの 先頭から|A+B|文字目までの文字列) と等しい
(2)A+B <  W で, A+B は (Wの 先頭から|A+B|文字目までの文字列) とは異なる
(3)A+B >  W である
 の3通りのどれかになる

(1)のとき
	認定問題のB問題と同じように考えることができる.
	BをAに加えた場合と,加えなかった場合で分けて,再帰的にといていく.
(2)のとき
	A+Bにどんな文字列Cを加えても
	A+B+C < W  となる.
	よって,文字列Cを,文字列B以降で正の価値を持つ文字列をすべて加えたもの
	とすることによって価値を最大化できる
(3)のとき
	文字列を加えることはできない


以上の解法を再帰関数を利用して実装した.
また無駄な計算を減らすためにメモ化再帰の手法を用いた.
メモ化の状態は
[追加しようとしているwの番号][すでに作った文字列Aの長さ]とした.
とりうる状態の数はたかだか(1000*10000)=10000000しかないので十分はやく計算できる.