Codeforces #637 Div1 B. Nastya and Scoreboard

まーた面倒な問題。
http://codeforces.com/contest/1340/problem/B

問題

電卓のようないわゆる7セグメント式の数値の表記を考える。
今、K桁の数字を表示したとき、N個のセグメントが点灯していた。
また、K桁中確実にセグメントが点灯していた場所が与えられる。

これらの条件を満たす最大の数値を求めよ。

解法

セグメント点灯条件から、各桁で取りえる値が決まる。
あとは各桁以降で消費できるセグメント数の集合をDPで求めておき、前の桁からどん欲にN本のセグメントを消費しきれる値を辞書順最大値で選んでいくとよい。

int N,K;
int ok[2020][10];

int mask[10];
string T[10]={
	"1110111", "0010010", "1011101", "1011011", "0111010", "1101011", "1101111", "1010010", "1111111", "1111011",
};

bitset<2048> BS[2020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	MINUS(ok);
	
	FOR(i,10) {
		FOR(j,7) if(T[i][j]=='1') mask[i]|=1<<j;
	}
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>s;
		x=0;
		FOR(j,7) if(s[j]=='1') x|=1<<j;
		FOR(j,10) if((mask[j]&x)==x) ok[i][j]=__builtin_popcount(mask[j]^x);
	}
	BS[N][0]=1;
	for(i=N-1;i>=0;i--) {
		FOR(j,2001) if(BS[i+1][j]) {
			FOR(k,10) if(ok[i][k]>=0) BS[i][j+ok[i][k]]=1;
		}
	}
	
	if(BS[0][K]==0) return _P("-1\n");
	string ret;
	FOR(i,N) {
		for(j=9;j>=0;j--) if(ok[i][j]>=0 && ok[i][j]<=K && BS[i+1][K-ok[i][j]]==1) {
			ret+='0'+j;
			K-=ok[i][j];
			break;
		}
	}
	cout<<ret<<endl;
}

まとめ

解法はともかく、問題文読むのがしんどい。