오늘 열린 GCJ R1A도 GCJ 퀄 라운드와 마찬가지로 쉬운 아이디어로 풀리는 문제가 많았다. 물론 나는 그 쉬운 아이디어가 빨리 안 떠올라서 망했지만 T_T

  1. Pylons
  2. Golf Gophers
  3. Alien Rhyme

Pylons

격자 그래프에서의 Hamiltonian Path를 찾는 문제로, 연속된 이동이 같은 열, 같은 행, 그리고 같은 대각선을 포함하면 안 된다는 조건이 Knight’s tour를 연상시키는 문제였다.

랜덤 서치를 이용하면 모든 경우에 대해 답을 구하는 데에 그닥 오랜 시간이 걸리지 않는다. 문제는 여기에 약간의 운빨이 필요하다는 사실인데.. 이를 극복하기 위해 C++ 로 모든 경우의 답을 미리 구한 다음, 파이썬으로 출력만 해서 편하게 풀려고 했었다.

근데.. 코드잼에 코드 길이 100K 제한이 있는줄은 몰랐지! 대회가 끝나고 나서 생각해보니 lzma, pickle, base64 모듈을 이용하면 이러한 꼼수도 이용 가능함을 알게 되었지만..

import lzma as l
import pickle as p
import base64 as b
from collections import defaultdict
a = p.loads(l.decompress(b.b85decode(b'(생략)')))

def solve(n, m):
    if n in a.keys() and m in a[n].keys():
        return "POSSIBLE\n" + "\n".join(["{} {}".format(x[0], x[1]) for x in a[n][m]])
    if m in a.keys() and n in a[m].keys():
        return "POSSIBLE\n" + "\n".join(["{} {}".format(x[1], x[0]) for x in a[m][n]])
    return "IMPOSSIBLE"
T = int(input().strip())
for C in range(1, T + 1):
    n, m = map(lambda x: int(x.strip()), input().strip().split())
    print("Case #{}: {}".format(C, solve(n, m)))
#include<ctime>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<tuple>
#include<vector>
#include<algorithm>
#define x first
#define y second
#define pb emplace_back
using namespace std;
using ii = pair<int, int>;

int n, m;
vector<ii> s, g[33][33];
bool vis[33][33];

bool possible(int x, int y, int nx, int ny) {
    if (nx == x || ny == y || nx < 1 || ny < 1 || nx > m || ny > n ||
        vis[ny][nx] || (ny - nx) == (y - x) || (ny + nx) == (y + x)) return false;
    return true;
}

void dfs(int x, int y)
{
    vis[y][x] = true;
    s.pb(x, y);
    if (s.size() == (n * m)) throw "ok!";
    const int N = g[x][y].size();
    for (int k = min(max(m, n), 32); k-- && N > 0;) {
        int nx, ny;
        tie(nx, ny) = g[x][y][rand() % N];
        if (possible(x, y, nx, ny))
            dfs(nx, ny);
    }
    vis[y][x] = false;
    s.pop_back();
}

void build_graph()
{
    for (int i = 1; i <= 20; i++) {
        for (int j = 1; j <= 20; j++) {
            g[i][j].clear();
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            for (int ni = 1; ni <= n; ni++) {
                for (int nj = 1; nj <= m; nj++) {
                    if (possible(j, i, nj, ni))
                        g[j][i].pb(nj, ni);
                }
            }
        }
    }
}

void solve()
{
    memset(vis, 0, sizeof vis);
    scanf("%d%d", &n, &m);
    build_graph();
    try {
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++)
                dfs(j, i);
        }
        puts("IMPOSSIBLE");
    } catch (...) {
        puts("POSSIBLE");
        for (auto& p: s) {
            printf("%d %d\n", p.y, p.x);
        }
    }
}

int main()
{
    srand(time(NULL));
    for (int T, C = scanf("%d", &T); C <= T; ++C) {
        printf("Case #%d: ", C);
        solve();
    }
    return 0;
}

Golf Gophers

18개의 칸에 N만큼의 수가 랜덤한 자연수로 분배되어 더해질 때, 몇 번의 쿼리를 통해 N을 구하는 문제이다. 각 칸은 모듈러 M으로 회전하는데(즉 0 -> 1 -> ... -> M-1 -> 0), 이 M을 칸 별로 직접 지정해서 결과를 쿼리할 수 있다.

문제를 읽으면 딱 Chinese Remainder Theorem이 생각난다. N이 랜덤하게 분배되므로 사용하기 어려울 것 같지만, 각 쿼리에 대해 모두 같은 M을 지정해 주면, Test Set 2의 경우에도 6개의 모듈러를 가지고 CRT를 수행할 수 있다.

from functools import reduce
mod = [5, 7, 11, 13, 17, 18]

def euclid(x, y):
    if y == 0: return x, 1, 0
    g, b, a = euclid(y, x % y)
    return g, a, b - a * (x // y)

def modinv(x, m):
    return (euclid((x % m + m) % m, m)[1] + m) % m

def solve(n):
    s, tot = 0, reduce(lambda x, y: x*y, mod, 1)
    for m in mod:
        print(" ".join([str(m)] * 18), flush=True)
        r = sum([int(x.strip()) for x in input().strip().split()]) % m
        s += r * modinv(tot // m, m) * (tot // m)

    print(s % tot, flush=True)
    input()

T, n, _ = map(int, input().strip().split())
[solve(n) for C in range(1, T + 1)]

Alien Rhyme

N개의 문자열 중 일부를 골라 쌍을 지을 때, 최대한 많은 쌍을 만드는 문제이다. 여기서 쌍을 짓기 위해서는 둘의 접미사가 일치해야 하고, 각 쌍 별로 선택된 접미사가 달라야 한다.

문제를 읽으면, 쌍을 지을 때에 최대한 긴 접미사를 먼저 선택하는 것이 최적이란 사실을 쉽게 떠올릴 수 있다. 이 아이디어를 구현하는 방법에는 여러 방법이 있지만, 나는 Trie와 DFS를 이용해서 아래부터(깊이가 깊은 노드부터) 쌍을 묶도록 구현했다.

class Trie:
    def __init__(self):
        self.link = {}
        self.count = 0
        self.end = False
        self.root = 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 count_pairs(self):
        ans, ret = 0, int(self.end == True)
        for x in self.link.keys():
            a, r = self.link[x].count_pairs()
            ans, ret = ans + a, ret + r

        if ret > 1 and self.root == False:
            ans, ret = ans + 2, ret - 2

        return ans, ret


def solve(ss):
    trie = Trie()
    trie.root = True
    for s in ss: trie.add(s)
    return trie.count_pairs()[0]


T = int(input().strip())
for C in range(1, T + 1):
    n = int(input().strip())
    ss = ["".join(list(reversed(input().strip()))) for _ in range(n)]
    print("Case #{}: {}".format(C, solve(ss)))