[editorial] SRM 419 Div 1 (예정)

  • Pan
    Pan

    Easy (250 pts.)
    단순한 텍스트 에디터가 있습니다. 유저가 할 수 있는 액션은 하나의 글자를 입력하거나 (type ) 지난 t 초간에 한 액션들을 실행 취소하거나, (undo ) 두 가지의 액션을 할 수 있습니다. undo 액션도 undo 될 수 있다는 것이 포인트. 유저가 취한 액션들과 각 액션을 취한 시점이 초 단위로 주어질 때, 텍스트 에디터에 undo 되지 않고 남아있는 글자들을 출력하는 문제입니다.
    [spoiler="풀이..."]
    앞에서부터 시뮬레이션 식으로 처리하려고 생각하면 '아 이거 어떻게 시뮬레이트 해야 해..' 라는 생각에 한숨이 푹 나오지만, 거꾸로 생각하면 쉬운 문제입니다. 커맨드들을 시간 순으로 정렬했을 때, 가장 마지막으로 입력된 커맨드는 Undo가 안 된다는 것이 포인트!
    1. 남아있는 command 중에 가장 나중에 입력된 command를 꺼냅니다. 이 녀석은 어떤 command에 의해서도 undo 되지 않습니다.
    2. type 꼴이면 출력 버퍼에 를 추가합니다.
    undo 꼴이면 남아있는 command 중에서 최근 초 안에 있는 command를 모두 제거합니다.
    3. command가 하나라도 남아있다면 1로 갑니다. 아니면 출력 버퍼를 앞뒤로 뒤집어 출력합니다.

    #define sz size()
class Undo {
public:
string getText(vector <string> commands, vector <int> time) {
    string output;
    int last_undoed = time.back() + 1;
    for (int i = commands.sz - 1; i >= 0; i--) {
        if (time[i] < last_undoed) {
            istringstream is(commands[i]);
            string cmd, oper;
            is >> cmd >> oper;
            if (cmd == "type")
                output = oper + output;
            else
                last_undoed = time[i] - atoi(oper.c_str());
        }
    }
    return output;
}

    코드의 last_undoed 는, '이 시간과 이 시간 이후의 command는 모두 undo 되었거나 처리되었다' 라는 뜻입니다.
    Medium (500 pts.)
    유명한 Nim 게임입니다. K 명의 사람이 원탁에 둘러앉아 게임을 하는데, 테이블 위에는 N 개의 돌이 있습니다. 1번 사람부터 차례로 N개의 돌 중 몇 개를 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다. 각각의 턴에서 플레이어가 가져갈 수 있는 돌의 개수는 남아있는 돌의 개수에 따라 다른데, 'n 개의 돌이 남아있을 때 현재 턴의 플레이어는 몇 개의 돌을 가져갈 수 있는가' 에 대한 정보가 입력으로 주어집니다.
    모든 플레이어가 최선을 다 한다고 가정합시다.
    1. 필승수가 있으면, 필승수 중 아무 수나 랜덤으로 선택합니다.
    2. 필승수가 없으면, 이길 수 있는 가능성이 있는 수를 택합니다.
    3. 이길 수 있는 가능성이 있는 수마저 없으면, 아무 수나 랜덤으로 택합니다.
    4. 선택할 수 있는 수가 아무 것도 없으면, 누구도 이길 수 없습니다.
    1번 플레이어부터 n개의 돌로 게임을 한다고 했을 때, 이길 수 있는 가능성이 있는 플레이어의 리스트를 구하시오.

    전형적인 Dynamic Programming 문제입니다.
    M[i][j] : 돌이 i 개 남아있다고 하자. 1번째 플레이어가 플레이한다고 할 때, j 번째 플레이어가 반드시 승리하는가?
    P[i][j] : 돌이 i 개 남아있다고 하자. 1번째 플레이어가 플레이한다고 할 때, j 번째 플레이어가 이길 수 있는 가능성이 있는가?
    돌이 하나도 안 남았으면 방금 전에 플레이한 사람이 승리한 겅시 되므로
    M[0][j] = true iff j == k, false if not.
    P[0][j] = true iff j == k, false if not.
    i가 1 이상일 때는, 돌이 i개일 때 1번째 플레이어가 가져갈 수 있는 돌의 개수의 집합을 S라 한다면,
    1번째 플레이어가 가져갈 돌의 개수의 집합 T는, 1번째 플레이어는 다음 턴에 k번째 플레이어가 되므로,
    T = { t | t is in S, M[i-t][k] is true } // 자신이 (다음 턴의 k 번째 플레이어가) 반드시 이기는 방법
    if the set above is empty, {t | t is in S, P[i-t][k] is true} // 자신이 이길 수 있는 가능성이 있는 방법.
    if the set above is empty, {t | t is in S} // 그 마저 없다면, 아무거나.
    이 때, M[i][j]과 P[i][j] 의 값은,
    M[i][j] = and ( M[i-t][j-1] ) for t in T // 1번 플레이어가 어떤 선택을 하든 j (다음 턴의 j-1) 가 이기면 무조건 승리
    P[i][j] = or ( P[i-t][j-1] ) for t in T // 1번 플레이어가 하는 선택에 따라 j 가 이길 수 있으면 승리 가능성이 있음
    단, T가 공집합이면 문제 조건에 따라 M[i][j] = false, P[i][j] = false 입니다.
    2차원 Dynamic Programming이 모두 끝난 후에 P[n][j] 가 true인 모든 j를 출력하면 됩니다.

    class NimForK {
public:
vector <int> winners(int n, int k, vector <string> moves) {
    bool mwin[60][30];
    bool pwin[60][30];
    vector<int> mvs[60];
    REP(i, moves.sz) {
        istringstream is(moves[i]);
        int a;
        while (is >> a) mvs[i+1].pb(a);
    }
    REP(i, n+1) {
        REP(j, k) {
            vector<int> pmoves;  // possible moves
            if (i == 0) {
                mwin[i][j] = (j == k-1);
                pwin[i][j] = (j == k-1);
                continue;
            }
            //  player 0 does its best
            if (pmoves.empty()) {
                //  any way that 0 must win
                FORE(it, mvs[i]) {  
                    if (mwin[i-*it][k-1]) pmoves.pb(*it);
                }
            }
            if (pmoves.empty()) {
                //  any way that 0 can win
                FORE(it, mvs[i]) {  
                    if (pwin[i-*it][k-1]) pmoves.pb(*it);
                }
            }
            if (pmoves.empty()) {
                //  any way that 0 can move
                pmoves = mvs[i];
            }
            if (pmoves.empty()) {
                //  no way to move. the last player wins
                mwin[i][j] = false;
                pwin[i][j] = false;
            }
            else {
                int prevj = (j-1+k) % k;
                mwin[i][j] = true;
                pwin[i][j] = false;
                FORE(it, pmoves) {
                    mwin[i][j] = mwin[i][j] && mwin[i-*it][prevj];
                    pwin[i][j] = pwin[i][j] || pwin[i-*it][prevj];
                }
            }
        }
    }
    vector<int> result;
    REP(i, k) {
        if (pwin[n][i]) result.pb(i+1);
    }
    return result;
}

    [/spoiler]
    Hard (1000 pts.)
    풀이:

    [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    16년 전
0개의 댓글이 있습니다.

  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.