読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 512 Div1 Medium: SubFibonacci

解法

d.hatena.ne.jp

コード

import java.util.Arrays;

public class SubFibonacci {
	private final int MAX_F = 46;

	public int maxElements(int[] S) {
		long[] fib = new long[MAX_F];
		fib[0] = 1;
		fib[1] = 0;
		for (int i = 2; i < fib.length; i++) {
			fib[i] = fib[i - 1] + fib[i - 2];
		}

		Arrays.sort(S);
		int N = S.length;
		int[][] max = new int[N][N];
		for (int i = 0; i < N; i++) {
			max[i][i] = 1;
			for (int j = i + 1; j < N; j++) {
				for (int a = 0; a < MAX_F - 1; a++) {
					for (int b = 0; b < MAX_F - 1; b++) {
						if (a == b) {
							continue;
						}
						// 連立方程式を解く
						// S[i] = fib[a] * x + fib[a + 1] * y;
						// S[j] = fib[b] * x + fib[b + 1] * y;
						long y = (long) S[i] * fib[b] - (long) S[j] * fib[a];
						y /= (fib[a + 1] * fib[b] - fib[b + 1] * fib[a]);
						long x = 0;
						if (fib[a] == 0) {
							x = S[j] - fib[b + 1] * y;
							x /= fib[b];
						} else {
							x = S[i] - fib[a + 1] * y;
							x /= fib[a];
						}

						// 連立方程式の解が不適ならスルー
						if (x <= 0 || y <= 0) {
							continue;
						}
						if (S[i] != fib[a] * x + fib[a + 1] * y) {
							continue;
						}
						if (S[j] != fib[b] * x + fib[b + 1] * y) {
							continue;
						}

						// 解を元にフィボナッチ数列を作る
						long[] tmpFib = new long[MAX_F];
						for (int k = 0; k < MAX_F - 1; k++) {
							tmpFib[k] = fib[k] * x + fib[k + 1] * y;
						}

						// フィボナッチ数列と一致する部分列の項の数を求める
						int s = i;
						int cnt = 0;
						for (int k = 0; k < MAX_F - 1; k++) {
							while (s < j && tmpFib[k] > S[s]) {
								s++;
							}
							if (tmpFib[k] == S[s]) {
								s++;
								cnt++;
							}
							if (s > j) {
								break;
							}
						}

						max[i][j] = Math.max(max[i][j], cnt);
					}
				}

			}
		}

		int ans = 0;
		for (int i = 0; i < N; i++) {
			for (int j = i; j < N; j++) {
				for (int k = j + 1; k < N; k++) {
					for (int l = k; l < N; l++) {
						ans = Math.max(ans, max[i][j] + max[k][l]);
					}
				}
			}
		}
		for (int i = 0; i < N; i++) {
			for (int j = i; j < N; j++) {
				ans = Math.max(ans, max[i][j]);
			}
		}

		return ans;
	}
}