RUPC 2015 Day 1

立命館は(どこにあるか知らないレベルで)遠かったので，家から参加しました．
結果はABCDの4完でした．

A(Soccer)

問題文はちゃんと読みましょう．

解法

言われたとおりに書く．

コード

#include <cstdio>
#include <cmath>

typedef long long ll;

ll F0[100], X0[100], Y0[100], A0[100], T0[100];

int main(){
    int N;
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%lld %lld %lld %lld %lld", F0+i, A0+i, T0+i, X0+i, Y0+i);
    }

    ll longest[2] = {-1, -1}, shortest[2] = {-1, -1};
    for(int i=0;i+1<N;i++){
        if(T0[i] != T0[i+1] || A0[i] == A0[i+1]){continue;}

        ll df = F0[i+1] - F0[i],
            dx = X0[i+1] - X0[i],
            dy = Y0[i+1] - Y0[i],
            dist2 = dx * dx + dy * dy;

        if(dist2 > longest[T0[i]]){
            longest[T0[i]] = dist2;
            shortest[T0[i]] = df;
        }else if(dist2 == longest[T0[i]] && df < shortest[T0[i]]){
            shortest[T0[i]] = df;
        }
    }

    for(int i=0;i<2;i++){
        if(longest[i] == -1){
            puts("-1 -1");
        }else{
            printf("%.6f %.6f\n", std::sqrt(longest[i]), 1. * shortest[i] / 60);
        }
    }

}

B(RUPC)

くるくる．

解法

累積和をとって，二分探索(upper_bound)．

コード

#include <cstdio>
#include <algorithm>

typedef long long ll;

ll A[300000], A_[300000];
ll B[300000], C[300000];

int main(){
    int N;
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        scanf("%lld", A+i);
    }
    std::sort(A, A+N);
    for(int i=0;i<N;i++){
        A_[i] = A[i];
        if(i > 0){A_[i] += A_[i-1];}
    }
    
    int M;
    scanf("%d", &M);

    for(int i=0;i<M;i++){
        scanf("%lld", B+i);
    }
    for(int i=0;i<M;i++){
        scanf("%lld", C+i);
    }
    for(int i=0;i<M;i++){
        if(A[0] > B[i]){
            puts(C[i] == 0 ? "Yes" : "No");
            continue;
        }
        if(A_[std::upper_bound(A, A+N, B[i])-A-1] >= C[i]){
            puts("Yes");
        }else{
            puts("No");
        }
    }
}

C(Shopping)

有向グラフだとおもって，強連結成分分解にしようとしてた．Ω＼ζ°)ﾁｰﾝ

解法

UnionFind木．mapをつかうと楽．

コード

#include <cstdio>
#include <iostream>
#include <unordered_map>

#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define REP(i,j) FOR(i,0,j)

const int MAX_N = 5000;

class UnionFind{
public:
    UnionFind(int n){
        REP(i, n){
            par[i] = i;
            rank[i] = 0;
        }
    }
    int find(int x){
        if(x == par[x])return x;
        return par[x] = find(par[x]);
    }
    bool same(int x, int y){
        return find(x) == find(y);
    }
    void unite(int x, int y){
        x = find(x);
        y = find(y);
        if(x == y){return;}
        
        if(rank[x] > rank[y]){
            par[y] = x;
        }else{
            par[x] = y;
            if(rank[x] == rank[y]){rank[y]++;}
        }
    }
private:
    int rank[MAX_N], par[MAX_N];
};

int N, M;
int X[5000];
std::unordered_map<std::string, int> map;
UnionFind uf(5000);

int main(){
    scanf("%d", &N);

    for(int i=0;i<N;i++){
        std::string name;
        std::cin >> name >> X[i];

        map[name] = i;
    }

    scanf("%d", &M);
    
    for(int i=0;i<M;i++){
        std::string from, to;
        std::cin >> from >> to;

        uf.unite(map[from], map[to]);
    }

    int sum = 0;
    for(int i=0;i<N;i++){
        int mn = 1001001001;
        for(int j=0;j<N;j++){
            if(uf.same(i, j)){
                mn = std::min(mn, X[j]);
            }
        }

        sum += mn;
    }

    printf("%d\n", sum);
}

D(Hopping Hearts)

ﾅﾆｿﾚｲﾐﾜｶﾝﾅｲ．BIT便利だなあ．

解法

左右をひっくり返して，うさぎが左にジャンプするようにする．
dp[i][j] := i番目のうさぎが位置jにいて，それより前のうさぎが位置jより左にいるような配置の数とすると，
X[i+1]-kA[i+1](kは非負整数)の形で表される整数jに対して，
dp[i+1][j] = dp[i][j-1] + dp[i][j-2] + ... + dp[i][0]
となる．右辺を計算するためにBITをつかう．
うさぎが同じ位置にジャンプする，すなわち，A[i]=0の場合があることに注意．

コード

#include <iostream>
#include <algorithm>
#include <cstring>

typedef long long ll;

const ll MOD = 1000000007ll;

int N, L;
int X[5000], A[5000];
ll BIT[2][5001];

inline void add(int k, ll v, ll (&bit)[5001]){
    k += 1;
    while(k <= L){
        bit[k] = (bit[k] + v) % MOD;
        k += k & -k;
    }
}

inline ll sum(int k, ll (&bit)[5001]){
    k += 1;
    ll res = 0ll;
    while(k > 0){
        res = (res + bit[k]) % MOD;
        k -= k & -k;
    }
    return res;
}

int main(){
    scanf("%d %d", &N, &L);

    for(int i=0;i<N;i++){
        scanf("%d", X+i);
        X[i] = L-1 - X[i];
    }
    std::reverse(X, X+N);
    
    for(int i=0;i<N;i++){
        scanf("%d", A+i);
    }
    std::reverse(A, A+N);

    if(A[0] == 0){
        add(X[0], 1, BIT[0]);
    }else{
        for(int i=X[0];i>=0;i-=A[0]){
            add(i, 1, BIT[0]);
        }
    }

    int prev = 0, next = 1;
    for(int i=1;i<N;i++){
        memset(BIT[next], 0, sizeof(BIT[next]));

        if(A[i] == 0){
            add(X[i], sum(X[i]-1, BIT[prev]), BIT[next]);
        }else{
            for(int j=X[i];j>=0;j-=A[i]){
                add(j, sum(j-1, BIT[prev]), BIT[next]);
            }
        }

        std::swap(prev, next);
    }

    printf("%lld\n", sum(L-1, BIT[prev]));
}

E(Ocarina of Time)

ダメです．

解法

Warshall-Floyd法とbitDP．
発生済みのイベントを固定して，任意の2つの街の最短距離を求める．
何もイベントが起きていないときについてはWarshall-Floyd法で求め，それ以外は1つずつイベントを追加すれば，それによって生じる道を通る経路と元の最短距離の短い方を選べばよくなる．
前者はO(N^3)，後者は全体でO(2^E E N^2)ぐらい．
得られた最短距離をつかいbitDPをする．[発生済みのイベント][日数][頂点]をもつようにする．
頂点はイベントを発生させる頂点と始点，終点以外はいらないので高々E+2個だけである．
よって，O(2^E R E^2)ぐらい．

コード

これを素で書けるぐらいになりたいなあ．

#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <tuple>

typedef std::tuple<int,int,int> T;

const int INF = 1001001001;

int N, M, E, S, T_, R;
int d[1<<8][100][100], dp[1<<8][101][10];
T events[8];
bool used[1<<8];

void rec(int s){
    if(used[s]){return;}
    used[s] = true;
    
    for(int i=0;i<E;i++){
        if(s >> i & 1){continue;}

        int ns = s | (1 << i);
        int a = std::get<0>(events[i]),
            b = std::get<1>(events[i]);
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                d[ns][j][k] = d[s][j][k];
            }
        }
        for(int j=0;j<N;j++){
            for(int k=0;k<N;k++){
                int nd = std::min(d[ns][j][a] + 1 + d[ns][b][k], d[ns][j][b] + 1 + d[ns][a][k]);
                if(nd > R){continue;}
                d[ns][j][k] = std::min(d[ns][j][k], nd);
            }
        }

        rec(ns);
    }
}

int rec2(int s, int day, int index){
    if(dp[s][day][index] != -1){return dp[s][day][index];}
    
    int u = index == E ? S : std::get<2>(events[index]);
    
    int res = INF;
    for(int i=0;i<E;i++){
        if(s >> i & 1){continue;}
        if(i == index){continue;}
        
        int c = std::get<2>(events[i]);
        if(day + d[s][u][c] <= R){
            res = std::min(res, d[s][u][c] + rec2(s | (1 << i), day + d[s][u][c], i));
        }
    }

    if(day + d[s][u][T_] <= R){
        res = std::min(res, d[s][u][T_]);
    }
    if(day > 0){
        res = std::min(res, rec2(s, 0, E) + 1);
    }

    return dp[s][day][index] = res;
}

int main(){
    scanf("%d %d %d %d %d %d", &N, &M, &E, &S, &T_, &R);

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            d[0][i][j] = i == j ? 0 : INF;
        }
    }
    
    for(int i=0;i<M;i++){
        int a, b;
        scanf("%d %d", &a, &b);

        d[0][a][b] = 1;
        d[0][b][a] = 1;
    }

    for(int k=0;k<N;k++){
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                if(d[0][i][k] + d[0][k][j] > R){continue;}
                d[0][i][j] = std::min(d[0][i][j], d[0][i][k] + d[0][k][j]);
            }
        }
    }

    for(int i=0;i<E;i++){
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);

        events[i] = std::make_tuple(a, b, c);
    }
    rec(0);
    
    for(int i=0;i<1<<E;i++){
        for(int j=0;j<=R;j++){
            for(int k=0;k<=E;k++){
                dp[i][j][k] = -1;
            }
        }
    }
    int res = rec2(0, 0, E);
    if(res < INF){printf("%d\n", res);}
    else{puts("-1");}
}

F(Tree)

あとで解きたい．