SRM 369 500pt: AbsSequence

問題概要

ある数列の初項A[0]、第二項A[1]が与えられる。数列はA[n] = abs(A[n-1]-A[n-2])を満たす。第k項を求めよ、というクエリをN(<50)個程度処理せよ。数字は全て非負で10^18以下。

考えたこと

• 入力がまたstringで与えられて非常に鬱陶しい。この辺は今でもたまに感じる(グラフがvectorで与えられたり)。
• これそのうちループに落ちるんだよね。というかやってることってgcdの計算そのものだ。
• gcdのmodの代わりに引き算使ってるだけなので、アイデアはすぐ分かるんだけど実装面倒そう。
• ある状態の先頭２つA、Bがわかっているとき、B, A%Bまでは規則的に落ちそう。mapに節目だけ突っ込んでlower_boundで探す感じか。
• でもA,Bの大小関係とかあってやっぱり面倒くさい。
• 節目でA=Bになるまで愚直にシミュレーションしよう。
• 規則を考えよう。(A=x+k*B, B)の状態から3ターン経過で(A=x+(k-2)*B, B)に落ちる。
• なので節目をlower_boundで探してそこからの経過ターン数を3で割った場合分けして出すか。
• 流石にこの場合分けは不可避だろう。
• 書けた。出した。通った。

practiceで通ったコード

計算量は大雑把にO(N*log(A))位。

#include <vector>
#include <string>
#include <sstream>
#include <map>
#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;

typedef long long int64;

struct AbsSequence {

	vector <string> getElements(string first, string second, vector <string> indices) {

		//データ変換
		int64 A = string_to_int64(first), B = string_to_int64(second);
		vector<int64> result, idxs;
		const int N = indices.size();
		for(int i=0; i<N;  i++){
			idxs.push_back( string_to_int64(indices[i]) );
		}

		//前処理
		map<int64, pair<int64,int64>, greater<int64> > dict;
		int64 cur = 0;
		dict[cur] = make_pair(A,B);
		while(A != 0 && B != 0){
			int64 k = A/B;
			if(k<=1){
				int64 C = abs(A-B);
				A = B;
				B = C;
				dict[++cur] = make_pair(A,B);
			}
			else{
				cur += k/2*3;
				A = A%B + (k&1)*B;
				dict[cur] = make_pair(A,B);
			}
		}

		//本体
		for(int i=0; i<N; i++){
			int64 ans = 0;

			int64 tmp_turn = dict.lower_bound(idxs[i])->first;
			if(tmp_turn == idxs[i]){
				ans = dict[tmp_turn].first;
			}
			else{
				int64 shift = idxs[i] - tmp_turn;
				int64 res = shift%3;
				int64 skip = shift/3;
				A = dict[tmp_turn].first;
				B = dict[tmp_turn].second;
				if(A==0 || B==0){
					if(res == 0){
						ans = A;
					}
					else if(res == 1){
						ans = B;
					}
					else{
						ans = abs(A-B);
					}
				}
				else{
					if(res == 0){
						ans = A - skip*2*B;
					}
					else if(res == 1){
						ans = B;
					}
					else{
						ans = A - (skip*2+1)*B;
					}
				}
			}


			result.push_back(ans);
		}

		//データ変換
		vector<string> ret;
		for(int i=0; i<N; i++){
			ret.push_back( int64_to_string(result[i]) );
		}
		return ret;
	}

	int64 string_to_int64(const string& a){
		stringstream ss(a);
		int64 ret;
		ss >> ret;
		return ret;
	}


	string int64_to_string(const int64 x){
		stringstream ss;
		ss << x;
		return ss.str();
	}
};