読者です 読者をやめる 読者になる 読者になる

SRM 577

今日はwriterがたくさんいたらしいです。

250:EllysRoomAssignmentsDiv1
期待値の計算を数学します。数学するのが結構大変なのでかなりみんな提出が遅い…(自分も遅いです)

import java.util.*;
public class EllysRoomAssignmentsDiv1{
	public double getAverage(String[]a){
		String str="";
		for(int i=0;i<a.length;i++)str+=a[i];
		String[]v=str.split(" ");
		int[]b=new int[v.length];
		int n=b.length;
		for(int i=0;i<n;i++)b[i]=Integer.parseInt(v[i]);
		int C=b[0];
		Arrays.sort(b);
		int at=0;
		for(int i=0;i<n;i++)if(C==b[i])at=i;
		int R=(n+19)/20;
		int W=n/R;
		System.out.println(R);
		if(at<n%R){
			double V=C;
			int m=0;
			double now=0;
			for(int i=0;i<R*W;i++){
				now+=b[n-1-i];
				m++;
			}
			V+=now/R;
			return V/(W+1);
		}else{
			double V=C;
			int m=0;
			double now=0;
			for(int i=0;i<R*W;i++){
				if(i/R!=(n-1-at)/R){
					now+=b[n-1-i];
					m++;
				}
			}
			if(m>0)V+=now/R;
			double NOW=0;
			for(int i=0;i<n%R;i++)
				NOW+=b[i];
			if(n%R>0)NOW/=n%R;
			return (V+NOW)/(W+1)*(n%R)/R+V/W*(R-n%R)/R;
		}
	}
}

500:EllysChessBoard
マンハッタン距離なので取り合えず45°回転させるという発想はすぐ出てくるのですが、それを何か活用できるのかと言われると結構微妙な感じです。式展開とかいろいろしたらこれ区間DPではという感じになって区間DPを書いた。合っていて謎。提出後修正しようとしたらそっちは答えが違った。

import java.util.*;
public class EllysChessboard{
	int p[][];
	int dp[][][][];
	int inf=100000000;
	int solve(int a,int b,int c,int d){
		if(dp[a][b][c][d]!=inf)return dp[a][b][c][d];
		int ret=inf;
		if(a!=c){
			int v=0;
			for(int i=b;i<=d;i++){
				if(p[a][i]==1){
					int A=0;
					for(int j=a+1;j<=c;j++){
						for(int k=b;k<=d;k++){
							A=Math.max(A,Math.max(Math.abs(j-a),Math.abs(k-i)));
						}
					}
					v+=A;
				}
			}
			ret=Math.min(ret,v+solve(a+1,b,c,d));
			v=0;
			for(int i=b;i<=d;i++){
				if(p[c][i]==1){
					int A=0;
					for(int j=a;j<c;j++){
						for(int k=b;k<=d;k++){
							A=Math.max(A,Math.max(Math.abs(j-c),Math.abs(k-i)));
						}
					}
					v+=A;
				}
			}
			ret=Math.min(ret,v+solve(a,b,c-1,d));
			
		}
		if(b!=d){
			int v=0;
			for(int i=a;i<=c;i++){
				if(p[i][b]==1){
					int A=0;
					for(int j=b+1;j<=d;j++){
						for(int k=a;k<=c;k++){
							A=Math.max(A,Math.max(Math.abs(j-b),Math.abs(k-i)));
						}
					}
					v+=A;
				}
			}
			ret=Math.min(ret,v+solve(a,b+1,c,d));
			v=0;
			for(int i=a;i<=c;i++){
				if(p[i][d]==1){
					int A=0;
					for(int j=b;j<d;j++){
						for(int k=a;k<=c;k++){
							A=Math.max(A,Math.max(Math.abs(j-d),Math.abs(k-i)));
						}
					}
					v+=A;
				}
			}
			ret=Math.min(ret,v+solve(a,b,c,d-1));
		}
		return dp[a][b][c][d]=ret;
	}
	public int minCost(String[]a){
		p=new int[15][15];
		dp=new int[15][15][15][15];
		for(int i=0;i<8;i++)
			for(int j=0;j<8;j++)
				if(a[i].charAt(j)=='#')p[i+j][i-j+7]=1;
	//	int inf=100000000;
		for(int i=0;i<15;i++)
			for(int j=0;j<15;j++)
				for(int k=0;k<15;k++)
					for(int l=0;l<15;l++)
						dp[i][j][k][l]=inf;
		for(int i=0;i<15;i++)
			for(int j=0;j<15;j++)
				dp[i][j][i][j]=0;
		return solve(0,0,14,14);
	}
}

1000:
明らかにヤバイ 最近こういう問題Div1Hardでよく見る。

Challenge Phase:
落としようがない感じの問題&提出数

System Test:
通る

160.0 + 238.4 + 0 + 0 = 398.4 (15th)
Rating: 2033 -> 2172(+39)
今まででぶっちぎりで最高順位。久しぶりに黄色に戻りました。
次で赤になります。