[Codeforces] Codeforces Round #461 (Div. 2) 이야기

그냥 기억에 남던 문제가 있어 하나만 올려보고자 한다.

(A번은 핵당했고 C번은 못풀었고 사실 B번만 풀기도 했다.)

문제 출처 :

http://codeforces.com/contest/922/problem/B

알고리즘 분석 :

문제 해결에 필요한 사항

1. XOR 이해

이 문제는 a ^ b ^ c == 0을 만족하는 그러한 1 <= a <= b <= c <= n을 찾아라는 문제이다.

1. n제한이 2500이니 우선 3중 포문을 돌리면 O(2500*2500*2500)이므로 시간 초과가 나게 될 것이다.

따라서 이 문제는 3중 포문은 아니라는 뜻이 된다.

2. 그래서 두 집합을 먼저 XOR하고 나머지수와 XOR을 해보자는 생각을 하였다. 이렇게하면 O(2500*2500 + 2500)으로 줄일 수 있게 된다.

3. 이때 느낀것이 XOR성질이다. 두 수가 XOR이 되어 어떤 수 k가 됐을 때, k ^ c = 0이라면 k == c라는 의미가 된다.

(XOR에서 같은 수를 XOR하면 0이 되기 때문)

이 내용을 기반으로 문제를 풀었더니 AC를 받을 수 있었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

#include <iostream> #include <cstdio>   using namespace std;   int main() {     int n;     cin >> n;       int cnt = 0;     for (int a = 1; a <= n; a++)         for (int b = a; b <= n; b++)             if (a + b > (a ^ b) && (a ^ b) <= n && (a ^ b) >= b)                 cnt++;       cout << cnt;     return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus