Codeforces ECR #165 : F. Card Pairing

忘れたころに乱数が出てくるな…。
https://codeforces.com/contest/1969/problem/F

問題

N枚のカードの山があり、各カードに書かれた番号があらかじめわかっている。
まず山からK枚手元にカードを取ったあと、以下を繰り返す。

• 手元のカードから2枚カードを選び捨てる。その際、同じ番号のカードであれば1ポイントを得る。
• 山にカードがまだあるなら、2枚手元に補充する。

最適な捨て方をした時、得られるポイントの最大値を求めよ。

解法

まず手元に同じ番号のカードが2枚あれば、それらを合わせて捨てるのが得なのは自明。
問題は、手元の全カードが異なる場合である。
dp(i) := カードをi枚目まで処理したら手元のカードが全部異なる状態になったとき、そこまでに得たポイントの最大値

dp(i)からの遷移だが、2つカードを選んだ時、次に手元のカードが全部異なる状態になるときがO(1)で求められるとよい。
これにはカードのprefixに対するhash値を取ればよい。

int N,K;
int A[1010];

int dp[1010];

ll H[1010];
ll HS[1010];

std::random_device rnd;
std::mt19937 mt(rnd());
std::uniform_int_distribution<int> dist(0, 1<<20);
int num[1010][1010];

map<int,set<int>> nex;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	FOR(i,1000) {
		H[i]=dist(mt);
		H[i]=(H[i]<<20)|dist(mt);
		H[i]=(H[i]<<20)|dist(mt);
	}
	
	cin>>N>>K;
	int ret=0;
	FOR(i,N) {
		cin>>A[i];
		A[i]--;
		if(i%2==1&&A[i]==A[i-1]) {
			ret++;
			i-=2;
			N-=2;
		}
	}
	
	
	set<int> S;
	int cur=0;
	while(S.size()<K&&cur<N) {
		if(S.count(A[cur])) {
			S.erase(A[cur]);
			ret++;
		}
		else {
			S.insert(A[cur]);
		}
		cur++;
		if(S.count(A[cur])) {
			S.erase(A[cur]);
			ret++;
		}
		else {
			S.insert(A[cur]);
		}
		cur++;
	}
	
	FOR(i,N) FOR(j,K) num[j][i+1]=num[j][i]+(A[i]==j);
	MINUS(dp);
	dp[cur]=ret;

	FOR(i,N) {
		HS[i+1]=HS[i]^H[A[i]];
		if(i+1>=cur&&(i+1)%2==0) nex[HS[i+1]].insert(i+1);
	}

	for(i=cur;i<N;i+=2) {
		nex[HS[i]].erase(i);
		int px=-1,py=-1;
		int sum=0;
		FOR(j,K) sum+=(num[j][N]+1-num[j][i])/2;
		
		FOR(y,K) FOR(x,y) {
			if(nex.count(HS[i]^H[x]^H[y])==0 || nex[HS[i]^H[x]^H[y]].empty()) {
				int tsum=sum-(num[x][N]+1-num[x][i])/2-(num[y][N]+1-num[y][i])/2;
				tsum+=(num[x][N]-num[x][i])/2+(num[y][N]-num[y][i])/2;
				dp[N]=max(dp[N],dp[i]+tsum);
			}
			else {
				j=*nex[HS[i]^H[x]^H[y]].begin();
				dp[j]=max(dp[j],dp[i]+(j-i)/2-1);
			}
		}
		if(K>=100) break;
		
	}
	
	
	int ma=0;
	FOR(i,N+1) ma=max(ma,dp[i]);
	cout<<ma<<endl;
	
	
}

まとめ

うーん、言われてしまえば単純なんだけど、パッと思いつかないな…。