SRM 495 Div1

引退級。もうTopCoderやめてもいい気がする。JOI近いし。

275:なにか
てきとうにDPやる。両側から。これintじゃあふれるじゃないか→再提出。
別に何通りあるかじゃなかったし。もういいや

public class ColorfulCards{
	public int[] theCards(int a,String b){
		char[] c=b.toCharArray();
		boolean [][] dp1=new boolean[b.length()][a];
		boolean [][] dp2=new boolean[b.length()][a];
		int []isPrime=new int[a+1];
		isPrime[0]=-1;
		isPrime[1]=-1;
		for(int i=2;i<a+1;i++){
			if(isPrime[i]!=-1){
				isPrime[i]=1;
				for(int j=i*2;j<a+1;j+=i)isPrime[j]=-1;
			}
		}
		for(int i=0;i<a;i++){
			if(c[0]=='B'&&isPrime[i+1]==-1){
				dp1[0][i]=true;
			}
			else if(c[0]=='R'&&isPrime[i+1]==1){
				dp1[0][i]=true;
			}
		}
		for(int i=1;i<c.length;i++){
			for(int j=0;j<a;j++){
				if(c[i]=='B'&&isPrime[j+1]==-1){
					for(int k=0;k<j;k++){
						if(dp1[i-1][k])dp1[i][j]=true;
					}
				}else if(c[i]=='R'&&isPrime[j+1]==1){
					for(int k=0;k<j;k++){
						if(dp1[i-1][k])dp1[i][j]=true;
					}
				}
			}
		}

		
		for(int i=0;i<a;i++){
			if(c[c.length-1]=='B'&&isPrime[i+1]==-1){
				dp2[c.length-1][i]=true;
			}
			else if(c[c.length-1]=='R'&&isPrime[i+1]==1){
				dp2[c.length-1][i]=true;
			}
		}
		for(int i=c.length-2;i>=0;i--){
			for(int j=0;j<a;j++){
				if(c[i]=='B'&&isPrime[j+1]==-1){
					for(int k=a-1;k>j;k--){
						if(dp2[i+1][k])dp2[i][j]=true;
					}
				}else if(c[i]=='R'&&isPrime[j+1]==1){
					for(int k=a-1;k>j;k--){
						if(dp2[i+1][k])dp2[i][j]=true;
					}
				}
			}
		}
	
		int ret[]=new int[c.length];
		for(int i=0;i<c.length;i++){
			int at=0;
			for(int j=0;j<a;j++){
				if(dp1[i][j]&&dp2[i][j]){
					if(at!=0)at=-1;
					else at=j+1;
				}
			}
			if(at==0)at=-1;
			ret[i]=at;
		}
		return ret;
	}
}

絶対無駄だなぁ　そして遅すぎるなぁ
もっと問題を解くべきなのかなぁ

500:なんか
知るか

975:エレベーターが何か
知るか

Challenge Phase
みんなと解法が違いすぎて何も出来ない

System test
とおった

Result
oxx 114.73 423rd
1532 -> 1509 (-∞)

またプロフィール開くとMarathonが出るようになった。
かろうじてはいいろ。もうじき色もらえなくなりそう。