5개의 댓글이 있습니다.
-
-
astein -
http://felix-halim.net/tc/index.php?rd=10659 을 이용하시면 됩니다 'ㅁ'
18년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
SINCE 2007
astein
오늘의 스탠딩입니다.
음.. 150등 안에 한국인이 다섯명이 있긴 하지만 성적은 썩 좋지 않네요.
개인적으로는 다들 맞은 Level 1 틀린게 좀 컸네요 -.-;;
Easy (250 pts.)
#define sz(a) ((a).size()) word, int w, int h, int fontsize) {
bool go(vector
int lines = h / (2 * fontsize); // panel에 채울 수 있는 최대 line
int chars = w / (fontsize + 2); // 한 줄에 채울 수 있는 최대 글자수
// 어떤 단어도 height제한 때문에 panel에 들어가지 않는 경우
if (lines == 0) return false;
int a = 1, b = -1; // a는 몇 개의 line을 사용했는지, b는 현재 line에 몇 개의 character를 사용했는지 count합니다.
for (int i = 0; i < sz(word); i++) {
// panel의 width제한 때문에 단어를 채울 수 없는 경우
if (sz(word[i]) > chars) return false;
b += sz(word[i]) + 1;
if (b > chars) {
a++;
if (a > lines) return false; // height 제한 초과
b = sz(word[i]);
}
}
return true;
}
[/spoiler]
Hard (1000 pts.)
* 문제설명
어떤 점들의 집합이 주어졌을 때, 아래의 조건을 만족시키는 나선(Spiral)을 구성하는 최대 점의 개수를 구하시오.
<< 조건 >>
1. 항상 (0, 0)에서 시작한다.
2. 현재의 위치에서 (x, y)로 이동한다면, 둘 사이를 연결하는 선분을 긋는다. (x, y)는 새로운 시작점이 된다.
3. 아래의 규칙을 모두 만족하는 조건 아래에서, rule 2를 반복한다.
- 규칙 1 : Spiral은 스스로 겹치지 않는다. 인접한 선분이 공유하는 끝점들을 제외하고, 다른 교점이 없다.
- 규칙 2 : 각각의 점은 두 번 이상 사용되지 않는다.
- 규칙 3 : 다음 선분으로 연결할 때, 항상 반시계 방향으로 꺾거나, 직진한다. 즉, 회전각 angle은 0 <= angle < 180이 된다.
- 규칙 4 : "마지막 바로 이전 점"에서 "마지막 점"은 선분이 아니라 반직선이라고 가정한다. 즉, 같은 선상에 spiral의 다른
선분(혹은 점)을 지나가지 않는다.
아래의 그림은 규칙 1, 2, 3을 만족시키지 못하는 예를 나타낸다.
아래의 그림은 규칙 4를 만족시키지 못하는 경우들이다.
[spoiler="더 보기..."]
* 해결방법
전체적인 큰 틀은 Dynamic Programming을 사용하였습니다. DP 테이블의 정의는 아래와 같습니다.
table[a][b][S] = 최근에 사용한 선분이 a-b 이고, 현재 사용되지 않는 점들의 set이 S일 때, 앞으로 사용할 수 있는 최대 점 수.
위와 같이 정의된 table에서 최근에 a - b 가 연결되었고, 아직 사용되지 않는 점들의 집합 S가 있습니다. 그러면 이 중에서 S - p를 연결할 수 있고, table[b][p][S - p] + 1 중에서 제일 큰 값이 table[a][b][S]에 들어가게 됩니다.
4가지 규칙 중 마지막 규칙을 해결하는 것이 제일 까다롭지만, 이 규칙은 "제일 마지막에 연결되는 선분(위의 설명에서, 선분b - p)이 현재까지의 spiral에서 사용했던 점들 모두 strict하게 left side에 있다"를 체크함으로서 해결 가능합니다. 만약 b - p와 같은 선 상에 점이 있다면, b - p 다음 점은 항상 반시계 방향(혹은 일직선)으로 꺾여야 하므로 spiral 안쪽으로 휘어들어가는 모양이 됩니다. 결국 위를 반복해도, 마지막 반직선은 spiral 어딘가에 부딪치게 되므로, 어떻게 하더라도 규칙 4를 만족시킬 수 없게 됩니다.
P.S) 일단 소스를 첨부하긴 합니다만, 매크로에 익숙하지 않은 경우, 읽으시는 데 약간 어려움이 있으실 수도 있겠네요 ㅜㅜ
다음에 시간나면 수정하겠습니다 orz
~~~ cpp
#define EPS 1e-10 a;
points) {
#define pb push_back
#define sz(a) ((int)a.size())
#define REP(i,n) FOR(i,0,n)
struct Point {
int x, y;
Point(int ix = 0, int iy = 0) : x(ix), y(iy) {}
bool operator == (const Point &a) const {
return abs(x - a.x) < EPS && abs(y - a.y) < EPS;
}
};
char table[16][16][1 << 16];
vector
int N;
struct SpiralConstruction {
// a, b, c가 일직선상에 있다고 가정했을 때 a -- b -- c => true
bool between(Point a, Point b, Point c) {
int X = (a.x - b.x) * (c.x - b.x);
int Y = (a.y - b.y) * (c.y - b.y);
return (X <= 0 && Y <= 0);
}
// a-b-c가 counter clockwise꺾임인가? (일직선 상이라면, 현재 방향 그대로 직진인 경우 true)
bool left(Point a, Point b, Point c) {
int p = (a.x * b.y + b.x * c.y + c.x * a.y);
p -= (a.x * c.y + b.x * a.y + c.x * b.y);
if (p < 0) return false;
if (p == 0 && !between(b, a, c)) return false;
return true;
}
// for memoization.
int go(int q, int w, int bit) {
if (table[q][w][bit] != -1) return table[q][w][bit];
int ret = 0;
REP(i, N) {
if (bit & (1 << i)) {
bool flag = true;
REP(j, N + 1) {
if (!(bit & (1 << j)) && j != w && j != i && !left(a[w], a[i], a[j]) ) flag = false; // (w - i - 현재까지 사용한 점)이 strict 왼쪽꺾임이 아닌 경우 더 이상 진행하지 않으면 되므로, flag = false;
}
if (flag) ret >?= go(w, i, bit - (1 << i)) + 1; // >?=는 ret = max(ret, go(w, i, bit - (1 << i)) + 1) 과 같습니다. ㅠㅠ
}
}
return (table[q][w][bit] = ret);
}
int longestSpiral(vector
memset(table, -1, sizeof(table));
N = sz(points);
a.resize(N + 1);
REP(i, N) {
istringstream sin(points[i]);
sin >> a[i].x >> a[i].y;
}
a[N] = Point(0, 0); // N번째 점은 (0,0)
int ret = 0;
REP(i, N)
ret >?= go(N, i, (1 << N) - 1 - (1 << i)) + 1; // N-i로 시작
return ret;
}
};
18년 전