SRM 605

僕がよく送ってrejectされるセットにとても近い。

250:
自明なgreedy

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
class AlienAndHamburgers{
	public:
	int val[1100];
	int M[1100];
	int T[1000];
	int H[1100];
	int getNumber(vector<int>a,vector<int>b){
		int n=a.size();
		for(int i=0;i<1000;i++){
			M[i]=-99999999;
			T[i]=0;
			H[i]=0;
		}
		for(int i=0;i<n;i++){
			M[a[i]]=max(M[a[i]],b[i]);
			if(b[i]>0)T[a[i]]+=b[i];
			H[a[i]]++;
		}
		int s=0;
		for(int i=0;i<1000;i++){
			if(H[i]){
				if(T[i]>0)val[s++]=T[i];
				else val[s++]=M[i];
			}
		}
		std::sort(val,val+s);
		int ret=0;
		int now=0;
		for(int i=s-1;i>=0;i--){
			now+=val[i];
			ret=max(ret,(s-i)*now);
		}
		return ret;
	}
};

450:
典型DP。Div2 Hard行って

public class AlienAndSetDiv1{
	public int getNumber(int a,int b){
		int mod=1000000007;
		int dp[][][]=new int[a+1][a+1][1<<(b)]; // white, black, bit(black)
		dp[0][b][(1<<(b))-1]=1;
		dp[b][0][0]=1;
		for(int i=0;i<=a;i++){
			for(int j=0;j<=a;j++){
				for(int k=0;k<(1<<(b));k++){
					if(dp[i][j][k]==0)continue;
					//System.out.println(i+" "+j+" "+k+" "+dp[i][j][k]);
					//white
					if(i<a){
						boolean ok=false;
						if(i>=j)ok=true;
						int m=0;
						for(int l=1;l<b;l++){
							if((k&(1<<l))>0)m++;
						}
						if(i<j-m)ok=true;
						if(ok){
							dp[i+1][j][k/2]=(dp[i+1][j][k/2]+dp[i][j][k])%mod;
						}
					}
					//black
					if(j<a){
						boolean ok=false;
						if(i<=j)ok=true;
						int m=0;
						for(int l=1;l<b;l++){
							if((k&(1<<l))==0)m++;
						}
						if(i-m>j)ok=true;
						if(ok){
							dp[i][j+1][k/2+(1<<(b-1))]=(dp[i][j+1][k/2+(1<<(b-1))]+dp[i][j][k])%mod;
						}
					}
				}
			}
		}
		int ret=0;
		for(int i=0;i<(1<<(b));i++)ret=(ret+dp[a][a][i])%mod;
		return ret;
	}
}

1000:
どうせ区間DPだし時間がたくさんあれば解けると思う。

challenge:
落ちそうな250が多すぎて迷うレベル。1つ落とした。

232.6 + 293.7 + 0 + 50 = 576.3 (14th)
Rating: 2348 -> 2426 (+78)
ようやくなんとかなった感じ。まあこんなセットでレート上げてもねえ…。今回は本当にレーティング以外のものが得られませんでした。

余談
EasyはC++で、MediumはJavaで通しました。こういうことやって両方通るのは結構珍しいです。