TopCoderOpen 2017 Pittsburgh Medium Avoid9

遅かったので出なかったけど、出てもよかったかも。
(URL掲載待ち)

問題

整数の集合Aが与えられる。
以下の条件を満たす最大の部分集合の大きさを求めよ。

• 3以上の大きさである。
• 3要素x,y,zを取り出したとき、x+y+zが9の倍数になることはない。

解法

色々解法はありそうだが、自分はbitDPで解いた。
Aの要素について、順に解に含む場合と含まない場合の部分集合の状態を更新していく。

要素を加える際、関係するのは既存の部分集合に対して1要素または2要素の和がどうなっているかだけなので、bitdpでその状態を列挙しよう。
具体的には以下の値を更新していけばよい。
f(i,m1,m2) := i番目までの要素の部分集合のうち、個々の要素のmod 9の値でとりえるもののbitmaskがm1、２要素の合計値のmod 9の値でとりえるもののbitmaskがm2であるようなものの最大要素数

class Avoid9 {
	public:
	int maxSizeOf9Free(vector <int> A) {
		
		ZERO(O);
		ZERO(from);
		ZERO(to);
		
		int m1,m2,i;
		FORR(a,A) {
			memmove(from,to,sizeof(from));
			a%=9;
			
			FOR(m1,9) if(O[m1]) {
				to[(1<<m1)|(1<<a)][1<<((m1+a)%9)]=max(to[(1<<m1)|(1<<a)][1<<((m1+a)%9)],2);
			}
			FOR(m2,1<<9) {
				int left=(9-a)%9;
				if(m2&(1<<left)) continue;
				FOR(m1,1<<9) {
					int nm2=m2;
					FOR(i,9) if(m1&(1<<i)) nm2 |= 1<<((i+a)%9);
					
					to[m1|(1<<a)][nm2]=max(to[m1|(1<<a)][nm2],from[m1][m2]+1);
				}
			}
			O[a]++;
		}
		
		int ma=0;
		FOR(m1,1<<9) FOR(m2,1<<9) ma=max(ma,to[m1][m2]);
		if(ma<=2) ma=-1;
		return ma;
	}
}

まとめ

組み合わせ的にも解けそうね。