TopCoder SRM 365 Div1 Medium ArithmeticProgressions

問題

n個の数が与えられる。
これらのうちの最小値をm,最大値をMとする。
この数のうち、3個以上がその項となっているような等差数列のうち、
(初項-d)がm以下、(末項+d)がM以上となっているようなものを考える。

この等差数列の項数をq、q個のうちn個の数のどれかに一致するものの数をpとしたとき、
p/qの最大値を{p, q}の形（ただしp,qは互いに素な整数）で出力せよ。
該当する等差数列がないとき、{0, 1}を出力せよ。

制約条件

n≦50
それぞれの数は18桁以下

方針

自分の方針は全探索+枝刈り。
dfs(c,d,a0)を、初項がa0,n個の数のうち現在見終わったのがc個、公差をdのような状態とする。
ここから、c個目の整数を数列に加える場合と加えない分岐が生じる。

c個目を加える場合、それが最初の項ならa0を更新する。
最初の項でない場合、dを更新する。

n項まで見終わった後で、数列と一致するものを数えてp/qを更新すればよい。

計算量はdの取りうる値があんまり多くないので多分そんなに多くないだろうと思って書いたら通ってしまった。

ソースコード

set<pair<int,pi> > s;
ll p,q;
int n;
vector<ll> a;
void dfs(int c,ll d,ll a0){
  if(s.count(mp(c,mp(d,a0))))return;
  s.insert(mp(c,mp(d,a0)));
  
  if(c==n){
    if(a0<0||d==0)return;
    int cnt=0;
    rep(i,n)if((a[i]-a0)%d==0)cnt++;
    ll t=(a[n-1]-a0)/d+(a0-a[0])/d+1;
    if(cnt>2&&p*1.0*t<cnt*1.0*q)p=cnt, q=t;
    return;
  }
  if(a0<0)dfs(c+1,0,a[c]);
  else{
    ll nxd=__gcd(d,a[c]-a0);
    dfs(c+1,nxd,a0);
  }
  dfs(c+1,d,a0);
}
class ArithmeticProgressions {
  public:
  vector <string> maxAptitude(vector <string> numbers) {
    n=numbers.size();
    a.clear();
    s.clear();
    rep(i,n)a.pb(atoll(numbers[i].c_str()));
    sort(all(a));
    p=0; q=1;
    dfs(0,0,-1);
    
    ll g=__gcd(p,q); p/=g; q/=g;
    vs ans;
    char buf[30];
    sprintf(buf,"%lld",p); ans.pb(buf);
    sprintf(buf,"%lld",q); ans.pb(buf);
    return ans;
  }
};