TopCoder SRM514 Div1Hard

問題

魔法少女回。魔法少女が呪文を唱える。呪文は0,1からなる文字列である。最初のK個の呪文(A[0]..A[K-1])は決まっている。i>=Kのとき、A[i] = A[i-1] + A[i-K-1] + A[i-2K-1] + …（i-nK-1>=0の限り繰り返し）である。呪文Sを、A[N]の[lo, hi]の部分とする。Sの中で、最も多く1が連続している部分の連続回数が魔法の強さである。これを求めよ。

解法

Nが途方もなく大きくて絶望しそうだが、A[i]はどんどん長い呪文になるので、実際は700程度でhiの上限を超えてしまうことがわかる。Nが大きすぎる場合は勝手に小さくしてよい。
後は、呪文の特徴のみをおさえた構造体を作り、再帰的に解けば良い。但し、そのまま解くと再帰回数が増えすぎて絶対間に合わないので、「A[i]全体について解くとき」だけ結果を覚えておいてメモ化する。それ以外の場合はほとんど発生しない(高々2N回程度)なので逐一計算する。

コード

#include <vector>
#include <string>
#include <algorithm>

using namespace std;

#define SIZE 700
typedef long long i64;

struct magic
{
	i64 left, right, ln, size;
	
	magic(){ left = right = ln = size = 0; }
};

magic operator+(const magic& L, const magic& R)
{
	magic ret;
	ret.size = L.size + R.size;
	ret.left = L.left + (L.left==L.size ? R.left : 0);
	ret.right = R.right + (R.right==R.size ? L.right : 0);
	ret.ln = max(L.right + R.left, max(max(ret.left, ret.right), max(L.ln, R.ln)));
	
	return ret;
}

class MagicalGirlLevelThreeDivOne
{
	vector<string> in;
	i64 len[SIZE];
	magic memo[SIZE];
	int K;
	
	magic calc(int N, int Lo, int Hi)
	{
		magic ret;
		ret.left = 0;
		for(int i=Lo;i<Hi;i++){
			if(in[N][i]=='0') break;
			ret.left++;
		}
		ret.right = 0;
		for(int i=Hi-1;i>=Lo;i--){
			if(in[N][i]=='0') break;
			ret.right++;
		}
		ret.size = Hi-Lo;
		ret.ln = 0;
		i64 p = 0;
		for(int i=Lo;i<Hi;i++){
			if(in[N][i]=='1'){
				 p++; ret.ln = max(ret.ln, p);
			}else p=0;
		}
		ret.ln = max(ret.ln, p);
		
		return ret;
	}
	
	magic solve(int N, i64 Lo, i64 Hi)
	{
		Lo = max(Lo, 0LL);
		Hi = min(Hi, len[N]);
		if(Lo >= Hi) return magic();
		
		if(Lo==0 && Hi==len[N]){
			if(memo[N].size==-1){
				if(N < K){
					return memo[N] = calc(N, (int)Lo, (int)Hi);
				}
				
				memo[N] = magic();
				for(int j=N-1;j>=0;j-=K){
					memo[N] = memo[N] + solve(j, 0, len[j]);
				}
			}
			return memo[N];
		}
		
		if(N < K){
			return calc(N, (int)Lo, (int)Hi);
		}
		
		magic ret;
		i64 pos = 0;
		for(int j=N-1;j>=0;j-=K){
			ret = ret + solve(j, Lo - pos, Hi - pos);
			pos += len[j];
		}
		return ret;
	}
	
public:
	i64 theMaxPower(vector<string> first, int N, i64 Lo, i64 Hi)
	{
		in = first;
		K = in.size();
		Hi++; //[Lo, Hi)
		
		for(int i=0;i<K;i++) len[i] = in[i].size();
		for(int i=K;i<=N;i++){
			len[i] = 0;
			for(int j=i-1;j>=0;j-=K) len[i] += len[j];
			if(len[i] > Hi){
				N = i;
				break;
			}
		}
		
		for(int i=0;i<=N;i++) memo[i].size = -1;
		
		magic ret = solve(N, Lo, Hi);
		return ret.ln;
	}
};