TopCoder SRM398 Div2 250Pts

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

A0、X、Y、Mとnという整数が与えられる。以下のルールに従って、数列Aを作成する。

• A[0] = A0
• A[i] = (A[i - 1] * X + Y) % M (0 < i < n)

できあがった数列Aの、2要素の絶対値誤差が最小になる組を求め、その絶対値誤差を返すメソッドを作成せよ。

私の解答はこちら。

import java.util.Arrays;

public class MinDifference {

 public int closestElements(int A0, int X, int Y, int M, int n) {
  int[] A = new int[n];
  A[0] = A0;
  for( int i=1 ; i<n ; i++ ){
   A[i] = (A[i-1] * X + Y) % M;
  }
  Arrays.sort(A);
  int min = Math.abs(A[1] - A[0]);
  for( int i=1 ; i<n ; i++ ){
   min = Math.min(min, Math.abs(A[i] - A[i-1]));
  }
  return min;
 }

}

得点は246.56/250、1回のsubmitでシステムテストクリア。中央値は約217点。工夫したのは数列Aに対し、ソートするという点で、これにより、絶対値誤差の最小値の候補が隣合う要素のみになるということが挙げられます。