Hatena::Grouptopcoder

kitayutaのTopCoderの何か

 | 

2011-08-28

TopCoder SRM 515 Div1

08:51

書くのが遅くなってしまっている

結果

Challenged Compiled Unopened +50*0 -25*0 Total:0.00 1289→1192(-97)

いい国つくろう鎌倉幕府。

250 RotatedClock

シュミレーション的に書く。時計を一番上にしている場所が、数字のついている所にしなければいけないことを考慮しないといけない。

具体的には、(与えられた長針の角度)%30==(本当の長針の角度)%30∧(与えられた短針の角度)%30==(本当の短針の角度)が成り立つ、というのを考慮すればよくて、この方針は間違っていなかったけれど(使っている人はあまり見当たらない)、余りを取っていなかったりなど初歩的な処理をを忘れていた…。

提出したコードは

//include等省略
class RotatedClock {
    public:
        string getEarliest(int hourHand, int minuteHand) {
            for(int i=0;i<60*12;i+=2){
                if(hourHand-minuteHand == (i/2 - i*6)%360 && hourHand%30==(i/2)%30 && minuteHand%30==(i*6)%30){
                    stringstream retss;
                    int hour=i/60;
                    if(hour<10){
                        retss<<'0';
                    }
                    retss<<hour<<':';
                    int minute=i%60;
                    if(minute<10){
                        retss<<'0';
                    }
                    retss<<minute;
                    return retss.str();
                }
            }
            return "";
        }
};

こんなコードを書けば通る。

//include等省略

class RotatedClock {
    public:
        string getEarliest(int hourHand, int minuteHand) {
            int motomod=(hourHand-minuteHand+360)%360;
            for(int i=0;i<60*12;i+=2){
                int hmod=(i/2)%360,mmod=(i*6)%360;
                if(motomod == (hmod-mmod+360)%360 && hourHand%30==hmod%30 && minuteHand%30==mmod%30){
                    stringstream retss;
                    int hour=i/60;
                    if(hour<10){
                        retss<<'0';
                    }
                    retss<<hour<<':';
                    int minute=i%60;
                    if(minute<10){
                        retss<<'0';
                    }
                    retss<<minute;
                    return retss.str();
                }
            }
            return "";
        }
};

550 NewItemShop

人が訪れたどうかの配列(最悪2^24通り程度)、今の時間(最悪24通り)、残りの本数(最悪25通り)でDP(メモ化再帰)すればよい。しかし、状態数が最悪で(2^24)*24*25ぐらいになるので、このままではTLEしてしまう。しかし、一回しか訪れない人についてはDPする上で保持する必要がない(少し考えれば分かると思う)ので、訪れたかどうかの配列の状態数は2^12通りにできる(これは自力では思いつかなかった)。この方法ではTLEはしない。

この方法に基づいて書いたコード:

//include等は省略
typedef pair<int,pair<int,int> > P;
struct cust{
    int T,C,P;
    cust(int t,int c,int p){
        T=t;
        C=c;
        P=p;
    }
    cust(){}
};
class NewItemShop {
    public:
        map<P,double> dp;
        vector<vector<cust> > custs;
        vector<int> mapping;
        double solve(vector<bool> whocame,int time,int nokori){
            if(time>=24 || nokori==0) return 0;
            int key=0;
            for(int i=0;i<whocame.size();i++){
                if(whocame[i]) key|=(1<<i);
            }
            P pa=make_pair(key,make_pair(time,nokori));
            if(dp.find(pa)==dp.end()){
                int ncome=-1,ncomeat,ntime=INT_MAX;
                for(int i=0;i<custs.size();i++){
                    if(mapping[i]==-1 || !whocame[mapping[i]]){
                        for(int j=0;j<custs[i].size();j++){
                            if(custs[i][j].T>=time && custs[i][j].T<ntime){
                                ncome=i;
                                ncomeat=j;
                                ntime=custs[i][j].T;
                            }
                        }
                    }
                }
                if(ncome==-1) return dp[pa]=0;
                double nmot=100,nson=custs[ncome][ncomeat].P;
                for(int i=0;i<custs[ncome].size();i++){
                    if(custs[ncome][i].T<ntime) nmot-=custs[ncome][i].P;
                }
                double pos=nson/nmot;
                double ret=0;
                if(mapping[ncome]!=-1) whocame[mapping[ncome]]=true;
                ret+=pos*(max(solve(whocame,ntime+1,nokori-1)+custs[ncome][ncomeat].C,solve(whocame,ntime+1,nokori)));
                if(mapping[ncome]!=-1) whocame[mapping[ncome]]=false;
                ret+=(1-pos)*solve(whocame,ntime+1,nokori);
                dp[pa]=ret;
            }
            return dp[pa];
        }
 
        double getMaximum(int swords, vector <string> customers) {
            custs=vector<vector<cust> >(customers.size());
            mapping=vector<int>(customers.size());
            int sz=0;
            for(int i=0;i<customers.size();i++){
                vector<string> custrs;
                int at=0;
                for(;;){
                    string now;
                    for(;at<customers[i].size()&&customers[i][at]!=' ';at++){
                        now+=string(1,customers[i][at]);
                    }
                    custrs.push_back(now);
                    if(at==customers[i].size()) break;
                    at++;
                }
                vector<cust> nowc(custrs.size());
                for(int j=0;j<custrs.size();j++){
                    int t,c,p;
                    sscanf(custrs[j].c_str(),"%d,%d,%d",&t,&c,&p);
                    nowc[j]=cust(t,c,p);
                }
                custs[i]=nowc;
                if(nowc.size()<=1) mapping[i]=-1;
                else mapping[i]=sz++;
            }
            return solve(vector<bool>(sz,false),0,swords);
        }
};

1000 MeetInTheMaze

みていない

Challenge Phase

250を落とされて萎える

 |