codeforces Round #636 (Div. 3) (A, B, C) review

풀이방법

 

A : 1 + 2 + 4 + .. + 2^k-1의 축적합을 구해서 주어지는 수를 나눠주면 된다.

주의사항으로는 int의 범위값을 넘기때문에 담는 배열을 long long으로 만들어주면된다.

축적합은 30까지만 만들어주면 주어진 범위 넘으니 30까지만 만들어주자.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

long long aSum[31];

void ASumInit()
{
	for (int i = 1; i <= 30; i++)
		aSum[i] = aSum[i - 1] + pow(2, i-1);
}

void solve(const long long& num)
{
	long long divNum = 0;
	long long ans = 0;
	for (int i = 2; i <= 30; i++)
	{
		if (num % aSum[i] == 0)
		{
			divNum = aSum[i];
			break;
		}
	}
	if (divNum == 0)
		divNum = 1;

	ans = num / divNum;
	cout << ans << '\n';
}

int main()
{
	ASumInit();
	int testcase;
	long long num;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		cin >> num;
		solve(num);
	}
	return 0;
}

  

B : n%4 == 0이여야 조건중 하나인 배열의 1~n/2까지 누적합 *2 = 배열의 1~ n까지의 누적합이 성립한다.

이제 no는 문제가 없고 yes일때 list를 생각해면 나같은 경우에는

만약에 n == 4일때 2 4 /1 5, n == 8일때 2 4 8 10 / 1 5 7 11으로 만든다.

이제 자세히 보면 짝수는 (+2, +4)순으로 반복, 홀수는 (+4, +2)순으로 반복하게 만들어 출력했다.

#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int testcase;
	cin >> testcase;
	int n;
	for (int i = 0; i < testcase; i++)
	{
		cin >> n;
		if (n % 4 != 0)
			cout << "NO" << '\n';
		else
		{
			cout << "YES" << '\n';
			int even = 2;
			int odd = 1;
			cout << even << ' ';
			for (int i = 1; i <= n/2 - 1; i ++)
			{
				if (i % 2 == 0)
					cout << (even += 4) << ' ';
				else
					cout << (even += 2) << ' ';
			}
			cout << odd << ' ';
			for (int i = 1; i <= n / 2 -1; i++)
			{
				if (i % 2 == 0)
					cout << (odd += 2) << ' ';
				else
					cout << (odd += 4) << ' ';
			}
				
			cout << '\n';
		}
	}
	return 0;
}

 

C : 부호가 같을때와 다를때의 조건을 정해 구한다.

그냥 순회하면서 부호가 같을때는 MAX값을 갱신하고, 다를때는 ans에 추가해주면됨.

#include <iostream>
#include <algorithm>

#define INF 9876543210

using namespace std;
long long arr[200001];
int n;

bool IsSameSign(long long a, long long b)
{
	if (a > 0 && b > 0 || a < 0 && b < 0)
		return true;
	return false;
}

void Input()
{
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> arr[i];
}

void solve()
{
	long long ans = 0, maxValue;
	long long prev = maxValue = arr[0];
	for (int i = 1; i < n; i++)
	{
		//부호가 같을때
		if (IsSameSign(prev, arr[i])== true)
		{
			maxValue = max(maxValue, arr[i]);
		}
		//부호가 다를때
		else
		{
			ans += maxValue;
			maxValue = numeric_limits<long long>::min();
			maxValue = max(maxValue, arr[i]);
		}
		prev = arr[i];
	}
	ans += maxValue;
	cout << ans << '\n';
}

int main()
{
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++)
	{
		Input();
		solve();
	}
	return 0;
}

---

후기

풀고있는데 코드포스 사이트가 터졌다.. 거의 일주일에 한번 터지는듯..