TopCoder SRM #629 Div2
ox- でした。1107 -> 1134? くらい(覚えてない)
Med通らなかったけどシステムテストケースが Constraints を満たしていなく、これを考慮すると通っていた。
http://apps.topcoder.com/forums/?module=Thread&threadID=829554&start=0
リジャッジがかかったようです。oo- 1107->1192 (+85) でした。
Easy 250
問題
W
,B
のどちらかで埋められた のグリッドが与えられる。縦方向に連続する同じ文字の数の最大値は?
解法
普通に数えた。転置するとやりやすくなった。
class TaroGrid { public: int getNumber( vector <string> g ) { int n=g.size(); rep(i,n)loop(j,i+1,n) swap(g[i][j],g[j][i]); int ans=1; rep(i,n){ ans=max(ans,f(g[i])); } return ans; } int f(string s){ int res=1; rep(i,s.size()){ int j=i; while(j<s.size() && s[i]==s[j]) j++; res = max<int>(j-i,res); } return res; } };
Med 500
問題
座標 に 匹の猫がいる。それぞれの猫は1秒毎に次の動作のうちいずれかを個別に行う。
- 動かない
- 正の方向に1だけ動く
- 負の方向に1だけ動く
移動できる座標に上限と下限はない。同じ座標に2匹以上の猫がいないという条件を満たすように時間 以内に分散できるか?
解法
貪欲法。
猫を座標で昇順ソートした後、0番目の猫から順に時間 で行け、かつ1つ前の猫と同じ座標にならない限界まで負の方向に移動する。最後の 番目の猫までこの方法で配置できたらPossible
できなければImpossible
。
問題文に と書いてあるのに、システムテストケースには であるようなデータが含まれている。 これに対応するように直したら通るのは納得がいかない… -> リジャッジされました。
class CatsOnTheLineDiv2 { public: string getAnswer( vector <int> pos, vector <int> cnt, int T ) { int n=pos.size(); vector<pii> v(n); rep(i,n) v[i]=make_pair(pos[i], cnt[i]); return solve(v,T) ? "Possible" : "Impossible"; } bool solve(vector<pii> v, int time){ sort(all(v)); int n=v.size(); int last = -inf; rep(i,n){ int p=v[i].first; int l=v[i].second; int beg = max(last+1,p-time); int en = beg+l-1; // dump(beg,en); if(abs(p-en) <= time){ last = en; }else{ return false; } } return true; } };
Hard 950
DPかな…?と思って考えてたけど解けませんでした。