글 읽기 - KOI 2004 지역 - 청개구리 시간초과 도와주세요!

foryou1006ll 5년 전 0

백트래킹을 적용하고 메모이제이션등 이것저것 사용해봤는데 아무리해도 시간초과가 나옵니다ㅠㅠ

혹시 이 문제를 실제 대회때 풀어보셨거나, 풀이 방법을 알고 계신분 있으시면 좀 도와주세요!

시간을 조금만 더 줄이면 될것 같은데... 착각이겠죠?

#include <iostream>
#include <vector>
#include <set>
#include <map>
#include <cstring>
#include <ctime>
#include <algorithm>
using namespace std;

const int INF = 987654321;

int N;
int halfN;
int step_list[200];
int imin_frog = INF;

class backtrack_info
{
public:
	int frog;
	vector<pair<int, int>> result;

public:
	backtrack_info()
		: frog(INF)
	{}

	backtrack_info(int _frog)
		: frog(_frog)
	{}
};

map<vector<int>, backtrack_info> dp;

backtrack_info backtracking(int curr, int _start, int _step, int* curr_step)
{
	if (curr > 100) return backtrack_info(INF);
	if (curr >= imin_frog) return backtrack_info(INF);

	int max_value = 0;
	int not_zero_cnt = 0;
	set<pair<int, int>> p_start_pos;
	int accum = 0;
	int first_not_zero_idx = -1;
	vector<int> dp_idx;

	int next_step[200];
	for (int i = 0; i < N; i++)
	{
		next_step[i] = curr_step[i];
		int calc = i - _start;
		bool check = (calc % _step == 0);
		if (next_step[i] > 0 && i >= _start && check)
		{
			next_step[i]--;
		}
		else if (i > _start + _step && check)
		{
			return backtrack_info(INF);
		}

		if (next_step[i] > 0)
		{
			max_value = max(max_value, next_step[i]);
			not_zero_cnt++;
			p_start_pos.insert(make_pair(next_step[i], i));
			if (first_not_zero_idx == -1)
			{
				if ((i + 1) > halfN) return backtrack_info(INF);
				first_not_zero_idx = i;
			}
			accum += next_step[i];
		}
		dp_idx.push_back(next_step[i]);
	}

	if (dp.find(dp_idx) != dp.end())
	{
		return dp[dp_idx];
	}

	if (max_value == 0)
	{
		imin_frog = curr;
		return backtrack_info(0);
	}

	if (curr + max_value > 100) return backtrack_info(INF);
	if (curr + max_value >= imin_frog) return backtrack_info(INF);
	if (not_zero_cnt < 2) return backtrack_info(INF);
	if (not_zero_cnt == 2 && accum % 2 == 1) return backtrack_info(INF);

	backtrack_info min_ret = backtrack_info(INF);
	for (auto it1 = p_start_pos.begin(); it1 != p_start_pos.end() && curr + max_value < imin_frog; it1++)
	{
		int start = it1->second;
		for (auto it2 = p_start_pos.begin(); it2 != p_start_pos.end() && curr + max_value < imin_frog; it2++)
		{
			if (it1 == it2) continue;
			int step = it2->second - start;
			if (step >= start + 1 && step <= 6 && start + step < N)
			{
				backtrack_info ret = backtracking(curr + 1, start, step, next_step);
				ret.frog += 1;
				ret.result.push_back(make_pair(start, step));

				if (min_ret.frog > ret.frog)
				{
					imin_frog = min(imin_frog, curr + ret.frog);
					min_ret = ret;
				}
			}
		}
	}

	dp[dp_idx] = min_ret;
	return min_ret;
}

int main()
{
	scanf("%d", &N);
	halfN = N / 2;

	set<pair<int, int>> p_start_pos;
	int max_value = 0;
	for (int i = 0; i < N; i++)
	{
		scanf("%d", &step_list[i]);
		if (step_list[i] > 0)
		{
			p_start_pos.insert(make_pair(step_list[i], i));
			max_value = max(max_value, step_list[i]);
		}
	}

	backtrack_info min_frog = backtrack_info(INF);
	for (auto it1 = p_start_pos.begin(); it1 != p_start_pos.end() && max_value < min_frog.frog; it1++)
	{
		int start = it1->second;
		for (auto it2 = p_start_pos.begin(); it2 != p_start_pos.end() && max_value < min_frog.frog; it2++)
		{
			if (it1 == it2) continue;
			int step = it2->second - start;
			if (step >= start + 1 && step <= 6 && start + step < N)
			{
				backtrack_info ret = backtracking(1, start, step, step_list);
				ret.frog += 1;
				ret.result.push_back(make_pair(start, step));

				if (min_frog.frog > ret.frog)
				{
					min_frog = ret;
				}
			}
		}
	}

	printf("%d\n", min_frog.frog);
	for (int i = 0; i < min_frog.result.size(); i++)
	{
		printf("%d %d\n", min_frog.result[i].first + 1, min_frog.result[i].second);
	}

	return 0;
}

djm03178 5년 전 3

수많은 사람들이 시도했지만, 아직까지 맞은 사람은 두 명입니다.

그 두 분을 찾아가셔야 될 것 같네요.

foryou1006ll 5년 전 0

Slack을 찾아가봐야겠어요 ㅠㅠㅠ

doju 5년 전 0

문제를 푸신 것을 축하드립니다 :) 관련해서 대화를 나눠 보고 싶은데, 슬랙 DM 걸어 주시면 감사하겠습니다!

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

문제

문제

출처

ICPC

KOI 2004 지역 - 청개구리 시간초과 도와주세요!

foryou1006ll 5년 전 0

djm03178 5년 전 3

foryou1006ll 5년 전 0

doju 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말