読者です 読者をやめる 読者になる 読者になる

Topcoderデビュー戦(SRM687 Div2)

GoogleCodeJamがあると聞いて久しぶりに競プロの練習をしてフローライブラリを作ったりしていたら急に競プロ熱が高まったのでTopcoderデビューしてきました。登録とかが難しいイメージがあったんですが、Javaアプレットもそこまで使いづらくはないし(字が小さいのは困りますが)、Greedという優秀プラグインのおかげでなんとかなってます。以下感想とか。
 Easy コメントの必要なし。
 Mid いわゆる貪欲法。簡単ですがコーナーケースの処理に手間取り260点ちょいしかもらえずかなC

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;
const int INF = 1000000000;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define rep(i,n) REP(i, 0, n)
const string qua = "quack";
bool don(string& s){
    vector<int> q;
    bool flag = false;
    rep(i, s.length()){
        int n = q.size();
        if(qua[n] == s[i]) q.push_back(i);
        if(q.size() == 5){
            rep(i, 5) s[q[i]] = '#';
            q.clear();
            flag = true;
        }
    }
    return flag;
}
class Quacking {
  public:
    int quack(string s) {
        int res = 0;
        while(true){
            bool f = don(s);
            if(f) res++; else break;
        }
        if(res == 0) res = -1;
        rep(i, s.length()){
            if(s[i] != '#'){
                res = -1;
                break;
            }
        }
        return res;
    }
};

Hard いわゆる数学ゲー+DP。三時間以上考えましたが解けず。つらい。

というわけで無事にDiv1に昇格はできましたが、Div2Hardを何時間考えても解けないようだと速攻で転落しそう。でも暇だし頑張るぞ~。暇だし。バイトしてない学生ですから。