Mediumが会心の出来で最多得点を取り、自己ベスト順位でHighest更新しました。
http://community.topcoder.com/stat?c=problem_statement&pm=15096
問題
掲示板の書き込みがN個ある。
各書き込みの成された正確な時刻と、システムメッセージが与えられる。
システムメッセージは書かれた時刻からの経過時間を示し、以下のいずれかである。
- 1分未満
- X分台(X分~X分59秒)
- X時間台(X時間~X時間59分59秒)
現在時刻としてあり得るもののうち、辞書順最小値を求めよ。
解法
以下いずれでも行ける。
- 各書き込みとメッセージから、あり得る時間帯の区間を求め、共通部分を求める。
- 00:00:00~23:59:59を総当たりし、各メッセージと矛盾がないか比較する。
class ForumPostEasy { public: int conv(string s) { int h=(s[0]-'0')*10+(s[1]-'0'); int m=(s[3]-'0')*10+(s[4]-'0'); int e=(s[6]-'0')*10+(s[7]-'0'); return h*3600+m*60+e; } pair<int,int> range(string s) { if(s[0]=='f') return {0,59}; int t=0, i=0; while(s[i]!=' ') { t=t*10+(s[i]-'0'); i++; } if(s[i+1]=='m') return {t*60,(t+1)*60-1}; else return {t*60*60,(t+1)*60*60-1}; } string getCurrentTime(vector <string> exactPostTime, vector <string> showPostTime) { int N=exactPostTime.size(); vector<int> V; vector<pair<int,int>> V2; FORR(s,exactPostTime) V.push_back(conv(s)); FORR(s,showPostTime) V2.push_back(range(s)); int t,i; FOR(t,24*60*60) { FOR(i,N) { int now=t; if(now<V[i]) now+=24*60*60; if(now<V[i]+V2[i].first) break; if(now>V[i]+V2[i].second) break; } if(i==N) { char hoge[11]; sprintf(hoge,"%02d:%02d:%02d",t/3600,t/60%60,t%60); return string(hoge); } } return "impossible"; } }
まとめ
なんでこんな実装問題入れるかな…と思ったけど、結構落ちてるのね。