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のどちらかで埋められた {n \times n} のグリッドが与えられる。縦方向に連続する同じ文字の数の最大値は?

解法

普通に数えた。転置するとやりやすくなった。

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

問題

座標 { position(i) }{ count(i) } 匹の猫がいる。それぞれの猫は1秒毎に次の動作のうちいずれかを個別に行う。

  • 動かない
  • 正の方向に1だけ動く
  • 負の方向に1だけ動く

移動できる座標に上限と下限はない。同じ座標に2匹以上の猫がいないという条件を満たすように時間 {T} 以内に分散できるか?

解法

貪欲法。
猫を座標で昇順ソートした後、0番目の猫から順に時間 {T} で行け、かつ1つ前の猫と同じ座標にならない限界まで負の方向に移動する。最後の {n-1} 番目の猫までこの方法で配置できたらPossibleできなければImpossible

問題文に { count(i) \ge 1 } と書いてあるのに、システムテストケースには {count(i) = 0} であるようなデータが含まれている。 これに対応するように直したら通るのは納得がいかない… -> リジャッジされました。

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かな…?と思って考えてたけど解けませんでした。