Hatena::Grouptopcoder

TopCoderの問題を解く

解いた問題の一覧表

2009-08-22

BirthdayOdds

| 16:29

問題文, SRM 174

同じ誕生日になる確率。

467.33/500

class BirthdayOdds {
public:
    int minPeople(int minOdds, int daysInYear) {
        double p = 1;
        for (int i = 1; i <= daysInYear; i++) {
            p *= static_cast<double>(daysInYear-i+1)/daysInYear;
            if ((1-p)*100 >= minOdds)
                return i;
        }
        return 0;
    }
};

2009-08-21

CrossWord

| 17:29

問題文, SRM 174

size個だけ連続した横方向の空白が、いくつあるのかを数える。

230.35/250

class CrossWord {
public:
    int countWords(vector <string> board, int size) {
        int count = 0;
        string pat(size, '.');
        pat = "X" + pat + "X";
        for (int i = 0; i < board.size(); i++) {
            board[i] = "X" + board[i] + "X";
            int idx = 0;
            while ((idx = board[i].find(pat,idx)) != string::npos) {
                count++;
                idx += size + 1;
            }
        }
        return count;
    }
};