SRM532 Div.1

300-450-1000という変則セット。

結果

o--(+0/-0) 142.27pts 314th(Div.1)
1224->1320(+96)

300　DengklekMakingChains

300は怖いなぁと思いつつ問題読む。

3つの{.|0-9}からなる文字列が与えられ、それを任意の順番でconcatしたときに
できる連続する数字の和の最大値を求めろ、という問題。
文字列は最大50個なので全探索は無理だなぁととりあえず思う。

文字列のreverseは許されていないので、
数字をdとして

ddd := 中央に置けば良い
.dd, ..d := 左端におけばよい
d.., dd. := 右端におけばよい
d.d      := どっちにでも置ける
.d.      := 中央の数字が独立している

として最大値を求めていけばよい。
まず全文字列を操作して、左端最大値、右端の最大値、独立の最大値、中央に置けるものの合計を求める。
どちらの端にもおけるものは左として使う場合、右として使う場合でそれぞれvectorに取って降順にsort、
左側、右側のどちらを優先するかの2通りで大きいものをとるとした。
このとき左右で同じものを使用しないか、indexも保持しておいた。
(後から考えると高々50個なので全探索すればよかった。)

あとは計算するだけ。

    int maxBeauty(vector <string> chains) {
        int n = chains.size();
        string tmpstr;
        int l = 0, r = 0, c = 0, all = 0;
        int ret = 0;
        vector<pair<int,int> > bothr; //use rightmost piece <val,index>
        vector<pair<int,int> > bothl; //use leftmost piece <val,index>
        for(int i=0;i<n;i++){
            tmpstr = chains[i];
            if(tmpstr[0] == '.' && tmpstr[1] == '.' && tmpstr[2] == '.'){
                //do nothing
            }else if(tmpstr[0] == '.' && tmpstr[1] == '.' && tmpstr[2] != '.'){
                //..d
                l = max(l, tmpstr[2] - '0');
            }else if(tmpstr[0] == '.' && tmpstr[1] != '.' && tmpstr[2] == '.'){
                //.d.
                c = max(c, tmpstr[1] - '0');
            }else if(tmpstr[0] == '.' && tmpstr[1] != '.' && tmpstr[2] != '.'){
                //.dd
                l = max(l, tmpstr[1] - '0' + tmpstr[2] - '0');
            }else if(tmpstr[0] != '.' && tmpstr[1] == '.' && tmpstr[2] == '.'){
                //d..
                r = max(r, tmpstr[0] - '0');
            }else if(tmpstr[0] != '.' && tmpstr[1] == '.' && tmpstr[2] != '.'){
                //d.d
                bothr.push_back(make_pair(tmpstr[0] - '0', i));
                bothl.push_back(make_pair(tmpstr[2] - '0', i));
            }else if(tmpstr[0] != '.' && tmpstr[1] != '.' && tmpstr[2] == '.'){
                //dd.
                r = max(r, tmpstr[0] - '0' + tmpstr[1] - '0');
            }else{
                //ddd
                all += tmpstr[0] - '0' + tmpstr[1] - '0' + tmpstr[2] - '0';
            }
        }

        sort(bothl.rbegin(), bothl.rend());
        sort(bothr.rbegin(), bothr.rend());

        int tmpmax = -1;
        if(bothr.size() != 0){
            if(r < bothr[0].first && l < bothl[0].first){
                //fix l
                for(int i=0;i < bothr.size() && bothr[i].first > r;i++){
                    if(bothl[0].second != bothr[i].second){
                        tmpmax = max(tmpmax, bothl[0].first + bothr[i].first);
                    }else{
                        tmpmax = max(tmpmax, bothl[0].first + r);
                    }
                }

                //fix r
                for(int i=0;i < bothl.size() && bothl[i].first > l;i++){
                    if(bothr[0].second != bothl[i].second){
                        tmpmax = max(tmpmax, bothr[0].first + bothl[i].first);
                    }else{
                        tmpmax = max(tmpmax, bothr[0].first + l);
                    }
                }
                l = tmpmax;
                r = 0;
            }else if(r < bothr[0].first){
                r = bothr[0].first;
            }else if(l < bothl[0].first){
                l = bothl[0].first;
            }
        }
        ret = max(ret, max(l+r+all, c));
        return ret;
    } 

450　DengklekBuildingRoads

よーわからんけどDPっぽいなと思ったけどうまくつくれなかった。
constraintが小さいので[]の多いDPだと思ったらそうだったらしい。

まとめ

Easy通せてよかった。
DPも「DPっぽいな」と思うとDPなことが多いので書けるようになりたい。
(決してわからない=DPだと思ってるわけではない)