問題
http://community.topcoder.com/stat?c=problem_statement&pm=1609&rd=4690
ＰＣのクロックが１ｍｓごとに時間を刻む。
また、ＰＣの中では複数のプログラムが順に動いており、一つのプログラムが終わったらすぐに次のプログラムが動く。
このときプログラムの起動タイミングによっては起動する前と終了した後に時刻が変わっていることがある。
このとき、各プログラムごとに時刻が変わっている／変わっていない２つ状態があるとしたとき、時刻の刻み方による全ての場合の数を求める。
解き方
時刻の取り方は小数点以下10^6あり、全探索していては間に合わない。
このケースの問題は、調べる箇所は絞らなければいけなく、その箇所は決めることができる場合が多い。
この問題の場合は各時刻に対して最小数分のみ足した場合を足すことで、
各プログラムにおいて時刻が変わるときの最小値、時刻が変わらないときの最小値をピックアップすることができる。
コード
using namespace std;
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TickTick {
public: int count(vector<string> events) {
set<string> ans;
vector<double> p(events.size()+1,0.0);
FORE(i,0,events.size())sscanf(events[i].c_str(),"%lf",&p[i+1]);
FORE(i,0,p.size()){
double tick=p[i]+1e-7;
tick=tick-(double)((int)tick);
int prev=-1;
string str="";
FORE(j,1,p.size()){
int cur=floor(p[j]-tick);
if(cur==prev)str+='S';
else str+='D';
prev=cur;
}
ans.insert(str);
}
return ans.size();
}
};
#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()
class TickTick {
public: int count(vector<string> events) {
set<string> ans;
vector<double> p(events.size()+1,0.0);
FORE(i,0,events.size())sscanf(events[i].c_str(),"%lf",&p[i+1]);
FORE(i,0,p.size()){
double tick=p[i]+1e-7;
tick=tick-(double)((int)tick);
int prev=-1;
string str="";
FORE(j,1,p.size()){
int cur=floor(p[j]-tick);
if(cur==prev)str+='S';
else str+='D';
prev=cur;
}
ans.insert(str);
}
return ans.size();
}
};