[Codeforces] Round #664 (Div.2)

문제 바로가기 : https://codeforces.com/contest/1395
문제 설명은 위 링크에서 확인해주시길 바랍니다.

A Solution

팰린드롬(대칭인 문자열)을 만들 수 있는지 판별하는 문제. 각 문자가 홀수인지 짝수인지 판별할 필요가 있다.
모두 짝수라면 당연히 팰린드롬을 만들 수 있고 홀수가 있다면 단 한개의 문자만 홀수여야 한다.
그래야 홀수인 문자열에서 1개를 빼서 가운데에 넣고 모두 대칭으로 나열할 수 있게 된다.

하지만 위 경우에 해당되지 않는 경우 r, g, b가 모두 한 개 이상이면 w를 증가시키는 연산을 할 수 있다.
나같은 경우 r, g, b를 1개씩 빼고 w를 3 증가시켜야 한다고 이해해서 그렇게 했는데 editorial에서는 1만 증가시키더라.
어차피 홀수를 증가시키는 거라서 때문에 결과에는 변함이 없다!

B Solution

일단 가로세로 범위가 적어서 직접 움직이면서 위치를 찍어도 문제없겠다고 생각했다.
수학적인 풀이가 굉장히 많던데.. 생각도 못했을 뿐더러 이해가 잘 가지 않았다. 갈 길이 멀다ㅡㅜ
내 풀이는 별거 없다. 현재 위치 (y, x)를 기준으로 위아래로 움직여서 탐색한다.
그럼 오른쪽으로 가서 처음 가는 곳이면 또 위아래 탐색. m열까지 반복. 그리고 왼쪽으로 가서 반복.
상당히 조잡해 보인다 엉엉

C Solution

비트 연산자를 자주 사용하지 않아서 꽤 혼란스러웠다.
a&b를 해서 c를 구하고 그렇게 구한 c들을 OR 연산을 해서 최솟값이 나오도록 하라고 써있다.
최솟값을 구하든 최댓값을 구하든 상관없다. 주어진 범위가 그렇게 크지 않다. (1<= n ,m <=100)
하나의 a_i에 대해 모든 b_j를 연산해서 첫 c_i을 만들어주고, 이를 bit에 적어준다. (i==1)

그 이후(else)에는 갱신된 m개의 c_1를 가지고 c_1|c_2를 해줘야 한다. 물론 c_2도 m개다.
위의 방법을 수행하되 이전에 갱신된 bit에서만 c_1|c_2를 해주자.
이전에 기록된 c_1는 OR 연산에 사용되고 새로운 값이 갱신되므로 지워져야 한다.

vector<int> now;
for (int A = 0; A < 512; A++) {
	if (bit[A]) {
		for (int j = 0; j < m; j++)
			now.push_back(A | tmp[j]);
	}
}
memset(bit, false, sizeof(bit));
for (int j = 0; j < now.size(); j++)
	bit[now[j]] = true;

c_1|c_2| … |c_n 이 최소가 되려면 최대 비트인 512-1(2^9-1)까지 탐색하면서
제일 먼저 true로 발견되는 위치를 반환하면 된다.

D번은 그리디로 어떻게 풀 수 있을줄 알았는데 계속 WA가 나와서 쓰지 못했다😂