2014-08-25

POJ 3685: Matrix

POJ 蟻本

概要

N次正方行列があって，その(i,j)-成分はi^2+100000*i+j^2-100000*j+i*jで与えられる．
M番目に小さい要素の値はいくつか．

解法

解について二分探索．列を固定してしまえば，値は行について単調増加であることが式からわかる．
2次方程式を解けばO(1)で計算できるのだろうけど，ここでも二分探索を使った．

#include <cstdio>
#include <algorithm>

typedef long long ll;

const ll MAX_N = 50010;

ll N, M;
ll func(ll i, ll j){
    return i * i + 100000 * i + j * j - 100000 * j + i * j;
}
bool C(ll x){
    ll cnt = 0;
    for(int j = 1; j <= N; ++j){
        ll lb = 0, ub = N + 1;
        while(ub - lb > 1){
            ll mid = (lb + ub) / 2;
            if(func(mid, j) < x){
                lb = mid;
            } else{
                ub = mid;
            }
        }
        cnt += lb;
    }
    // printf(">>%lld\n", cnt);
    return cnt < M;
}
main(){
    int T;
    scanf("%d", &T);
    for(;T>0;--T){
        scanf("%lld%lld", &N, &M);
        ll ub = MAX_N * MAX_N * 3 + MAX_N * 100000 * 2;
        ll lb = -ub;
        while(ub - lb > 1){
            ll mid = (lb + ub) / 2;
            // printf("(%lld)\n", mid);
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%lld\n", lb);
    }
    return 0;
}

2014-08-25

POJ 3662: Telephone Lines

POJ 蟻本

概要

N頂点，辺P本のグラフが与えられる．K本の辺は無料で使うことができ，それ以上使うとK本からはみ出た辺の中での最大の長さだけの料金が発生する．
頂点1から頂点Nまでの経路をできるだけ安い料金で実現したい．

解法

料金（辺の長さの最大値）について二分探索．料金をdと仮定したとき，dより長い辺をK本以下使って1からNへの経路をつくれるかを判定する．判定にはDijkstraを利用．

typedef int Weight;
struct Edge{
    int from, to;
    Weight weight;
    Edge(int f, int t, Weight w) : from(f), to(t), weight(w) { }
};
bool operator<(const Edge &a, const Edge &b){
    return a.weight > b.weight;
}
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;

const int INF = 1000000;

int N, P, K;
int d[1010];
bool visited[1010];
bool C(Graph &g, int L) {
    priority_queue<Edge> Q;
    for(int i = 0; i < N; ++i) d[i] = INF;
    memset(visited, 0, sizeof(visited));
    
    d[0] = 0;
    Q.push(Edge(-1, 0, 0));
    while(!Q.empty()){
        int v = Q.top().to;
        int cnt = Q.top().weight;
        Q.pop();
        if(visited[v]) continue;
        visited[v] = true;
        if(v == N-1) return cnt <= K;
        EACH(i, g[v]){
            int ncnt = cnt;
            if(i->weight > L) ncnt++;
            if(d[i->to] > ncnt){
                d[i->to] = ncnt;
                Q.push(Edge(i->from, i->to, ncnt));
            }
        }
    }
    return false;
}
main(){
    scanf("%d%d%d", &N, &P, &K);
    Graph g(N);
    for(int i = 0; i < P; ++i){
        int a, b, l;
        scanf("%d%d%d", &a, &b, &l);
        --a; --b;
        g[a].push_back(Edge(a, b, l));
        g[b].push_back(Edge(b, a, l));
    }
    int lb = -1, ub = 1000010;
    while(ub - lb > 1){
        int mid = (lb + ub) / 2;
        // printf(">%d\n", mid);
        if(C(g, mid)){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%d\n", ub > 1000000 ? -1: ub);
}

2014-08-25

POJ 2991: Crane

POJ 蟻本

何を血迷ったのか，くっそ忙しいときに取り組んだ．そのうえ，勘違いをただすためにかなり時間を食った．今は反省している．

問題文・解法は蟻本まんまのため省略．
多分同じ間違いをする人はいないと思うが，もしも同じ勘違いで頭を悩ませる人が出てきたときのために勘違いしてたことを書く．

疑問：「回転する角度って，累積していっていいの？」

問題ない．というか，普通の人にはこれを勘違いする理由が見当たらないかもしれない．
クレーンの座標の導出式は，
$\displaystyle{\vec{v_0} + \sum_{i=1}^{n-1} R(\theta_i)\vec{v_i}}$
だと思っていた．ただし，i番目のクレーンの回転角度を $\theta_i$ ， $R(\theta)$ を $\theta$ だけ回転させる行列， $\vec{v_i} = (0,L_i)$ とする．

この式はまちがっていて，正しくは
$\displaystyle{\vec{v_0} + R(\theta_1)(\vec{v_1} + R(\theta_2)(\vec{v_2} + \dots)).}$
もうちょっとかっこよくすると，
$\displaystyle{\vec{v_0} + \sum_{i=1}^{n-1} (\prod_{j=1}^i R(\theta_j))\vec{v_i}}.$

なぜならば，i番目のクレーンを回転させると，それ以外のクレーンも（原点は違うが）同じ角度の分だけ回転されるから．
i番目のクレーンから見た座標系は，i-1番目のクレーンの座標系に乗っていると考えたらすっきり納得できた．
今では，なぜ勘違いをしていたのかわからない．．．

2014-08-23

POJ 3579: Median

POJ 蟻本

概要

N個の配列が与えられる．この中から2つの要素を取り出し，その差を計算し別の数列とする．
新しく作った配列の中央値を探索する．ただし，この問題において偶数長(m)の配列の中央値はm/2番目に小さい値と定義する．

解法

解を仮定して二分探索．

入力された配列はソートする．（絶対値をとっていて，順番には左右されないので）
そうすることで，個数のカウントが二分探索を使って行える．

制限時間がかなり厳しい．

int N;
int x[100010];
ll M;
bool C(int mid){
    ll cnt = 0;
    for(int i = 0; i < N; ++i){
        cnt += lower_bound(x + i + 1, x + N, x[i] + mid) - (x + (i + 1));
    }
    return cnt < M;
}
int main(){
    while(~scanf("%d", &N)){
        for(int i = 0; i < N; ++i) scanf("%d", x+i);
        M = (ll)N * (N - 1) / 2;
        if(M % 2) M = M / 2 + 1;
        else      M = M / 2;

        sort(x, x+N);
        int lb = 0, ub = 1000000010;
        while(ub - lb > 1){
            int mid = (lb + ub) / 2;
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%d\n", lb);
    }
    return 0;
}

2014-08-23

POJ 3111: K Best

POJ 蟻本

概要

n個の宝石があって，k個を残して売り払いたい．その時，残したk個の宝石の単位重さあたりの評価値を最大化したい．

解法

蟻本そのままで二分探索．謎WA連発の末，探索終えた後にもう一回答えを計算したほうがいいという結論に至る．
繰り返し回数が結構シビアかもしれない．

int n, k;
int v[100010], w[100010];

pair<double, int> y[100010];
bool C(double x){
    for(int i = 0; i < n; ++i) y[i] = make_pair(v[i] - w[i] * x, i + 1);
    sort(y, y + n);
    double sum = 0;
    for(int i = 0; i < k; ++i){
        sum += y[n-i-1].first;
    }
    return sum >= 0;
}
int main(){
    scanf("%d%d", &n, &k);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", &v[i], &w[i]);
    }
    double lb = 0, ub = 1e8;
    for(int i = 0; i < 50; ++i){
        double mid = (lb + ub) / 2;
        if(C(mid)){
            lb = mid;
        }
        else{
            ub = mid;
        }
    }
    C(lb);
    for(int i = 0; i < k; ++i)
        printf("%d%c", y[n-i-1].second, i == k - 1 ? '\n': ' ');

    return 0;
}

2014-08-22

POJ 2976: Dropping Tests

概要

授業でn回のテストを受けた．i番目のテストではb[i]問中a[i]問正解した．
受けたテストのうちk回を取り除き， $100 \cdot (\sum_i a_i) / (\sum_i b_i)$ を最大化したい．

解法

二分探索．蟻本の練習問題まんま．

int n, k;
int a[1010], b[1010];
double v[1010];
bool C(double x){
    for(int i = 0; i < n; ++i) v[i] = 100LL * a[i] - x * b[i];
    sort(v, v + n);
    double sum = 0;
    for(int i = k; i < n; ++i){
        sum += v[i];
    }
    return sum >= 0;
}
main(){
    for(;;){
        scanf("%d%d", &n, &k);
        if( n == 0  && k == 0 ) return 0;
        for(int i = 0; i < n; ++i){
            scanf("%d", &a[i]);
        }
        for(int i = 0; i < n; ++i){
            scanf("%d", &b[i]);
        }
        double lb = 0, ub = 100;
        for(int i = 0; i < 100; ++i){
            double mid = (lb + ub) / 2;
            if(C(mid)){
                lb = mid;
            }
            else{
                ub = mid;
            }
        }
        printf("%d\n", (int)floor(lb + 0.5));
    }
}

2014-08-21

POJ 3045: Cow Acrobats

POJ 蟻本

概要

牛がN匹いる．i番目の牛は重さがw[i]で，強さがs[i]であることがわかっている．
この牛でタワーをつくりたい．タワーは牛が別の牛一頭にのることを繰り返してつくられる．
この時，牛iの危険度は (牛iの上に乗っている牛の重さの合計) - (牛iの強さ) で求められる．
N匹の牛を使って作るとき，牛の危険度の最大値を最小化したい．

解法

危険度を仮定して二分探索．

調べてみると二分探索使わなくても貪欲で解けるらしい．
貪欲力が低い．．．

const ll MAX_S = 1000000100;

int N, sum;
pair<int, int> cow[50010];

bool C(ll risk){
    priority_queue<int> Q;
    int i = 0;
    int tsum = sum;
    while(i < N){
        for(; i < N && tsum - cow[i].first <= risk; ++i){
            Q.push(cow[i].second); 
        }
        if(i < N && Q.empty()) return false;
        tsum -= Q.top();
        Q.pop();
    }
    return true;
}
int main(){
    scanf("%d", &N);
    sum = 0;
    for(int i = 0; i < N; ++i){
        int w, s;
        scanf("%d%d", &w, &s);
        cow[i] = make_pair(s + w, w);
        sum += w;
    }
    sort(cow, cow + N);
    reverse(cow, cow + N);
    ll lb = -MAX_S, ub = MAX_S;
    while(ub - lb > 1){
        ll mid = (ub + lb) / 2;
        if(C(mid)){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%lld\n", ub);
    return 0;
}