naoya_t@topcoder

過去問マラソン(#12):SRM153(続き)

過去問マラソン | 14:22 |

ちょっとブランクが空いたが気を取り直して。オフィスの環境テストを兼ねて過去問にトライ。

無刻印のHHKB Professional 2で初めて書くC++。打ちやすい。矢印キーが無い事が不慣れなので指慣らしに時々過去問でも解くか。

Medium(450): Collision

• 今日も問題が頭に入ってこない...
• 要は実装するだけ?
• 211.83 (41'45'') インストール作業の裏でやっているとはいえ時間かけすぎ
• passed system test

using namespace std;

#define sz(a)  int((a).size())
#define pb  push_back
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)

class Collision {
  vector<int> az; int iz, azn, tz;

  double memory(int i,int used,double nocol){ // have memory.
    if(i==azn) return nocol;
    int a = az[i];
    if (used+a > iz) return 0;
    long double r = 1.0;
    for(int j=0,l=iz,re=iz-used; j<a; j++,l--,re--){
      r = r * re / l;
    }
    return memory(i+1,used+a,nocol*r);
  }
  double no_memory(){
    long double r = 1.0;
    for(int i=0,l=iz;i<tz;i++,l--) {
      r = r * l / iz;
    }
    return (double)r;
  }

 public:
  double probability(vector<int> assignments, int ids) {
    az.assign(all(assignments)); azn=sz(az); iz = ids;

    int total = 0; tr(az,it) total += *it; if (total > iz) return 0.0;
    tz = total;

    double r1 = memory(0,0,1), r2 = no_memory();
    return abs(r1 - r2);
  }
};