SRM467 Div1 250 LateProfessor

TopCoder

作業してたらいつの間にかSRMの時間を過ぎてたので，あとから解いてみる．

問題

  • 時間0に来たJohnがwaitTimeだけ教室で待ちwalkTime散歩するループを繰り返す
  • 教授が時間bestTimeからworstTimeの間に来て，教授の到着からlateTime以上遅れると遅刻
  • Johnが遅刻扱いされる確率は？


解いてみた

  • 境界条件で何故か混乱して無駄に時間がかかってしまった．
  • bestTime = worstTimeのときだけマジメに考える
  • それ以外なら単位時間内で支配的な方にカウントする
  • 絶対にもっと綺麗な解き方ありそう…．
#include <iostream>

using namespace std;

class LateProfessor{
public:
    double getProbability(int wait, int walk, int late, int best, int worst){
        if(best == worst){
            int time = 0;
            while(true){
                time += wait;
                if(best <= time) return 0.0;
                time += walk;
                if(best + late <= time) return 1.0;
            }
        }
        static bool ok[10000001];
        memset(ok, false, sizeof(ok));
        int t = 0;
        while(t<=worst){
            for(int i=0;i<wait&&t<=worst;i++) ok[t++] = true;
            for(int i=0;i<walk&&t<=worst;i++){
                if(i+late>=walk) ok[t] = true;
                t++;
            }
        }
        double res = 0.0;
        for(int i=best;i<worst;i++) res += (1.0-ok[i])/(worst-best);
        return res;
    }
};