TopCoder SRM230 Div2 250Pts

このTopCoderの問題はこちらで見ることができる(要TopCoder登録 & 問題文は英語)。それでは、問題について説明する。なおSRM 231のDiv2 250PtsはSRM 186と同じ問題なので、省略する。

数学的帰納法により、次の式を示すことができる。
s = 1³ + 2³ + ... + (n-1)³ < n⁴ < 1³ + 2³ + ... + n³ = S

上の式にnが与えられたとして、(S+s)/2 - n⁴/4を表す分数を返せ。ただし、分数は2要素の整数型配列からなり、一つ目の要素が分子、二つ目の要素が分母を表すものとする。また、約分も行うこと。

私の解答は以下の通り。

public class InequalityChecker {
 public int[] getDifferences(int n) {
  int s = ((n-1)*n/2)*((n-1)*n/2);
  int S = (n*(n+1)/2)*(n*(n+1)/2);
  int num = 2*(S+s)-n*n*n*n;
  int den = 4;
  if( num % 4 == 0){
   num /= 4;
   den /= 4;
  }else if( num % 2 == 0 ){
   num /= 2;
   den /= 2;
  }
  return new int[]{num,den};
 }
}

得点は235.09/250、中央値は約160点。開催時の提出者の正解率は約90%。最大公約数の計算が不要なので、約分も難しくないと思います。分母の候補は(2(s+S)-n⁴)/4を返すということから1,2,4しかありえないので、2、4で割り切れるか検討すればOKということになります。また、sやSの計算には高校数学で習うシグマの公式を利用しているので、ちょっとわかりにくいかもしれません。ただ、O(1)で計算できるので速い計算になると思います。