[코드포스 Practice21] D. Anu Has a Function

이걸 어떻게 하지????

어떻게??? 하지???

 

고민하다가 손도 못 댈까봐 힌트 받았다.

 

이거 보면 a|b - b라 하면 a, b 전부 1로 만들고 b인 부분은 다시 0으로 바꾼다.

 

a, b, c, d 연속으로 하면 a | b | c - b | c | d 와 같으니 a가 최댓값이 되고 b가 최솟값이 되면 되겠다 싶었음.

 

그리고 중간의 b, c 값은 더하고 빼니 어떤 값이든 상관 없을 것 같았다.

 

최댓값과 최솟값은 1의 개수를 구해서 1의 개수가 많은 걸 최대값 1의 개수가 작은 걸 최솟값으로 설정했음

 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
bool sortbyfirst(const pair<int,int> &a, const pair<int,int> &b) 
{ 
    return (a.second > b.second); 
}
 
int count_one(int n)
{
    int count = 0;
 
    for (i64 i = 1; i <= n; i *= 2)
    {
        int res =  n & i;
        if (res == i)
          count++;
    }
 
    return count;
}
 
 
int main() {
    int n;
    scanf("%d", &n);
    
    vector<ii> v(n);
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &v[i].first);
        v[i].second = count_one(v[i].first);
    }
 
    sort(v.begin(), v.end(), sortbyfirst);
 
    for (int i = 0; i < n; i++)
    {
        printf("%d ", v[i].first);
    }
    
    // i64 a = 0;
    // i64 b = 0;
    // for (int i = 0; i < n - 1; i++)
    //     a = a | v[i].first;
        
    // for (int i = 1; i < n; i++)
    //     b = b | v[i].first;
    
    // printf("%lld", a - b);
    
    return 0;
}

그와중에 문제 이해 잘못해서 다시 주석 처리함,,, ㅎㅎ

 

그냥 1의 개수 구한 다음 1의 개수 순서대로 정렬한다음 출력했다.

 

틀림 ㅂㄷㅂㄷ

 

이 문제에서 틀려서 왜 틀렸는지 확인해봤다

 

 

이진수 세다가 눈알 빠지는 줄

 

이진수 대충 만들거라 저거 뒤집어서 생각해야 한다.

 

암튼 결과 비교해보니 내가 만든 게 최댓값이 아니었다.

 

내가 실수한 부분이 두 가지가 있는데 하나는 1의 개수가 많다고 무조건 최대값이 아니고

 

a | b | c - b | c | d

 

두 번째는 이렇게 구하는 게 아니고 a | b | c | d - b | c | d 가 되어야 한다.

 

 

이 다음 생각이 든 게 그냥 하나하나 다 비교해보면 되지 않을까 싶었다. 

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main()
{
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n);
    i64 sum = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &v[i]);
        sum |= v[i];
    }
 
    i64 max = 0;
    i64 max_idx = 0;
    for (int i = 0; i < n; i++)
    {
        if (sum - (sum - v[i]) > max)
        {
            max = sum - (sum - v[i]);
            max_idx = i;
        }
    }
 
    printf("%d ", v[max_idx]);
    for (int i = 0; i < n; i++)
    {
        if (i != max_idx)
            printf("%d ", v[i]);
    }
    
    return 0;
}

 

내 생각에는 코드를 잘못짠듯

 

여기서 틀렸는데 나중에 생각해봐야지

---

앗 이 부분이 문제였다

 

형광펜 칠한 부분이 b|c|d|e 가 된다고 생각했는데 이거 그냥 빼는거라 값이 다름,,

 

그렇다고 for문으로 돌려버리면 n^2이 되어 버리고..

 

힌트 얻어서 부분합! 쓰면 된다는 걸 알았다.

 

 

신기해!

 

앞뒤 부분합!

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <functional>
#include <string>
#include <queue>
#include <stack>
#include <set>
#include <map>
#define xx first
#define yy second
 
using namespace std;
using i64 = long long;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;
 
int main()
{
    int n;
    scanf("%d", &n);
    
    vector<i64> v(n);
    i64 all = 0;
    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &v[i]);
        all |= v[i];
    }
 
    vector<i64> left(n, 0);
    for (int i = 1; i < n; i++)
        left[i] = left[i-1] | v[i-1];

    vector<i64> right(n, 0);
    for (int i = n-1; i > 0; i--)
        right[i-1] = right[i] | v[i];
 
    int max_idx = 0;
    i64 max = all - (left[0] | right[0]);
    for (int i = 1; i < n; i++)
    {
        if (all - (left[i] | right[i]) > max)
        {
            max = all - (left[i] | right[i]);
            max_idx = i;
        }
    }

    printf("%d ", v[max_idx]);
    for (int i = 0; i < n; i++)
    {
        if (i != max_idx)
            printf("%d ", v[i]);
    }
    
    return 0;
}

 

---

이건 북님 코드

 

#include <stdio.h>
#include <vector>
#include <queue>
#include <algorithm>
#include <iostream>
#include <string>
#include <bitset>
#include <map>
#include <set>
#include <tuple>
#include <string.h>
#include <math.h>
#include <random>
#include <functional>
#include <assert.h>
#include <math.h>
#define all(x) (x).begin(), (x).end()
#define xx first
#define yy second
#define MOD ((i64)1e10)

using namespace std;

template<typename T, typename Pr = less<T>>
using pq = priority_queue<T, vector<T>, Pr>;
using i64 = long long int;
using ii = pair<int, int>;
using ii64 = pair<i64, i64>;

int main()
{
    int n;
    scanf("%d", &n);

    vector<int> arr(n+2);

    for (int i = 1; i <= n; i++)
        scanf("%d", &arr[i]);
    
    vector<int> fromL(n+2), fromR(n+2);

    for (int i = 1; i <= n; i++)
        fromL[i] = fromL[i-1] | arr[i];

    for (int i = n; i >= 1; i--)
        fromR[i] = fromR[i+1] | arr[i];

    int total = fromL[n];
    int maxIdx = 1;

    for (int i = 2; i <= n; i++)
    {
        int maxv = total - (fromL[maxIdx -1] | fromR[maxIdx + 1]);
        int now = total - (fromL[i-1] | fromR[i+1]);

        if (now > maxv)
            maxIdx = i;
    }

    swap(arr[maxIdx], arr[1]);

    for (int i = 1; i <= n; i++)
        printf("%d ", arr[i]);

    return 0;
}

 

---

 

x|y = x + y - (x&y) 

 

이 문제에서 이 공식을 사용해서 문제를 풀었다.

 

---

 

관련된 문제 

 

https://codeforces.com/contest/1368/problem/D

Problem - D - Codeforces

 

처음에 어떻게 풀 지 몰라서 힌트 받아서 풀었음ㅋㅋ x|y = x + y - (x&y) 공식을 사용하면 전체의 합이 일정하다는 걸 알 수 있다. 전체 합이 일정할 경우 숫자를 최대한 몰아줘야 제곱의 합이 최대가 된다.

 

 

풀이 방법은 먼저 각 자리수 별 비트 개수를 세고 → 비트 최대치를 사용해서 큰 수를 만든다음 → 제곱해서 답에 더해준다.

 

어제 비트마스크를 사용하는 문제를 풀어서 비트 연산이 어렵지 않았다ㅋㅋ 배운 걸 써먹으니 뿌듯하네