UVa-10401 : Injured Queen Problem

問題概要

キング+上下に動くようなクイーンに対して、Nクイーンが何通りあるか求める問題。いくつかのクイーンは配置が指定されている。

解法

ごくごく素直なDPだとO(N^3)。?のとき全部に配るのを止めて、全体に配って近くだけ差っ引くというやりかたをすればO(N^2)に落ちる。入力に空行含めたりするの本当に止めてほしい。

acceptされたコード

計算量O(N^2)。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>
#include <numeric>
using namespace std;

typedef long long int64;

const int MAX_L = 15;

char buf[MAX_L + 10];
int as[MAX_L];
int64 dp[MAX_L][MAX_L];
int64 dp2[MAX_L];
int to_num[0x100];

void pre(){
	for(int i=0; i<9; i++){
		to_num['1' + i] = i;
	}
	for(int i=0; i<6; i++){
		to_num['A' + i] = i + 9;
	}
}

bool init(){
	return gets(buf)!=NULL;
}

int64 solve(){
	memset(dp, 0, sizeof(dp));
	memset(dp2, 0, sizeof(dp2));
	int L = strlen(buf);
	for(int i=0; i<L; i++){
		if(buf[i] == '?'){
			as[i] = -1;
		}
		else if(isdigit(buf[i]) || isalpha(buf[i])){
			as[i] = to_num[buf[i]];
		}
		else{
			L = i;
			break;
		}
	}
	if(!L){
		return -1;
	}
	if(as[0] == -1){
		for(int i=0; i<L; i++){
			dp[0][i] = 1;
		}
	}
	else{
		dp[0][as[0]] = 1;
	}

	for(int i=1; i<L; i++){
		for(int j=0; j<L; j++)if(dp[i-1][j] > 0){
			if(as[i] == -1){
				dp2[i] += dp[i-1][j];
				if(j>0){
					dp[i][j-1] -= dp[i-1][j];
				}
				dp[i][j] -= dp[i-1][j];
				if(j<L-1){
					dp[i][j+1] -= dp[i-1][j];
				}
			}
			else if(abs(j-as[i]) > 1){
				dp[i][as[i]] += dp[i-1][j];
			}
		}
		for(int j=0; j<L; j++){
			dp[i][j] += dp2[i];
		}
	}

	return accumulate(dp[L-1], dp[L-1] + L, 0LL);
}

int main(){
	pre();
	while(init()){
		int64 ans = solve();
		if(ans >= 0){
			printf("%lld\n", ans);
		}
	}

	return 0;
}