SRM過去問 SRM471 Div2

なんか解いた覚えがある問題だと思ったら、本当にそうだった。記録に残ってないけどあのときNo Contestだったのね。懐かしい。あの時もそういや2完だったな。

250: PrimeContainers
問題文が良く分からない。225点しか取れない。

public class PrimeContainers{
	public boolean isPrime(int a){
		if(a==2)return true;
		if(a==1)return false;
		if(a%2==0)return false;
		for(int i=3;i*i<=a;i+=2)if(a%i==0)return false;
		return true;
	}
	public int containerSize(int a){
		int ret=0;
		while(a>1){
			if(isPrime(a))ret++;
			a/=2;
		}
		return ret;
	}
}

500: EllysPlaylists
楽なDPなのにDPってとこまでしか思いつかない。400点も取れない。

import java.util.*;

public class EllysPlaylists{
	public int countPlaylists(String[] name,int a){
		int [][] dp=new int[name.length][a];
		for(int i=0;i<name.length;i++){
			dp[i][0]=1;
		}
		for(int i=1;i<a;i++){
			for(int j=0;j<name.length;j++){
				for(int k=0;k<name.length;k++){
					if(true){
						if(name[k].substring(0,3).equals(name[j].substring(name[j].length()-3))){
							dp[k][i]=(dp[k][i]+dp[j][i-1])%1000000007;
						}
					}
				}
			}
		}
		int ret=0;
		for(int i=0;i<name.length;i++){
			ret=(dp[i][a-1]+ret)%1000000007;
		}
		return ret;
	}
}

1000: Thirteen
BFSかもしれない。わからない。

まとめ:
この回もなかなか厳しい。こんなんでレーティング上がるのだろうか。
700点は欲しい。