2014-09-03

POJ 3185: The Water Bowls

POJ 蟻本

概要

20個のボウルが一列に並んでいて，あるボウルを選ぶとそのボウルと両側のボウルが一緒にひっくり返る．（端っこのボウルを選ぶと2個だけひっくり返る）
全てのボウルを正しい向きにするには，何回の選択が必要になるか？

解法

端っこから地道にシミュレーション．2^20通り全列挙は時間が足りない．
ただし，端の2つを反転する場合と反転しない場合に分け，中央のボウルを選択するのではなく，端のボウルを選択するようにする．

int calc(int *a){
    int cnt = 0;
    for(int i=0;i<19;++i){
        //for(int j = 0; j < 20; ++j) printf("%d", a[j]);
        //printf("\n");
        if(a[i]){
            ++cnt;
            for(int j=0;j<3;++j) a[i+j]^=1;
        }
    }
    //printf("%d\n", cnt);
    return a[19]==0 ? cnt: 32;
}

int a[32];
int b[32];
int main(){
    int s = 0;
    for(int i = 0; i < 20; ++i){
        scanf("%d", a+i);
        b[i] = a[i];
        //s = (s << 1) | a[i];
    }
    b[0] ^= 1; b[1] ^= 1;
    printf("%d\n", min(calc(a), calc(b) + 1));
    return 0;
}

2014-09-03

POJ 1222: EXTENDED LIGHTS OUT

POJ 蟻本

ほろ酔いコーディング

概要

5行6列のライトのついたボタンがあって，ボタンを押したらそのボタンと4近傍のボタンが反転する．
与えられた状態からライトを全部消す押し方を求める．

解法

蟻本まんま．幅と高さをいじればそのまま通用する．．．と思う．
僕は一から実装しました．

const int W = 6;
const int H = 5;

int di[] = {0, 0, 1, 0, -1};
int dj[] = {0, 1, 0, -1, 0};
int ans[10][10];
int tmp[10][10];
int f[10][10];
int M;
void solve(int s){
    memset(ans, 0, sizeof(ans));
    for(int j = 0; j < W; ++j) if(s >> j & 1){
        ans[1][j+1] = 1;
        for(int k=0;k<4;++k) tmp[1+di[k]][j+1+dj[k]] ^= 1;
    }
    for(int i=1;i<H;++i)for(int j=1;j<=W;++j){
        if(tmp[i][j]){
            ans[i+1][j] = 1;
            for(int k=0;k<5;++k) tmp[i+1+di[k]][j+dj[k]] ^= 1;
        }
    }
    bool f = true;
    for(int j=1;j<=W;++j) f = f && tmp[H][j] == 0;
    if(f){
        for(int i=1;i<=H;++i) for(int j = 1; j <= W; ++j)
            printf("%d%c", ans[i][j], j < W ? ' ':'\n');
    }
}
int main(){
    scanf("%d", &M);
    for(int m=1;m<=M;++m){
        for(int i = 0; i < H; ++i)for(int j = 0; j < W; ++j)
            scanf("%d", f[i]+j);
        printf("PUZZLE #%d\n", m);
        for(int s=0; s < 1 << W; ++s){
            for(int i=0;i<H;++i)for(int j=0;j<W;++j) 
                tmp[i+1][j+1] = f[i][j];
            solve(s);
        }
    }
    return 0;
}

2014-09-02

POJ 2739, POJ 2100

POJ 蟻本

POJ 2566は，そのままだとしゃくとりできないが，累積和にしてソートするとしゃくとりできるようになる．なぜならば，問題が知りたいのは合計の絶対値であるから，累積和の差だけを考えればよいため．カンニング先→POJ-2566 : Bound Found - komiyamの日記

POJ 2739 Sum of Consecutive Prime Numbers

概要

与えられた整数値を連続した素数の和で表す方法は何通りあるか．

解法

素数列挙してしゃくとり．

vector<int> sieve_of_eratosthenes(ll n, vector<ll> &prime){
    vector<int> isPrime(n);
    for(ll i=2; i<n; ++i)
        isPrime[i] = i;
    for(ll i=2;i<n;++i)
        if(isPrime[i]){
            prime.push_back(i);
            for(ll j = i * i; j < n; j += i)
                isPrime[j] = 0;
        }
    return isPrime;
}

int main(){
    vector<ll> prime;
    sieve_of_eratosthenes(10010, prime);
    int n = prime.size();
    for(;;){
        int p;
        scanf("%d", &p);
        if(p == 0) return 0;
        int cnt = 0, sum = 0;
        for(int s=0,t=0;;){
            while(t < n && sum < p) sum += prime[t++];
            if(sum < p) break;
            if(sum == p) ++cnt;
            sum -= prime[s++];
        }
        printf("%d\n", cnt);
    }
}

POJ 2100 :Graveyard Design

与えられた整数値を，連続する二乗数の和で求めたい．

解法

何も考えずしゃくとり．

ll n;
vector<pair<ll, ll> > res;
int main(){
    scanf("%lld", &n);
    ll m = (ll)ceil(sqrt(n)) + 1;
    ll sum = 0LL;
    for(ll s = 1, t = 1;;){
        while(t <= m && sum < n){
            sum += t * t;
            ++t;
        }
        if(sum < n) break;
        if(sum == n){
            res.push_back(make_pair(s, t));
        }
        sum -= s * s;
        ++s;
    }
    printf("%d\n", res.size());
    EACH(i, res){
        printf("%lld ", i->second-i->first);
        for(ll j=i->first; j<i->second; ++j){
            printf("%lld%c", j, j + 1 == i->second?'\n':' ');
        }
    }
    return 0;
}

2014-09-02

POJ 1759: Garland

POJ 蟻本

概要

N個の提灯が下がった糸を垂らす．片方の端点はAとし，他方をBとする．
このとき，糸は重力にしたがって垂れ下がる．
i番目の提灯の高さをH_iとすると，
H_1 = A, H_N = B,
H_i = (H_(i-1) + H_(i+1)) - 1
が成り立つ．
あるAが与えられたとき，全ての提灯の高さを0以上にするにはBを最小でいくつにすればよいか．

解法

Bの位置について二分探索．．．が差分方程式を解かないといけない．
$\Delta_i = H_{i+1}-H_i$
とすると，与式をいじいじして，
$\Delta_i = \Delta_{i-1} + 2$
を得る．したがって，
$H_i = H_1 + \sum_{k=1}^{i-1} \Delta_k = H_1 + (i-1)\Delta_1 + (i-1)^2$
H_1 = A，H_N = Bより， $\Delta_1$ が求められる．

他の人のを見ると，H_2について二分探索している．確かにこちらの方が簡単だ．

int N;
double A;
int main(){
    scanf("%d%lf\n", &N, &A);
    double lb = 0, ub = 1000000;
    for(int k = 0; k < 100; ++k){
        double mid = (lb + ub) / 2;
        double d1 = (mid - A) / (N - 1) - (N - 1);
        bool f = true;
        for(int i = 1; i < N; ++i){
            double p = A + (i-1)*d1 + (i-1)*(i-1);
            f = f && p >= 0;
        }
        if(f){
            ub = mid;
        }
        else{
            lb = mid;
        }
    }
    printf("%.2f\n", ub);
    return 0;
}

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番目のクレーンの座標系に乗っていると考えたらすっきり納得できた．
今では，なぜ勘違いをしていたのかわからない．．．