요즘 #icpc 채널의 밤을 불태우고 있는 1주1셋운동의 첫번째 세트. 헤헷 난 멋있게 A번부터 풀어야지 하다가 A번 일주일 동안 못풀고, 마지막 날에 몇개 풀고 말았다. -_- 그런데 꽤나 못푼 것의 답을 들으니 배운 점이 많아서 정리해서 포스팅.
배운 점:
- solve by hand: 안 풀리면 일단 작은 예제를 손으로 풀어본다. 문제에 있는 예제도 풀어본다.
- decompose: 복잡한 조건을 분해해서 간단한 조건들의 집합으로 만들 수 있는지 본다.
- avoid premature optimization.
A Assembling Services
요는 DAG 를 serial-parallel 로 묶는 건데, 문제를 잘못 읽고 없는 제약을 괜히 만들어 생각했다가 1주일동안 삽질함. 예를 들어, a, b 와 c 가 각각 10, 9, 8분씩 걸리고 d 는 a, b 에, e 는 b, c 에 dependent 하다고 하자. 그러면 (a|b)d 와 (b|c)e 를 어떻게 묶을 수가 없으니 와 이거 시망 ㅋ 그러고 있었는데, 예제 데이터를 손으로 따라가 보면 (ad|be|c) 로 해도 된단걸 알 수 있다. 욱신 만세.
졸려서 코딩은 미룸.
B Box Relations
/good/great/graph/topologicalsort/modeling
일단 각 차원이 독립인 것을 알고 나면 위상정렬 아이디어는 간단히 얻을 수 있다. 그러나 둘이 겹친다는 제약이 있기 때문에 안드로. 그러나, 둘이 겹친다는 조건은 사실 s1 < e2 && s2 < e1 로 나타낼 수 있다는 것을 생각하면 모든 조건을 less-than 관계로 변환해 DAG 로 만들 수 있고, 그러면 간단히 위상정렬하면 됨. 다른 형태의 조건들을 한 가지 모양으로 통일해서 풀 수 있다는 점에서 아주 좋은 문제인 것 같다. 이런 연습문제 하나 내기로 맘먹음. [...]
lang:cpp
#include<cstring>
#include<cassert>
#include<algorithm>
#include<string>
#include<vector>
#include<cstdio>
using namespace std;
const int BLACK = 0;
const int GRAY = 1;
const int WHITE = 2;
void dfs(int here, vector<vector<int> >& adj, vector<int>& color, vector<int>& order)
{
color[here] = GRAY;
for(int i = 0; i < adj[here].size(); ++i)
{
int there = adj[here][i];
if(color[there] == GRAY) throw 1;
if(color[there] == BLACK) continue;
dfs(there, adj, color, order);
}
color[here] = BLACK;
order.push_back(here);
}
void solve(vector<vector<int> >& adj, vector<int>& minV, vector<int>& maxV)
{
int n = adj.size();
vector<int> color(n, WHITE);
vector<int> order;
for(int i = 0; i < n; ++i)
if(color[i] == WHITE)
{
dfs(i, adj, color, order);
}
reverse(order.begin(), order.end());
assert(order.size() == n);
minV.resize(n/2);
maxV.resize(n/2);
for(int i = 0; i < order.size(); ++i)
{
if(order[i] % 2 == 1)
maxV[order[i] / 2] = i;
else
minV[order[i] / 2] = i;
}
}
int main()
{
int cc = 0, n, R;
while(scanf("%d %d", &n, &R) == 2)
{
if(n == 0 && R == 0) break;
vector<vector<int> > adj[3];
for(int i = 0; i < 3; ++i)
adj[i].resize(n*2);
for(int k = 0; k < 3; ++k)
for(int i = 0; i < n; ++i)
adj[k][2*i].push_back(2*i+1);
for(int i = 0; i < R; ++i)
{
static char buf[32];
int a, b;
scanf("%s %d %d", buf, &a, &b);
--a; --b;
if(buf[0] == 'I')
{
for(int k = 0; k < 3; ++k)
{
adj[k][2*a].push_back(2*b+1);
adj[k][2*b].push_back(2*a+1);
}
}
else
{
int k = buf[0] - 'X';
adj[k][2*a+1].push_back(2*b);
}
}
printf("Case %d:", ++cc);
vector<int> minV[3], maxV[3];
try
{
for(int k = 0; k < 3; ++k)
{
solve(adj[k], minV[k], maxV[k]);
}
printf(" POSSIBLE\n");
for(int i = 0; i < n; ++i)
{
for(int k = 0; k < 3; ++k)
{
if(k) printf(" ");
printf("%d", minV[k][i]);
}
for(int k = 0; k < 3; ++k)
printf(" %d", maxV[k][i]);
printf("\n");
}
}
catch(int)
{
printf(" IMPOSSIBLE\n");
}
printf("\n");
}
}
C Crossing Rivers
자세한 설명은 생략한다.
lang:cpp
int main()
{
int n, D, cc = 0;
while(scanf("%d %d", &n, &D) == 2)
{
if(n == 0 && D == 0) break;
double ret = D;
for(int i = 0; i < n; ++i)
{
int p, L, v;
scanf("%d %d %d", &p, &L, &v);
ret = ret - L + L * 2.0 / v;
}
printf("Case %d: %.3lf\n\n", ++cc, ret);
}
}
D Download Manager
복잡하게 시뮬레이션 했는데, 여러 개 받는데서 속도 loss 가 없기 때문에 무조건 한개씩만 받아도 되는 함정 문제. 후... 이건 시뮬레이션.
lang:cpp
#include<cstdio>
#include<vector>
#include<queue>
#include<utility>
#include<algorithm>
using namespace std;
int main()
{
int cc = 0, T, n, B; // lame variable names
while(scanf("%d %d %d", &T, &n, &B) == 3)
{
if(T == 0 && n == 0 && B == 0) break;
vector<pair<double,double> > files(T);
for(int i = 0; i < T; ++i)
{
double size; int percentage;
scanf("%lf %d", &size, &percentage);
files[i].first = size;
files[i].second = size * (100 - percentage) / 100.0;
}
sort(files.begin(), files.end());
priority_queue<double, vector<double>, greater<double> > finish;
double bandwidth = B * 1.0 / n;
for(int i = 0; i < n; ++i) finish.push(files[i].second / bandwidth);
int next = n;
double ret = 0, time = 0;
while(!finish.empty())
{
double finishAt = finish.top();
finish.pop();
ret += (finishAt - time) * (finish.size() + 1) * 1.0 / n;
time = finishAt;
if(next < T)
{
finish.push(time + files[next].second / bandwidth);
++next;
}
}
printf("Case %d: %.2lf\n\n", ++cc, ret);
}
}
E Exclusive OR
/graph/implementation/again
그래프 구현 문젠데 알고리즘은 맞는데 틀리고 있음. 안드로 ㅋ ㅠ
G Gift Hunting
Standard DP. 쓸데없는 최적화 했다가 코딩은 복잡해지고 TLE. 지우니까 맞더라.
lang:cpp
#include<cstdio>
#include<cstring>
#include<vector>
using namespace std;
inline void setmax(int& a, int b)
{
a = max(a, b);
}
int main()
{
static int cache[2][501][51][2];
static int p[301], h[301], special[301];
int cc = 0, V1, V2, n;
while(scanf("%d %d %d", &V1, &V2, &n) == 3)
{
if(V1 == 0 && V2 == 0 && n == 0) break;
for(int i = 0; i < n; ++i)
scanf("%d %d %d", &p[i], &h[i], &special[i]);
memset(cache, -1, sizeof(cache));
cache[0][0][0][0] = 0;
for(int gift = 0; gift < n; ++gift)
{
for(int v1 = 0; v1 <= V1; ++v1)
for(int v2 = 0; v2 <= V2; ++v2)
for(int used = 0; used <= 1; ++used)
{
const int v = cache[gift&1][v1][v2][used];
if(v == -1)
continue;
if(!special[gift])
setmax(cache[(gift+1)&1][v1][v2][used], v);
if(!used)
setmax(cache[(gift+1)&1][v1][v2][1], v + h[gift]);
if(p[gift] + v1 <= V1)
setmax(cache[(gift+1)&1][p[gift] + v1][v2][used], v + h[gift]);
if(p[gift] + v2 <= V2)
setmax(cache[(gift+1)&1][v1][p[gift] + v2][used], v + h[gift]);
}
memset(cache[gift&1], -1, sizeof(int)*501*51*2);
}
int ret = -1;
for(int v1 = 0; v1 <= V1; ++v1)
for(int v2 = 0; v2 <= V2; ++v2)
for(int used = 0; used <= 1; ++used)
setmax(ret, cache[n&1][v1][v2][used]);
printf("Case %d: %d\n\n", ++cc, ret);
}
}
H: Help Bubu
남겨 놨다가 끝에 가서 정산하는 형태의 동적 계획법. 풀 수 있었는데 말리다가 패닉해서 못푼듯. :-( 얘넨 왜이렇게 sliding window 를 좋아해.. 아놔.. memoization 쓰고싶네..
lang:cpp
#include<iostream>
#include<cstring>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<cstdio>
#include<cassert>
using namespace std;
int n, k;
int height[101], has;
int cache[2][9][256][101];
inline void setmin(int& a, int b)
{
if(a == -1 || a > b) a = b;
}
int popcount[256];
int main()
{
for(int i = 0; i < 256; ++i)
{
popcount[i] = 0;
for(int j = 0; j < 10; ++j)
if(i & (1 << j))
++popcount[i];
}
int cc = 0;
while(scanf("%d %d", &n, &k) == 2)
{
if(n == 0 && k == 0) break;
has = 0;
for(int i = 0; i < n; ++i)
{
scanf("%d", &height[i]);
height[i] -= 25;
has |= (1 << height[i]);
}
memset(cache, -1, sizeof(cache));
// first book is height 8
cache[0][8][0][k] = 0;
for(int i = 0; i < n; ++i)
{
memset(cache[(i+1)%2], -1, sizeof(int)*9*256*101);
for(int lasth = 0; lasth < 9; ++lasth)
{
for(int seen = 0; seen < 256; ++seen)
{
for(int moves = 0; moves <= k; ++moves)
{
int& val = cache[i%2][lasth][seen][moves];
if(val == -1) continue;
// leave this book
setmin(cache[(i+1)%2][height[i]][seen | (1 << height[i])][moves], val + (height[i] != lasth));
// take this book
if(moves > 0)
setmin(cache[(i+1)%2][lasth][seen][moves-1], val);
}
}
}
}
int ret = 9999;
for(int lasth = 0; lasth < 9; ++lasth)
{
for(int seen = 0; seen < 256; ++seen)
{
for(int moves = 0; moves <= k; ++moves)
{
int& val = cache[n%2][lasth][seen][moves];
if(val != -1) ret = min(ret, val + popcount[has & ~seen]);
}
}
}
printf("Case %d: %d\n\n", ++cc, ret);
}
}
J Jiajia's Robot
미칠듯한 기하?!?!
