こんにちは、松野です。
今月もやりますよTopCoder問題！

TopCoder
過去問を解いてみる

今日はdiv1が50%ほどの問題を解いてみましょう。
少し考えればすぐ解けるレベルの問題だと思います。

今日の問題はコレ

等差数列の問題
例えば3, 7, 11, 15, 19という数列は、前後の項目の差は4である。
そして、数値の個数は5である。

このように、数値配列を与えて、最長の等差数列の個数を求める式を完成させなさい。

クラス名、メソッド名の仕様

クラス名：ASeries
メソッド名:longest
引数：int[]
戻値：int
シグニチャ：int longest(int[] values)

制約
引数で与えられる配列の個数はは2から50の間とする
引数で与えられる数値は、-1,000,000から1,000,000の間とする

Examples
0)
{3, 8, 4, 5, 6, 2, 2}
戻値：5
上記引数だと、2, 3, 4, 5, 6が最長の等差数列となるため、その等差数列の個数5を返す

1)
{-1, -5, 1, 3}
戻値：3
上記引数だと、-1, 1, 3(3, -1, -5でも可)が最長の等差数列となるため、その等差数列の個数3を返す

2)
{-10, -20, -10, -10}
戻値：3
この場合、-10, -10, -10が差が0の等差数列となるため、3を戻す

以下解答
答えは1つではないので、正しい動きをすれば正解です。
このプロブレムで優勝したコードを見てみましょう。
※ちなみに5分49秒で書いてsubmitしてます。

import java.util.*;
public class ASeries {
  public int longest(int[] values) {
    Arrays.sort(values);
    int res =-1;
    for (int i = 0; i < values.length; i++)  {
      for (int j = i+1; j < values.length; j++)  {
        int d = values[j] - values[i];
        int c = 0;
        for (int k = j+1; k < values.length; k++)  if (values[k] == values[j]+(1+c)*d)  c++;
        res = Math.max(res, c);
      };
    };
    return res+2;
  }
 
}

約6分でこの問題文の真意を読み取って、このコードが書けるってスゴイですね。
まだまだ勉強の余地がありそうです！

以上、今日のTopCoderでした。

 

【関連記事】
ハニーポットについて （1）サーバーを立てる
ハニーポットについて （2）アクセスログ有効活用方法
TopCoderをやろう！