GCJ R1C는 안 망했다!! 다행히 Round 2에 진출 가능한 등수를 받았다. C 라지를 고민하다가 결국 스몰만 풀고 던진 다음 나머지를 급하게 풀어서 A, B는 라지까지 맞았다. 야호! 대회 난이도를 돌아보면, C는 그런디 정리1를 알면 쉽지만 모르면 풀 수 없는 문제였고, B는 올해 출제된, 즉 R1A나 R1B, 그리고 QR에 나온 인터랙티브 문제들에 비해 굉장히 쉬웠으며, A는 문제만 잘 해석하면 정말 아무렇게나 풀어도 라지까지 맞는 낚시 문제였다.

  1. Robot Programming Strategy
  2. Power Arrangers
  3. Bacterial Tactics

Robot Programming Strategy

가위바위보 로봇들이 토너먼트에 출전하고, 각각의 로봇이 자신의 프로그램(차례로 낼 수)를 공개해 두었을 때, 토너먼트의 대진표가 어떻든간에 항상 우승하는 가위바위보 프로그램을 작성하는 문제이다.

언뜻 보면 토너먼트 때문에 복잡해 보이지만, 대진표를 적절히 바꾸어 모든 경우를 만들 수 있기 때문에 결국 모든 상대를 이기는 프로그램을 만들어야 한다. 이러한 프로그램은 사실 단순하게 시뮬레이션을 통해 만들어도 각 단계에서 패배하지만 않으면 된다는 특성 덕분에 이전 단계로 돌아가서 탐색을 다시 시작하는 back-tracking이 거의 일어나지 않아서 빠르게 수행된다.

#!/usr/bin/env python3
counters = {
    'R': 'P',
    'P': 'S',
    'S': 'R'
}

def solve(cur, ss, win):
    idx = len(cur)
    if idx >= 500: return '', False

    for k in ['R', 'P', 'S']:
        okay = True
        nxtmoves, nxtwins = cur + k, win[:]

        for j, s in enumerate(ss):
            if nxtwins[j]: continue
            elif s[idx] == counters[k]: okay = False
            elif counters[s[idx]] == k: nxtwins[j] = True

        if not okay: continue

        for j, s in enumerate(ss):
            if nxtwins[j]: continue
            nxt, npos = solve(cur + k, ss, nxtwins)
            if not npos: okay = False
            nxtmoves = nxt
            break

        if okay: return nxtmoves, True

    return '', False

T = int(input().strip())
for C in range(1, T + 1):
    n = int(input().strip())
    ss = [input().strip() for _ in range(n)]
    zz = [(t * (999 // len(t)))[:500] for t in ss]

    ans, possible = solve('', zz, [False] * len(zz))
    print("Case #{}: {}".format(C, ans if possible else 'IMPOSSIBLE'))

쉬운 문제를 어렵게 꼬아서 풀어보는 방법으로는 트라이를 이용한 풀이가 있다. 사실 대회중에 이걸 디버깅 하다가 시간이 부족해서 스몰이라도 맞자! 하는 마음에 시뮬레이션을 냈고, 그렇게 라지를 맞았다(…)

#!/usr/bin/env pypy
counters = {
    'R': 'P',
    'P': 'S',
    'S': 'R'
}

class Trie:
    def __init__(self):
        self.link = {}
        self.end = False

    def add(self, s):
        c, i = self, 0
        while i < len(s):
            nc = s[i]
            if nc not in c.link:
                c.link[nc] = Trie()
            c = c.link[nc]
            i += 1
        c.end = True

    def win(self):
        if len(list(self.link.keys())) == 3: return '', False
        if len(list(self.link.keys())) == 2 and sum([int(self.link[k].end) for k in self.link.keys()]) == 2: return '', False
        if len(list(self.link.keys())) == 1: return counters[list(self.link.keys())[0]], True
        if len(list(self.link.keys())) == 0: return '', True

        rets = {opt: self.link[opt].win() for opt in self.link.keys()}

        for move in ['R', 'P', 'S']:
            okay, nxt = True, ''
            for others in self.link.keys():
                if move == counters[others]: continue
                if counters[move] == others or not rets[others][1]: okay = False
                if not okay: break
                nxt = rets[others][0]
            if okay: return move + nxt, True

        return '', False

def solve(ss):
    trie = Trie()
    for s in ss: trie.add(s)
    ans, possible = trie.win()
    return ans[:500] if possible else "IMPOSSIBLE"

T = int(raw_input().strip())
for C in range(1, T + 1):
    n = int(raw_input().strip())
    ss = [raw_input().strip() for _ in range(n)]
    zz = [(t * (999 // len(t)))[:500] for t in ss]
    print("Case #{}: {}".format(C, solve(zz)))

Power Arrangers

A, B, C, D, E 의 다섯 개로 만들 수 있는 순열의 개수는 120개이다. 이 중에서 119개의 순열을 무작위 순서로 늘어놓았을 때, 빠진 하나의 순열을 최대 150개의 질문을 통해 알아내는 문제이다. 각 질문은 원하는 위치의 알파벳을 물어보는 것으로, 예를 들어 i번째 순열의 j번째 알파벳을 물어볼 경우 i * 5 + j를 물어보면 된다.

첫 번째 글자부터 순차적으로 결정해 나가면 해결할 수 있는 문제이다. 빠진 순열의 첫 글자는 119개의 순열에서 $4! - 1 = 23$번 등장한다는 사실을 이용하면 총 119번의 쿼리를 통해 첫 번째 알파벳을 알 수 있다. 같은 방법을 반복해서 두 번째 글자를 알아낼 때에는 $3! - 1 = 5$번 등장하는 알파벳을 찾으면 되는데, 여기에는 총 23번의 쿼리가 필요하다. 이런 식으로 마지막 글자까지 반복하면 총 119 + 23 + 5 + 1 = 148번의 쿼리를 통해 답을 찾을 수 있다.

#include<cstdio>
#include<set>
#include<vector>
#include<numeric>
#define sz size()
#define pb emplace_back
#define ALL(X) (X).begin(),(X).end()
using namespace std;
vector<int> range(int n) { vector<int> a(n); iota(ALL(a), 0); return a; }

void solve()
{
    vector<vector<vector<int>>> cand(6, vector<vector<int>>(5));
    set<int> until_now;
    const int target[] = {23, 5, 1, 0, 0};
    char ans[10]{}, last = 0;
    cand[0][0] = range(119);

    for (int k = 0; k < 5; k++) {
        for (int i: cand[k][last]) {
            printf("%d\n", i * 5 + k + 1), fflush(stdout);
            char x[4]{}; scanf("%s", x);
            int al = int(*x - 'A');
            cand[k+1][al].pb(i);
        }

        for (int i = 0; i < 5; i++) {
            if (until_now.count(i) == 0 && cand[k+1][i].sz == target[k]) {
                ans[k] = char(i + 'A');
                until_now.emplace(i);
                last = i;
                break;
            }
        }
    }

    puts(ans); fflush(stdout);
    char verdict[4]{}; scanf("%s", verdict);
    if (*verdict == 'N') exit(-1);
}

int main()
{
    int T;
    scanf("%d%*d", &T);
    while (T--) solve();
    return 0;
}

Bacterial Tactics

박테리아를 게임 판에 번갈아가며 하나씩 배치해서 자신의 차례에 더이상 둘 수 있는 수가 없는 사람이 패배하는 게임에 대한 문제이다. 게임에는 두 종류의 박테리아가 존재하는데, 놓으면 가로로 최대한 퍼지는 종과 놓으면 세로로 최대한 퍼지는 종이다. 단, 게임 판에는 방사성 물질이 존재하는 칸이 있는데, 박테리아가 해당하는 칸까지 퍼져나가면 바로 죽어버리고, 플레이어들은 이러한 일이 일어나도록 배치할 수 없다. 내가 첫 순서라고 생각했을 때, 첫 수를 어떻게 두어야 이길 수 있는지 그 경우의 수를 세어보자.

사실 이는 전형적인 알고리즘 게임 문제로, 매번 한 개의 박테리아를 배치할 때마다 게임 판이 둘로 나뉘어 부분 문제 2개의 답으로부터 전체 문제의 답을 구하는 형태를 갖는다. 이렇게 여러 게임의 승패로부터 전체 승패를 구하는 문제는 그런디 정리1를 이용해서 해결할 수 있다.

각 상태의 그런디 수는 부분 문제의 그런디 수를 XOR 하여 얻을 수 있고, 그렇게 각 상태의 그런디 수를 구했을 때 0이 나온다면 해당하는 상태로부터 승리하는 방법이 없다는 것이고, 이를 이용해서 모든 첫 수에 대해 그런디 수가 0이 되는 경우 - 즉 상대가 패배하는 경우의 수를 세면 답을 구할 수 있다.

#include<cstdio>
#include<cstring>
#include<cstdint>
#include<vector>
#include<algorithm>
#define ALL(X) (X).begin(),(X).end()
using namespace std;

int n, m, d[18][18][18][18], f[18][18];

bool place_h(int x, int y, char vacant, char mark)
{
    int le = x, ri = x;
    while (le >= 0 && f[y][le] == vacant) --le;
    if (le >= 0 && f[y][le] == '#') return false;
    while (ri < m && f[y][ri] == vacant) ++ri;
    if (ri < m  && f[y][ri] == '#') return false;
    while (++le < ri) f[y][le] = mark;
    return true;
}

bool place_v(int x, int y, char vacant, char mark)
{
    int lo = y, hi = y;
    while (lo >= 0 && f[lo][x] == vacant) --lo;
    if (lo >= 0 && f[lo][x] == '#') return false;
    while (hi < n && f[hi][x] == vacant) ++hi;
    if (hi < n  && f[hi][x] == '#') return false;
    while (++lo < hi) f[lo][x] = mark;
    return true;
}

int grundy(int lx, int ly, int rx, int ry, int mark=100)
{
    if (lx >= rx || ly >= ry) return 0;
    int &ret = d[lx][ly][rx][ry];
    if (~ret) return ret;
    ret = 0;

    vector<bool> mex(n * n * m * m + 1, false);
    for (int i = ly; i < ry; i++) {
        for (int j = lx; j < rx; j++) {
            if (place_h(j, i, '.', mark)) {
                int g = grundy(lx, ly, rx, i, mark + 1) ^ grundy(lx, i+1, rx, ry, mark + 1);
                mex[g] = true;
                place_h(j, i, mark, '.');
            }

            if (place_v(j, i, '.', mark)) {
                int g = grundy(lx, ly, j, ry, mark + 1) ^ grundy(j+1, ly, rx, ry, mark + 1);
                mex[g] = true;
                place_v(j, i, mark, '.');
            }

        }
    }

    return ret = find(ALL(mex), false) - mex.begin();
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &m);
        for (int i = 0; i < n; i++) {
            char buf[22]{};
            scanf("%s", buf);
            for (int j = 0; j < m; j++) f[i][j] = buf[j];
        }

        int ret = 0;
        memset(d, -1, sizeof d);
        for (int i = 0; i < n; i++) if (place_h(0, i, '.', 99)) {
            ret += m * !(grundy(0, 0, m, i) ^ grundy(0, i+1, m, n));
            place_h(0, i, 99, '.');
        }

        for (int i = 0; i < m; i++) if (place_v(i, 0, '.', 99)) {
            ret += n * !(grundy(0, 0, i, n) ^ grundy(i+1, 0, m, n));
            place_v(i, 0, 99, '.');
        }

        printf("%d\n", ret);
    }
    return 0;
}

대회 중에는 테스트 셋 1을 해결하는 다이나믹 프로그래밍 코드를 이렇게 작성했다. $2^{4\cdot 4}$개의 상태만 고려하면 되기 때문에 모든 경우를 무식하게 탐색하는 방법이다. 여기서도 매번 재귀 호출을 할 때마다 부호를 뒤집는데, 이는 상대가 패배하는 것(다음 함수 호출)이 내(현재 함수 호출)가 승리하는 것이기 때문이다.

#include<cstdio>
#include<cstring>
#include<cstdint>
#include<map>

int n, m;
std::map<int, int8_t> d;
char f[16][16];

bool go(int stat)
{
    if (d.count(stat)) return bool(d[stat] - 1);
    int8_t &ret = d[stat];
    ret = 1;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) if (f[i][j] == '.') {
            // horizontal
            {
                int le = j, ri = j, nstat = stat;
                while (le >= 0 && f[i][le] == '.') {
                    nstat |= 1 << (i * m + le);
                    --le;
                }

                if (le < 0 || f[i][le] == '@') {
                    while (ri < m && f[i][ri] == '.') {
                        nstat |= 1 << (i * m + ri);
                        ++ri;
                    }

                    if (ri >= m || f[i][ri] == '@') {
                        for (int x = le+1; x < ri; x++) f[i][x] = '@';
                        bool verdict = go(nstat);
                        for (int x = le+1; x < ri; x++) f[i][x] = '.';
                        if (!verdict) {
                            ret = 2;
                            return true;
                        }
                    }
                }
            }

            // vertical
            {
                int le = i, ri = i, nstat = stat;
                while (le >= 0 && f[le][j] == '.') {
                    nstat |= 1 << (j + le * m);
                    --le;
                }

                if (le < 0 || f[le][j] == '@') {
                    while (ri < n && f[ri][j] == '.') {
                        nstat |= 1 << (ri * m + j);
                        ++ri;
                    }

                    if (ri >= n || f[ri][j] == '@') {
                        for (int x = le+1; x < ri; x++) f[x][j] = '@';
                        bool verdict = go(nstat);
                        for (int x = le+1; x < ri; x++) f[x][j] = '.';
                        if (!verdict) {
                            ret = 2;
                            return true;
                        }
                    }
                }
            }
        }
    }

    return false;
}

int main()
{
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        scanf("%d%d", &n, &m);

        uint8_t rok[16]{}, cok[16]{};
        for (int i = 0; i < m; i++) cok[i] = 1;

        for (int i = 0; i < n; i++) {
            scanf("%s", f[i]);
            rok[i] = 1;
            for (int j = 0; j < m; j++) {
                rok[i] &= f[i][j] != '#';
                cok[j] &= f[i][j] != '#';
            }
        }

        int ret = 0;
        d.clear();
        for (int i = 0; i < n; i++) if (rok[i]) {
            int stat = 0;
            for (int j = 0; j < m; j++) {
                f[i][j] = '@';
                stat |= 1 << (m * i + j);
            }

            ret += m * !go(stat);

            for (int j = 0; j < m; j++)
                f[i][j] = '.';
        }

        for (int i = 0; i < m; i++) if (cok[i]) {
            int stat = 0;
            for (int j = 0; j < n; j++) {
                f[j][i] = '@';
                stat |= 1 << (i + j * m);
            }

            ret += n * !go(stat);

            for (int j = 0; j < n; j++)
                f[j][i] = '.';
        }

        printf("%d\n", ret);
    }
    return 0;
}

  1. 그런디 정리에 대한 짧은 요약, TopCoder 튜토리얼. ↩ ↩2