코드포스 - 익숙해지는 중

codeforce round #805(div 3), #806(div 4) 업솔빙

Codeforces Round #805, #806 개요

+97점, -10점 했다.
그래도 긍정적인 부분은 이제 코포 유형이 뭔지 감이 잡히고 있다.
코포는 코포로 공부하는게 맞는것같다.
그래도 버추얼은 귀찮아서 안하지만 ㅋㅋㅋ
div 4는 다 풀어야하는데 정말 슬프다.. 빨리 더 수련을 해야겠다.
div 3, div 4 둘다 4솔했고 틀린 문제만 업솔빙 해보려고 한다.

805 E. Split into Two Sets

이때 당시 멀티셋에 빠져있던터라 멀티셋 썼는데 왜틀렸는지 당시에는 진짜 몰랐다.
끝나고 푼 사람들을 보니 싸이클이 있는지 확인해서 푼 사람들이 많았다.
에디토리얼은 맵을 이용했다.
맵을 이용한 풀이는 나랑 같았지만 여기서 추가적으로 결과적으론 사이클을 판별해야했다.
두 그룹으로 나눈다는게(Split into Two Sets) 그림으로 그려보면 고등학교 때 함수 개념 배울 때 사용하는 모양이 나오니까 Bipartite Graph(이분그래프)를 떠올리는 건 자연스럽다.

1. 같은 숫자가 주어지면 NO
2. map에 넣을 때 크기가 2가 넘어가면 NO
3. 홀수 사이클이 판별되면 NO

    cin >> n;
        for(int i=0;i<n;i++){
            int num; cin >> num;
            while (!(num&1)) num >>= 1;
            m1.insert(num); //m1은 multiset이다.
        }
        multiset<int> :: iterator iter;
        for(int i=0;i<n;i++){
            int num; cin >> num;
            iter = m1.find(num);
            while (iter==m1.end()&&num!=1){
                num >>=1;
                iter = m1.find(num);
            }
            if(iter!=m1.end()) m1.erase(iter);
        }
        if(m1.empty()) cout<<"YES\n";
        else cout << "NO\n";
           
        m1.clear();
    }
   

805 F. Equate Multisets

코포에 많이 나오는듯한 느낌의 문제였다.
관찰은 해봤지만 내가 생각한 방법에대한 시간복잡도 땜에 쫄아서 그런지 아무 생각이 안났다.
핵심은 »1 과 «1 밖에 안쓰니까 비트연산으로 접근해도 된다는 것이다.
그러면 같은 숫자가 될 수 있는 것은 비트연산에서 마지막 0들을 뗀 값일 것이다.
예를 들면, 3 = 11, 24 = 11000 이러면 3번 연산 필요하다는 것을 0세번 떼면서 알 수 있다. 그래서 첫번재 배열은 0들을 다 뗀 값을 넣어주고 두번쨰 배열을 입력받을 때 하나하나 쉬프트 연산 해주면서 있는 지없는지 확인한다.

805 G. Passable Paths

귀찮아서 생략!

806 D. Double string

< algorithm >에 있는 find함수가 그냥 무지성으로 왼쪽에서부터 검사하는지 몰랐다.
그냥 이럴줄 알았으면 멀티셋으로 끝내버리는건데…하..substr으로 문자열 잘 나눠서 푸는건 잘했지만…..
많이 배웠다.. 멀티셋으로 하면 문제점이 크기 순으로 정렬하니까 idx를 관리 할때 힘들다.
그래서 algorithm을 건드렸지만 잘모르고 건드리면 안된다는 걸 확실히 배웠다.

F. Yet Another Probelm About Pairs Satisfying an Indquality

이건 문제 이름이 왜케 긴건지 ㅋㅋㅋ 해석이 잘 안된다.
이분탐색의 직관은 잡을 수 있었는데 못풀었다. ㅎㅎ
이분탐색 문제들은 다 넘 어려웡 ㅠㅠ
arr[i]>i를 이용해서 arr[i] < i ,arr[j] < j 를 다 해결하는 것이 인상깊었다.

vector<int> arr;
int main(){
    fast_io;
    int test; cin >> test;
    while (test--) {
        int n; cin >> n;
        arr = vector<int> (n+1);
        for(int i=1;i<=n;i++) cin >> arr[i];
        vector<int> v;
        ll res =0;
        for(int i =1;i<=n;i++){
            if(arr[i]>=i) continue; //i, j 둘다 거름
            res += (ll)(lower_bound(v.begin(), v.end(), arr[i])-v.begin()); //arr[j]보다 작은 i의 개수 세기
            v.push_back(i);
        }
        cout << res << '\n';
    }
}

G. Good Key, Bad key

F같은 유형에서 도망가서 사실 G를 더 많이 봤다.
솔직히 그리디라는 걸 눈치채지 못했다.
Bad key가 이름만 들어도 좀 쓰면 안좋을 것 같은 기분이긴 했는데 ㅋㅋㅋ
나의 감각에 어느정도 기대도 될 것 같기도 했다.
결론은 Good Key를 앞에서 몰아서 쓰는게 이득이라는 것이다.
Bad key를 사용해야 하는 개수는 정해져 있고 good key를 앞에서 몰아서 쓰자는 것이다.

ll res=0, sum=0;    //sum은 goodkey를 앞에서 쓰는 것이다.
for(int i=0;i<=n;i++){
    ll now = sum;
    for(int j=i+1;j<=min(n, 32+i);j++){  //bad키를 쓰는 모든 경우를 check
        ll copy = arr[j];           //bad key를 32번 넘게 쓰면 10^9을 0으로 만들고 더 줄이는 꼴이라 의미가 없음
        copy >>= j-i;               // i=0 -> bad키를 n번씀, i=n -> bad키를 안씀
        now += copy;
    }
    res = max(res, now);
    if(i==n) continue;
    sum += arr[i+1]-k;
}
cout << res << '\n';