今日は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)
今まででぶっちぎりで最高順位。久しぶりに黄色に戻りました。
次で赤になります。
