SRM580 Div1 Easy(250) EelAndRabbit

TopCoder

EelAndRabbit

それぞれの鰻の頭の位置を試せば充分。

#include <vector>
using namespace std;

class EelAndRabbit{public:
int getmax( vector <int> l, vector <int> t )
{
    int n = (int)l.size();
    int ans = 0;
    for ( int i=0; i<n; i++ )
    for ( int j=0; j<n; j++ )
    {
        int c = 0;
        for ( int k=0; k<n; k++ )
            if ( t[k]<=t[i] && t[i]<=t[k]+l[k] ||
                 t[k]<=t[j] && t[j]<=t[k]+l[k] )
                c++;
        ans = max( ans, c );
    }
    return ans;
}};

SRM579 Div1 Hard(1000) MarblePositioning

TopCoder

MarblePositioning

ビー玉の個数が高々8個なので、全ての並び順を試してみれば良い。半径aと半径bのビー玉が接する距離は√((a+b)2-(a-b)2)。

#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

class MarblePositioning{public:
double totalWidth( vector <int> radius )
{
    int n = (int)radius.size();
    double ans = 1e100;

    sort(radius.begin(),radius.end());
    do
    {
        vector<double> p(n);
        for ( int i=0; i<n; i++ )
        for ( int j=0; j<i; j++ )
        {
            double d = sqrt(
                pow(radius[i]+radius[j],2.) -
                pow(radius[i]-radius[j],2.) );
            p[i] = max( p[i], p[j]+d );
        }
        ans = min( ans, p[n-1] );
    }
    while (next_permutation(radius.begin(),radius.end()));

    return ans;
}};

SRM579 Div2 Easy(250) PrimalUnlicensedCreatures

TopCoder

PrimalUnlicensedCreatures

#include <vector>
using namespace std;

class PrimalUnlicensedCreatures{public:
int maxWins( int initialLevel, vector <int> grezPower )
{
    int level = initialLevel;
    for ( int c=0; ; c++ )
    {
        int p = -1;
        for ( int i=0; i<(int)grezPower.size(); i++ )
            if ( grezPower[i]<level &&
                 ( p==-1 || grezPower[i]>grezPower[p] ) )
                p = i;
        if ( p==-1 )
            return c;
        level += grezPower[p]/2;
        grezPower.erase(grezPower.begin()+p);
    }
}};

SRM579 Div1 Medium(450) TravellingPurchasingMan

TopCoder

TravellingPurchasingMan

bitDP。まず、先頭M店の全点対間最短路を求める。Mは高々16なので、行った店と現在いる店ごとに、その状態になる最も早い時刻を覚えておく。

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

int countbit( int n ) { int c=0; while(n)c+=n&1,n>>=1; return c; }

class TravellingPurchasingMan{public:
int maxStores( int N, vector <string> interestingStores, vector <string> roads )
{
    int INF = 1000000000;

    //  店の間の最短距離
    vector<vector<int> > D;
    D = vector<vector<int> >(N,vector<int>(N,INF));
    for ( int i=0; i<(int)roads.size(); i++ )
    {
        stringstream ss(roads[i]);
        int A,B,L;
        ss>>A>>B>>L;
        D[A][B] = D[B][A] = L;
    }
    for ( int i=0; i<N; i++ )
        D[i][i] = 0;
    for ( int i=0; i<N; i++ )
    for ( int j=0; j<N; j++ )
    for ( int k=0; k<N; k++ )
        D[j][k] = min(D[j][k],D[j][i]+D[i][k]);

    int M = (int)interestingStores.size();
    vector<int> open(M);
    vector<int> close(M);
    vector<int> duration(M);
    for ( int i=0; i<M; i++ )
    {
        stringstream ss(interestingStores[i]);
        ss>>open[i]>>close[i]>>duration[i];
    }

    //  [i][j]: iのbitが立っている店の商品を買って店jに行く最早時刻
    vector<vector<int> > T(1<<M,vector<int>(M,INF));

    for ( int i=0; i<M; i++ )
        if ( D[N-1][i]<=close[i] )
            T[1<<i][i] = max(D[N-1][i],open[i])+duration[i];

    for ( int bn=1; bn<M; bn++ )
    for ( int b=0; b<(1<<M); b++ )
    if ( countbit(b)==bn )
    for ( int p=0; p<M; p++ )
        for ( int i=0; i<M; i++ )
            if ( T[b][p]+D[p][i]<=close[i] )
                T[b|1<<i][i] = min(T[b|1<<i][i],
                    max(T[b][p]+D[p][i],open[i])+duration[i]);

    int ans = 0;
    for ( int b=0; b<(1<<M); b++ )
    for ( int p=0; p<M; p++ )
        if ( T[b][p]<INF )
            ans = max( ans, countbit(b) );
    return ans;
}};

SRM579 Div1 Easy(250), Div2 Medium(550) UndoHistory

TopCoder

UndoHistory

貪欲法。不要な文字をundoに作るくらいなら、必要なときに作れば良い。

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

int pref( string a, string b )
{
    a += "!";
    b += "?";
    for ( int i=0; ; i++ )
        if ( a[i]!=b[i] )
            return i;
    return -1;
}

class UndoHistory{public:
int minPresses( vector <string> lines )
{
    int ans = (int)lines[0].size()+1;

    for ( int i=1; i<(int)lines.size(); i++ )
    {
        int a = 1000000000;
        //  bufferを使う
        if ( pref(lines[i-1],lines[i])==(int)lines[i-1].size() )
            a = min( a, (int)lines[i].size()-(int)lines[i-1].size()+1 );
        //  undoを使う
        for ( int j=0; j<i; j++ )
            a = min( a, 2+(int)lines[i].size()-pref(lines[j],lines[i])+1 );
        ans += a;
    }

    return ans;
}};