TopCoder練習 SRM 423 DIV2

250問題文

public class TheSimpleGame {
 public int count(int n, int[] x, int[] y) {
  int a = (n+1)/2;
  int b = 0;
  for(int i = 0; i < x.length; i++) {
   b += (x[i] <= a) ? x[i] - 1 : n - x[i];
   b += (y[i] <= a) ? y[i] - 1 : n - y[i];
  }
  return b;
 }
}

簡単。

600

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;

public class TheTower {
 public int[] count(int[] x, int[] y) {
  int[] a = new int[x.length];
  a[0] = 0;
  if(x.length == 1) {
   return a;
  }
  ArrayList<Integer> xList = new ArrayList<Integer>();
  ArrayList<Integer> yList = new ArrayList<Integer>();
  for(int i = 0; i < x.length; i++) {
   boolean flag1 = false;
   boolean flag2 = false;
   for(int j = 0; j < xList.size(); j++) {
    if(x[i] == xList.get(j)) {
     flag1 = true;
     break;
    }
   }
   if(!flag1) {
    xList.add(x[i]);
   }
   for(int j = 0; j < yList.size(); j++) {
    if(y[i] == yList.get(j)) {
     flag2 = true;
     break;
    }
   }
   if(!flag2) {
    yList.add(y[i]);
   }
  }
  for(int i = 1; i < x.length; i++) {
   ArrayList<Integer> list = new ArrayList<Integer>();
   for(int j = 0; j < xList.size(); j++) {
    for(int k = 0; k < yList.size(); k++) {
     list.add(checkCell(xList.get(j), yList.get(k), i+1, x, y));
    }
   }
   Collections.sort(list);
   a[i] = list.get(0);
  }
  return a;
 }
 
 private int checkCell(int x, int y, int n, int[] arrayX, int[] arrayY) {
  int[] array = new int[arrayX.length];
  for(int i = 0; i < array.length; i++) {
   array[i] = (int)Math.abs((double)(x - arrayX[i])) + (int)Math.abs((double)(y - arrayY[i]));
  }
  Arrays.sort(array);
  int move = 0;
  for(int i = 0; i < n; i++) {
   move += array[i];
  }
  return move;
 }
}

間違えたので後で修正した解答。
問題文は読めても結構難しい問題だと思う。これが600か。
おそらく、移動先のx,yはそれぞれのメジアン（中央値）になる。（ただしチェッカーが偶数のときは中央2つの平均ではなく、その2つのどちらかになる
そう考えると、x座標のリストと、y座標のリストの組み合わせ分だけ考慮すればいいので、その中で一番移動数が少ないものを選ぶ。