Facebook Hacker Cup 2017 Round 1

Facebook Hacker Cup 2017 Round 1

https://www.facebook.com/hackercup/round/1825579961046099/

A. Pie Progress (10 points)

저번 문제 이름이랑 완전 똑같은 줄 알았는데, 지금 와서 확인해보니 앞뒤로만 바뀐 형태였다. ㅋㅋ

문제는 엄청 쉬운데, 내가 DP에서 뻘짓해서 시간안에 답이 나오질 않았다.

inf(무한대)로 초기화 하고 if(ret!=inf) return ret; 형태로만 쓴 다음에 뒤에 별다른 처리를 안해줬더니,

그 밑의 코드에서 ret값이 바뀌질 않으면 ret에 inf가 남아있어서 계속 연산하는 꼴이 되어버렸다. ㅠㅠㅠㅠㅠㅠ

6분 시간 다 지나고 나서야 발견함 ㅠㅠㅠㅠㅠ

수정한 코드를 올린다.

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll d[310][310], psum[310][310];
int v[310][310];
const ll inf = 0x3f3f3f3f3f3f3f3fULL;
int m;
ll f(int n, int r) {
    if(r<0) return inf;
    ll &ret = d[n][r];
    if(ret>=0) return ret;
    else ret=inf;
    if(n==0) return ret=(r==0)?0:inf;
    else if(r==0) return ret=0ll;
    int mn = min(m,r);
    for(int p=mn; p>=0; p--) {
        ret = min(ret, f(n-1,r-p)+psum[n][p]+p*p);
    }
    return ret;
}
int main() {
    freopen("./a_input.txt","r",stdin);
    freopen("./a_output.txt","w",stdout);
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        memset(d,-1,sizeof(d));
        memset(psum,0,sizeof(psum));
        memset(v,0,sizeof(v));
        int n; scanf("%d%d",&n,&m);
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=m; j++) {
                scanf("%d",&v[i][j]);
            }
            sort(v[i]+1,v[i]+m+1);
            for(int j=1; j<=m; j++) {
                psum[i][j]=psum[i][j-1]+v[i][j];
            }
 
        }
        printf("Case #%d: %lld\n", z,f(n,n));
    }
    return 0;
}
 

B. Fighting the Zombies (25 points)

저번이랑 문제 이름이 완전 똑같이 나왔다.

뭔가 제대로 이해하고 풀었다고 생각했는데,

제출하고 나서보니 틀렸음을 직감했다.

왜 틀렸는지는 안적겠음... 쪽팔림... 궁금하면 코드 들여다보세요 (WA받은거임)

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
typedef pair<int,int> pii;
vector<pii> co,cox,coy,bco,board;
int getcnt(int sx, int sy, int ex, int ey) {
    if(ex<sx||ey<sy) return 0;
 
    int cnt=0;
    auto s = lower_bound(cox.begin(), cox.end(), pii(sx,0));
    auto e = lower_bound(cox.begin(), cox.end(), pii(ex+1,0));
    for(auto it=s; it!=e; it++) {
        int y=co[it->second].second;
        if(sy<=y && y<=ey) cnt++;
    }
    return cnt;
}
int main() {
    freopen("b_input.txt", "r", stdin);
    freopen("b_output.txt", "w", stdout);
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        co.clear();
        cox.clear();
        coy.clear();
        board.clear();
        bco.clear();
 
        int n,r;
        scanf("%d%d",&n,&r);
        for(int i=0; i<n; i++) {
            int x,y; scanf("%d%d",&x,&y);
            co.push_back({x,y});
            cox.push_back({x,i});
            coy.push_back({y,i});
        }
        sort(cox.begin(), cox.end());
        int idx=0, mx=0;
        for(auto &cx: cox) {
            for(auto &cy: coy) {
                int bx=cx.first, by=cy.first;
                int cnt=getcnt(bx,by,bx+r,by+r);
                mx = max(mx,cnt);
                board.push_back({cnt,idx++});
                bco.push_back({bx,by});
            }
        }
        for(int i=0; i<board.size(); i++) {
            int bxi=bco[board[i].second].first, byi=bco[board[i].second].second;
            for(int j=0; j<board.size(); j++) {
                if(i==j) continue;
                int bxj=bco[board[j].second].first, byj=bco[board[j].second].second;
                mx = max(mx,board[i].first+board[j].first-getcnt(bxj,byj,bxi+r,byi+r));
            }
        }
        printf("Case #%d: %d\n",z,mx);
    }
    return 0;
}

C. Manic Moving (25 points)

이것마저 틀렸으면 너무 우울할 뻔 ㅠ

A번과 같이 아주 쉬운 문제였다.

사실 대부분 사람들이 실수를 안했다면, 아마 A,C로 Round1을 통과하는 사람들이 많았을거라 생각한다.

그러고 보니 이 문제도 DP였군.

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
#include <cassert>
using namespace std;
int dist[102][102], d[5002][2][3], s[5002], e[5002], K;
const int inf = 0x3f3f3f3f;
int f(int k, int x, int r) {
    if(k<=0||k>K) return inf;
    int &ret = d[k][x][r];
    if(ret>=0) return ret;
    if(k==1&&x==0) return ret=dist[1][s[1]];
    else ret=inf;
 
    if(r==2) {
        ret = min(f(k,0,1)+dist[s[k]][e[k]], f(k-1,1,1)+dist[e[k-1]][e[k]]);
    } else if(r==1) {
        if(x==1) {
            if(k!=K) ret=f(k+1,0,0)+dist[s[k+1]][e[k]];
        } else ret=f(k-1,1,2)+dist[e[k-1]][s[k]];
    } else {
        ret = f(k-1,0,1)+dist[s[k-1]][s[k]];
        if(k!=1) ret = min(ret, f(k-2,1,1)+dist[e[k-2]][s[k]]);
    }
    if(ret>=inf) ret=inf;
    return ret;
}
int main() {
    freopen("./c_input.txt", "r", stdin);
    freopen("./c_output.txt", "w", stdout);
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        memset(dist,0x3f,sizeof(dist));
        memset(d,-1,sizeof(d));
        memset(s,0,sizeof(s));
        memset(e,0,sizeof(e));
 
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        K=k;
        for(int i=0; i<=n; i++) dist[i][i]=0;
        for(int i=0; i<m; i++) {
            int x,y,g;
            scanf("%d%d%d",&x,&y,&g);
            dist[y][x]=dist[x][y]=min(dist[x][y],g);
        }
 
        for(int k=1; k<=n; k++) {
            for(int i=1; i<=n; i++) {
                if(i==k) continue;
                for(int j=1; j<=n; j++) {
                    if(i==j||j==k) continue;
                    dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j]);
                }
            }
        }
 
        for(int i=1; i<=k; i++) scanf("%d%d",&s[i],&e[i]);
 
        int ans = f(k,1,2);
        if(ans>=inf) ans=-1;
        printf("Case #%d: %d\n",z,ans);
    }
    return 0;
}

보다시피 플로이드 써서 dist를 N^3에 구해준 다음 dp써서 해결했다.

d[k][x][r]: k번째 이사를 도와주고 있는데, 현재 x(x는 0또는 1을 갖는다. 0이면 출발지점, 1이면 도착지점)에 있고, r만큼 더 들 수 있는 용량이 있을 때, gas 최소 값.

D. Beach Umbrellas (40 points)

아놔 이게 너무 아깝다 ㅠㅠ

진짜 거의 다했는데..

심지어 오늘 코포도 제끼고 남은 한시간 열심히 코딩했는데 ㅠㅠ

fermat little theorem 부분이 약해서 망했다.

물론 이게 정해일리는 없다고 생각되지만,

일단 내가 만든 알고리즘으로는 페북에서 제시하는 예제는 다 맞는다..

문제는 이 방법에 mCr형태로 조합을 구해야 하는 부분이 있는데,

m제한이 10억이다. ㅠ

페르마 소정리 써서 (a^(mod-2))%mod == a%mod 임을 이용하려고 했다.

그래서 자그마치 10억!을 (10억이 아니라 10억 factorial 이다.) 파일에 저장하고 (9.7GB 나옴 ㅋㅋ)

모듈러 inverse도 똑같이 저장하려고 했으나, 남은 시간이 얼마 없었다.

생각해보면 modulo inverse는 분할정복으로 대충하면 되니까 10억7에 해당하는 로그값이 30정도 밖에 안돼서 걍 돌려보기로 했다.

파일 입력만 한참걸려서 한 4분정도 지나니까 답이 뜨는데...

젠장.. 왜 뭐가 잘못된거냐 ㅠㅠㅠㅠㅠ 아무래도 페르마를 잘못쓴거 같다.

아무래도 관련된 공부를 이참에 해야할 듯 싶다.

http://koosaga.myungwoo.kr/entry/이항계수-nCr-mod-p-계산하기

여기 구사과님 사이트가 딱인듯...

캠프 끝나고 꼭 정리하자 ㅠㅠ

일단 작은 m에서 돌아가는 코드를 올려본다.

(여기에 9.7G짜리 input file을 필요로 하는 코드를 올릴 순 없잖엉ㅠ)

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll d[2001];
int r[2001];
ll mm(ll x) {
    if(x>=mod) return x%mod;
    else return x;
}
ll fact(ll n) {
    ll &ret = d[n];
    if(ret) return ret;
    if(n==0) return ret=1ll;
    else return ret = mm(n*fact(n-1));
}
map<int, map<int,ll>> com;
ll combi(int n, int r) {
    if(n==r||r==0) return 1ll;
    if(com.count(n)) {
        if(com[n].count(r)) {
            return com[n][r];
        }
    }
    return com[n][r] = mm(combi(n-1,r-1)+combi(n-1,r));
}
int main() {
    freopen("./d_input.txt", "r", stdin);
    freopen("./d_output.txt", "w", stdout);
    int tc; scanf("%d", &tc);
    for(int z=1; z<=tc; z++) {
        memset(r,0,sizeof(r));
        int n,m,sum=0;
        scanf("%d%d",&n,&m);
        for(int i=0; i<n; i++) {
            scanf("%d", &r[i]);
            sum+=r[i]*2;
        }
 
        if(n==1) printf("Case #%d: %d\n", z,m);
        else {
            ll ans=0ll;
            for(int i=0; i<n; i++) {
                for(int j=0; j<n; j++) {
                    if(i==j) continue;
                    int board = m-1+r[i]+r[j];
                    int g = board-sum;
                    if(g<0) continue;
                    ans = mm(ans + combi(n+g,min(n,g))*fact(n-2));
                }
            }
            printf("Case #%d: %lld\n",z,ans);
        }
    }
    return 0;
}

아 너무 아쉽다. ㅠㅠ

작년 처음 코드잼 봤던거에 비하면 난이도가 상당히 쉬운편이었던 것 같은데,

이번 해커컵은 Round1에서 좌절됐다.ㅠㅠㅠㅠㅠ

3월에 하는 코드잼이나 열심히 해봐야겠다.