DPじゃなく貪欲で解けるのか…。
http://community.topcoder.com/stat?c=problem_statement&pm=13279
問題
基本的な条件はDiv2 Mediumと同じ。
TopCoder SRM 631 Div2 Medium CatsOnTheLineDiv2 - kmjp's blog
Div2では今回は2匹以上猫がいるセルの有無が求められたが、今度はどうしても2匹以上猫がいるセルが必要であれば、そのセル数の最小値を求めよ。
解法
基本的に左から詰めていくのはDiv2と同じ。
ただどうしても猫が2匹以上いるマスが出てきてしまう場合、そのマスをできるだけ右に寄せる。
例えばP[i]にいた猫を1匹ずつ配置できない場合、あきらめてP[i]+Tに全部集める(この際、2匹以上猫がいるセルが1個増加する)。
そうすると、P[i]以降の猫でP[i]+T>=P[j]-Tを満たすP[j]の猫は、皆P[i]+Tに集めてしまえば2匹以上いるセルは増えない。
また、P[j]の猫を左から1匹ずつ配置するより、P[j]の猫の右端が左端に来る。
ということで、まとめると以下の貪欲で行ける。
- すでに2匹以上いるマスに到達可能な猫はそこに集める。
- 到達不可な場合、2匹以上いるセルを作らずに済むならDiv2同様に左から猫を詰める。
- 上記処理で2匹以上いるセルを作らざるを得ない場合、できるだけ右側に作る。
class CatsOnTheLineDiv1 { public: int getNumber(vector <int> position, vector <int> count, int time) { int N=position.size(); int i,j,x,y; vector<pair<ll,ll> > P; FOR(i,N) P.push_back(make_pair(position[i],count[i])); sort(P.begin(),P.end()); int ret=0; ll po=-1LL<<60,lm=-1LL<<60; FOR(i,N) { if(lm>=P[i].first-time) continue; ll hoge=max(po+1,P[i].first-time)-1+P[i].second; if(hoge>P[i].first+time) { lm=P[i].first+time; ret++; } else { po=hoge; } } return ret; } }
まとめ
本番はガリガリDPやったんだけど、なぜかSystestで落ちてしまった。