SRM 579
いつもwriterをするときにろくでもない文章を書いてmisofさんを困らせていたので、仕返しされました。
250: TheEnglishReadingDivOne
英語を読むだけ。(Mediumのコード書くより難しい。てか結局問題の意味わからなかったし)
public class UndoHistory{ public int minPresses(String[]a){ //Arrays.sort(a); int n=a.length; int ret=a[0].length()+1; for(int i=1;i<a.length;i++){ int v=2+a[i].length()+1; if(a[i].startsWith(a[i-1]))v=1+a[i].length()-a[i-1].length(); for(int j=0;j<i;j++){ int tp=0; for(int k=0;k<Math.min(a[i].length(),a[j].length());k++){ if(a[i].charAt(k)!=a[j].charAt(k))break; tp++; } v=Math.min(v,2+a[i].length()-tp+1); } ret+=v; } return ret; } }
450:Tenkei
典型すぎるのでコード書くだけ。遷移が面倒
public class TravellingPurchasingMan{ int p; int [][]dp; int [][]g; boolean [][]v; int L[]; int R[]; int N; int T[]; int solve(int bit,int at){ if(v[bit][at])return dp[bit][at]; int ret=999999999; int prev=(bit-(1<<at)); if(prev==0){ ret=g[N-1][at]; } for(int i=0;i<p;i++){ if((prev&(1<<i))>0){ ret=Math.min(solve(prev,i)+g[i][at],ret); } } if(ret<L[at])ret=L[at]; if(ret>R[at]){ ret=999999999; }else ret+=T[at]; v[bit][at]=true; dp[bit][at]=ret; //System.out.println(bit+" "+at+" "+ret); return ret; } public int maxStores(int a,String[]b,String[]c){ p=b.length; L=new int[p]; R=new int[p]; N=a; T=new int[p]; for(int i=0;i<p;i++){ L[i]=Integer.parseInt(b[i].split(" ")[0]); R[i]=Integer.parseInt(b[i].split(" ")[1]); T[i]=Integer.parseInt(b[i].split(" ")[2]); } dp=new int[1<<p][p]; g=new int[a][a]; v=new boolean[1<<p][p]; for(int i=0;i<a;i++) for(int j=0;j<a;j++) g[i][j]=999999999; for(int i=0;i<a;i++)g[i][i]=0; for(int i=0;i<c.length;i++){ int x=Integer.parseInt(c[i].split(" ")[0]); int y=Integer.parseInt(c[i].split(" ")[1]); int z=Integer.parseInt(c[i].split(" ")[2]); g[x][y]=g[y][x]=z; } for(int k=0;k<a;k++) for(int i=0;i<a;i++) for(int j=0;j<a;j++) g[i][j]=Math.min(g[i][j],g[i][k]+g[k][j]); for(int i=0;i<p;i++) for(int j=0;j<(1<<p);j++) dp[j][i]=999999999; for(int i=0;i<p;i++){dp[0][i]=g[a-1][i];v[0][i]=true;} for(int i=0;i<p;i++)solve((1<<p)-1,i); int ret=0; for(int i=0;i<(1<<p);i++){ int count=0; for(int j=0;j<p;j++)if((i&(1<<j))>0)count++; for(int j=0;j<p;j++){ if(dp[i][j]!=999999999){ ret=Math.max(ret,count); } } } return ret; } }
1000:Janken
いる~~~~~~~ん
Challenge Phase:ながめた
System Test:Easyの解釈当たってた
128.82 + 275.96 + 0 = 404.78 (111th)
Rating: 2212 -> 2237 (-75)
こんなんでも赤残れるんだね。正直意外。