TopCoder SRM278 Div2 300Pts

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

グループに分けられた長方形のリストを持っている。グループのインデックスはグループ内のすべての長方形の面積の総和である。もっとも大きいインデックスになるグループを求めようとしている。rectangles[]という文字列型の配列が与えられる。各要素は1つの長方形を表しており、そのフォーマットは"G L W"で表される。Gは長方形が属するグループ、Lは長方形の高さ、Wは長方形の幅を表している。作成するメソッドが返す文字列のフォーマットは"G I"である。Gは最大のインデックスになるグループの名前、Iはそのグループのインデックスである(先頭に0はつかない)。もし最大のインデックスになるものが複数あった場合、アルファベット順で一番最初に来るものを返すようにせよ。グループを表す文字は正規表現で言うところの[A-Z]である。

私の解答はこちら。

import java.util.Set;
import java.util.TreeMap;

public class RectangleGroups {

 public String maximalIndexed(String[] rectangles) {
  String[] work;
  // キー値をアルファベット順にしておくためにTreeMapを利用する。
  TreeMap<String, Integer> tm = new TreeMap<String, Integer>();
  for( int i=0 ; i<rectangles.length ; i++ ){
   work = rectangles[i].split(" ");
   // 面積sは必ず利用するので先に計算しておく。
   int s = Integer.parseInt(work[1])*Integer.parseInt(work[2]);
   if( tm.containsKey(work[0]) == false ){
    tm.put(work[0], s);
   }else{
    Integer v = (Integer)tm.get(work[0]);
    tm.remove(work[0]);// 本当はリムーブは不要で
    tm.put(work[0], v+s); // これで上書きすればよい。
   }
  }
  Set<String> it = tm.keySet();
  String[] keys = (String[]) it.toArray(new String[0]);
  int max = 0;
  String ret = "";
  // 先頭から順にみて、面積最大を更新するグループを求める
  // ここでTreeMapを利用したことが活きる
  for( int i=0 ; i<keys.length; i++ ){
   if( tm.get(keys[i]) > max ){
    max = tm.get(keys[i]);
    ret = keys[i] + " " + max;
   }
  }
  return ret;
 }

}

得点は90.0/300、中央値は約239点。敗因はSetを配列に変換する方法(toArrayメソッドでnew String[0]を引数に取ること)を知らなかったことです。何日か前に同じようなパターンでtoArrayメソッドにはまっていたのを解消したついでに解きました。