TopCoder SRM 680 Div2 Hard BearFair2

ほんと謎な制限。
https://community.topcoder.com/stat?c=problem_statement&pm=14132

問題

基本的にはDiv1 Easyと同じ。
TopCoder SRM 680 Div1 Easy BearFair - kmjp's blog

ただ、Div1 EasyはS中偶数奇数の数をそろえたが、こちらはS中3で割った余りが0,1,2となるものが1/3ずつなるようにせよ。

解法

Div1 EasyのDP解の変形で十分間に合う。
f(x,m0,m1,m2) := S中x以下の要素で3で割った余りが0,1,2の数がm0,m1,m2個となるものがあるかないか
上記fを順次求めていくと、O(b*n^3)と少しDiv1 Easyより重いものの余裕で間に合う。

こちらも計算時間がbに依存しない解法がある。
Div1 Easy同様クエリをU[i]順にソートしておく。
(U[i]+1)～U[i+1]中に登場する3で割った余りが0,1,2となる整数の数はわかるので、そこからグラフを作れば最大フロー問題にできると思われる。

int ok[1010][26][26];
int must[1010];

class BearFair {
	public:
	string isFair(int n, int b, vector <int> upTo, vector <int> quantity) {
		int i;
		MINUS(must);
		FOR(i,upTo.size()) {
			if(must[upTo[i]]!=-1 && n-quantity[i]!=must[upTo[i]]) return "unfair";
			must[upTo[i]] = n-quantity[i];
		}
		
		ZERO(ok);
		ok[0][n/2][n/2]=1;
		for(i=1;i<=b;i++) {
			int o,e;
			FOR(o,n/2+1) FOR(e,n/2+1) if(ok[i-1][o][e]) {
				// nottake
				ok[i][o][e] = 1;
				if(i%2==1 && o) ok[i][o-1][e] = 1;
				if(i%2==0 && e) ok[i][o][e-1] = 1;
			}
			if(must[i]!=-1) {
				FOR(o,n/2+1) FOR(e,n/2+1) if(o+e!=must[i]) ok[i][o][e]=0;
			}
		}
		if(ok[b][0][0]) return "fair";
		else return "unfair";
		
	}
}

まとめ

Div2 Hard 1000ptなら、安直DPが通らないようbが大きくていいと思うんだけどなぁ。