Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2010-12-29

SRM492 550 Source

| 02:44

O(n^4)のDP解です。コンテスト中は木の分岐の仕方を間違えてたのが問題だった。

#define rep(i, n) for(int i=0; i<(int)(n); i++)

#define INF (1LL<<60)
long long d[100][100];
long long dp[100][100][100];

class TimeTravellingTour {
public:
    long long determineCost(int n, vector <int> cities, vector <string> roads) {
        rep(i, 100) rep(j, 100) d[i][j]=i!=j?INF:0;
        string road;
        rep(i, roads.size()) road+=roads[i];
        stringstream sin(road);
        string s;
        while(sin>>s) {
            int a, b, c;
            sscanf(s.c_str(), "%d,%d,%d", &a, &b, &c);
            d[a][b]=d[b][a]=c;
        }
        rep(k, n) rep(i, n) rep(j, n) d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
        int m=cities.size();
        rep(i, m) if(d[0][cities[i]]==INF) return -1;
        rep(i, n) rep(j, m) dp[i][j][j]=d[i][cities[j]];
        for(int w=1; w<m; w++) {
            for(int i=0; i+w<m; i++) {
                int j=i+w;
                rep(k, n) dp[k][i][j]=INF;
                rep(k, n) for(int z=i; z<j; z++) {
                    dp[k][i][j]=min(dp[k][i][j], dp[k][i][z]+dp[k][z+1][j]);
                }
                rep(k, n) rep(l, n) {
                    dp[k][i][j]=min(dp[k][i][j], d[k][l]+dp[l][i][j]);
                }
            }
        }
        return dp[0][0][m-1];
    }
};

2010-12-23

Codeforces #47 復習

| 18:26

きれいに書き直し+改良したソース。


A

floor(面積/2)は必ず敷き詰めれる。

#include <stdio.h>

int main() {
    int m, n;
    scanf("%d%d", &m, &n);
    printf("%d\n", m*n/2);
    return 0;
}

B

それぞれの文字について、i番目までに出てきた数をcに記録

#include <iostream>
#include <string>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int c[128];

int main() {
    string s;
    cin >> s;
    long long ans=s.size();
    rep(i, s.size()) ans+=2*c[s[i]]++;
    cout << ans << endl;
    return 0;
}

C

ななめ45度に傾いた長方形で囲ってやればよい。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int n, x, y;
int INF = 1<<30;

int main() {
    scanf("%d", &n);
    int mink=INF, maxk=-INF, minl=INF, maxl=-INF;
    rep(i, n) {
        scanf("%d%d", &x, &y);
        mink = min(mink, x+y);
        maxk = max(maxk, x+y);
        minl = min(minl, -x+y);
        maxl = max(maxl, -x+y);
    }
    printf("%d\n", maxk-mink+maxl-minl+4);
    return 0;
}

D

半径について2分探索+確率についてDP.

#include <stdio.h>
#include <math.h>
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int N, K, eps, xo, yo, x, y;
double d[200], f[200], dp[200][200];

double p(double r) {
    rep(i, N) f[i] = d[i]<=r ? 1 : exp(1-d[i]*d[i]/r/r);
    rep(i, 200) rep(j, 200) dp[i][j]=0;
    dp[0][0] = 1;
    rep(i, N) rep(j, i+1) {
        dp[i+1][j+1] += dp[i][j] * f[i];
        dp[i+1][j] += dp[i][j] * (1-f[i]);
    }
    double s=0;
    rep(i, K) s+=dp[N][i];
    return s;
}

int main() {
    scanf("%d%d%d%d%d", &N, &K, &eps, &xo, &yo);
    rep(i, N) {
        scanf("%d%d", &x, &y);
        d[i] = hypot(x-xo, y-yo);
    }
    double l=0, r=1e10, m;
    rep(q, 100) {
        m = (l+r)/2;
        if(p(m)*1000<eps) r=m;
        else l=m;
    }
    printf("%.9f\n", l);
    return 0;
}

E

解説は参加記の方を参照。結構すっきりしたコードになる。

前半のループ内で範囲を列挙しvに突っ込み、次のソート+ループ部分で範囲をマージしている。

#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
#define rep(i, n) for(int i=0; i<(int)(n); i++)

int main() {
    long long n, m, k, ans=0;
    cin >> n >> m;
    vector<pair<int, int> > v;
    for(long long b=1; b<=n; b++) {
        ans += min(m, b*b)*2;
        k = b*b>m ? b-sqrt(b*b-m) : b;
        if(k>0) {
            ans -= k*2;
            v.push_back(make_pair(1, k));
            v.push_back(make_pair((int)b*2-k, (int)b*2-1));
        }
    }
    sort(v.begin(), v.end());
    int z=0;
    rep(i, v.size()) {
        if(z>0 && v[z-1].second>=v[i].first) v[z-1].second=v[i].second;
        else v[z++] = v[i];
    }
    rep(i, z) ans += (v[i].second-v[i].first+1);
    cout << ans << endl;
    return 0;
}