KOJ 0021 - MAX Sequence

問題 : MAX Sequence

解法 :

少し場合分けをすれば, 各クエリに対して$O(1)$ で答えが求まる.
数列は, 基本的には一定の値に収束するかずっと1 ずつ増加する.
厄介な場合として, 入力された範囲で配列が再帰的に自分を参照する場合がある. これを回避するには数列を適当な長さまで伸ばして, 最初の何項かを事前計算すれば良い. (前計算する範囲の上界を, 問題の性質から抑えられた気がしたが忘れてしまった……)

コード :

#include <cstdio>
#include <algorithm>

using namespace std;

int main()
{
	int m, q;
	
	while (scanf("%d %d", &m, &q) && m){
		long long int a[1024], maxi = -1;
		
		for (int i = 1; i <= m; i++){
			scanf("%lld", a + i);
			maxi = max(maxi, a[i]);
		}
		
		for (int i = m + 1; i <= 1023; i++){
			a[i] = a[min((long long int)(i - 1), maxi)] + 1;
			maxi = max(a[i], maxi);
		}
		
		for (int i = 0; i < q; i++){
			long long int x;
			scanf("%lld", &x);
			
			if (x <= 1023) printf("%lld", a[x]);
			else if (maxi <= 1023){
				if (a[maxi] + 1 <= 1023) printf("%lld", a[maxi] + 1);
				else printf("%lld", a[maxi] + x - 1023);
			}
			else {
				if (a[1023] + x - 1023 <= maxi || a[1023] >= 1023) printf("%lld", a[m] + x - m);
				else printf("%lld", maxi);
			}
			
			printf("%c", i == q - 1 ? '\n' : ' ');
		}
	}
	
	return (0);
}