끝나고 뒷풀이 겸 해서 참가자들끼리 간단히 맥주 한 잔 하고 컴실 들어와서 잤다. 'ㅡ')r 8시간동안 잠도 한번 안깨고 쿨쿨 잤음. 기억이 사라지기 전에 얼른 기록.
문제 맞은 순서
- A1 (6), A2 (8) (JM)
- B1 (15), B2 (16) (스탱)
- D1 (24) (JM)
- G1 (39) (JM)
- E1 (40), E2 (41) (스탱)
- J1 (61) (JM)
- K1 (88+10), K2 (93) (JM)
- D2 (119-40) (일루)
- L1 (142) (JM)
- M1 (170) (JM)
- F1 (189) (스탱)
- J2 (281+40) (JM)
- I1 (299+20) (일루)
초반에는 A, B 조낸 빨리 풀고 실수로 내가 D1 맞아버리면서 - _ -; 비교적 잘 나갔다. G1 이랑 E 를 풀었을 40분쯤까지는 거의 3위권 안을 유지하고 있었지만.. 120분 정도까지는 그래도 10위권 유지하고 있었다. 후반에 내가 L1 과 J2 에 말리면서 순위가 점점 하락.. -_-; 마지막에 J2 I1 을 풀어서 결국 15위로 올라가고 끝났다. 돌이켜보면 G2, M2 를 못 푼 게 제일 아쉬움. 둘 중에 하나라도 풀었으면 7등, 둘 다 풀었으면 5등 막 이런데 ;ㅁ;
갭이 줄어들긴 하지만 여전히 갭은 있다는 것을 깨다른 하루엿따 [...]
문제별 기록 - 스크롤의 압박
A: Arithmetics for Dummies
처음에 스탱이 읽었는데, Big int 가 필요할 것 같대서 바꿔 풀었다. 열일곱 줄이면 끗 'ㅡ')r
lang:py
#!/usr/bin/python
import sys
lines = sys.stdin.readlines()
n = int(lines[0])
for i in range(n):
tokens = lines[2*i+2].split()[:-1]
v = int(tokens[0])
for j in range(1,len(tokens),2):
if tokens[j] == "+":
v += int(tokens[j+1])
if tokens[j] == "*":
v *= int(tokens[j+1])
if tokens[j] == "/":
v /= int(tokens[j+1])
if tokens[j] == "-":
v -= int(tokens[j+1])
print v
B: Bouncing Balls
시뮬레이션인데, 충돌 무시해도 되기 때문에 단순히 modulo 연산만으로 해결 가능. 스탱한테 맡겼더니 휘닥닥 풀어 줬다.
C: Cryptic Punchcards
이미지 프로세싱 + EBCDIC 디코딩. 무식한 문제였다.... ㅜㅜ
D: Don't Worry About Wrong Answers
특정 조건을 만족하는 답 외에 모든 답이 AC 를 받고, WA 를 받을 때마다 페널티가 내려가는 이상한 문제... 하지만 실수해서 처음에 맞아버렸다. orz 이 시점에서 이미 페널티 경쟁은 포기 ㅋㅋㅋ
E: Easy Representation
스탱이 슝하고 풀어버림. 나도 따라 짜보았다.
분할정복으로 풀 수 있는 것 같지만, 실제로 해 보면 스택 깊이 때문에 귀찮다. 파이썬은 스택 깊이 제한이 있어서 죽어버림. C++ 도 8MB 스택을 초과해서 죽는다. IPSC 이기 때문에, 그냥 생까고 스택 사이즈를 8MB 에서 40MB 로 늘려서 풀면 풀 수 있다. 스탱은 어떻게 풀었는지 물어봐야겠당..
lang:py
#!/usr/bin/python
import sys
def read():
while True:
line = sys.stdin.readline().strip()
if line != "": return line
return ""
# returns (height, width, black)
def go(str):
if str == "()": return (1, 1, 1)
op = 0
for i in range(len(str)):
if str[i] == "(":
op += 1
else:
op -= 1
if op == 0:
if i + 1 < len(str):
a = go(str[:i+1])
b = go(str[i+1:])
h = max(a[0], b[0])
w = a[1] + b[1] + 1
bl = a[2] + b[2]
return (h, w, bl)
else:
t = go(str[1:-1])
h = t[0] + 1
w = t[1] + 2
bl = h * w - t[2]
return (h, w, bl)
print "OUCH"
return (-1,-1,-1)
cases = int(read())
for cc in range(cases):
print go(read())[2]
C++ 버전:
lang:cpp
struct state
{
int height, width;
long long black;
state(int h, int w, long long b) : height(h), width(w), black(b) {}
};
string str;
state go(int lo, int hi)
{
if(lo+1 == hi) return state(1, 1, 1);
int op = 0;
for(int i = lo; i <= hi; ++i)
if(str[i] == '(')
++op;
else
{
--op;
if(op == 0)
{
if(i == hi)
{
state t = go(lo+1, hi-1);
int h = t.height + 1, w = t.width + 2;
return state(h, w, (long long)h * (long long)w - t.black);
}
else
{
state a = go(lo, i);
state b = go(i+1, hi);
return state(max(a.height, b.height), a.width + b.width + 1, a.black + b.black);
}
}
}
throw 1;
return state(-1, -1, -1);
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
cin >> str;
cout << go(0, str.size()-1).black << endl;
}
}
F: Fish Fillets
플래시 게임을 손으로 풀어야 하다니 ㅠ.ㅠ 우엉 난 이런거 약해..
G: Going To The Movies
꽤 재미있는 확률 DP. 답은 조합론적으로 풀 수 있다고 한다. easy 만 exponential time DP 로 풀어 버리고 못 풀었다. /again/dp/hard/good
G1 소스코드
lang:cpp
long long gcd(long long a, long long b)
{
while(long long c = a % b) { a = b; b = c; } return b;
}
struct Frac
{
long long up, down;
Frac(long long u = 0, long long d = 1) : up(u), down(d) { assert(down >= 0); long long g = gcd(up, down); up /= g; down /= g; }
Frac operator * (const Frac& rhs) const { return Frac(up * rhs.up, down * rhs.down); }
Frac operator + (const Frac& rhs) const { return Frac(up * rhs.down + rhs.up * down, down * rhs.down); }
double toDouble() const { return up * 1.0 / down; }
};
int n, k;
Frac cache[1<<11][11];
Frac go(int taken, int left)
{
if(left == 0) return Frac(0, 1);
Frac& ret = cache[taken][left];
if(ret.up >= 0) return ret;
ret = Frac(0, 1);
for(int i = 0; i < n; ++i)
{
int j = i;
while(j < n && (taken & (1 << j))) ++j;
if(j == n)
ret = ret + Frac(1, n);
else
ret = ret + Frac(1, n) * go(taken | (1<<j), left-1);
}
return ret;
}
int main()
{
int cases;
cin >> cases;
int lastN = -1;
for(int cc = 0; cc < cases; ++cc)
{
cin >> k >> n;
for(int i = 0; i < (1<<n); ++i)
for(int j = 0; j <= k; ++j)
cache[i][j] = -1;
Frac sol = go(0, k);
cout << sol.up << "/" << sol.down << endl;
}
}
H: Hunt!
.. 이거 일루옹 시킬걸 ㅠ.ㅠ
I: Instructions
제한된 instruction 만 갖고 있는 머신의 어셈블러를 이용해서 원하는 일을 하기. 안드로라고 할 수 있다 ㅡ_ㅡ;;; 갈수록 이런 문제가 많이 나오네..
J: Jumbo Airlines
MxN 칸의 grid 에 K명의 사람들을 배치하려 하는데, 상하좌우로 인접하면 안 된다. 이 때 배치하는 경우의 수는?
일단 easy 는 N 이 작아서 2^N * M * K 동적 계획법으로 풀 수 있다. J2 는 어쩔까 하다가 입력을 열어 보니 몇 개 유형으로 나눠진다:
- Easy 보다 입력이 약간 더 큼: 동적 계획법 열심히 돌리면 풀린다.
- N 과 M 이 모두 큼: 근데 대개 K 가 1 이나 2 라서 그냥 풀 수 있다.
- N 이 무지 크고 M 이 무지 작음: K 가 작기 때문에 K 를 적절히 row 별로 decompose 하고, 조합을 이용해 경우의 수를 때려맞췄다.
K 가 2 인 경우 핸들링 같은 데서 실수를 많이 하고, 이항계수 계산할 때 modular inverse 땜에 고생을 많이 하긴 했는데 결과적으로 다 잘 되었다. ㅠ.ㅠ~
근성의 소스코드.
lang:cpp
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef long long ll;
const int MAXK = 50;
long long n, m, k;
VVI cache[MAXK];
const int M = 420047;
int go(int row, int lastRow, int rem)
{
if(rem == 0) return 1;
if(row == n) return 0;
int& ret = cache[rem][row][lastRow];
if(ret != -1) return ret;
ret = 0;
for(int thisRow = 0; thisRow < (1<<m); ++thisRow)
{
if((thisRow & (thisRow >> 1)) || (thisRow & lastRow)) continue;
int nrem = rem - __builtin_popcount(thisRow);
if(nrem < 0) continue;
(ret += go(row+1, thisRow, nrem)) %= M;
}
return ret;
}
long long umm(long long a, int b)
{
if(b == 0) return 1;
if(b == 1) return a;
ll half = umm(a, b/2);
long long ret = (half*half) % M;
if(b % 2) ret = (ret * a) % M;
return ret;
}
long long uinv(ll t)
{
return umm(t,M-2);
}
long long combi(long long n, int r)
{
long long ret = 1;
for(int i = 0; i < r; ++i)
(ret *= (n-i)) %= M;
for(int i = 2; i <= r; ++i)
(ret *= uinv(i)) %= M;
return ret;
}
long long solve(VI& rows, int large)
{
for(int i = 0; i+1 < rows.size(); ++i)
if(rows[i] & rows[i+1])
{
--large;
}
large -= rows.size();
return combi(large+rows.size(), rows.size());
}
long long backtrack(int small, int large, int rem, VI& arr)
{
if(rem == 0) return solve(arr, large);
long long ret = 0;
for(int i = 1; i < (1<<small); ++i)
{
if(__builtin_popcount(i) > rem) continue;
if((i >> 1) & i) continue;
arr.push_back(i);
ret = (ret + backtrack(small, large, rem - __builtin_popcount(i), arr)) % M;
arr.pop_back();
}
return ret;
}
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
cin >> n >> m >> k;
fprintf(stderr, "%d %d %d ..\n", n, m, k);
if(n < m) swap(n, m);
if(k == 1)
{
cout << ((n % M) * (m % M)) % M << endl;
}
else if(k == 2)
{
long long all = (n % M) * (m % M);
all %= M;
long long ret = all*((all-1+M)%M);
ret %= M;
ret *= uinv(2);
ret %= M;
long long a = (m % M) * ((n-1) % M);
long long b = (n % M) * ((m-1) % M);
ret = (ret - a % M + M) % M;
ret = (ret - b % M + M) % M;
cout << ret << endl;
}
else if(n > 100000)
{
VI a;
cout << backtrack(m, n, k, a) << endl;
}
else
{
for(int i = 0; i <= k; ++i) cache[i].assign(n, VI(1<<m, -1));
cout << go(0, 0, k) << endl;
}
}
}
K: Karl's Shopping
NetworkFlow 돌리면 됩니다. 'ㅅ' 서브미션 잘못해서 틀린게 통한 이거만 안했어도 ACRush 는 이기는건데 흑흑 ㅋㅋㅋㅋ 시발 ㅋㅋㅋㅋ
lang:cpp
struct NetworkFlow
{
struct Edge
{
int target, cap, flow; Edge* reverse;
Edge(int t, int c) : target(t), cap(c), flow(0), reverse(NULL) {}
int res() const { return cap - flow; }
void push(int c) { flow += c; reverse->flow = -flow; }
};
int totalFlow, V;
vector<vector<Edge*> > adj;
NetworkFlow(int V): totalFlow(0), V(V), adj(V) {}
~NetworkFlow() { for(int i = 0; i < V; ++i) for(int j = 0; j < adj[i].size(); ++j) delete adj[i][j]; }
int res(int a, int b)
{
for(int i = 0; i < adj[a].size(); ++i)
if(adj[a][i]->target == b)
return adj[a][i]->res();
assert(0);
return -1;
}
void addEdge(int a, int b, int a2b, int b2a = 0)
{
Edge *ab = new Edge(b, a2b), *ba = new Edge(a, b2a);
ab->reverse = ba; ba->reverse = ab;
adj[a].push_back(ab);
adj[b].push_back(ba);
}
int pushFlow(int source, int sink)
{
vector<Edge*> pred(V, (Edge*)NULL);
queue<int> q;
q.push(source);
while(!q.empty() && pred[sink] == NULL)
{
int u = q.front(); q.pop();
for(int i = 0; i < adj[u].size(); ++i)
{
Edge* e = adj[u][i];
int v = e->target;
if(e->res() > 0 && pred[v] == NULL && v != source) { pred[v] = e->reverse; q.push(v); }
}
}
if(pred[sink] == NULL) return 0;
int h, amt = 2147483647;
h = sink; while(source != h) { amt = min(amt, pred[h]->reverse->res()); h = pred[h]->target; }
h = sink; while(source != h) { pred[h]->reverse->push(amt); h = pred[h]->target; }
totalFlow += amt;
return amt;
}
int go(int source = 0, int sink = 1)
{
int ret = 0, f;
while(f = pushFlow(source, sink))
ret += f;
return ret;
}
};
int main()
{
int cases;
cin >> cases;
for(int cc = 0; cc < cases; ++cc)
{
int n, m;
cin >> n >> m;
fprintf(stderr, "%d %d\n", n, m);
NetworkFlow nf(n+m+2);
for(int i = 0; i < n; ++i)
{
int price;
cin >> price;
nf.addEdge(2+m+i, 1, price);
}
for(int i = 0; i < m; ++i)
{
int value;
cin >> value;
nf.addEdge(0, 2+i, value);
}
for(int i = 0; i < m; ++i)
{
int cnt;
cin >> cnt;
for(int j = 0; j < cnt; ++j)
{
int item;
cin >> item;
--item;
nf.addEdge(2+i, 2+m+item, 999999);
}
}
nf.go();
int ret = 0;
for(int i = 0; i < n; ++i)
ret += nf.res(2+m+i, 1);
cout << ret << endl;
}
}
L: Let There Be Rainbows!
Easy 에서는 NQ<10^8^ 이 주어지기 때문에 풀 수 있음. 한 가지 예외 경우는 직선으로 쭉 편다음에 무식하게 풀었다. 10분쯤 돌리니까 나오더라능... 역시 linear 하게 펴놔야지 CPU 효율이 훨씬 좋다. Hard 해법은 생각도 안해봄 ㅜㅜ
한번에 맞았다는 게 놀라운 근성의 소스 코드.
lang:cpp
int n;
vector<int> adj[1000000];
vector<pair<int,int> > edge;
VI color;
VI parent, toParent;
string names[7] = { "red", "orange", "yellow", "green", "blue", "indigo", "violet" };
map<string,int> clrindex;
vector<long long> p;
VI seen;
int qry = 0;
int other(int a, int b)
{
if(edge[a].first == b) return edge[a].second;
return edge[a].first;
}
int paint(int a, int b, int clr)
{
++qry;
int pa = a;
while(true)
{
seen[pa] = qry;
if(pa == 0) break;
pa = parent[pa];
}
int pb = b, c = -1;
while(true)
{
if(seen[pb] == qry) { c = pb; break; }
pb = parent[pb];
}
int ret = 0;
int here = a;
while(here != c)
{
int edgeTaken = toParent[here];
if(color[edgeTaken] != clr)
{
color[edgeTaken] = clr;
++ret;
}
here = parent[here];
}
here = b;
while(here != c)
{
int edgeTaken = toParent[here];
if(color[edgeTaken] != clr)
{
color[edgeTaken] = clr;
++ret;
}
here = parent[here];
}
return ret;
}
void special()
{
vector<int> line;
int st = -1;
for(int i = 0; i < n; ++i)
if(adj[i].size() == 1)
{
st = i; break;
}
assert(st != -1);
VI seen(n, 0);
seen[st] = 1;
line.push_back(st);
while(true)
{
seen[st] = 1;
int next = -1;
for(int i = 0; i < adj[st].size(); ++i)
{
int there = other(adj[st][i], st);
if(seen[there]) continue;
next = there;
}
if(next == -1) break;
line.push_back(next);
st = next;
}
assert(line.size() == n);
map<int,int> t;
for(int i = 0; i < line.size(); ++i)
t[line[i]] = i;
int q;
cin >> q;
VI color(n, -1);
int accum = 0;
for(int i = 0; i < q; ++i)
{
if(i % 1000 == 0) cerr << i << "/" << q << endl;
int a, b; string c;
cin >> a >> b >> c;
int clr = clrindex[c];
a = t[a];
b = t[b];
if(a > b) swap(a, b);
for(int i = a; i < b; ++i)
if(color[i] != clr)
{
p[clr]++;
color[i] = clr;
}
}
cerr << n << " " << q << endl;
cerr << "accum " << accum << endl;
}
int main()
{
for(int i = 0; i < 7; ++i)
clrindex[names[i]] = i;
int cases;
scanf("%d", &cases);
for(int cc = 0; cc < cases; ++cc)
{
scanf("%d", &n);
seen.assign(n, -1);
qry = 0;
fprintf(stderr, "n = %d\n", n);
for(int i = 0; i < n; ++i)
adj[i].clear();
edge.resize(n-1);
color.assign(n-1, -1);
for(int i = 0; i < n-1; ++i)
{
int a, b;
scanf("%d %d", &a, &b);
edge[i] = make_pair(a, b);
adj[a].push_back(i);
adj[b].push_back(i);
}
p.assign(7, 0);
if(n == 1000000)
{
special();
}
else
{
{
parent.assign(n, -1);
toParent.assign(n, -1);
queue<int> q;
q.push(0);
parent[0] = 0;
while(!q.empty())
{
int here = q.front(); q.pop();
for(int i = 0; i < adj[here].size(); ++i)
{
int there = other(adj[here][i], here);
if(parent[there] == -1)
{
parent[there] = here;
toParent[there] = adj[here][i];
q.push(there);
}
}
}
}
{
int q;
cin >> q;
cerr << n << " " << q << endl;
for(int i = 0; i < q; ++i)
{
int a, b; string c;
cin >> a >> b >> c;
assert(clrindex.count(c));
int clr = clrindex[c];
// p[clr] += paint(a, b, clr);
}
}
}
if(cc) cout << endl;
for(int i = 0; i < 7; ++i)
cout << names[i] << " " << p[i] << endl;
}
}
M: Muzidabutur
평문으로 적힌 문자열의 설명과 문자열 예가 들어오면, 문자열이 매칭되는지를 확인한다. 매우 풍부한 오류 처리와 토크나이징 과정을 거치면 문자열 설명을 regular expression 으로 바꿀 수 있음. 그래서 매칭하면 된다.
M2 도 풀려고 시도했는데, 파이썬 정규식 엔진이 백트래킹을 쓰는지라 멈춰버림. Thompson NFA 쓰는 좀 더 빠른 구현이 있을 텐데 하고 고민하다가 포기했는데, grep 에 있는 정규식이 훨씬 빠르단 걸 나중에 깨달았다!
이것만 풀었어도.. 아아....
M1 은 풀 수 있는 파이썬 소스 코드.
lang:py
#!/usr/bin/python
import sys,re
def read():
while True:
line = sys.stdin.readline().strip()
if line != "":
return line
return "NONE"
def normal(ch):
return ch == ";" or ch.isalpha()
def tokenize2(tok):
if tok.startswith("d4f5r6e5"):
return ["d4f5r6e5"] + tokenize2(tok[8:])
tok = tok.replace("{", "\\{")
tok = tok.replace("}", "\\}")
tok = tok.replace("*", "\\*")
ret = []
for ch in tok:
"""
if not ch.isdigit() and not normal(ch) and ch not in "()":
print "SHIT SHIT SHIT"
print tok, ch
sys.exit(0)
"""
if len(ret) > 0 and ((normal(ret[-1][-1]) and normal(ch)) or (ret[-1][-1].isdigit() and ch.isdigit())):
ret[-1] += ch
elif len(ret) > 0 and ret[-1][-1] == ";" and ch == "1":
ret[-1] += ch
else:
ret += [ch]
return ret
def tokenize(desc):
ret = []
toks = desc.split()
for tok in toks:
ret = ret + tokenize2(tok)
return ret
def proc(tok):
if len(tok) == 0: return ""
opened = 0
for i in range(len(tok)):
if tok[i] == "(":
opened += 1
elif tok[i] == ")":
opened -= 1
elif opened == 0 and tok[i] == "OR":
# print "a"
return "(?:(?:" + proc(tok[:i]) + ")|(?:" + proc(tok[i+1:]) + "))"
opened = 0
for i in range(len(tok)):
if tok[i] == "(":
opened += 1
elif tok[i] == ")":
opened -= 1
elif opened == 0 and tok[i:i+2] == ["FOLLOWED", "BY"]:
# print "b"
return "(?:" + proc(tok[:i]) + ")(?:" + proc(tok[i+2:]) + ")"
opened = 0
for i in range(len(tok)):
if tok[i] == "(":
opened += 1
elif tok[i] == ")":
opened -= 1
elif opened == 0 and tok[i:i+2] == ["AT", "MOST"]:
# print "b"
rep = int(tok[i+2])
return "(?:(?:" + proc(tok[:i]) + "){,%d})" % rep + proc(tok[i+4:])
elif opened == 0 and tok[i:i+2] == ["AT", "LEAST"]:
# print "b"
rep = int(tok[i+2])
return "(?:(?:" + proc(tok[:i]) + "){%d,})" % rep + proc(tok[i+4:])
elif opened == 0 and tok[i] == "FROM":
a = int(tok[i+1])
b = int(tok[i+3])
return "(?:(?:" + proc(tok[:i]) + "){%d,%d})" % (a,b) + proc(tok[i+5:])
elif opened == 0 and tok[i].isdigit() and i+1 < len(tok) and tok[i+1] == "TIMES":
rep = int(tok[i])
return "(?:(?:" + proc(tok[:i]) + "){%d})" % (rep) + proc(tok[i+2:])
opened = 0
for i in range(len(tok)):
if tok[i] == "(":
opened += 1
elif tok[i] == ")":
opened -= 1
elif opened == 0 and tok[i:i+2] == ["ONE", "OF"]:
return "[" + tok[i+4] + "]" + proc(tok[i+5:])
elif opened == 0 and tok[i:i+2] == ["THE", "STRING"]:
return tok[i+2] + proc(tok[i+3:])
elif opened == 0 and tok[i:i+2] == ["ANY", "CHARACTER"]:
# print "c"
return "[^" + tok[i+3] + "]" + proc(tok[i+4:])
if tok[0] != "(" or tok[-1] != ")":
print "SHIT SHIT SHIT 2"
print tok
sys.exit(0)
return "(?:" + proc(tok[1:-1]) + ")"
cases = int(read())
for cc in range(cases):
sys.stderr.write("%d/%d ..\n" % (cc, cases))
desc = read()
tok = tokenize(desc)
#print tok
regexp = proc(tok) + "$"
#print regexp
r = re.compile(regexp)
#sys.stderr.write("%s\n" % regexp)
queries = int(read())
for i in range(queries):
sys.stderr.write("\t%d/%d ..\n" % (i, queries))
q = read()
print "YES" if r.match(q) else "NO"
#break
난 걍 cpp로 한거같은디...;; ㅋㅋ