SRM497 Div1 Easy(250), Div2 Medium(500) PermutationSignature

TopCoder

PermutationSignature

例えば、

DIIDIDD

先頭にIを付加してIで分割

ID I ID IDD

それぞれのセグメント内は降順になっていて、セグメント間は昇順になっている。このときそれぞれのIを最も小さくすることを考えると、

2 1   3   5 4   8 7 6
#include <string>
#include <vector>
using namespace std;

class PermutationSignature{public:
vector <int> reconstruct( string signature )
{
    signature = "I" + signature;
    int n = (int)signature.size();
    
    vector<int> ans;

    for ( int i=0; i<n; )
    {
        int c = 1;
        for ( ; ++i<n && signature[i]=='D'; )
            c++;
        for ( int j=0; j<c; j++ )
            ans.push_back(i-j);
    }

    return ans;
}};