6개의 댓글이 있습니다.
-
-
carlo -
역시 누군가 해놓은 사람이 있군요 ㅎㅎ
허접 포탈 풀이를 해보았습니다.
1.미로를 찾는다.
2.포탈로 거리를 줄인다.
우선 미로찾는 알고리즘을 간단히 생각해 보았다.
이름하여 프로브 알고리즘.
전제:프로브는 자기가 지나온 길의 중요포인트(시작,끝,코너) 및 전체 코너의 수와 전체이동거리를 기억한다. 자기자신을 무한히 복사할 수 있다.(기억한거 포함) - (클래스로 구현하면 될듯)
맵을 읽어들인 배열이 있다.
미로찾기 알고리즘: 프로브알고리즘 by Carlo
스텝1:시작점에 프로브를 만든다.
스텝2:모든프로브는 새로운길이 2개이상일 경우 자기자신을 하나이상 복사하여 (어떠한방향으로)한칸 전진한다.
스텝3:모든프로브의 생과사를 점검한다.
1:충돌상황 점검: 생존의 우선순위 -- 적은전체거리>적은코너>컴퓨터저장상위랭크
2:생존 프로브수: 0 이면 실패
3:끝점에 도착한프로브? 있으면 성공
스텝4:Go to 스텝2
포탈사용 알고리즘: 포탈가속화알고리즘 by Carlo
전제:생존프로브는 중요 포인트, 전체 거리, 전체 코너수를 기억하고 있다.
: Sum=0, N=0
스텝1:메모리에 기억하고있는 N,N+1번째 포인트 사의의 거리와 N,N+1번째 포인의 이동방향의 각각의 벽방향과의 거리의 합((N쪽벽과 N사이의거리)+ (N+1쪽벽과 N+1사이의 거리))과 비교하여 작은쪽으로 Sum에 더한다.
스텝2:if N+1== 전체코너+ 2 끝
스텝3:N++ Go to step1
머그다지 효율성과 결과는 확인해보지 못했습니다. ;;
http://univac.egloos.com/
그럼, 남은 명절즐겁게 ...
16년 전 link
-
-
-
ibroker -
C번 문제는 bipartite graph에서 maximum independent set을 찾는 문제로 치환할 수 있겠군요.
그래서 matching으로 되는듯?! 합니다.
http://acm.pku.edu.cn/JudgeOnline/problem?id=3692
이 문제도 풀어보세요~
16년 전 link
-
-
정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.
astein
아무도 안올리셔서 제가 씁니다 :)
A. How Big Are the Pockets?
[문제 설명]
Polygonovich 교수는 평면 상의 위치에서 랜덤하게 걸어다니는것을 즐긴다. 교수는 아침에 원점에서 북쪽을 바라보며 긴 여행을 떠난다. 교수는 직진하거나 왼쪽으로 90도 회전, 오른쪽으로 90도 회전만 하면서 여행을 즐긴다. 이 여행동안 한번 방문했던 점을 두번 다시 방문하지 않으며, 해가 지기 전에 시작했던 위치로 돌아온다. 따라서 교수가 지나간 경로는 연결하면 하나의 도형을 만들게 된다. (아래 그림 참조)
교수가 한 바퀴 돌고 온 구간이 위의 그림과 같다고 하자. 당신은 이 구간이 convex가 아니라는 것을 깨달았다. 따라서 아래와 같이 "pocket" 을 채워서 convex로 만들려고 한다.
아래의 둘 중 하나를 만족하면 "pocket" 이라고 부른다.
1) 한 점을 기준으로 위-아래가 막혀있으면 이 점은 pocket이다.
2) 한 점을 기준으로 왼쪽-오른쪽이 막혀있으면 이 점은 pocket이다.
따라서 첫 번째 그림에서 x는 2)를, y는 1), 2)를, z)는 1)을 만족하므로 이 세 점은 pocket이고, w는 둘 다 만족하지 않으므로 pocket이 아니다.
교수가 이동한 경로가 입력으로 주어질 때, "pocket"의 크기를 출력하는 프로그램을 작성하시오.
Small Data Set) 각 좌표의 절대값은 100 이하
Large Data Set) 각 좌표의 절대값은 3000 이하
[spoiler="풀이 보러가기"][문제 풀이]
Small Data Set의 경우에는 좌표의 절대값이 작기 때문에, 배열로 표현할 수 있습니다. 아래의 그림을 살펴보도록 하지요.
위와 같이 좌표를 변형합니다. 즉, 모든 좌표를 2배해서 점선부분까지 배열에 채우는 것이지요. 이렇게 2배씩 해주는 이유는, 내부/외부의 점을 쉽게 체크하기 위해서 입니다. 이렇게 해서 내부/외부를 나눴다면 문제에서 정의한 pocket의 수를 찾으면 해결할 수 있습니다. 내부가 아닌 모든 점에 대하여 현재 점이 pocket인지 찾으면 됩니다. 케이스 하나에 대하여 최대 400 * 400 * 400 정도의 연산이면 답을 구할 수 있지요. 소스코드에 간단한 주석을 달아두었습니다 :D
하지만 Large Data Set은 좌표의 절대값이 너무 크지요. 따라서 각 점에 대하여 직접 pocket을 구하는 위의 알고리즘으로는 무리가 있습니다. 따라서 현재 점이 pocket인지 아닌지를 빨리 계산하면 되지요. 임의의 어떤 점에서 그 점의 왼쪽에 polygon 내부점이 존재하는가? 오른쪽에 내부점이 존재하는가? 위쪽은? 아래쪽은? 이라는 4가지의 질문을 바로바로 대답할 수 있다면 pocket인지 아닌지를 알 수 있지요.
만약 (x, a)라는 점이 내부점이고, (x, b)라는 점이 내부점이라면, a <= c <= b를 만족하는 모든 c에 대하여 (x, c)가 내부점이나 pocket이 된다는 점을 알 수 있습니다. 이는 90도 회전하여 y좌표에 대해서도 마찬가지이지요. 즉 모든 좌표에 대하여 현재 점이 내부점이냐? pocket이냐? 둘 다 아니냐?를 O(1)만에 계산할 수 있게 된 셈입니다.
Large Data Set은 직접 테이블로 표현할 수 없습니다. 하지만 모든 점에 대하여 이 점이 내부점 or pocket인지를 구할 수 있고요. 입력받은 다각형이 있을 때 내부 넓이는 따로 구해야 합니다. 다각형의 내부넓이를 구하는 알고리즘은 검색하면 금방 나올테니 여기에다가 쓰진 않겠습니다 :)
[/spoiler]
[spoiler="소스코드 보러가기(Small)"]~~~ cpp
#include > Q; now = Q.front(), next; Q.pop();
> P;
#include
#include
#include
#include
#include
using namespace std;
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
int table[420][420];
void fill(int x, int y) {
table[x][y] = 1;
queue
Q.push(make_pair(x, y));
while (!Q.empty()) {
pair
for (int i = 0; i < 4; ++i) {
next.first = now.first + dx[i];
next.second = now.second + dy[i];
if (next.first < 0 || next.first == 420) continue;
if (next.second < 0 || next.second == 420) continue;
if (table[next.first][next.second] == 0) {
table[next.first][next.second] = 1;
Q.push(next);
}
}
}
}
int main() {
int T;
cin >> T;
for (int cn = 1; cn <= T; ++cn) {
printf("Case #%d: ", cn);
int L, N, head = 0, x = 0, y = 0;
vector
string S;
cin >> L;
P.push_back(make_pair(x, y));
for (int i = 0; i < L; ++i) {
cin >> S >> N;
for (int j = 0; j < N; ++j) {
for (int k = 0; k < S.size(); ++k) {
if (S[k] == 'F') {
x += dx[head];
y += dy[head];
P.push_back(make_pair(x, y));
}
if (S[k] == 'R') head = (head + 1) % 4;
if (S[k] == 'L') head = (head + 3) % 4;
}
}
}
int ret = 0;
for (int i = 0; i < P.size(); ++i) {
P[i].first += 105;
P[i].second += 105;
}
memset(table, 0, sizeof(table));
for (int i = 0; i < P.size() - 1; ++i) {
table[P[i].first * 2][P[i].second * 2] = 1;
table[P[i].first + P[i + 1].first][P[i].second + P[i + 1].second] = 1;
}
fill(0, 0);
for (int i = 1; i < 420; i += 2) {
for (int j = 1; j < 420; j += 2)
if (table[i][j] == 1) { // 바깥쪽인 경우
int ct = 0;
for (int k = j - 1; k >= 0; --k) if (table[i][k] == 0) { ct++; break; }
for (int k = j + 1; k < 420; ++k) if (table[i][k] == 0) { ct++; break; }
for (int k = i - 1; k >= 0; --k) if (table[k][j] == 0) { ct++; break; }
for (int k = i + 1; k < 420; ++k) if (table[k][j] == 0) { ct++; break; }
if (ct >= 3) ret++; // 상하좌우로 반직선을 그렸는데 세 점이상 만났다는 말은 pocket 이라는 뜻
}
}
cout << ret << endl;
}
}
또한 너비우선탐색은 초기상태에서 시작하여 점점 깊이가 깊어지도록 하는 것이 핵심입니다. 이를 priority_queue로 두고 할 수도 있겠지만, deque를 사용하여 접근하였습니다. deque를 사용하면 현재 리스트에 있는 상태들의 깊이 차이가 최대 1이라는 것을 보장할 수 있습니다. 현재 위치에서 포탈건을 발사했으면 이동횟수는 증가하지 않으므로 deque에 push_front를, 한칸 이동한 경우는 push_back을 해주면 되기 때문이지요. 현재 레벨에서의 모든 상태를 검색한 다음에야 다음 레벨로 넘어가게 될 것이고, 이전 상태의 deque에 남아있지 않게 되니까요.
또한 현재 상태를 이전에 지나간 적이 있는가? 를 map을 사용하여 check하였습니다. 6차원 배열을 잡아도 되지만 좀 귀찮아서요 [...] B번 문제는 문제풀이보다는 소스코드를 보는게 낫지 않을까...라고 생각하고 있습니다 :) 결국 구현의 문제니까요. [/spoiler]
[spoiler="소스코드 보러가기"]~~~ cpp
#include
#include
#include
#include
#include
#include
[/spoiler]
[spoiler="소스코드 보러가기(Large)"]~~~ cpp
#include
#include
#include
#include
using namespace std;
/*********************************************** *
[/spoiler]
[spoiler="소스코드 보러가기(Large)"]
[/spoiler]
16년 전