TopCoder SRM314 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。問題文について説明する。

Byterlandの牛は騒々しく鳴き、住民に迷惑をかけている。PemberleyのDarcyさんはこの問題を牛1匹だけが鳴くことを許すことによって解決しようと計画している。他の牛にもっとも攻撃的でない牛を1匹選ぶ。Pemberleyの農場はn*mの長方形の草原に分けられる。各区画は何もないか、牛がいるという状態のどちらかである。(x,y)の位置にいる牛が鳴いたとき、(i,j)の位置にいる牛の不満はユークリッド距離の2乗であらわされる。不満の総計はすべての牛の不満の合計で表される。1匹の牛が鳴くことのみを許したとき、牛の不満が最小となるときのその値を返せ。農場はfarmlang[]という文字列型の配列で表され、"."は空の区画、"C"が牛のいる区画を表すものとする。

私の解答はこちら。

import java.util.ArrayList;

public class MooingCows {

 public int dissatisfaction(String[] farmland) {
  ArrayList<Integer> xPos = new ArrayList<Integer>();
  ArrayList<Integer> yPos = new ArrayList<Integer>();
  // 前半で牛のいる位置を全部求める。
  for( int i=0 ; i<farmland.length ; i++ ){
   for( int j=0 ; j<farmland[0].length() ; j++ ){
    if( farmland[i].charAt(j) == 'C' ){
     xPos.add(i);
     yPos.add(j);
    }
   }
  }
  // 後半は各牛が鳴いたと仮定したときの不満の最小値を計算する
  int minDissatisfaction = Integer.MAX_VALUE;
  for( int i=0 ; i<xPos.size() ; i++ ){
   int x = xPos.get(i); // x,yは特定の牛1頭の位置である
   int y = yPos.get(i);
   int curDissatisfaction = 0;
   for( int j=0 ; j<xPos.size() ; j++ ){
    if( i == j ) continue; // この箇所は無くてもOK
    int cx = xPos.get(j);
    int cy = yPos.get(j);
    curDissatisfaction += (x-cx)*(x-cx)+(y-cy)*(y-cy);
   }
   if( curDissatisfaction < minDissatisfaction ) minDissatisfaction = curDissatisfaction;
  }
  return minDissatisfaction;
 }

}

得点は221.44/250、中央値は約196点。