SRM470 Div1 Easy(250), Div2 Medium(500) DoorsGame

DoorsGame

最適戦略は、以下の順番。

• 自分の邪魔になっていて相手の邪魔になっていない色があるなら開く
• 自分にも相手にも邪魔になっている色があれば開く
• 自分にも相手にも邪魔になっていない色があれば開く
• 自分の邪魔になっていなくて相手の邪魔になっている色を開く

なんかちょっとスッキリしないけど、通るから合っているんだろう……。

最初数える以外はループ回さずに、場合分けでゴリゴリ解いている人も居た。すげー。

#include <string>
#include <set>

using namespace std;

class DoorsGame
{
public:
    int determineOutcome( string doors, int trophy );
};

int DoorsGame::determineOutcome( string doors, int trophy )
{
    set<char> close;            //  開いていない色
    set<char> barrier[2];   //  0:John, 1:Gogo とトロフィーの間にある色

    int N = (int)doors.length();

    for ( char c='A'; c<='P'; c++ )
        close.insert( c );
    for ( int i=0; i<trophy; i++ )
        barrier[0].insert( doors[i] );
    for ( int i=trophy; i<N; i++ )
        barrier[1].insert( doors[i] );

    for ( int t=0; ; t++ )
    {
        if ( barrier[0].empty()  &&  barrier[1].empty() )
            return 0;
        if ( barrier[0].empty() )
            return t;
        if ( barrier[1].empty() )
            return -t;

        char best = '\0';

        //  自分の障害となっていて、相手の障害となっていない色
        for ( set<char>::iterator c=close.begin(); c!=close.end(); c++ )
             if ( barrier[  t%2].count(*c) != 0  &&
                  barrier[1-t%2].count(*c) == 0 )
            best = *c;

        //  自分も相手も障害になっている色
        if ( best == '\0' )
        for ( set<char>::iterator c=close.begin(); c!=close.end(); c++ )
             if ( barrier[  t%2].count(*c) != 0  &&
                  barrier[1-t%2].count(*c) != 0 )
            best = *c;

        //  自分も相手も障害になっていない色
        if ( best == '\0' )
        for ( set<char>::iterator c=close.begin(); c!=close.end(); c++ )
             if ( barrier[  t%2].count(*c) == 0  &&
                  barrier[1-t%2].count(*c) == 0 )
            best = *c;

        //  その他
        if ( best == '\0' )
        for ( set<char>::iterator c=close.begin(); c!=close.end(); c++ )
            best = *c;

        close.erase( best );
        barrier[0].erase( best );
        barrier[1].erase( best );
    }
}