TopCoder SRM433 Div2 250Pts

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

かつて数学がいつも大問題となっている王国があった。王家の会計のポストを充足しなければならいというときに、応募者には以下の問題が与えられた。「AとBという二つのN個の要素を持つ整数型の配列が与えられる。AとBに関する関数SをS = A0*B0 + … + AN-1*BN-1と定義する。Sをできるだけ小さくするようにAを並び替えよ。Bについては並び替えを認めないものとする。問題作成者は応募者の解答が正しいかチェックするようなプログラムを書くことに迫られた。A、Bという配列が与えられたとき、Sの取り得る最小値を返すようなメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class RoyalTreasurer {

 public int minimalArrangement(int[] A, int[] B) {
  Arrays.sort(A);
  Arrays.sort(B);
  for( int i=0 ; i<A.length/2 ; i++ ){
   int tmp = A[i];
   A[i] = A[A.length-i-1];
   A[A.length-i-1] = tmp;
  }
  int sum = 0;
  for( int i=0 ; i<A.length ; i++ ){
   sum += A[i]*B[i];
  }
  return sum;
 }

}

得点は246.01/250、1回のsubmitでシステムテストクリア。Sが最小値を取るのはAを降順、Bを昇順に並び替えて、添字が同じものを順に掛け算したときになります。Bを並べ替えるなと言っても、並べ替えた方が簡単というちょっと意地悪な問題。