読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2669

codeiq.jp

「やるだけ」なのかもしれないけどどうもエレガントに書けない.
問題では分割していたけれど, 逆に条件に合うような長方形を生成すれば高々O(2^n)のコストで済み, また条件に合わないときに枝刈りすればもっと計算量は減らせる. mは1000以下の縛りがあったけどもっと大きくなった時にどうやって書けばいいのだろうか?

int m, n;
set<pair<int,int> > T;

void solve(int x, int y, int num)
{
  int s = max(x,y);
  int t = min(x,y);
  if(s > m) return;
  else if(num == n)
  {
    T.insert(make_pair(s,t));
    return;
  }
  else if(s==t)
  {
    solve(s+t,s,num+1);
  }
  else
  {
    solve(s+t,s,num+1);
    solve(s+t,t,num+1);
  }
}

int main()
{
  cin.tie(0);
  ios::sync_with_stdio(false);
  scanf("%d,%d",&m,&n);
  FOR(i,1,m) solve(i,i,1);
  cout << T.size() << "\n";
  return 0;
}