TopCoderOpen 2018 Round3A Easy LeftToRightGame

Mediumでしょうもないミスして、Hardが適当に書いて通ってしまい、結果レート増といういまいち喜べない結果に。
http://community.topcoder.com/stat?c=problem_statement&pm=14950

問題

2人でL桁の整数値を作る際、両者交互に先頭から桁の値を１つずつ埋めていく。
最終的にできる値に対し、先手はDの倍数とならないように、後手は倍数となるように最適手を取った場合、勝者はいずれか。
なお、先手はLeading Zeroは設置できない。

解法

O(1)解法もあるが、状態としては埋まった桁数と、そこまでの値のmod DということでO(LD)しかないし、そこからの状態遷移も高々10通りということで、メモ化再帰やDPで間に合う。

int num[1010];
int memo[1010][1010];

class LeftToRightGame {
	public:
	int L,D;
	
	int win_a(int d,int cur) {
		if(d==L) return cur!=0;
		if(memo[d][cur]>=0) return memo[d][cur];
		
		int i;
		int win=0;
		for(i=0;i<=9;i++) {
			if(i==0 && d==0) continue;
			int now=(cur+num[L-1-d]*i)%D;
			if(win_b(d+1,now)==0) win=1;
		}
		return memo[d][cur]=win;
		
	}
	int win_b(int d,int cur) {
		if(d==L) return cur==0;
		if(memo[d][cur]>=0) return memo[d][cur];
		int i;
		int win=0;
		for(i=0;i<=9;i++) {
			int now=(cur+num[L-1-d]*i)%D;
			if(win_a(d+1,now)==0) win=1;
		}
		return memo[d][cur]=win;
	}
	
	string whoWins(int length, int divisor) {
		L=length;
		D=divisor;
		int i,j,k;
		num[0]=1;
		
		MINUS(memo);
		FOR(i,length) num[i+1]=num[i]*10%D;
		
		if(win_a(0,0)) return "Alice";
		else return "Bob";
		
		
	}
}

まとめ

O(LD)で間に合う程度の上限だったので、O(1)手は怖くて手が出せないし考えもしなかったよ…。