mayoko’s diary

プロコンとかいろいろ。

SRM 532 div1 easy: DengklekMakingChains

解法

3 つ連続になっているものを全部並べて, あと左側と右側にプラス要素があったら添える, ということをやれば良いだけです。

真ん中 only に値があるものは, これだと全く無視されますが, 他になんの値もない場合などは真ん中 only に値があるものが答えになることもあるのに注意です(サンプルにあるので引っかからないような気がしますが)。

class DengklekMakingChains {
public:
    int maxBeauty(vector <string> chains) {
        int ans = 0, sum = 0;
        int onlyLeft = 0, onlyRight = 0;
        vector<pii> d;
        for (string s : chains) {
            int flag = 0;
            if (s[0] != '.') flag |= 1;
            if (s[1] != '.') flag |= 2;
            if (s[2] != '.') flag |= 4;
            if (flag == 1) onlyRight = max(onlyRight, s[0]-'0');
            if (flag == 2) ans = max(ans, s[1]-'0');
            if (flag == 3) onlyRight = max(onlyRight, s[0]-'0' + s[1]-'0');
            if (flag == 4) onlyLeft = max(onlyLeft, s[2]-'0');
            if (flag == 5) d.emplace_back(s[0]-'0', s[2]-'0');
            if (flag == 6) onlyLeft = max(onlyLeft, s[1]-'0' + s[2]-'0');
            if (flag == 7) {
                for (int i = 0; i < 3; i++) {
                    sum += s[i]-'0';
                }
            }
        }
        int left = 0, right = 0;
        for (pii p : d) {
            left = max(left, p.second);
            right = max(right, p.first);
        }
        ans = max(ans, onlyLeft+sum+onlyRight);
        ans = max(ans, left+sum+onlyRight);
        ans = max(ans, onlyLeft+sum+right);
        int n = d.size();
        for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) {
            if (i==j) continue;
            ans = max(ans, d[i].second+sum+d[j].first);
        }
        return ans;
    }
};