글 읽기 - 2282번 문제 반례나 알고리즘의 문제점을 지적해주셨으면 합니다.

sqa314 4년 전 2

산맥 그리기 문제입니다.

인접 리스트를 만들어서 최단 경로 문제로 바꾸되, 레이어를 만들듯이 여러 단계를 거치도록 했습니다.

가장 큰 오차:

4 0

1 1

2 10000

9999 10000

10000 1

이 가장 큰 오차를 가질 수 있는데

99970002 로 정확히 나옵니다.

기타 여러 예제들을 실험해 보았는데 대부분 문제 없이 출력 되었습니다.

다만 일정 수준 이상의 n이나 K는 제가 예제를 만들어도 확인이 어려워서 에러가 나지 않는 것만 확인했습니다.

cout.precision(20)으로 스페셜 저지 문제라서 발생할 수 있는 오차도 아닌 것으로 보입니다.

도저히 모르겠습니다.

혹시 코드가 눈에 잘 안 들어오신다면 메모하시면 제가 설명 드리겠습니다.

#include <iostream>
#include <fstream>
#include <cstdbool>
#include <vector>
#include <cstdlib>
#include <cmath>
using namespace std;

class _edge
{
public:
	int node;
	double weight;
	_edge* next;
	_edge();
	_edge(int, double);
};
_edge::_edge()
{
	node = -1;
	weight = -1;
	next = NULL;
}
_edge::_edge(int node, double weight)
{
	this->node = node;
	this->weight = weight;
	next = NULL;
}
class _Adj
{
public:
	_edge* first;
	_edge* last;
	_Adj()
	{
		first = last = NULL;
	}
};

class Graph
{
	int n;
	_Adj* Adj;
public:
	void vertexInsert(int);
	void dirEdgeInsert(int, int, double);
	void B_F(int, vector< vector<double> >&, int, int);
	void B_Fl(int, vector< vector<double> >&, int, int);
};
void Graph::vertexInsert(int n)
{
	this->n = n;
	Adj = new _Adj[n + 1];
}
void Graph::dirEdgeInsert(int base, int node, double weight)
{
	_edge* temp = new _edge(node, weight);

	if (Adj[base].first)
		Adj[base].last = Adj[base].last->next = temp;
	else
		Adj[base].first = Adj[base].last = temp;
}
void Graph::B_F(int k, vector< vector<double> >& diff, int n, int K)
{
	int i, j;
	_edge* temp;
	for (i = k + 1; i < n - K + k; i++)
		for (j = 1, temp = Adj[i].first; temp; temp = temp->next, ++j)
			if (diff[i + j][k + 1] > diff[i][k] + abs(temp->weight))
				diff[i + j][k + 1] = diff[i][k] + abs(temp->weight);
}
void Graph::B_Fl(int k, vector< vector<double> >& diff, int n, int K)
{
	int i, j;
	_edge* temp;
	for (i = k + 1; i < n - K + k; i++)
		for (j = 1, temp = Adj[i].first; temp; temp = temp->next, ++j)
			if (diff[n][k + 1] > diff[i][k] + abs(temp->weight))
				diff[n][k + 1] = diff[i][k] + abs(temp->weight);
}
double sum(vector< vector<double> >& peak, int i, int j)
{
	double sum = 0;
	int n;
	double x;
	double a, b, c, d;
	double A, C, B, D;
	for (n = i; n < j; n++)
	{
		A = (peak[n][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1];
		C = peak[n][1];
		B = (peak[n + 1][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1];
		D = peak[n + 1][1];
		if (A == C && B == D);
		else if (A <= C && B <= D)
			sum += (peak[n + 1][0] - peak[n][0]) * ((peak[n + 1][1] + peak[n][1]) - ((peak[n + 1][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1] + (peak[n][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1])) / 2;
		else if (A >= C && B >= D)
			sum += (peak[n + 1][0] - peak[n][0]) * (((peak[n + 1][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1] + (peak[n][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1]) - (peak[n + 1][1] + peak[n][1])) / 2;
		else
		{
			a = (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]);
			c = (peak[n + 1][1] - peak[n][1]) / (peak[n + 1][0] - peak[n][0]);
			b = (peak[n][0] - peak[i][0]) * (peak[j][1] - peak[i][1]) / (peak[j][0] - peak[i][0]) + peak[i][1];
			d = peak[n][1];
			x = (d - b) / (a - c);
			sum += (x * abs(C - A) + (peak[n + 1][0] - peak[n][0] - x) * abs(D - B)) / 2;
		}
	}
	return sum;
}
int main()
{
	int i, j, v;
	int n, K;
	int idx, height;
	cin >> n >> K;
	Graph* g = new Graph[K + 1];
	for (i = 0; i <= K; ++i)
		g[i].vertexInsert(n);
	vector< vector<double> > diff(n + 1, vector<double>(K + 2, 100000000));
	vector< vector<double> > peak(n + 1, vector<double>(2));
	diff[1][0] = 0;
	cout.precision(20);
	for (i = 1; i <= n; ++i)
	{
		cin >> idx >> height;
		peak[i][0] = idx;//peak[i][0]는 해당 점의 x좌표
		peak[i][1] = height;//peak[i][0]은 해당 점의 y좌표 (높이)
	}
	if (K == 0)
		g[0].dirEdgeInsert(1, n, sum(peak, 1, n));
	else
	{
		for (i = 1, j = 2; j <= n - K; ++j)
			g[0].dirEdgeInsert(i, (int)peak[j][0], sum(peak, i, j));
		for (v = 1; v < K; ++v)
			for (i = 1 + v; i < n; ++i)
				for (j = i + 1; j <= n - K + v; ++j)
					g[v].dirEdgeInsert(i, (int)peak[j][0], sum(peak, i, j));
		for (i = K + 1, j = n; i < n; ++i)
			g[K].dirEdgeInsert(i, (int)peak[j][0], sum(peak, i, j));
	}
	for (i = 0; i < K; ++i)
		g[i].B_F(i, diff, n, K);
	g[K].B_Fl(K, diff, n, K);
	cout << diff[n][K + 1];
	return 0;
}

herdson 4년 전 1

아무도 못 푼 문제인데 지적이나 반례를 줄 사람 역시 없지 않을까요...

llqoap00 4년 전 0

제가 푼거랑 테스트케이스 몇개 해봤는데 답이 거의 일치하네요

7 2
1 1
2 5
3 3
4 7
5 1
6 6
7 3
6.460000
님꺼로 했을 때 6.459999999999999964510 3
1 3
2 4
3 7
4 4
5 8
6 9
7 23
8 12
9 10
10 1
6.746033

님꺼로 했을 때 6.7460317460317451577

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

문제

문제

출처

ICPC

2282번 문제 반례나 알고리즘의 문제점을 지적해주셨으면 합니다.

sqa314 4년 전 2

herdson 4년 전 1

llqoap00 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말