SRM532 Div1(300), Div2(600) DengklekMakingChains

DengklekMakingChains

3個とも輪が綺麗な鎖を並べて左右に一番点数が高くなるように鎖を付けるか、１個の鎖の中央の輪だけを取るかのどちらかが最善。サンプルがしっかりしているかと思ったけど、まだ罠がある。例えば、{"1.1"}とか。

#include <string>
#include <vector>
#include <numeric>
using namespace std;

class DengklekMakingChains{public:
int maxBeauty( vector <string> chains )
{
    //  左右に付ける鎖が無い場合の代わり
    chains.push_back( "..." );
    chains.push_back( "..." );

    int n = (int)chains.size();

    //  3個とも輪が綺麗な鎖の美しさ、左・右側から連続している綺麗な鎖の美しさ
    vector<int> C(n), L(n), R(n);
    for ( int i=0; i<n; i++ )
    {
        for ( int j=0; j<3 && chains[i][j]!='.'; j++ )
            C[i] += chains[i][j]-'0',
            L[i] += chains[i][j]-'0';
        for ( int j=2; j>=0 && chains[i][j]!='.'; j-- )
            R[i] += chains[i][j]-'0';
    }
    
    for ( int i=0; i<n; i++ )
    {
        if ( chains[i][0]!='.' &&
             chains[i][1]!='.' &&
             chains[i][2]!='.' )
            L[i] = R[i] = 0;
        else
            C[i] = 0;
    }

    int ans = 0;

    //  3個とも輪が綺麗な鎖を中心に鎖を作る
    int c = accumulate(C.begin(),C.end(),0);

    for ( int l=0; l<n; l++ )
    for ( int r=0; r<n; r++ )
        if ( l!=r )
            ans = max( ans, c+L[l]+R[r] );

    //  中央の輪のみから鎖を作る
    for ( int i=0; i<n; i++ )
        if ( chains[i][1]!='.' )
            ans = max( ans, chains[i][1]-'0' );

    return ans;
}};