Codeforces Round #388 (Div. 2) - All Solved (Edited)

Codeforces Round #388 (Div. 2): http://codeforces.com/contest/749

A. Bachgold Problem

숫자 n이 주어지면 이걸 가장 많은 소수의 합으로 나타내는거다. (소수를 중복해서 사용 가능함)

n이 2이상이니까 그냥 2를 최대한 많이 쓰고 홀수인 경우 3을 써주면 되는 문제

#include <cstdio>
using namespace std;
int main() {
    int n;
    scanf("%d", &n);
    if(n%2==0) {
        printf("%d\n", n/2);
        int x=n/2;
        for(int i=0; i<x; i++) printf("2 ");
    } else if(n==3) {
        puts("1");
        puts("3");
    } else {
        int x=n-3;
        printf("%d\n", 1+x/2);
        int y=x/2;
        for(int i=0; i<y; i++) printf("2 ");
        printf("3");
    }
    return 0;
}
 

B. Parallelogram is Back

Parallelogram이 평행사변형이다.

좌표 3개 주어지면 평행사변형을 만들 수 있는 나머지 다른 좌표 1개를 출력하는 문제다.

가능한 모든 좌표를 전부 출력해주면 된다.

정확히 3개씩 뽑아낼 수 있지만, 그렇게 생각하는게 귀찮으니 그냥 set을 썼다.

근데 +,- 부호를 하나 거꾸로 써서 심지어 한번 틀리기까지 했다. ㅠㅠ

#include <cstdio>
#include <set>
#include <algorithm>
using namespace std;
set<pair<int,int> > s;
int main() {
    int a,b,c,d,e,f;
    scanf("%d%d%d%d%d%d",&a,&b,&c,&d,&e,&f);
    int x=c-a, y=d-b;
    s.insert(make_pair(e+x,f+y));
    s.insert(make_pair(e-x,f-y));
    x=e-a; y=f-b;
    s.insert(make_pair(c+x,d+y));
    s.insert(make_pair(c-x,d-y));
    x=e-c; y=f-d;
    s.insert(make_pair(a+x,b+y));
    s.insert(make_pair(a-x,b-y));
 
    printf("%lu\n", s.size());
    for(auto p: s) {
        printf("%d %d\n", p.first, p.second);
    }
    return 0;
}

C. Voting

아이고 또 sysfail이 떴다.

상대팀 맨 앞에 놈을 없애면 된다고 생각했는데, 그게 아니라 현재 나의 위치에서 나보다 뒤에있는 상대팀을 없애야 했던 거였다 ㅠ

시스템 채점에서 나가니까 바로 떠오르더라.. ㅠㅠ 아직 고치진 않았음.

내일 과제3번 채점만 다 하고 빨리 고쳐봐야지

아래 코드는 WA먹은 코드.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
queue<int> dq,rq;
char s[200001];
bool chk[200001];
int main() {
    int n;
    scanf("%d", &n);
    scanf("%s", s);
    for(int i=0; i<n; i++) {
        if(s[i]=='D') dq.push(i);
        else rq.push(i);
    }
 
    for(int i=0; !dq.empty() && !rq.empty(); i++) {
        if(i==n) i=0;
        if(chk[i]) continue;
        if(s[i]=='D') {
            chk[rq.front()]=true;
            rq.pop();
        } else {
            chk[dq.front()]=true;
            dq.pop();
        }
    }
    if(rq.size()>0) puts("R");
    else puts("D");
    return 0;
}

 

수정해서 AC 받음

sgc109님 코드를 참고했다. set 2개를 돌려쓰면서 뒤부터 검색하시던데, 나는 살짝 바꿔서 앞에서부터 검색했다.

그러니까 현재 보고 있는 값이 D이고 해당 인덱스가 x라면 R의 인덱스를 저장하고 있는 set에서 x보드 큰 인덱스가 있는지 lower_bound()로 찾고(사실 upper_bound()가 더 정확함) 없으면 0값으로 다시한번 lower_bound()를 돌렸음.

아래 코드가 AC받은 코드

#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set<int> s[2];
int cnt[2];
int idx(char x) {
    if(x=='D') return 0;
    else return 1;
}
bool chk[200001];
bool rm(int x, int opp) {
    s[opp].erase(x);
    chk[x]=true;
    return (--cnt[opp] == 0);
}
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    string str;
    int n; cin >>n>>str;
    for(int i=0; i<n; i++) {
        int x=idx(str[i]);
        s[x].insert(i);
        cnt[x]++;
    }
    while(cnt[0]!=0&&cnt[1]!=0) {
        for(int i=0; i<n; i++) {
            if(chk[i]) continue;
            int opp = idx(str[i])^1;
            auto it = s[opp].lower_bound(i);
            if(it == s[opp].end()) {
                if(cnt[opp]==0) break;
                else {
                    auto it = s[opp].lower_bound(0);
                    if(it == s[opp].end()) break;
                    else if(rm(*it,opp)) break;
                }
            } else if(rm(*it,opp)) break;
        }
    }
    if(cnt[0]) puts("D");
    else puts("R");
    return 0;
}

D. Leaving Auction

뜨벌.. 마지막 문구를 못읽어서 삽질 했다. (It's guaranteed that the sum of k over all question won't exceed 200 000.)

사람들 얘기들어보니 그냥 셋으로 하면 쉽게 풀린다는데,

나는 세그트리로 풀었다.

근데 8번에서 TLE가 난다. ㅠ

에휴...... 일단 query에서 모든 맥스를 갱신하는거 부터가 문제인듯 한데,

내일 smu님 코드보고 고쳐봐야겠다.

아래 코드는 WA먹은 코드.

#include <cstdio>
#include <vector>
#include <algorithm>
#include <cstring>
#include <set>
using namespace std;
#define r2 (r<<1)
#define m2 ((s+e)>>1)
vector<vector<int>> bid;
typedef pair<int,int> pii;
struct Seg{
    int s,e;
    vector<int> tree;
    Seg(int n):s(1) {
        for(e=0; (1<<e)<n; e++);
        tree.clear(); tree.resize((1<<(e+1)),0);
        e=n;
    }
    void init(int r, int s, int e) {
        if(s==e) {
            if(bid[s].size()==0) tree[r]=0;
            else tree[r]=bid[s].back();
        } else { init(r2,s,m2); init(r2+1,m2+1,e); }
    }
    pii query(int r, int s, int e, set<int>&amp; chk) {
        if(s==e) {
            if(chk.count(s)) return pii(0,0);
            else return pii(tree[r],s);
        } else {
            pii L=query(r2,s,m2,chk), R=query(r2+1,m2+1,e,chk);
            if(L.first>R.first) return L;
            else return R;
        }
    }
}

수정해서 AC 받음

오랫만에 다시풀면서 또 한참 고민했었는데, 블로그에 적어놓고도 또 문제를 제대로 안읽었다. ㅠㅠ

It's guaranteed that the sum of k over all question won't exceed 200 000.

아오.... ㅠㅠ

이거 놓치면 문제가 너무 어려워진다.

저거 때문에 그냥 set에 지우고 추가하는 짓을 계속 query마다 반복해도 상관이 없게 된다.

나는 각 사람마다 vector를 따로 둬서 bid를 전부 저장했고,

각 사람마다 bid의 max를 mx라는 set에 따로 저장했다.

그래서 query가 들어오면 해당하는 사람의 max bid값을 mx에서 찾아서 지워버리고

첫번째로 큰 max bid값을 갖는 사람의 vector에서 두번째로 큰 max bid값을 찾도록

lower_bound(정확히는 upper_bound)를 돌렸다.

그리고 query로 들어온 사람에 해당되는 max bid값들을 다시 mx set에 추가해줬다.

코드는 아래와 같다.

#include <cstdio>
#include <vector>
#include <set>
#include <algorithm>
#include <queue>
using namespace std;
typedef pair<int,int> pii;
vector<int> v[200001];
set<pii> mx;
queue<int> q;
int main() {
    int n,a,b;
    scanf("%d", &n);
    v[0].push_back(0);
    int mxpno=0;
    for(int i=1; i<=n; i++) {
        scanf("%d %d", &a, &b);
        v[a].push_back(b);
        mxpno=max(a,mxpno);
    }
    for(int i=1; i<=mxpno; i++) {
        if(v[i].empty()) continue;
        mx.insert({v[i].back(),i});
    }
    int Q; scanf("%d", &Q);
    for(int i=0; i<Q; i++) {
        int k; scanf("%d", &k);
        for(int j=0; j<k; j++) {
            int l; scanf("%d", &l);
            if(v[l].empty()) continue;
            q.push(l);
            mx.erase({v[l].back(),l});
        }
        if(mx.empty()) puts("0 0");
        else {
            auto it = mx.end();
            if(--it == mx.begin()) {
                printf("%d %d\n",it->second,v[it->second][0]);
            } else {
                int x = it--->second;
                auto jt = lower_bound(v[x].begin(),v[x].end(),v[it->second].back());
                printf("%d %d\n", x, *jt);
            }
 
        }
        while(!q.empty()) {
            int x=q.front(); q.pop();
            mx.insert({v[x].back(),x});
        }
    }
    return 0;
}

이 문제의 핵심은 max값만 따로 추려서 set에 저장하는게 아닌가 싶다.

(+ 문제 잘 읽는거랑.. ㅠㅠ)

E. Inversions After Shuffle

http://codeforces.com/contest/749/problem/E

역시 이 문제는 뭔지도 모른다. 보지도 못함. ㅋ

와아ㅏㅏㅏㅏ 다시 풀었다~! 아래는 AC받은 코드

와 내겐 너무 어려웠던 문제였다.

결론부터 말하자면, 확률식을 세우고.. 그걸 시간안에 구하려면 펜윅을 적용했어야 하는 문제였다.

제대로 집중안하고 집에서 뒹굴거리다가 여기저기서 풀이 설명 보고 짜집기하고.... 나중에는 도주님 설명을 듣고나서야 겨우 풀 수 있었다. ㅠㅠ

먼저 문제 설명부터..ㅎㅎ

난 영알못이라 문제 이해하는데도 한참 걸렸다.

3
2 3 1

이 예제의 답이 왜

1.916666666666666666666666666667

인지 알아보자.

문제에서 inversion은 두 숫자의 순서가 거꾸로 되어있는 경우를 의미한다.

그래서 2 3 1 이라는 수열이 있을 때 모든 순서쌍에 대한 inversion의 개수는 2개이다. (왜냐하면 (2,3)=>0, (2,1)=>1, (3,1)=>1 이므로)

그럼 여기서 순열(permuation)을 선택하자.

순열을 선택할 확률은 모두 같다고 한다.

즉, 존재하는 순열은 [2], [3], [1], [2 3], [3 1], [2 3 1] 총 6가지이다. ( 에서 n이 3이므로 6이다.)

그럼 이렇게 순열을 택한 다음에 그 순열이 뒤집어지는 경우를 모두 생각해야한다.

예를 들어 2를 선택한 경우 두 숫자의 순서가 뒤바뀔 확률같은건 당연히 없다. (숫자 하나만 가지고는 inversion 수를 늘리거나 줄일 수 없으므로)

그럼 [2 3]을 선택한 경우 이를 바꾸는 방법은 [3 2]가 있다.

여기서 [3 2]로 바꾸면 전체 수열이 3 2 1이 되고 여기서 inversion의 수는 3개가 된다.

즉, [1,n]에서 [l, r]부분의 원래 inversion 수를 빼고 [l, r]부분으로 만들 수 있는 inversion수 를 더하면 될 것이다.

식으로는 다음과 같이 표현할 수 있다.

 참고로 여기서  

그럼 여기서 부분만 구하면 답을 구할 수 있다. (나머지는 다 상수이므로)

그런데, 나는 위와 같은 방법으로 풀지 않았다. 이 설명은 문제를 쉽게 이해하기 위해서 썼다.

에디토리얼도 이 방법으로 설명하고 있으나, 나는 이 방법으로 하루종일 헤매다 도주님이 설명해준 방법으로 풀었다.

헤맨 이유는 저 식에서 이 부분을 에 Fenwick Tree로 처리하는 부분이 전혀 이해가 가지 않아서 그랬다.

물론 지금 다 이해한 시점에선 이 방법으로 풀 수도 있으나 도주님이 소개한 방법이 더 효과적인것 같다. (다만, 도주님이 알려준 방법은 콘테때 안 떠오를 것 같지만... ㅠ)

아무튼 누구 방법이 됐던 간에 코포 에디토리얼 밑에 (영어로) 댓글이 전부 세세하게 달려있다.

=== 풀이 ===

답을 바로 적어봤다.

딱 보면 수식이 너무 많아서 읽기 싫을 수도 있지만, 잘 읽어보면 별거 없다.

는 을 만족하는 (x,y)쌍을 골랐을 때 두 숫자의 순서가 뒤바뀔 확률이라 하자.

여기서 v[x]<v[y]인 경우 inversion은 1만큼 증가할 수 있다.

반대로 v[x]>v[y]인 경우 inversion은 1만큼 감소할 수 있다.

따라서 x<y이면서 v[x]<v[y]인 경우 을 더해주고,

x<y이면서 v[x]>v[y]인 경우 을 더해주면 된다.

그럼 여기서 를 구해보자.

에서 (x,y)를 고르는 방법은 [1,x]에서 1개를 고르고 [y,n]에서 1개를 고르는 것이다.

물론 고르는 순서는 상관이 없으므로 를 곱해줘야 한다.

그럼 [1,x]는 개이고 [y,n]은 개인데, 전체 세그먼트를 선택하는 방법은 이므로  이다.

즉, 이다.

그럼 이제 를 구하는게 문제다 ㅠㅠ (물론 원래 inversion값도 구해야겠지)

이걸 무식하게 하면 이 2개니까 만큼 걸리는데, 펜윅을 사용해서 에 해결할 수 있다. ㄷㄷ

를 고정했다면 에서 만 구하면 되는 것을 알 수 있다. 값을 제외하면 모든 식이 상수로 처리되기 때문이다.

는 x<y이면서 v[x]<v[y]를 만족하는 x들의 합이다.

이 값은 v[i]가 큰 순서대로 인덱스인 i값을 펜윅트리에 쑤셔넣을 때 prefix sum값이다. (와우~ 이게 핵심임~!)

사실 펜윅 트리를 제대로 배웠다면, 이런 곳에서 가장 많이 쓰이는 것을 쉽게 알 수 있을텐데..

나는 구간합 구하는 거 정도로만 배웠기 때문에 (날로 배웠기 때문에) 이거 이해하는데 꽤나 걸렸다 ㅠㅠ

펙윅트리 부분이 잘 이해가 안된다면 코드를 보시라~ 이해가 팍팍 됨.

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int v[100001],n;
double seg[100001],ans;
void add(int at, int by) { for(int i=at; i<=n; i+=i&-i) seg[i]+=by; }
double sum(int at) {
    double ret=0.0;
    for(int i=at; i>=1; i-=i&-i) ret+=seg[i];
    return ret;
}
int main() {
    scanf("%d", &n);
    for(int i=1; i<=n; i++) {
        int x; scanf("%d", &x);
        v[x]=i;
    }
 
    for(int i=n; i>=1; i--) {
        ans += sum(v[i]);
        add(v[i],1);
    }
 
    memset(seg,0,sizeof(seg));
    for(int i=1; i<=n; i++) {
        ans += sum(v[i])*(n-v[i]+1)/n/(n+1);
        add(v[i],v[i]);
    }
 
    memset(seg,0,sizeof(seg));
    for(int i=n; i>=1; i--) {
        ans -= sum(v[i])*(n-v[i]+1)/n/(n+1);
        add(v[i],v[i]);
    }
 
    printf("%.9lf", ans);
    return 0;
}

한가지 주의할 점은 위에서 선언한 seg 배열을 int로 선언하면 16번 테케에서 계속 틀릴 수 밖에 없다.

fenwick tree이므로 배열 하나에 최대 까지 들어갈 수 있기 때문이다. (int 범위 초과~)

그러니까 double이나 long long으로 선언해야 한다.

또 이 100억을 넘어갈 수 있으므로 주의해야 한다.

도주님이 이런 비슷한문제로 BOJ에 있는 굉장한 학생 문제를 추천해주셨다.

이전에도 세그의 완성은 굉장한 학생을 푼 사람과 안 푼사람으로 나뉜다는 얘기를 슬렉에서 언뜻 들었던거 같은데 ㅋ

빨리 풀어봐야겠다

와.. 근데 이거 정리하는데 시간이.. 너무 오래걸렸다 ㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠㅠ

# 최종 스코어 #

개 똥망.

내가 친구로 등록한 사람들 중에서도 제일 못봤다.

거기다가 오늘 sgc님은 드디어 블루를 달았다.

아ㅏㅏㅏㅏㅏㅏㅏㅏ 나도 블루달고파 ㅠㅜ

올해 끝나기전에 cyan으로라도 마무리를 짓고 싶다. 

All SOLVED