TopCoder SRM301 Div2 250Pts

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

すべて値が異なる数列Aを挿入ソートで昇順にソートする。数列Aの先頭から順に挿入先を決めて、途中に挿入することになれば、後ろに要素をずらして値を挿入する。さて、A[]というすべて値が異なる数列が与えられたときに、挿入ソートで数値をずらした回数を返すメソッドを作成せよ。

例えば、A={2,4,3,1}という数列をソートすると4という値が返されることになる。これは2、4を挿入した後に、3を挿入すると、4がずれて1回。さらに1を挿入すると、2、3、4がずれて3回ずらすことになり、全部で4回ずらすからである。

私の解答はこちら。

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

public class InsertionSortCount {

 public int countMoves(int[] A) {
  ArrayList<Integer> al = new ArrayList<Integer>();
  int ret = 0;
  for( int i=0 ; i<A.length ; i++ ){
   int n = A[i];
   for( int j=0 ; j<al.size() ; j++ ){
    if( n < al.get(j) ){
     ret += al.size()-j;
     break;
    }
   }
   al.add(n);
   Collections.sort(al);
  }
  return ret;
 }

}

得点は194.01/250、中央値は約219点。毎回Collections.sortを呼ばないで、昇順でソートするTreeSetを使っても良かったかもしれない。