SRM 650 div1 easy: TaroFillingAStringDiv1

そんなに難しくないが結構時間を食ってしまった。

問題:http://community.topcoder.com/stat?c=problem_statement&pm=13669&rd=16314

解法:まずpositionの順に文字をソートする。そして、確定した文字と文字の間に最適な文字の入れ方が何通りあるかを調べていく(状況としては文字c,dが確定していて、c◯◯...◯dというような形になっている)。
①cとdが同じとき:◯の数が奇数ならば、1通りに確定する。偶数ならば、どこで連続するかで(丸の数+1)通りの可能性がある。
②cとdが異なる時:丸の数が偶数ならば、1通りに確定する。奇数ならば、どこで連続するのかで(丸の数+1)通りの可能性がある。
これらを掛けあわせれば良い。複数通りの可能性があるところで2通りしかないと思ってしまい結構悩んだ。
以下ソースコード

const ll MOD = 1000000007;

class TaroFillingAStringDiv1 {
public:
    int getNumber(int N, vector <int> position, string value) {
        ll ret = 1;
        int m = position.size();
        vector<pair<int, char> > P;
        for (int i = 0; i < m; i++) {
            P.push_back(make_pair(position[i]-1, value[i]));
        }
        sort(P.begin(), P.end());
        for (int i = 0; i < m-1; i++) {
            bool same = false, even = false;
            if ((P[i+1].first-P[i].first) % 2 == 1) even = true;;
            if (P[i+1].second == P[i].second) same = true;
            if (same && even) {
                if (P[i+1].first-P[i].first != 1) {
                    ret *= P[i+1].first-P[i].first;
                    ret %= MOD;
                }
            } else if (!same && !even) {
                ret *= P[i+1].first-P[i].first;
                ret %= MOD;
            }
        }
        return ret;
    }
};