EPIC Institute of Technology Round Summer 2024 : D. World is Mine

微妙な出来だった回。
https://codeforces.com/contest/1987/problem/D

問題

整数集合Aが与えられる。
ここから、以下のように2人が交互に整数を取り合う。

• 先手は、取った整数が単調増加となるように取る
• 後手は、任意の整数を取る

先手が、先手が取れる整数の数を最大化、後手は最小化しようとするとき、値はどうなるか。

解法

先手は取れる整数のうち最小のものを取り、後手は今後先手が取るもののうち先手が取り始める前にとりつくせるものを取ろうとする。
後手が、各整数を見逃すか見逃さないかを2通り見て行き、先手が取れる整数の数を最小となるようにしていこう。

int T,N,A[5050];
int dp[5050][5050];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N;
		map<int,int> M;
		FOR(i,N) {
			cin>>x;
			M[x]++;
		}
		vector<int> V;
		FORR2(a,b,M) V.push_back(b);
		N=V.size();
		FOR(x,N+2) FOR(y,N+2) dp[x][y]=100000;
		dp[0][0]=0;
		FOR(i,N) {
			int v=V[i];
			FOR(j,N+1) {
				if(j+v<=N&&j>0) dp[i+1][j]=min(dp[i][j-1]+1,dp[i][j+v]);
				else if(j+v<=N) dp[i+1][j]=dp[i][j+v];
				else if(j>0) dp[i+1][j]=dp[i][j-1]+1;
				
			}
		}
		int ret=1000000;
		FOR(i,N+1) ret=min(ret,dp[N][i]);
		cout<<ret<<endl;
		
	}
}

まとめ

ここまではすんなり。