blue_jamのTopCoder日記

SRM497 DIV1 Easy

SRM, Practice | 22:17

概要

N-1個の要素からなる数列の増減情報が与えられる．この増減情報に合致する辞書順で最小の順列を求める．

解法

いくら限定できる情報があっても50個は多すぎるだろうということで，特殊な生成方法を模索．

辞書順最小とあるので，増加するときは単純に今まで使用した要素の中で最も大きい数より1大きい数を追加すればいいだろう．

減少するときは，前の連続して減少している間その要素に1を加え，現在最後尾になっている要素に1を引いた数を追加する．

class PermutationSignature {
public:
    vector <int> reconstruct(string signature) {
        vector <int> res;
        int n = signature.size() + 1;
        int p = 1;
        res.push_back(1);
        for(int i=0;i<n-1;++i){
            ++p;
            if(signature[i] == 'D'){
                for(int j=i;j>=0;--j){
                    res[j] = res[j] + 1;
                    if(res[j] == p) break;
                }
                res.push_back(res[i]-1);
            }
            else if(signature[i] == 'I'){
                res.push_back(p);
            }
        }
        return res;
    }
};

反省

なんか頭が固くなった気がする．解法を思いつくのに時間がかかったし，思いついてから実装するのに時間がかかった．

事前に解法を詰める癖をつけるべきか．