散々な結果に、TopCoder SRM661

今日は自宅作業、仕事合間の休憩がてらにTopCoderに参加。

easyは、oが砂、xが壁で砂を自由落下させるとき、
砂は壁の上をとどまるという条件で、最終条件がどうなるか求めよという問題。
一番下から見ていく方針でやりましたが、多分いちばん楽な解はスワップしていくだけということ。


public class FallingSand {

public String[] simulate(String[] board) {
boolean[][] sand = new boolean[board.length][board[0].length()];
for(int i = board.length - 1 ; i >= 0 ; i--){
for(int j = 0 ; j < board[0].length(); j++){
if(board[i].charAt(j) == 'o'){
int lastindex = i;
for(int k = i + 1 ; k < board.length ; k++){
if(sand[k][j] || board[k].charAt(j) == 'x')break;
lastindex = k;
}
sand[lastindex][j] = true;
}
}
}
String[] str = new String[board.length];
for(int i = 0 ; i < str.length ; i++){
String subs = "";
for(int j = 0 ; j < board[0].length(); j++){
if(sand[i][j]){
subs += "o";
}else if(board[i].charAt(j) == 'x'){
subs += "x";
}else{
subs += ".";
}
}
str[i] = subs;
}
return str;
}

}


mediumは、2行の点が1列ごとにそれぞれコストa[i]、b[i]で結ばれているので、
ちょうどK本上の行から下の行に垂直にコスト0の線を伸ばした時に、
ある点からある点へのコストの最大値がなるべく小さくなるようにせよという問題。
1行が最大でも12列しかないので、2^12は4096パターンしかなく、
総当りで良いでしょうと。
後は愚直に全パターンをダイクストラ法でやっても、間に合うでしょうと実装にとりかかっていましたが、
まさかの自分のライブラリの仕様を忘れていたせいで、間に合わず。

初期化は-1ではなく、大きな値でやらないといけない仕様にしていました。ああっ…。


public class BridgeBuildingDiv2 {

public int minDiameter(int[] a, int[] b, int K) {
int[][] paths = new int[(a.length + 1) * 2][(a.length + 1) * 2];
for(int i = 0 ; i < paths.length ; i++){
for(int j = 0 ; j < paths.length ; j++){
if(i == j){
paths[i][j] = 0;
}else{
paths[i][j] = 1000000000;
}
}
}

for(int i = 0 ; i < a.length ; i++){
paths[i][i + 1] = a[i];
paths[i + 1][i] = a[i];
paths[i + a.length + 1][i + a.length + 2] = b[i];
paths[i + a.length + 2][i + a.length + 1] = b[i];
}

long min = Long.MAX_VALUE;
int max = (int)Math.pow(2, a.length + 1);
for(int i = 1 ; i < max ; i++){
long tmp = Integer.MIN_VALUE;
if(Integer.bitCount(i) == K){
String st = Integer.toBinaryString(i);
int less = a.length + 1 - st.length();
for(int j = 0 ; j < less ; j++){
st = "0"+st;
}
for(int j = 0 ; j < a.length + 1 ; j++){
if(st.charAt(j) == '1'){
paths[j][j + a.length + 1] = 0;
paths[j + a.length + 1][j] = 0;
}
}

for(int j = 0 ; j < paths.length ; j++){
for(int k = j + 1 ; k < paths.length ; k++){
tmp = Math.max(dijkstra(j,k,paths.length,paths), tmp);
}
}

for(int j = 0 ; j < a.length + 1 ; j++){
if(st.charAt(j) == '1'){
paths[j][j + a.length + 1] = 1000000000;
paths[j + a.length + 1][j] = 1000000000;
}
}
min = Math.min(tmp, min);
}
}


return (int)min;
}

//初期化は大きい値でやること
public static long dijkstra(int st,int g,int n,int[][] dist){
int x;
long min;
long INF = 1000000000000000000l;
boolean[] used = new boolean[n];
long[][] cost = new long[n][n];
int rindex = -1;
for(x = 0; x < n; x++){
for(int y = 0 ; y < n ; y++){
cost[y][x] = INF;
}
}
cost[g][g] = 0;
while(true){
min = INF;
for(x = 0; x < n; x++){
if(!used[x] && min > cost[g][x]){
min = cost[g][x];
rindex = x;
}
}

if(min == INF)break;
for(x = 0; x < n; x++){
if(cost[g][x] > dist[x][rindex] + cost[g][rindex]){
cost[g][x] = dist[x][rindex] + cost[g][rindex];
}
}
used[rindex] = true;
}
if(cost[g][st] == INF){
return -1;
}else{
return cost[g][st];
}
}

}


1065 -> 1068と、なんとも言えない結果に。
そして、某アレは一瞬で8000が吹き飛んでいてだいぶ悲惨なことに。

夜はジムに行き、筋トレメインに。後は15min/(10.0km/h)を軽くやるのみ。

ゲーセンはEXUSIA(A)をクリアできそうにも、ラストで削られ死亡。
散々な結果に、TopCoder SRM661_f0019846_64550100.jpg


December Breezeは91.9%に更新。
散々な結果に、TopCoder SRM661_f0019846_6461490.jpg

  by ddrer-yossi | 2015-06-12 23:35 | TopCoder

<< ひたすらシレン Xperia Z4に機種変更。... >>

SEM SKIN - DESIGN by SEM EXE