Hatena::Grouptopcoder

TopCoder煮ブログ

本家ブログはこっち → http://d.hatena.ne.jp/nitoyon/

2008-10-28

BirthdayReminders (SRM412 DIV2 Medium)

| 03:43 | BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ を含むブックマーク はてなブックマーク - BirthdayReminders (SRM412 DIV2 Medium) - TopCoder煮ブログ

順番に求めていけばいいかと思いきや、優先順位がちょっと厄介。ならば、全ての組み合わせでの誕生日を記憶しておいて、選ばれたものから次の誕生日で上書きしてやればよい。

STL の練習がてら、operator < を定義した構造体にデータを格納して、set に格納していった。こうすれば誕生日が近く、また、優先順位の高いものから順番に並んでくれる。多少ロジックミスで手間取ったが、System Test には合格。やったね。

上位の人の回答をみたらもっと直接的に解いていた。friendNames と occasions の2次元配列に次の誕生日を格納していって、最小のものを調べている。優先順位も occations が小さいものから調べていけば実現できてしまう。なるほどねー。

以下、ソース。

struct Birthday{
    int f;
    int date;
    int occ;
    int num;

    Birthday(int _f, int _date, int _occ, int _num)
        : f(_f), date(_date), occ(_occ), num(_num)
    {}

    bool operator <(const Birthday& bd) const{
        if(date < bd.date) return true;
        if(date == bd.date){
            if(occ < bd.occ) return true;
            if(occ == bd.occ){
                return f < bd.f;
            }
        }
        return false;
    }
};

vector <string> remind(vector <string> friendNames, vector <int> birthDates, int currentDate, vector <string> occasions, vector <int> days, int k)
{
    set<Birthday> s;
    for(int i = 0; i < friendNames.size(); i++){
        for(int j = 0; j < occasions.size(); j++){
            int n = (int)ceil(((double)currentDate - birthDates[i]) / days[j]);
            s.insert(Birthday(i, birthDates[i] + n * days[j], j, n));
        }
    }

    vector<string> v;
    for(int i = 0; i < k; i++){
        Birthday b = *s.begin();
        s.erase(s.begin());
        s.insert(Birthday(b.f, b.date + days[b.occ], b.occ, b.num + 1));

        ostringstream os;
        os << b.date << ". " << friendNames[b.f] << " " << occasions[b.occ] << " (" << b.num << ")";
        v.push_back(os.str());
    }

    return v;
}

比較関数

| 09:43 | 比較関数 - TopCoder煮ブログ を含むブックマーク はてなブックマーク - 比較関数 - TopCoder煮ブログ

上で貼り付けたソースは

    bool operator <(const Birthday& bd) const{
        if(date < bd.date) return true;
        if(date == bd.date){
            if(occ < bd.occ) return true;
            if(occ == bd.occ){
                return f < bd.f;
            }
        }
        return false;
    }

と冗長な感じだったけど、Java 1位の人のソースを見ていて、次のようにシンプルに書けることが分かった。

    bool operator <(const Birthday& bd) const{
        if(date != bd.date) return date < bd.date;
        if(occ != bd.occ) return occ < bd.occ;
        return f < bd.f;
    }

シンプルだと分かりやすい。