SRM 485 DIV1 Easy - AfraidOfEven (復習×)

January 26, 2014

問題

http://community.topcoder.com/stat?c=problem_statement&pm=11146&rd=14238

・ある数列が与えられる。
・その数列は等差数列だが、偶数の数字は奇数になるまで２で割られている。
このとき、もとの等差数列を求める。

解き方

等差数列の差と、初項が決まれば等差数列になるかどうかは容易に判定できる。
問題文から数字はintの範囲なので、この範囲で全探索すれば答えが求まる。

＃もしくは、初項が偶数・奇数、差が偶数、奇数の場合を考えると
２項目から０項目の差/2、もしくは３項目から１項目の差/2が答えになることがわかる。

コード

class AfraidOfEven {

public:

vector<int> calc(vector<int> org,int d){
int invalid=0;

FORE(i,1,org.size()){

while(1){
if(org[i]!=org[i-1]+d)org[i]*=2;
else break;
if(org[i]<1||org[i]>org[i-1]+d){
invalid=1;
break;
}
}

if(invalid){
org[0]=-1;
return org;
}
}

return org;
}

vector<int> restoreProgression(vector<int> seq) {
vector<int> ans;

FORE(d,-1000,1001){
vector<int> cur=seq;
while(cur[0]<=1e+9){
vector<int> tmp=calc(cur,d);
if(tmp[0]!=-1 && (ans.empty()||ans>tmp))ans=tmp;
if(cur[0]>1e+8)break;
cur[0]*=2;
}
}

return ans;
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class AfraidOfEven {

public:

vector<int> restoreProgression(vector<int> seq) {
int n=seq.size();
vector<int> ans;

for(long long first=seq[0];first<=INT_MAX;first*=2){
for(long long second=seq[1];second<=INT_MAX;second*=2){
int ok=1;
long long d=second-first;
FORE(i,0,n){
long long cur=first+d*i;
if(cur<1||cur>INT_MAX||cur%seq[i]!=0){
ok=0;
break;
}
cur/=seq[i];
if((cur&(cur-1))!=0){
ok=0;
break;
}
}
if(ok){
FORE(i,0,n)ans.push_back(first+i*d);
return ans;
}
}
}

return ans;
}

};

実装