[C++]白準17968号:Fire on Field

質問リンク

17968号：Fire on Field

問題の概要

数列AのA[0]A[0]A[0]およびA[1]A[1]A[1]は1である.iが2より大きい場合、a[i]は、以下を求めることができる.
k>0 k>0 k>0に対して、i-2 k≧0 i-2 kgeq 0 i-2 k≧0のすべての整数k
A[i]−A[i−k]≠A[i−k]−A[i−2×k]A[i] - A[i - k]\neq A[i -k] - A[i - 2\times k]A[i]−A[i−k]​=A[i−k]−A[i−2×k]が成立する最小正の整数はA[i]である.
Nが与えられた場合、A[N]A[N]A[N]を出力する必要がある.

方法

簡単な実装、DP問題.A[0]、A[1]は予め値を初期化し、A[2]はすべてのkが条件に合致することを保証するために値を1から1に増やし始める.成立が見つかった場合、ループを終了し、次のA[i]値を得る.

コード#コード#

#include <bits/stdc++.h>

using namespace std;

int main(void) {
	int n;
	cin >> n;

	vector<int> a(n + 1);
	a[0] = a[1] = 1;

	for (int i = 2; i <= n; i++) {

		int num = 1;
		while (1) {
			bool flag = false;
			a[i] = num++;
			for (int j = 1; i - 2 * j >= 0; j++) {
				if (a[i] - a[i - j] == a[i - j] - a[i - 2 * j]) {
					flag = true;
					break;
				}
			}

			if (!flag)
				break;
		}
	}

	cout << a[n] << '\n';
	return 0;
}