SRM487 Div1 Easy(250), Div2 Medium(500) BunnyComputer

BunnyComputer

k+1で割った余りが等しい時刻しか干渉しないので分けて考える。例の問題なら、3,1,2と1,5,6と4,9。グループの要素数が偶数ならすべてのpreferenceが得られる。奇数ならば奇数番目のpreferenceのうちどれか１つが得られない。

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

class BunnyComputer{public:
int getMaximum( vector <int> preference, int k )
{
    int n = (int)preference.size();

    vector<vector<int> > p(k+1);
    for ( int i=0; i<n; i++ )
        p[i%(k+1)].push_back( preference[i] );

    int ans = accumulate( preference.begin(), preference.end(), 0 );

    for ( int i=0; i<k+1; i++ )
    if ( p[i].size() % 2 == 1 )
    {
        int m = p[i][0];
        for ( int j=2; j<(int)p[i].size(); j+=2 )
            m = min( m, p[i][j] );
        ans -= m;
    }

    return ans;
}};