SRM485 Div1 Easy(250), Div2 Medium(500) AfraidOfEven

a[i+1]-a[i]<a[i]-a[i-1]ならばa[i]を2倍に、そういうiが無くなりa[N-1]-a[N-2]>a[N-2]-a[N-3]ならばa[N-1]を2倍に、と繰り返す。それで駄目ならa[0]を２倍にして最初から。

としても解けるけど、そんな面倒なことをする必要は無いと教わった。

等差数列は、

偶偶偶偶……
偶奇偶奇……
奇偶奇偶……
奇奇奇奇……

のいずれか。1.は全ての項を半分にすることでより小さい等差数列になるので解にはならない。この問題の解はa[0]とa[2]が奇数、もしくはa[1]とa[3]が奇数。数を倍にすれば当然偶数になるので奇数の項はseqがそのまま残る。すなわち解となりうるのはseq[0]とseq[2]を残した数列か、seq[1]とseq[3]を残した数列。

#include <vector>

using namespace std;

bool check( vector<int> org, vector<int> seq )
{
    for ( int i=0; i<(int)seq.size(); i++ )
    {
        while ( org[i] > 0  &&  org[i] % 2 == 0 )
            org[i] /= 2;
        if ( org[i] != seq[i] )
            return false;
    }
    return true;
}

class AfraidOfEven{public:
vector <int> restoreProgression( vector <int> seq )
{
    vector<int> A, B;
    for ( int i=0; i<(int)seq.size(); i++ )
        A.push_back( seq[0] + (seq[2]-seq[0])/2*i ),
        B.push_back( seq[1] + (seq[3]-seq[1])/2*(i-1) );
        
    if ( check(A,seq) && check(B,seq) )
        return min( A, B );
    if ( check(A,seq) )
        return A;
    else
        return B;
}};