카카오 코드 페스티벌 잘 못푼 이야기

일단 A번은 쉬웠으므로 패스.

아무리 나의 허접한 실력이더라도 A번 쯤이야 풀 수 있다.

그런데 막상 B번에서 막혔다.

구해야 할 것은 수열에서 표준 편차가 가장 작은 연속구간을 알아내어, 그 표준편차를 출력하는 것.

분산이 E(X^2) - E(X)^2 임을 이용하기 위해 누적 합 배열을 두개 유지시켰고,

이 배열 두개를 토대로, 모든 구간을 for문 두개로 돌려가면서 최솟값을 찾는 코드를 짰다.

근데 웬일?

맞왜틀?

채점 50% 구간에서 틀리길래, 아 이건 무조건 경계값에서 잘못된 것이라고 생각해서

경계값만 생각했더니 그게 아닌것 같더라.

뇌정지가 온건가 해서 다음문제로 넘어갔다가 나중에 다시 돌아와도, 도대체 왜 틀린건지 모르겠다.

아래는 문제의 코드다.

코드는 따로 신텍스를 받아야 하는데 아직 없어서.... 그냥 텍스트로 올린다.

그새 받아왔다.

코드 맨 마지막에 </iostream> 이 남아있는건 알아서 없다고 보면 된다.

#include 

#include 

#include 

#include 

#include 



using namespace std;



long long dat[511];

long long sum[511];

long long sqsum[511];

int main()

{

   ios_base::sync_with_stdio(false);

   cin.tie(0);

   int N, K;

   cin >> N >> K;

   sum[0] = 0;

   sqsum[0] = 0;

   for (int i = 1; i <= N; i++)

   {

      cin >> dat[i];

      sum[i] = sum[i - 1] + dat[i];

      sqsum[i] = sqsum[i - 1] + (dat[i] * dat[i]);

   }

   //

   double ans = 20000000000000;

   double a, b; // E(X^2) , E(X)^2

   for (int i = 0; i <= N - K; i++)

   {

      for (int j = i + K; j <= N; j++)

      {

         a = (double)(sqsum[j] - sqsum[i]) / (j - i);

         b = (double)(sum[j] - sum[i]) / (j - i);

         b = b * b;



         ans = min(ans, a - b);

      }

      // a = (double)(sqsum[i + K - 1] - sqsum[i -1]) / K;

      // b = (double)(sum[i + K - 1] - sum[i - 1]) / K;

   }

   cout.precision(16);

   cout << sqrt(ans);

   return 0;

}

뭐가 틀렸지?

B번에서 시간을 매우 허비하고  C로 패스해서 넘어가려는데,

스코어 보드를 보니 하이랭크에 다들 C를 피하고 D부터 시작하는 것이 아닌가?

나는 C번은 문제는 슥 읽고 바로 D로 넘어갔다.

D번은 쉬워보였다.

x 좌표와 y좌표의 일정 거리 이내에만 있으면 연결 가능한 경유점이므로,

일단 그래프를 그린 후 경로탐색을 하면 될 것이라고 생각했다.

그런데 왜 메모리 초과가 나오는 거야??????

방향을 바꿔서 그 Disjoint-Set인가 하는 방법으로 바꿨다. (Union, find)

그런데 시간초과가 뜨는게 아닌가?

코드 진행은 대략 이랬다.

x 좌표와 y 좌표를 각각 순서대로 정렬한 후,

모든 경유점들을 for문에 넣어 돌린다.

이 for문에서는 자신의 x 좌표 보다 큰 점들을 조금씩 맛보는데,

이 맛이 정해진 길이 X보다 작으면 같은 집합에 넣고, 그렇지 않으면 break한다.

아 문제도 안쓰고 설명하려니까 이상하네.

아무튼.

처음에는 이렇게 해서 시간초과가 나오길래, 방법을 하나 추가했다.

들어오는 쿼리에 있는 X값을 토대로 정렬한 뒤, 증가하는 순서대로 쿼리를 실행하는거다.

이렇게 하면 놀랍게도 집합(Disjoint Set)을 쿼리마다 새롭게 만들 필요 없이 추가 길이분에 대해서만 연결시켜주면 된다.

아무튼 이렇게 해도 시간초과였고 접었다.

그 실패한 코드는 아래와 같다.

아, disjoint set 구현은 사실 http://bowbowbow.tistory.com/26 여기 있는 코드를 그대로 사용했다.

혹시 문제가 될까봐 아래 코드에서는 해당 구조체를 아예 지웠다.

#include 
#include 
#include 
#include 
#include 
#include 
#define INTMAX 2147483646

using namespace std;


vector,int> > dat;
vector, int> > dat2;
vector g(250001);

int findr(int a)
{
	int ra = a;
	while (ra != g[ra])
	{
		ra = g[ra];
	}
	return ra;
}

int group(int a, int b)
{
	if (findr(a) == findr(b))
		return 1; //already in group
	int ra = a, rb = b;
	int label = max(findr(ra), findr(rb));
	int tmp;
	g[a] = label;
	g[b] = label;
	return 0;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int tmp1, tmp2;
	for (int i = 1; i <= N; i++)
	{
		cin >> tmp1 >> tmp2;
		dat.push_back(make_pair(make_pair(tmp1, tmp2),i));
		dat2.push_back(make_pair(make_pair(tmp2, tmp1),i));
	}
	dat.push_back(make_pair(make_pair(INTMAX, INTMAX), N + 1));
	dat2.push_back(make_pair(make_pair(INTMAX, INTMAX), N + 1));
	sort(dat.begin(), dat.end());
	sort(dat2.begin(), dat2.end());

	int A, B, X;

	vector,pair > > query(Q);
	vector ans_v(Q);
	for (int i = 0; i < Q; i++)
	{
		cin >> A >> B >> X;
		query[i] = make_pair(make_pair(X,i), make_pair(A, B));
	}
	sort(query.begin(), query.end());

	for (int i = 0; i <= N; i++)
		g[i] = i;
	
	OptimizedDisjointSet g_(N);

	vector preidx_x(N + 1, 1);
	vector preidx_y(N + 1, 1);

	for (int q = 0; q < Q; q++)
	{
		A = query[q].second.first;
		B = query[q].second.second;
		X = query[q].first.first;
		for (int i = 0; i <= N - 2; i++)
		{
			int idx = preidx_x[i];
			while (dat[i + idx].first.first - dat[i].first.first <= X)
			{
				g_.merge(dat[i].second - 1, dat[i + idx].second - 1);
				// group(dat[i].second, dat[i + idx].second);
				// g[dat[i].second].push_back(dat[i + idx].second);
				// g[dat[i + idx].second].push_back(dat[i].second);
				idx++;
			}
			preidx_x[i] = idx;
		}
		for (int i = 0; i <= N - 2; i++)
		{
			int idx = preidx_y[i];
			while (dat2[i + idx].first.first - dat2[i].first.first <= X)
			{
				g_.merge(dat2[i].second - 1, dat2[i + idx].second - 1);
				// g[dat2[i].second].push_back(dat2[i + idx].second);
				// g[dat2[i + idx].second].push_back(dat2[i].second);
				idx++;
			}
			preidx_y[i] = idx;
		}
		//
		int ans = 0;
		if (g_.find(A - 1) == g_.find(B - 1))
			ans = 1;
		ans_v[query[q].first.second] = ans;
	}
	for (auto it : ans_v)
	{
		if (it == 1)
			std::cout << "YES\n";
		else
			std::cout << "NO\n";
	}
	return 0;
}

이건 왜 시간초과가 뜨는거지...? 나중에 볼 수 있도록이라도 이렇게 적어놓는다.

====

완전 일기식으로 쓰긴 했지만, 뭐 비정기적인 알고리즘 대회가 다 이렇겠지?