TopCoderをやろう 等差数列の問題
- 2015年01月07日
- CATEGORY- 1. 技術力{技術情報}
こんにちは、松野です。
今月もやりますよ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をやろう!
- 2015年01月07日
- CATEGORY- 1. 技術力{技術情報}