hihoCoder Magic Box

タイトル

タイトル1:Magic Box時間制限:10000 ms単点時限:1000 msメモリ制限:256 MB記述The circus clown Sunny has a magic box.When the circus is performing, Sunny puts some balls into the box one by one. The balls are in three colors: red(R), yellow(Y) and blue(B). Let Cr, Cy, Cb denote the numbers of red, yellow, blue balls in the box. Whenever the differences among Cr, Cy, Cb happen to be x, y, z, all balls in the box vanish. Given x, y, z and the sequence in which Sunny put the balls, you are to find what is the maximum number of balls in the box ever.
For example, let’s assume x=1, y=2, z=3 and the sequence is RRYBRBRYBRY. After Sunny puts the first 7 balls, RRYBRBR, into the box, Cr, Cy, Cb are 4, 1, 2 respectively. The differences are exactly 1, 2, 3. (|Cr-Cy|=3, |Cy-Cb|=1, |Cb-Cr|=2) Then all the 7 balls vanish. Finally there are 4 balls in the box, after Sunny puts the remaining balls. So the box contains 7 balls at most, after Sunny puts the first 7 balls and before they vanish.
Line 1:x y z入力
Line 2: the sequence consisting of only three characters ‘R’, ‘Y’ and ‘B’.
For 30% data, the length of the sequence is no more than 200.
For 100% data, the length of the sequence is no more than 20,000, 0 <= x, y, z <= 20.
出力The maximum number of balls in the box ever.
ヒントAnother Sample
Sample Input Sample Output 0 0 0 RBYRRBY 4
サンプル入力1 2 3 RRYBRBRYBRYサンプル出力7

ぶんせき

isMatch関数の実装といえば,x,y,zおよび|Cr-Cy|=3,|Cy-Cb|=1,|Cb-Cr|=2がmatchであるか否かを判断する関数である.現在はvectorに入れて並べ替えて、直接比較することができます.2つのsetの中に入れて、setを巡り、対応する要素を比較するという考え方もあります.set内部実装は赤黒樹なので、遍歴するときは秩序があります.

コード#コード#

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
bool isMatch(int cr, int cy, int cb, int x, int y, int z){
    int xx = cr - cy;
    int yy = cr - cb;
    int zz = cy - cb;
    xx = xx > 0 ? xx : -xx;
    yy = yy > 0 ? yy : -yy;
    zz = zz > 0 ? zz : -zz;
    vector<int> cc;
    cc.push_back(xx);
    cc.push_back(yy);
    cc.push_back(zz);
    sort(cc.begin(), cc.end());
    vector<int> xyz;
    xyz.push_back(x);
    xyz.push_back(y);
    xyz.push_back(z);
    sort(xyz.begin(), xyz.end());
    return cc[1] == xyz[1] && cc[2] == xyz[2] && cc[0] == xyz[0];
}
int main(){
    int x, y, z;
    string str;
    cin >> x >> y >> z;
    cin >> str;
    int len = str.length();
    int cr = 0, cy = 0, cb = 0;
    int ans = 0;
    for(int i = 0; i < len; i++){
        if(str.at(i) == 'Y'){
            cy++;
        }
        else if(str.at(i) == 'R'){
            cr++;
        }
        else{
            cb++;
        }
        ans = max(ans, cr+cy+cb);
        if(isMatch(cr, cy, cb, x, y, z)){
            cr = 0;
            cy = 0;
            cb = 0;
        }
    }
    cout << ans;
    return 0;
}