tozangezan's diary

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

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)

こんなんでも赤残れるんだね。正直意外。