쉬운 Easy와, 조금 생각이 필요하지만 풀이는 짧은 Medium, 그리고.. 대체 이걸 제한시간 안에 어떻게 코딩하라는건지 모르겠는 Hard로 구성된 Set이었습니다.

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 되었거나 처리되었다' 라는 뜻입니다.
[/spoiler]
Medium (500 pts.)
유명한 Nim 게임입니다. K 명의 사람이 원탁에 둘러앉아 게임을 하는데, 테이블 위에는 N 개의 돌이 있습니다. 1번 사람부터
차례로 N개의 돌 중 몇 개를 가져갑니다. 마지막 돌을 가져가는 사람이 이깁니다. 각각의 턴에서 플레이어가 가져갈 수 있는 돌의
개수는 남아있는 돌의 개수에 따라 다른데, 'n 개의 돌이 남아있을 때 현재 턴의 플레이어는 몇 개의 돌을 가져갈 수 있는가'
에 대한 정보가 입력으로 주어집니다.
모든 플레이어가 최선을 다 한다고 가정합시다.
1. 필승수가 있으면, 필승수 중 아무 수나 랜덤으로 선택합니다.
2. 필승수가 없으면, 이길 수 있는 가능성이 있는 수를 택합니다.
3. 이길 수 있는 가능성이 있는 수마저 없으면, 아무 수나 랜덤으로 택합니다.
4. 선택할 수 있는 수가 아무 것도 없으면, 누구도 이길 수 없습니다.
1번 플레이어부터 n개의 돌로 게임을 한다고 했을 때, 이길 수 있는 가능성이 있는 플레이어의 리스트를 구하시오.
[spoiler="풀이..."]전형적인 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.)그래프 하나가 주어지는데, 다음 속성을 만족합니다.

• 그래프에 여러 개의 simple cycle이 존재할 수 있다.
• 한 vertex은 최대 하나의 simple cycle에 속할 수 있다. 이 속성을 만족하는 그래프를 'cactus'라고 부를 수 있습니다. 그래프의 automorphism을 원래 그래프와 동형 (isomorphic)인 그래프 relabeling의 개수라 할 때, 이 cactus가 총 몇 개의 automorphism을 가지는지 개수를 구해 1000000003 으로 나눈 나머지를 구하는 프로그램으로 작성하시오. [spoiler="풀이..."] Tree의 Automorphism 은 유명한 문제입니다. - Subtree Identification 알고리즘을 사용하면 쉬운 문제이지요. 자세한건 이 논문을 참조하시고 - http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.35.1187 이 논문은 'Fast' 알고리즘을 설명한거라 설명이 복잡한데.. 이 논문이 참고하는 1970년대의 논문의 알고리즘이 쉽습니다. 비록 원문을 찾진 못했지만.. 아래에 알고리즘을 간략하게 설명하겠습니다. Cactus는 선인장 덩어리를 하나의 vertex으로 두는 supergraph로 나타내면 tree 처럼 보입니다. - 맞습니다. 우선은 모든 simple cycle을 구하고, - 2-connected component 알고리즘으로 하면 빠르지만 그냥 DFS로 해도 문제 없습니다. 각각의 simple cycle마다 노드 하나씩을 만들고, - 일반 노드와 구분짓기 위해 '★' 로 표시합시다. 일반 노드는 ● 라고 하고, 그 simple cycle 의 모든 vertex을 생성된 ★과 연결합시다. 이 때, vertex의 순서가 cycle 순서대로 되도록 유의하며 저장합시다. ● 의 이웃들은 서로 순서가 바뀌어도 같은 것이지만, 변환된 ★의 경우엔 이웃들의 순서가 원래 그래프의 edge 연결 순서와 관련있기 때문에, 순서가 섞이면 다른 그래프가 됩니다. 그렇게 그래프를 트리로 변환하고 나면, unrooted- 트리의 leaf 부터 트리의 root를 향해 한 step 한 step 나아가는, 일명 '털 뽑기' 알고리즘을 씁시다.
• 트리의 모든 leaf들에게 '1' 이란 라벨을 붙입시다.
• 라벨이 붙어있지 않은 노드들 중, 하나의 이웃을 제외하고 모두 라벨이 붙어있는 노드를 구합니다. 각각의 노드는 라벨이 붙어있는 이웃들의 parent가 되고, 라벨이 붙어있지 않은 하나의 이웃의 자식이 될 것입니다.
• 이 노드들을 'isomorphic' 한 녀석끼리 클러스터링합니다. 편의상 노드를 ●(i1, i2, i3, ..) 또는 ★(i1, i2, i3, ..) 으로 표현하겠습니다. i1, i2, i3, .. 는 해당 노드의 자식 노드들의 라벨들입니다. a. ●(i1, i2, i3, ..) 과 ★(j1, j2, j3, ... ) 는 isomorphic 하지 않습니다. b. ●(i1, i2, i3, ...) 과 ●(j1, j2, j3, ...) 은, {i1, i2, i3, ...} = {j1, j2, j3, ...} 일 경우에 isomorphic 입니다. (집합 비교) c. ★(i1, i2, i3, ...) 과 ★(j1, j2, j3, ...) 은, (i1, i2, i3, ...) = (j1, j2, j3, ...) 이거나 (i1, i2, i3, ...,, jp ) = (jp, ..., j3, j2, j1) 일 경우에 isomorphic 합니다.
• 클러스터마다 이제까지 부여하지 않았던 새 라벨을 부여합니다. 2, 3, 4, ... 같은 라벨을 갖고 있다는 것은, 해당 subtree들이 isomorphic 하단 의미입니다.
• 각 라벨에 해당하는 subtree 마다, rooted tree automorphism의 개수를 구합니다. a. ●(i1, i2, i3, ...) 의 경우에, automorphism의 개수는 각각의 subtree의 automorphism의 개수의 총 곱 * Π (각각의 클러스터의 원소의 개수)! b. ★(i1, i2, ... ) 의 경우에 automorphism 의 개수는 각각의 subtree의 automorphism의 개수의 총 곱 * (i1, i2, .. 이 좌우 대칭이면 2, 아니면 1)
• 2번으로 되돌아갑니다. 이 작업을 두 개의 unlabeled node가 남거나 하나의 unlabeled node만 남을 때까지 되풀이합니다. 이 경우에 어떻게 처리할지는 여러분에게 숙제로 남기겠습니다. (_ _) 한 개의 unlabeled node만 남았는데, 그 놈이 ★일 때만 특수 처리를 해 주시면 되겠습니다. ~~~ cpp

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n) FOR(i,0,n)
#define FORE(it,x) for(typeof((x).begin())it=(x).begin();it!=(x).end();++it)
#define all(x) (x).begin(),(x).end()
#define CLR(x,v) memset(x,v,sizeof(x))
#define pb push_back
#define sz size()
#define exist(c,x) ((c).find(x)!=(c).end())
#define cexist(c,x) (find(all(c),x)!=(c).end())
#define SMIN(a, b) a = min((a),(b))
#define SMAX(a, b) a = max((a),(b))
typedef vector vi;
typedef vector< pair > vpi;
typedef long long ll;
ll magic = 1000000003ll;
class Bcc {
public:
vi* ed;
vector< vpi > cycles;
int stns;
int stn[500];
int back[500];
vpi ed_stack;
Bcc(int N, vi *ed) : ed(ed) {
stns = 1;
REP(i, N) {
stn[i] = 0;
}
cycle_dfs(0, -1);
}
int cycle_dfs(int u, int p) {
stn[u] = stns;
back[u] = stns;
stns++;
FORE(it, ed[u]) {
int v = *it;
if (v == p) continue;
if (stn[v] == 0) {
ed_stack.pb( make_pair(u, v) );
int b = cycle_dfs(v, u);
if (b >= stn[u]) {
// report the cycle
vpi cycle;
while(true) {
pair e = ed_stack.back();
ed_stack.pop_back();
cycle.pb(e);
if (e == make_pair(u, v)) break;
}
reverse(all(cycle));
cycles.pb(cycle);
}
SMIN(back[u], b);
}
else if (stn[v] >= stn[u]) {
// nothing to do
}
else {
ed_stack.pb( make_pair(u, v) );
SMIN(back[u], stn[v]);
}
}
return back[u];
}
};
class CactusAutomorphisms {
public:
int N;
vi ed[500];
bool fixed[500];
struct nodeprop {
vi children;
vi childid;
} np[500];
int count(int n, vector edges) {
N = n;
REP(i, N) {
ed[i].clear();
fixed[i] = false;
}
ostringstream os;
FORE(it, edges) {
os << *it;
}
string inps = os.str();
REP(i, inps.sz) {
if (inps[i] == ',') inps[i] = ' ';
}
istringstream is(inps);
int a, b;
while ( is >>a >>b ) {
a--; b--;
ed[a].pb(b);
ed[b].pb(a);
}
Bcc bcc(N, ed);
FORE(it, bcc.cycles) {
if (it->sz > 2) {
int newIdx = N;
ed[newIdx].clear();
fixed[newIdx] = true;
N++;
FORE(jt, *it) {
int a = jt->first;
int b = jt->second;
ed[a].erase(find(all(ed[a]), b));
ed[b].erase(find(all(ed[b]), a));
ed[a].pb(newIdx);
ed[newIdx].pb(a);
}
}
}
vi levels[500];
vi children[500];
REP(i, N) {
if (ed[i].sz <= 1) {
levels[0].pb(i);
}
}
map map_id;
map map_aut;
vi ed_orig[500];
int id[500];
REP(i, N) {
ed_orig[i] = ed[i];
id[i] = 0;
}
int id_num = 1;
REP(lvl, 500) {
if (levels[lvl].sz == 0) {
return 0;
}
if (levels[lvl].sz == 2) {
int a = levels[lvl][0];
int b = levels[lvl][1];
if (cexist(ed[a], b) && cexist(ed[b], a)) {
int newIdx = N;
ed[newIdx].clear();
ed[newIdx].pb(a);
ed[newIdx].pb(b);
*find(all(ed[a]), b) = newIdx;
*find(all(ed[b]), a) = newIdx;
ed_orig[newIdx] = ed[newIdx];
*find(all(ed_orig[a]), b) = newIdx;
*find(all(ed_orig[b]), a) = newIdx;
fixed[newIdx] = false;
N++;
}
}
FORE(it, levels[lvl]) {
int u = *it;
int p = -1;
if (!ed[u].empty()) {
p = ed[u][0];
ed[u].erase(find(all(ed[u]), p));
ed[p].erase(find(all(ed[p]), u));
if (ed[p].sz == 1) {
levels[lvl+1].pb(p);
}
}
vi child_ids;
REP(i, ed_orig[u].sz) {
if (p == -1) {
int v = ed_orig[u][i];
child_ids.pb( id[v] );
}
else if (ed_orig[u][i] == p) {
REP(j, ed_orig[u].sz - 1) {
int v = ed_orig[u][(i+j+1) % ed_orig[u].sz];
child_ids.pb( id[v] );
}
break;
}
}
if (!fixed[u]) {
sort(all(child_ids));
}
else {
vi child_ids_rev = child_ids;
reverse(all(child_ids_rev));
if (child_ids > child_ids_rev) {
child_ids = child_ids_rev;
}
child_ids.pb(-1); // bocho
}
if (exist(map_id, child_ids)) {
id[u] = map_id[child_ids];
}
else {
id[u] = id_num++;
map_id[child_ids] = id[u];
if (fixed[u]) child_ids.pop_back();
ll result = 1ll;
if (!fixed[u]) {
REP(i, child_ids.sz) {
int cid = child_ids[i];
int multi = 1;
result = (result * map_aut[cid]) % magic;
REP(j, i) {
if (child_ids[j] == cid) multi++;
}
result = (result * multi) % magic;
}
}
else if (p >= 0) {
bool symmetric = true;
REP(i, child_ids.sz) {
int cid = child_ids[i];
result = (result * map_aut[cid]) % magic;
if (child_ids[child_ids.sz - 1 - i] != cid) {
symmetric = false;
}
}
if (symmetric) result = (result * 2) % magic;
}
else {
int multi = 0;
REP(i, child_ids.sz) {
int cid = child_ids[i];
result = (result * map_aut[cid]) % magic;
vi rot, rot_rev;
REP(j, child_ids.sz) {
rot.pb(child_ids[(i+j) % child_ids.sz]);
}
rot_rev = rot;
reverse(all(rot_rev));
if (rot == child_ids) multi++;
if (rot_rev == child_ids) multi++;
}
result = (result * multi) % magic;
}
map_aut[id[u]] = result;
}
if (p == -1) return map_aut[id[u]];
}
}
return 0;
}
};

[/spoiler]
<div>[이 글은 과거 홈페이지에서 이전된 글입니다. <a href="http://algospot.andromeda-express.com/zbxe/editorial/51197">원문보기</a>]</div>