SRM 504 div1 easy:MathContest

SRM練習会に参加しました。結果はeasy, med解いてまぁよかったんですがeasy気づくのが遅すぎて140ptくらいしか取れなかったのが残念です。

問題

TopCoder Statistics - Problem Statement

解法

単にシミュレーションするだけ。ただ本当に愚直にやると黒を引いた時にO(N)の計算量がかかって死ぬので,何回色の変換が起こったかを管理する変数cntを作ってそれの偶奇と最初のボールの配置の情報から今見ているボールが何色であるかを判断する。

少し汚い下のコードではl, rが左側の現在位置と右側の現在位置を表していて,leftが今左側からボールを見ていってるならtrue,右側から見ていってるならfalseになる。

int state[100100];

class MathContest {
public:
    int countBlack(string ballSequence, int repetitions) {
        int n = ballSequence.size();
        int all = n*repetitions;
        int l = 0, r = all-1;
        int cnt = 0;
        bool left = true;
        for (int i = 0; i < all; i++) {
            if (ballSequence[i%n] == 'B') state[i] = 1;
            else state[i] = 0;
        }
        int ans = 0;
        while (r >= l) {
            if (left) {
                if (cnt%2) {
                    if (state[l] == 1) {
                        l++;
                        left = false;
                    } else {
                        l++;
                        cnt++;
                        ans++;
                    }
                } else {
                    if (state[l] == 1) {
                        l++;
                        cnt++;
                        ans++;
                    } else {
                        l++;
                        left = false;
                    }
                }
            } else {
                if (cnt%2) {
                    if (state[r] == 1) {
                        r--;
                        left = true;
                    } else {
                        r--;
                        cnt++;
                        ans++;
                    }
                } else {
                    if (state[r] == 1) {
                        r--;
                        cnt++;
                        ans++;
                    } else {
                        r--;
                        left = true;
                    }
                }
            }
        }
        return ans;
    }
};