れんしゅうちょう。

■ [RUPC]RUPC2015 day1 00:17

問題

odan さんと omurice さんと出ていました.

僕はコーディングをしていなかったので, 懇親会を抜けだした後 indeed なうを解いた後書いて見ました.

とりあえずコードだけ.

A

#include <bits/stdc++.h>
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define repsz(i, v) rep(i, (v).size())
#define all(v) begin(v), end(v)
#define eb emplace_back
typedef long long ll;
using namespace std;
template<typename C>
inline int size(const C &c){ return c.size(); }
template<class T>bool chmin(T&a,const T&b){if(a<=b)return false;a=b;return true;}
template<class T>bool chmax(T&a,const T&b){if(a>=b)return false;a=b;return true;}

signed main(){
    cout << std::fixed << std::setprecision(10);
    int n;
    cin >> n;
    vector<int> f(n), a(n), t(n), x(n), y(n);
    rep(i, n) cin >> f[i] >> a[i] >> t[i] >> x[i] >> y[i];
    vector<int> res_len(2, -1), res_time(2, 1<<10);
    rep(i, n-1) if(t[i] == t[i+1] and a[i] != a[i+1]){
        int dx = x[i] - x[i+1], dy = y[i] - y[i+1];
        int d = dx*dx + dy*dy;
        if(chmax(res_len[t[i]], d)) res_time[t[i]] = f[i+1] - f[i];
        if(res_len[t[i]] == d) chmin(res_time[t[i]], f[i+1] - f[i]);
    }
    rep(i, 2){
        if(res_len[i] == -1) cout << "-1 -1" << endl;
        else cout << sqrt(res_len[i]) << " " << res_time[i]/60.0 << endl;
    }
    return 0;
}

以下, テンプレは略.

B

signed main(){
    int n; cin >> n;
    vector<ll> a(n);
    rep(i, n) cin >> a[i];
    sort(all(a));
    vector<ll> s(n+1);
    rep(i, n) s[i+1] = s[i] + a[i];

    int m; cin >> m;
    vector<ll> b(m), c(m);
    rep(i, m) cin >> b[i];
    rep(i, m) cin >> c[i];

    rep(i, m){
        int t = upper_bound(all(a), b[i]) - begin(a);
        cout << (s[t] >= c[i] ? "Yes" : "No") << endl;
    }
    return 0;
}

C

struct UF{
    vector<int> p, min;
    UF(int n) : p(n, -1), min(n, 1<<29) {}
    int find(int i){ return p[i] < 0 ? i : p[i] = find(p[i]); }
    bool unite(int i, int j){
        if((i = find(i)) == (j = find(j))) return false;
        if(p[i] > p[j]) swap(i, j);
        p[i] += p[j];
        chmin(min[i], min[j]);
        p[j] = i;
        return true;
    }
};

signed main(){
    int n; cin >> n;
    map<string, int> zip;
    UF uf(n);
    rep(i, n){
        string name;
        int cost;
        cin >> name >> cost;
        int id = size(zip);
        if(zip.count(name)) id = zip[name];
        zip[name] = id;
        uf.min[id] = cost;
    }
    int m; cin >> m;
    rep(_, m){
        string s, t;
        cin >> s >> t;
        uf.unite(zip[s], zip[t]);
    }
    ll res = 0;
    repsz(i, zip) res += uf.min[uf.find(i)];
    cout << res << endl;
    return 0;
}

D

const int mod = 1000 * 1000 * 1000 + 7;

signed main(){
    int n, l;
    cin >> n >> l;
    vector<int> x(n), a(n);
    rep(i, n) cin >> x[i];
    rep(i, n) cin >> a[i];
    for(auto &t : x) ++t;

    vector<int> dp(l+1);
    dp[0] = 1;
    rep(i, n){
        vector<int> s(l+2);
        rep(p, l+1) s[p+1] = (s[p] + dp[p]) % mod;
        rep(p, l+1){
            int ok = x[i] == p;
            ok |= a[i] != 0 and x[i] <= p and (p - x[i]) % a[i] == 0;
            dp[p] = s[p] * ok;
        }
    }
    cout << accumulate(all(dp), 0LL) % mod << endl;
    return 0;
}

E

const int INF = 1<<29;
signed main(){
    int n, M, E, S, T, R;
    cin >> n >> M >> E >> S >> T >> R;

    vector<vector<vector<int>>> dist(1<<E,
            vector<vector<int>>(n, vector<int>(n, INF)));
    {
        auto &d = dist[0];
        rep(u, n) d[u][u] = 0;
        rep(_, M){
            int s, t; cin >> s >> t;
            d[s][t] = d[t][s] = 1;
        }
        rep(k, n) rep(i, n) rep(j, n) chmin(d[i][j], d[i][k] + d[k][j]);
    }
    vector<int> ea(E), eb(E), ec(E);
    rep(i, E) cin >> ea[i] >> eb[i] >> ec[i];

    rep(A, 1<<E) if(A){
        rep(i, E) if(A>>i&1){
            int B = A ^ (1<<i);
            auto &d = dist[A];
            d = dist[B];

            rep(u, n) rep(v, n) chmin(d[u][v], d[u][ea[i]] + 1 + d[eb[i]][v]);
            rep(u, n) rep(v, n) chmin(d[u][v], d[u][eb[i]] + 1 + d[ea[i]][v]);
            break;
        }
    }

    int res = INF;

    vector<int> event(E);
    rep(i, E) event[i] = i;
    do{
        vector<int> dp(R+1, 0);
        int u = S;
        int A = 0;
        event.eb(-1);
        for(auto &i : event){
            auto &d = dist[A];
            rep(r, R+1){
                if(r >= d[u][T]) chmin(res, dp[r] + d[u][T]);
                if(R >= d[S][T]) chmin(res, dp[r] + 1 + d[S][T]);
            }
            if(i == -1) break;

            vector<int> qb(R+1, INF);
            int v = ec[i];
            rep(r, R+1){
                if(r >= d[u][v]) chmin(qb[r - d[u][v]], dp[r] + d[u][v]);
                if(R >= d[S][v]) chmin(qb[R - d[S][v]], dp[r] + 1 + d[S][v]);
            }
            u = v;
            A |= 1<<i;
            swap(dp, qb);
        }
        event.pop_back();
    }while(next_permutation(all(event)));

    if(res == INF) res = -1;
    cout << res << endl;
    return 0;
}

ツイートする