[Codeforces] Round 862 Div.2 후기

대회링크 : https://codeforces.com/contest/1805

 

 

A. We Need the Zero

문제 : 배열 원소를 특정 x로 xor한 원소들의 xor 값을 0으로 만드는 x값 출력 

 

조건 : x의 범위는 0~255, 만족하는 x가 없을 경우 -1 출력

 

해결방법 1 : 0~255까지 x를 대입하며 만족하는 x 값을 찾는다.

 

해결방법 2 : xor의 교환법칙이 성립함을 이용한다.

 

배열의 원소 개수 - 짝수

해당 경우에는 x는 최종결과에 영향을 미치지 못하게 된다

(같은 x를 짝수 번 xor 한 경우 0이 나오기 때문)

(x⊕x = 0)

즉, 짝수인 경우에는 주어진 배열의 xor 연산 결과가 0일 경우에만 성립한다.

(a⊕x)⊕(b⊕x)⊕(c⊕x)⊕(d⊕x)

= a⊕b⊕c⊕d⊕x⊕x⊕x⊕x

= a⊕b⊕c⊕d

 

배열의 원소 개수 - 홀수

해당 경우에는 x는 주어진 배열의 xor한 값에 x를 xor한 값과 같게 된다.

즉, x 는 주어진 배열의 xor 한 값이 되게 된다.

(a⊕x)⊕(b⊕x)⊕(c⊕x)

= a⊕b⊕c⊕d⊕x⊕x⊕x

= a⊕b⊕c⊕x

 

B. The String Has a Target

문제 : 주어진 문자열에서 두 문자를 한 번만 바꾸어 사전순으로 가장 앞에 오는 단어 출력

 

조건 : 두 문자가 같아도 된다.

 

주어진 문자열의 앞 부분 부터 탐색하며 사전순으로 가장 앞서는 문자의 위치를 기록한다.

이때 사전순으로 앞서는 단어가 여러 개 있을 경우 가장 뒤에 있는 문자의 위치를 기록한다.

 

마지막으로 기록된 위치의 문자를 출력하고

문자열을 다 돌면서 기록된 위치를 제외한 문자열을 출력하면 된다.

 

 

C. Place for a Selfie

문제 : 이차방정식이 주어진 일차방정식에 근을 갖지 않는 경우 판단

 

조건1 : 일차방정식은 원점을 지난다 (y=kx)

조건2 : 이차방정식은 항상 아래로 볼록하다 (a>0)

 

y = ax^2 + bx + c

y = kx

두 그래프가 근을 갖지 않으려면 판별식(D)에 의해 (b-k)^2 - 4ac < 0 이어야 한다.

이때 (b-k)^2은 항상 양수이기 때문에 (b-k)의 절댓값이 가장 작을 때 성립할 가능성이 높아진다.

따라서 b-k의 절대값이 가장 작은 경우를 구해 판별했을 때 음수가 나오면 근이 없음을 증명할 수 있다.

 

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
 
	int iT;
	cin >> iT;
	while (iT--)
	{
		int iN, iM;
		cin >> iN >> iM;
		vector<long long> vecSlope(iN);
		for (int i = 0; i < iN; ++i) cin >> vecSlope[i];
 
		sort(vecSlope.begin(), vecSlope.end());
 
		while (iM--)
		{
			long long lA, lB, lC;
			cin >> lA >> lB >> lC;
 
			int iLeft = 0;
			int iRight = iN - 1;
 
			long long lMulti = abs(lB - vecSlope[0]);
			long long lAns = vecSlope[0];
			while (iLeft <= iRight)
			{
				int iMid = (iLeft + iRight) / 2;
				if (lB >= vecSlope[iMid])
				{
					iLeft = iMid + 1;
				}
				else
				{
					iRight = iMid - 1;
				}
				if (lMulti > abs(lB - vecSlope[iMid]))
				{
					lMulti = abs(lB - vecSlope[iMid]);
					lAns = vecSlope[iMid];
				}
			}
			if (lMulti * lMulti - 4 * lA * lC < 0)
			{
				cout << "YES\n";
				cout << lAns << "\n";
			}
			else
			{
				cout << "NO\n";
			}
		}
	}
	return 0;
}

 

D, E.

 

F. Survival of the Weakest (easy version)

문제 : F(F(F(A)))... 즉 F를 A의 길이의 n-1번 반복했을 때 나오는 수 출력

 

조건1 : n은 2~3000 (easy version)

조건2 : 배열의 원소는 0~10억

 

F는 A의 두 서로 다른 원소의 합으로 나올 수 있는 수들 중에서 A의 개수보다 1개 적은 개수를 뽑는 함수

F(1, 2, 5, 7) =>  (1+2, 1+6, 2+5, ... ) => (3, 6, 7) 

 

원소의 개수를 모두 보며 최소 값을 계산하는 건 시간적 낭비가 매우 크다

즉 작아지는 순에서 커지는 순으로 잘라서 보면 연산 횟수가 매우 줄어든다.

 

i는 0번째 j는 i+1번째부터 시작하며 원소를 순회한다.

우선순위큐(내림차순)를 이용하여 i와 j번째 원소 합을 넣어주고

우선순위큐의 크기가 n-1보다 클 경우 원소 하나를 꺼내준다.

i를 증가시킬 때 우선순위큐에 가장 위에 있는 값보다 i번째와 i+1번째의 합이 클 경우에는

더 이상 우선순위큐에 들어갈 조건이 성립이 되지 않는다.

 

위에서 구한 값을 이용해 배열을 다시 재배치해준다.

A를 F함수를 통하여 F(A)를 구했다.

이때 배열의 원소가 모두 컸다고 가정하면 배열의 최댓값은 최대 2배씩 확장되게 된다.

long long 범위를 사용한다고 해도 10억 * 2^2999 는 감당할 수 가없다.

그래서 배열 재배치 후 첫 번째 원소의 값을 mod로 나눴을 때 나오는 정수만큼

배열의 모든 값을 빼서 F(A)를 계산해 준다.

 

 

6번의 배치를 끝내고 다행히 블루에 도달할 수 있었다.

 

부족한 점을 보완해서 더 나은 코드를 짤 수 있게 노력해야겠다.