JMK no matter what

A, B, C 모두 쉬웠다. A 는 그냥 시뮬레이션, B 는 그리디, C 는 동적 계획법. 쉽게 풀려던 유혹을 C 에서 저버리지 못하고 무식하게 짜느라 시간을 낭비함. 막상 동적 계획법으로 풀어보니 어렵지 않다. 이건 그냥 감이 떨어진 걸로 봐야 하는지... ㅠ 다행히 코드 실수는 없어서 (오버플로우 따위 신경쓸 필요 없는 파이썬 만세올시다) 하드는 다 맞고 무난하게 58등.

코드에서는 문제에서 주어지는 N, T, K, B 따위의 한 글자 변수명을 사용하지 않고 가능한 의미있게 쓰려고 노력하는데 꽤 좋은거 같다. 가독성도 좋아지고.

A: File, Fix It

그냥 시뮬레이션. 트리 만들 것도 없이 set 써서 풀면 더 쉽긴 하다. 그래도 난 꿋꿋하게 풀었다.

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

def add(here, tokens):
    if len(tokens) == 0: return 0
    ret = 0
    if tokens[0] not in here:
        ret = 1
        here[tokens[0]] = {}
    return ret + add(here[tokens[0]], tokens[1:])

t = int(rl())
for cc in range(t):
    n, m = map(int, rl().split())
    root = {}
    for i in range(n):
        existing = rl()
        add(root, existing.split("/")[1:])
    ret = 0
    for i in range(m):
        new = rl()
        ret += add(root, new.split("/")[1:])
    print "Case #%d: %d" % (cc+1, ret)

B: Picking Up Chicks

그림으로 그려보면 간단. 'ㅅ' 문제 제목 넘 웃김. ㅋㅋ

lang:py
import sys
rl = lambda: sys.stdin.readline().strip()

t = int(rl())
for cc in range(t):
    chicks, deliver, barn, time_limit = map(int, rl().split())
    location = map(int, rl().split())
    speed = map(int, rl().split())
    ret = 0
    delivered = 0
    lagging = 0
    for i in range(chicks-1,-1,-1):
        # (barn-location[i])/speed[i] <= T
        if barn-location[i] <= time_limit*speed[i]:
            delivered += 1
            ret += lagging
            if delivered == deliver: break
        else:
            lagging += 1
    print "Case #%d:" % (cc+1),
    if delivered < deliver:
        print "IMPOSSIBLE"
    else:
        print ret

C: Your Rank Is Pure

이지를 결국 유혹을 버리지 못하고 무식하게 풀다.

이지

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;
const int M = 25;
const int MOD = 100003;

int main()
{
    int ret[26] = {0};
    for(int subset = 0; subset < (1<<(M+1)); subset++) {
        if(subset & 3) continue; // no zeros and no ones
        for(int start = M; start >= 2; --start) {
            if(subset & (1<<start)) {
                bool pure = true;
                int here = start;
                while(pure) {
                    int before = 0;
                    for(int i = 0; i < here; ++i)
                        if(subset & (1<<i))
                            ++before;
                    int rank = before + 1;
                    if(rank == here)
                        pure = false;
                    else if(rank == 1)
                        break;
                    else if(!(subset & (1<<rank)))
                        pure = false;
                    else
                        here = rank;
                }
                if(pure) {
                    ret[start] = (ret[start] + 1) % MOD;
                    if(start == 6)
                    {
                        printf("%d => ", subset);
                        for(int i = 1; i <= start; ++i)
                            if(subset & (1<<i))
                                printf("%d ", i);
                        printf("\n");
                    }
                }
                break;
            }
        }
    }
    int t;
    cin >> t;
    for(int i = 0; i < t; ++i) {
        int n;
        cin >> n;
        printf("Case #%d: %d\n", i+1, ret[n]);
    }
}

하드

lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<sstream>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<fstream>
#include<cassert>
#include<numeric>
#include<set>
#include<map>
#include<queue>
#include<list>
#include<deque>
using namespace std;

int MOD = 100003;

int cache[501][501];
int combi[501][501];

int go(int n);

int go2(int largest, int size) {
    if(largest <= size) return 0;
    if(size == 1)
        return 1;
    int& ret = cache[largest][size];
    if(ret != -1) return ret;
    ret = 0;
    for(int k = 1; k <= size - 1; ++k) {
        int shrinked = size - k;
        if(shrinked > largest - size) continue;
        long long add = go2(size, k);
        add = (add * combi[largest-size-1][shrinked-1]) % MOD;
        (ret += add) %= MOD;
    }
    return ret;
}

int go(int n) {
    int ret = 0;
    for(int i = 1; i <= n - 1; ++i)
        (ret += go2(n, i)) %= MOD;
    return ret;
}

int main()
{
    memset(cache, -1, sizeof(cache));
    memset(combi, 0, sizeof(combi));
    combi[0][0] = 1;
    for(int i = 1; i <= 500; ++i) {
        combi[i][0] = 1;
        for(int j = 1; j <= i; ++j)
        {
            combi[i][j] = (combi[i-1][j-1] + combi[i-1][j]) % MOD;
        }
    }
    int cases;
    scanf("%d", &cases);
    for(int cc = 0; cc < cases; ++cc)
    {
        int n;
        scanf("%d", &n);
        printf("Case #%d: %d\n", cc+1, go(n));
    }
}