글 읽기 - 10167 금광 문제 질문드립니다.

kks227 8년 전 0

중등부 문제라는데 도저히 중등부 문제라는 것을 믿을 수 없어하면서 제 머리로 몇 시간에 걸쳐 솔루션을 이해하고 짜본 결과 20% 가량에서 마주치는 비교적 작은 테스트 케이스에서 오답을 뱉는다고 합니다.

일단 51~55번 줄에서 점들을 X좌표 기준으로 정렬한 후 X좌표마다 증가하는 순으로 새로운 번호를 매겼고

56~58번 줄에서 점들을 Y좌표 기준으로 재정렬하고(이때 튜플의 x, y 원소 순서가 바뀝니다)

60~69번 줄에서 가능한 모든 Y1, Y2의 쌍에 대해 등장 가능한 모든 maxsum을 얻어보고 그 중 최댓값을 찾아서 result에 넣는 중입니다. 이때 같은 Y좌표 점들은 반드시 한번에 처리하려 했습니다.

어디가 잘못된 걸까요? 실수를 몇 개나 다잡아봤지만 여전히 틀려서 결국 의욕이 떨어졌습니다. 앞쪽의 큼직해보이는 케이스 2개는 통과했는데... 뭔가 사소한 예외처리가 잘못된 것 같습니다.

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <tuple>
using namespace std;
const int SIZE = 8192;
typedef tuple<int, int, int> P;

struct SegTree{
	int size, start;
	long long sum[SIZE], lsum[SIZE], rsum[SIZE], maxsum[SIZE];
	SegTree(int n): size(n){
		start = 1;
		while(start < size) start *= 2;
		clear();
	}
	void clear(){
		memset(sum, 0, sizeof(sum));
		memset(lsum, 0, sizeof(lsum));
		memset(rsum, 0, sizeof(rsum));
		memset(maxsum, 0, sizeof(maxsum));
	}
	void renew(int n, int w){
		int c = start + n;
		sum[c] = lsum[c] = rsum[c] = maxsum[c] += w;
		c /= 2;
		while(c > 0){
			int l = c*2;
			int r = l+1;
			sum[c] = sum[l] + sum[r];
			lsum[c] = max(lsum[l], sum[l]+lsum[r]);
			rsum[c] = max(rsum[r], sum[r]+rsum[l]);
			maxsum[c] = max(max(rsum[l]+lsum[r], sum[c]), max(maxsum[l], maxsum[r]));
			c /= 2;
		}
	}
};

int main(){
	int N, range = 0;
	long long result = 0;
	scanf("%d", &N);
	P point[3000];
	for(int i=0; i<N; i++){
		int x, y, w;
		scanf("%d %d %d", &x, &y, &w);
		point[i] = P(x, y, w);
		result = max(result, 1LL*w);
	}
	
	sort(point, point+N);
	for(int i=0; i<N; i++){
		if(i>0 && get<0>(point[i]) != get<0>(point[i-1])) range++;
		get<0>(point[i]) = range;
	}
	for(int i=0; i<N; i++)
		swap(get<0>(point[i]), get<1>(point[i]));
	sort(point, point+N);

	SegTree ST(range+1);
	for(int i=0; i<N; i++){
		if(i>0 && get<0>(point[i]) == get<0>(point[i-1])) continue;
		ST.clear();
		for(int j=i; j<N; j++){
			ST.renew(get<1>(point[j]), get<2>(point[j]));
			if(j==N-1 || get<0>(point[j]) != get<0>(point[j+1]))
				result = max(result, ST.maxsum[1]);
		}
	}
	printf("%lld\n", result);
}

koosaga 8년 전 4

만약에 빈 집합에 -1이 하나가 달랑 들어가 있다면 정의상 maxsum은 0인가요 -1인가요? 저도 저거때문에 처음 할 때 엄청 해멨던 기억이.. ㅠㅠ

추가로 저 문제는 대회때 만점자가 없었습니다.

kks227 8년 전 0

엄밀히는 -1이 나와야 하겠지만, 문제에서 w가 양수인 자원이 최소 하나 있다고 해서 result가 일단 0보다 클 것이라 생각해서 그런 부분을 신경쓰지 않았는데, 다시 한 번 생각해 보니까 문제가 꼭 안 되리라는 보장도 없네요. 한번 생각해 봐야겠습니다.

ㅋㅋㅋㅋ 문제가 너무 어렵네요... 제가 정올 출신은 아니지만 아무리 봐도 중등부 수준이 아닌데...

kks227 8년 전 1

1 1 4
1 2 6
2 1 7
2 2 -1000

이런 최소 케이스는 실험해 봐서 11이 잘 나왔었는데, 하루 동안 잠만 자다가 일어나서 방금 전에

4
2 2 4
1 2 6
2 1 7
1 1 -1000

이 케이스를 넣어보니까 갑자기 17을 뱉어내서 디버깅했더니 맞았습니다.

x좌표를 새로 매기는 부분에서, 이미 이전 x좌표가 바뀌어 버렸는데 그거랑 같은지 비교를 하고 있어서 문제가 생겼네요.

이게 대체 어떻게 두 개의 큰 케이스를 통과한건지는 의문이지만... 그래도 해피엔딩 이군요

도와주신 koosaga님께 다시 한번 감사의 말씀 드립니다.

h0ngjun7 4년 전 0

지금 생각해도 중학생에게는 많이 어렵지 않았나 싶네요ㅋㅋ

당시에는 만점 방지 + 서브테스크 긁기 싸움의 의도로 출제했을텐데...

실제로 금상 이상인 중학생 친구들 점수 분포도 예상보다 높았던 걸로 기억해요.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

10167 금광 문제 질문드립니다.

kks227 8년 전 0

koosaga 8년 전 4

kks227 8년 전 0

kks227 8년 전 1

h0ngjun7 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말