TopCoder SRM 569 Div1

2013. 02. 07.

250..맞긴 맞았는데 틀렸다고 생각하고 있어서 늦게 내고,

챌에 모든걸 건다! 하고 혼신의 챌을 했으나 -25.

그린 가야지 헤헤 드디어 마음에 안정이 찾아오네!

하면서 놀다가 보니까

내 솔루션이 맞았다!.. 나도 분명 틀릴거라고 생각했는데!

물론 그래도 레이팅은 떨어졌다..ㅜㅜ

..아 ㅋㅋ 아깝다.. 거의 다 간단하게, 빠르게 생각했었는데.

난 아무래도 생각을 정리하는 연습이 아직 덜 된것 같다.

250

길이가 같은 N (1 ~ 50) 개의 길이가 M(1 ~ 50)인 비트 스트링 (이진수 문자열) 이 주어진다.

그리고 어떤 기계에 이 문자열들 중 두 개를 골라서 모두 돌려볼 수 있고,

이 기계는 두 문자열의 각 비트 (0번째 비트, 1번째 비트, ... ) 에 대해

XOR, OR, AND 중 하나를 한 결과를 표시한다.

(그러니까, 0번째 비트는 XOR, 1번째 비트는 AND, 이럴 수 있다는 말)

이 기계가 각 비트 에 대해 무슨 연산을 하는지 확실히 알아내려면

몇 개의 비트 스트링이 더 필요한가?

일단 간단히 몇가지 경우를 생각해보자.

1. XOR 한 것과 OR 한 것을 구분하려면 어떤 조건이 필요할까?

─A. 두 비트가 모두 0일 경우.

──이 경우에는 이 위치의 비트가 1인 두 개의 문자열이 더 필요하다.

──왜냐면 0 xor 0 = 0, 0 xor 1 = 1, 0 or 0 = 0, 0 or 1 = 1로 한 개는 의미가 없지만

──1 xor 1 = 0, 1 or 1 = 0으로 두 개는 의미가 있기 때문이다.

─B. 두 비트가 다를 경우.

──이 경우, 이 위치의 비트가 1인 것이 하나만 더 있으면 된다.

──1 xor 1 = 0, 1 or 1 = 1이니까.

2. OR 한 것과 AND 한 것을 구분하려면 어떤 조건이 필요할까?

─A. 두 비트가 모두 0인 경우.

──이 경우, 이 위치의 비트가 1인 것이 하나만 있으면 된다(이유는 이제 생략).

─B. 두 비트가 모두 1 인 경우.

──이 경우, 이 위치의 비트가 0인 것이 하나만 있으면 된다.

3. XOR 한 것과 AND한 것을 구분하려면 어떤 조건이 필요할까?

─A. 두 비트가 모두 0인 경우.

──이 경우, 이 위치의 비트가 1인 것이 하나만 있으면 된다.

자 이제 구분하는 방법을 모두 살펴봤다.

이제 각 비트에 대해서, 모든 문자열의 쌍을 보면 된다! (시간 복잡도는 결국 O(N^3))

한 가지 경우만 살펴보자 (나머지는 다 이런식으로 똑같이 하면 되기에 생략!)

현재 보고있는 위치에서~

0인 비트가 두 개 이상 있으면 ?

XOR과 AND를 구분하기 위해서 이 자리가 1인게 하나 필요하다.

AND와 OR을 구분하기 위해서 이 자리가 1인게 하나 필요하다.

XOR과 OR을 구분하기 위해서 이 자리가 1인게 둘 필요하다.

그래서 이 중 최댓값인 2가 답의 후보가 된다.

(물론, 2는 답의 최댓값이므로 이대로 리턴해도 괜찮다)

(내가 생각을 정리하지 못해서 망한 부분이

바로 이 부분이다.. 아래 부분. 정말 간단한건데..)

500

1000