SRM過去問 SRM357 Div2

明日SRMだし、過去問解いてみた。

500を安定させる練習にもなるし。

250:MnemonicMemory
文字列をソートしてなんだかんだするだけ。面倒。
どうやらJavaではデフォルトでStringをソートできるらしい。
無難に228.42点。いまいちよくない。まあしかたがない。

import java.util.*;

public class MnemonicMemory{


	public String getPhrase(String a,String[] b){
		Arrays.sort(b);
		String[] ret=new String[a.length()];
		for(int i=0;i<a.length();i++){
			int keta=(int)(a.charAt(i)-'0');
			for(int j=0;j<b.length;j++){
				if(keta==b[j].length()){
					ret[i]=b[j];
					b[j]="";
					break;
				}
			}
		}
		String ans="";
		for(int i=0;i<ret.length-1;i++)ans+=ret[i]+" ";
		return ans+ret[ret.length-1];
	}
}

500:Hotel
ちょっと考えたら気がついたDP。250より正直言って楽。
459.00点。250点換算だと229.50点だから、こっちのほうが速かったみたい。
誰にでもソース読めば分かるはず。

public class Hotel{
	public int marketCost(int a,int b[],int c[]){
		int[]dp=new int[a+100];
		dp[0]=0;
		for(int i=1;i<a+100;i++)dp[i]=999999999;
		for(int i=0;i<a;i++){
			for(int j=0;j<b.length;j++){
				dp[i+b[j]]=Math.min(dp[i+b[j]],dp[i]+c[j]);
			}
		}
		int min=999999999;
		for(int i=a;i<a+100;i++){
			if(dp[i]!=0)min=Math.min(dp[i],min);
		}
		return min;
	}
}

1000:WebsiteRank
むり。問題文の意味分からん。

結果
228.42+459.00=687.42

良い。