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)