tozangezan's diary

勝手にソースコードをコピペして利用しないでください。

SRM507,508,509 Div1Medium

今日もちょっとずつMediumを埋めていきます。

SRM507 Div1Med(500)
解法:2辺の長さを決めるのはO(だいたいの体積^(5/6))で出来るので、それぞれについてもう1辺を決めます。
オーバーフローに注意。こんな問題どう考えてもオーバーフローが危険なんだから全部longでやるべきかもしれない。

public class CubePacking{
	public int getMinimumVolume(int A,int B,int C){
		long ret=2100000000;
		long a=A;
		long b=B;
		long c=C;
	//	int P=0;
	//	int Q=0;
	//	int R=0;
		for(int i=C;i<1300;i++){
			for(int j=i;(long )i*j*j<2050000000;j++){
				long s=(i/c)*(j/c);
				long dan=(b+s-1)/s;
				long K=c*dan;
				if(K*i*j-b*c*c*c<a){
					long t=a-K*i*j+b*c*c*c;
					long d=(t+i*j-1)/(i*j);
					K+=d;
				}
				if(ret>K*i*j){
					ret=K*i*j;
				//	P=i;Q=j;R=K;
				}
			}
		}
	//	System.out.println(P+" "+Q+" "+R);
		return (int)ret;
	}
}

SRM508 Div1Med(500)
解法:上の桁(2進)からどの項に1をいれるか(もしくはどこにもいれないか)を決めていきます。それ以下のbitがどうであれ必ず制約の最大値以下に出来るかどうかをn個もってbitDP。
ゆっくりやっていたら、結構正解者が多いらしく順位が低めでした。

import java.util.*;
public class YetAnotherORProblem{
	public int countSequences(long[]a){
		int MOD=1000000009;
		int n=a.length;
		int dp[][]=new int[61][1<<n];
		dp[60][0]=1;
		for(int i=60;i>0;i--){
			for(int j=0;j<(1<<n);j++){
			//	System.out.print(dp[i][j]+" ");
				int TO=j;
				for(int m=0;m<n;m++){
					if((a[m]&(1L<<(i-1)))>0&&(a[m]>=(1L<<(i-1))))TO|=(1<<m);
				}				
				dp[i-1][TO]=(dp[i-1][TO]+dp[i][j])%MOD;
				for(int k=0;k<n;k++){
					if(a[k]>=(1L<<(i-1))){
						if((j&(1<<k))>0||(a[k]&(1L<<(i-1)))>0){
							int to=j;
							for(int m=0;m<n;m++){
								if(m!=k&&(a[m]&(1L<<(i-1)))>0&&(a[m]>=(1L<<(i-1))))to|=(1<<m);
							}
							dp[i-1][to]=(dp[i-1][to]+dp[i][j])%MOD;
						}
					}
				}
			}
		//	System.out.println();
		}
		int ret=0;
		for(int i=0;i<(1<<n);i++){
			ret=(ret+dp[0][i])%MOD;
		//	System.out.print(dp[0][i]+" ");
		}
		return ret;
	}
}

SRM509 Div1Med(500)
解法:最短路っぽいものを求めてから区間DP
慎重にやらないと危険な要素が多すぎて落ちます。場合分けも多いので1回で通しにくい。本番の正答率は7%台です。

public class PalindromizationDiv1{
	long del[];
	long add[];
	long conv[][];
	long dp[][];
	String str;
	long solve(int a,int b){
		if(dp[a][b]!=-1)return dp[a][b];
		if(a+1==b||a==b)return dp[a][b]=0;
		long ret=99999999999999L;
		for(int i=0;i<26;i++){
			ret=Math.min(ret,conv[(int)(str.charAt(a)-'a')][i]+conv[(int)(str.charAt(b-1)-'a')][i]+solve(a+1,b-1));
			ret=Math.min(ret,add[i]+conv[(int)(str.charAt(a)-'a')][i]+solve(a+1,b));
			ret=Math.min(ret,add[i]+conv[(int)(str.charAt(b-1)-'a')][i]+solve(a,b-1));	
		}
		ret=Math.min(ret,del[(int)(str.charAt(a)-'a')]+solve(a+1,b));
		ret=Math.min(ret,del[(int)(str.charAt(b-1)-'a')]+solve(a,b-1));
		//System.out.println(a+" "+b+" "+ret);
		return dp[a][b]=ret;
	}
	public int getMinimumCost(String a,String[]b){
		str=a;
		del=new long[26];
		add=new long[26];
		conv=new long[26][26];
		dp=new long[a.length()+1][a.length()+1];
		for(int i=0;i<a.length()+1;i++)
			for(int j=0;j<a.length()+1;j++)dp[i][j]=-1;
		for(int i=0;i<26;i++){
			del[i]=add[i]=99999999999999L;
			for(int j=0;j<26;j++)conv[i][j]=99999999999999L;
			conv[i][i]=0;
		}
		for(int i=0;i<b.length;i++){
			if(b[i].charAt(0)=='a')add[(int)(b[i].charAt(4)-'a')]=Long.parseLong(b[i].split(" ")[2]);
			if(b[i].charAt(0)=='e')del[(int)(b[i].charAt(6)-'a')]=Long.parseLong(b[i].split(" ")[2]);
			if(b[i].charAt(0)=='c')conv[(int)(b[i].charAt(7)-'a')][(int)(b[i].charAt(9)-'a')]=Long.parseLong(b[i].split(" ")[3]);
		}
		for(int k=0;k<26;k++)
			for(int i=0;i<26;i++)
				for(int j=0;j<26;j++)conv[i][j]=Math.min(conv[i][k]+conv[k][j],conv[i][j]);
		for(int i=0;i<26;i++){
			for(int j=0;j<26;j++){
				add[i]=Math.min(add[i],add[j]+conv[j][i]);
				del[i]=Math.min(del[i],conv[i][j]+del[j]);
			}
		}
		long ret=solve(0,str.length());
		if(ret>=99999999999999L)return -1;
		else return (int)ret;
	}
}

Div1Medium Solved: 26 -> 29 (+3)