Hatena::Grouptopcoder

naoya_t@topcoder RSSフィード

2009-01-20

SRM363 Div1 Easy: HandsShaking

| 00:51 | SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder を含むブックマーク はてなブックマーク - SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder SRM363 Div1 Easy: HandsShaking - naoya_t@topcoder のブックマークコメント

ちょっと悩んだ。203.42点(=14'17")

  • DP。最初の1人が誰と手をつなぐか。その線の右側と左側の小グループについて考える分割統治。
  • 最初の1人は、右側と左側の小グループにそれぞれ偶数人が属するように相手を選んで手をつなぐ。というか、隣りの人から始めて1人おきに回り、反対側の隣りの人で終わる。
typedef long long ll;
#define found(s,e)  ((s).find(e)!=(s).end())

class HandsShaking {
  map<int,ll> memo;
 public:
  long long countPerfect(int n) {
    if(n==0) return 0LL;
    if(n==2) return 1LL;
    if(found(memo,n)) return memo[n];
    ll sum=0;
    for(int i=1;i<n;i+=2){
      int a=i-1, b=n-i-1;
      if(a==0) sum+=countPerfect(b);
      else if(b==0) sum+=countPerfect(a);
      else sum+=countPerfect(a)*countPerfect(b);
    }
    return memo[n]=sum;
  }
};
トラックバック - http://topcoder.g.hatena.ne.jp/n4_t/20090120