Isa@Diary

ソフトウェア開発やってます。プログラミングとか、US生活とかについて書きます。

Facebook Hacker Cup Round.1

FHC2012

結果

ooo　887th
Round.1は通過、次はむり。

この形式のコンテストは(GCJとか)
MLEとTLEをあんまり気にしなくていいのが楽である。

Checkpoint

カタラン数(http://ja.wikipedia.org/wiki/%E3%82%AB%E3%82%BF%E3%83%A9%E3%83%B3%E6%95%B0)のような問題。
格子上を(0,0)から(a,b)を通って(x,y)に至るような最短経路の総数がSになるような(a,b),(x,y)のうち、その経路長の最小値を求める。

(0,0)から(a,b)までの最短経路の総数は(a+b)C(a)で求まる。S<=10^7なのでnCr<=10^7となるものを全て列挙し、ある値k=nCrとなる最小のnをkごとに覚えておき、あとは1からsqrt(S)まで回して最小値を出せる。

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cstdio>
#include <cmath>

#define ll long long
#define INF 10000000000

using namespace std;

ll least_sum[10000001];

ll fact(ll arg){
    ll ret = 1;
    for(ll i=1;i<=arg;i++){
        ret *= i;
    }
    return ret;
}

ll c(ll x, ll y){
    ll tmp = x;
    ll ret = 1;
    for(ll i=0;i<y;i++){
        ret *= tmp;
        tmp--;
    }
    return ret / fact(y);
}

int main(){
    ll tmp;

    for(ll i=0;i<10000001;i++) least_sum[i] = INF;
    least_sum[1] = 1;
    for(ll i=1;i<10000001;i++){
        for(ll j=1;j<=i/2;j++){
            tmp = c(i,j);
            if(tmp > 10000000) break;
            least_sum[tmp] = min(least_sum[tmp], i);
        }
    }

    int case_num;
    int s;
    cin >> case_num;
    for(int x=1;x<=case_num;x++){
        cin >> s;
        ll ret = INF;
        for(int i=1;i<=sqrt(s);i++){
            if(s%i == 0){
                ret = min(ret, least_sum[i]+least_sum[s/i]);
            }
        }
        printf("Case #%d: %lld \n", x, ret);
    }   
}

Recover the sequence

ソート済みの列からログに従ってmerge_sortの逆をしてやると
どう入れ替えたかの数列ができるのでmapに入れてやれば元の数列が出てくる。
若干配列がもったいない

#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <cstdio>
#include <map>

#define MP make_pair

using namespace std;

string str;
int t;
int n;
int array[10001];
int working[10001];

void merge(pair<int,int> a1, pair<int,int> a2){
    //copy array
    for(int i=0;i<n;i++){
        working[i] = array[i];
    }
    int lim1 = a1.second - a1.first + 1;
    int lim2 = a2.second - a2.first + 1;
    int cnt1 = 0, cnt2 = 0;
    int tmp;
    int pos = a1.first;
    while(lim1 > cnt1 && lim2 > cnt2){
        tmp = str[0] - '0';
        str.erase(0,1);
        if(tmp == 1){
            working[pos] = array[a1.first + cnt1];
            cnt1++;
        }else{
            working[pos] = array[a2.first + cnt2];
            cnt2++;
        }
        pos++;
    }
    while(lim1 > cnt1){
        working[pos] = array[a1.first + cnt1];
        cnt1++;
        pos++;
    }
    while(lim2 > cnt2){
        working[pos] = array[a2.first + cnt2];
        cnt2++;
        pos++;
    }

    //write back
    for(int i=0;i<n;i++){
        array[i] = working[i];
    }
    return;
}

pair<int,int> sep(int begin, int end){
    if(begin == end) return MP(begin,end);
    
    int mid = floor((double)(end-begin+1)/2);
    pair<int,int> m_b, m_e;
    m_b = sep(begin,begin+mid-1);
    m_e = sep(begin+mid,end);
    merge(m_b, m_e);
    return MP(m_b.first, m_e.second);
}


int main(){
    cin >> t;
    for(int x=1;x<=t;x++){
        cin >> n;
        cin >> str;
        for(int i=0;i<n;i++){
            array[i] = i;
        }

        sep(0,n-1);

        map<int,int> m;
        for(int i=0;i<n;i++){
            m[array[i]] = i+1;
        }
        int ret = 1;
        for(int i=0;i<n;i++){
            ret = (31 * ret + m[i]) % 1000003;
        }
        printf("Case #%d: %d\n",x, ret);
        str = "";
    }
}

Squished Status

DP。
dp[位置][これまでのMAX][右端]
としたけどMAX項はいらなかった。

#include <iostream>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdio>

#define ll long long

using namespace std;

ll dp[1024][256][256];
ll mod = 0xfaceb00c;

int main(){
    int case_num;
    int m;
    string str;
    int tmp;
    int len;

    cin >> case_num;
    for(int x=1;x<=case_num;x++){
        memset(dp, 0, sizeof(dp));
        cin >> m;
        cin >> str;
        tmp = str[0] - '0';
        len = str.size();
        //if invalid input
        if(tmp == 0){
            printf("Case #%d: 0\n", x);
            continue;
        }

        dp[0][tmp][tmp] = 1;

        for(int i=1;i<len;i++){
            tmp = str[i] - '0';
            for(int j=1;j<=m;j++){
                for(int k=1;k<=j;k++){
                    if(tmp == 0){
                        if(k*10 <= m){
                            if(k*10 > j){
                                dp[i][k*10][k*10] += dp[i-1][j][k] % mod;
                                dp[i][k*10][k*10] %= mod;
                            }else{
                                dp[i][j][k*10] += dp[i-1][j][k] % mod;
                                dp[i][j][k*10] %= mod;
                            }
                        }
                    }else{
                        if(k*10 + tmp <= m){
                            //join right most integer
                            if(k*10 + tmp > j){
                                dp[i][k*10+tmp][k*10+tmp] += dp[i-1][j][k] % mod;
                                dp[i][k*10+tmp][k*10+tmp] %= mod;
                            }else{
                                dp[i][j][k*10+tmp] += dp[i-1][j][k] % mod;
                                dp[i][j][k*10+tmp] %= mod;
                            }
                        }
                        if(tmp <= m){
                            //generate a new integer
                            if(tmp > j){
                                dp[i][tmp][tmp] += dp[i-1][j][k] % mod;
                                dp[i][tmp][tmp] %= mod;
                            }else{
                                dp[i][j][tmp] += dp[i-1][j][k] % mod;
                                dp[i][j][tmp] %= mod;
                            }
                        }
                    }
                }
            }
        }
        ll ret=0;
        for(int i=1;i<=m;i++){
            for(int j=1;j<=m;j++){
                ret += dp[len-1][i][j] % mod;
                ret %= mod;
            }
        }
        printf("Case #%d: %lld\n", x, ret);
    }
}