POJ 3109: Inner Vertices

概要

2次元格子上においてある黒い石の情報が与えられる．
ある格子点において，x方向，y方向共に黒い石に挟まれているならそこにも黒い石を置く．
最終的に格子上においてある黒い石の個数はいくつか？

解法

扱いやすいように座標圧縮をしておく．
各x座標について，そのx座標をもつ最小(最大)のy座標を計算．
y座標についても同様の操作を行う．この時，「同じy座標をもつ中で最小（最大）のx座標の点で線分の追加（削除）をする」というイベントにして管理する．

x座標の小さい方から，縦方向の範囲をBITに足しこむ．線分の追加・削除のところで点の個数をカウントするとうまくいく．

コードが雑で，変な使い回しをしているためわかりにくい．

typedef int Type;
struct Fenwick{
    vector<Type> bit;
    Fenwick(int n){
        bit = vector<Type>(n + 1);
    }
    void update(int i, Type v){
        int n = bit.size();
        ++i;
        while(i <= n){
            bit[i] += v;
            i += i & -i;
        }
    }
    Type get(int i){
        Type res = 0;
        ++i;
        while(i > 0){
            res += bit[i];
            i -= i & -i;
        }
        return res;
    }
};

int n, nx, ny;
pair<int, int> p[200010];
int xl[100010], yl[100010];
int sx[100010], sy[100010];
int ex[100010], ey[100010];
Fenwick bit(100010);
int main(){
    scanf("%d", &n);
    for(int i = 0; i < n; ++i){
        scanf("%d%d", xl+i, yl+i);
        p[i] = make_pair(xl[i], yl[i]);
    }
    sort(xl, xl+n);
    nx = unique(xl, xl+n) - xl;
    sort(yl, yl+n);
    ny = unique(yl, yl+n) - yl;

    for(int i = 0; i < n; ++i){
        sx[i] = sy[i] = 200010;
        ex[i] = ey[i] = 0;
    }
    for(int i = 0; i < n; ++i){
        p[i].first = lower_bound(xl, xl+nx, p[i].first) - xl;
        p[i].second = lower_bound(yl, yl+ny, p[i].second) - yl;
        sy[p[i].first] = min(sy[p[i].first], p[i].second);
        ey[p[i].first] = max(ey[p[i].first], p[i].second);
        sx[p[i].second] = min(sx[p[i].second], p[i].first);
        ex[p[i].second] = max(ex[p[i].second], p[i].first);
    }
    for(int i = 0; i < ny; ++i){
        p[2*i] = make_pair(sx[i], i);
        p[2*i+1] = make_pair(ex[i], i+ny);
    }
    ll cnt = 0;
    int idx = 0;
    sort(p, p+ny*2);
    for(int i = 0; i < nx; ++i){
        while(idx < ny * 2 && p[idx].first == i && p[idx].second < ny){
            int y = p[idx].second;
            cnt -= bit.get(y);
            ++idx;
        }
        bit.update(sy[i], 1);
        bit.update(ey[i]+1, -1);
        while(idx < ny * 2 && p[idx].first == i){
            int y = p[idx].second - ny;
            cnt += bit.get(y);
            ++idx;
        }
    }
    printf("%d\n", cnt);
    return 0;
}

POJ 1990: MooFest

概要

一次元座標x[i]と，値v[i]が与えられる．iとjの間の通信コストはmax(v[i],v[j])*|x[i]-x[j]|である．コストの総和を求めよ

解法

座標でソートしておく．
各iについて，BITを用いてv[i]以下であるiより小さい場所の座標の総和とそのような場所の個数を計算する．

const int M = 20010;
int N;
pair<ll, ll> c[20010];

ll bit1[20010], bit2[20010];

void init(){
	memset(bit1, 0, sizeof(bit1));
	memset(bit2, 0, sizeof(bit2));
}
pair<ll,ll> sum(int x){
	ll r1 = 0, r2 = 0;
	while(x > 0){
		r1 += bit1[x];
		r2 += bit2[x];
		x -= x & -x;
	}
	return make_pair(r1, r2);
}
void add(int x, ll v){
	while(x < M){
		bit1[x] += v;
		bit2[x] += 1;
		x += x & -x;
	}
}

main(){
	scanf("%d", &N);
	for(int i = 0; i < N; ++i){
		ll v, x;
		scanf("%lld%lld", &v, &x);
		c[i] = make_pair(x, v);
	}
	sort(c, c + N);
	ll res = 0LL;
	init();
	for(int i=0;i<N;++i){
		//printf("%lld,%lld\n", c[i].first, c[i].second);
		pair<ll, ll> r = sum(c[i].second);
		//printf("[%lld, %lld]\n", r.first, r.second);
		res += c[i].second * (r.second*c[i].first-r.first);
		add(c[i].second, c[i].first);
	}
	//printf("%lld\n", res);
	init();
	for(int i=N-1;i>=0;--i){
		pair<ll, ll> r = sum(c[i].second-1);
		res += c[i].second * (r.first-r.second*c[i].first);
		add(c[i].second, c[i].first);
	}
	printf("%lld\n", res);
	return 0;
}

POJ 2674: Linear World

思いがけないところではまったのでメモ．

概要

線分の上を物体がある方向に向かって動く．2つの物体が衝突すると反対に動く．
一番最後に落ちる物体の名前とその時間を求める．

解法

蟻本の蟻と似た考え方．最後に落ちるものを特定するには，左側にどれだけ落ちる物体があるか数えればいい．左右の位置関係は保存されるので，左側の方にあるのが左側に落ちる．

はまったのは，最小値を0からスタートして，インデックスを-1にしていたこと．
落ちる時間が0のときバグってた．

int N;
double L, V;
char D[32010];
double P[32010];
char str[32010][256];
int main(){
    for(;;){
        scanf("%d", &N);
        if(N == 0) return 0;
        scanf("%lf%lf", &L, &V);
        for(int i = 0; i < N; ++i){
            char buf[8];
            scanf("%s%lf%s", buf, P+i, str[i]);
            D[i] = tolower(buf[0]);
        }
        double res = -eps;
        int idx = -1;
        int l = 0;
        for(int i = 0; i < N; ++i){
            double t = L - P[i];
            if(D[i] == 'n' || D[i] == 'N'){
                t = P[i];
                ++l;
            }
            if(t > res){
                res = t;
                idx = i;
            }
        }
        res /= V;
        if(D[idx] == 'p' || D[idx] == 'P')  idx = l;
        else                                idx = l - 1;
        printf("%13.2f %s\n", (int)(res*100)/100.0, str[idx]);
    }
}

POJ 3185: The Water Bowls

概要

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;
}

POJ 1222: EXTENDED LIGHTS OUT

ほろ酔いコーディング

概要

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;
}

POJ 2739, POJ 2100

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;
}

POJ 1759: Garland

概要

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の位置について二分探索．．．が差分方程式を解かないといけない．

とすると，与式をいじいじして，

を得る．したがって，

H_1 = A，H_N = Bより，が求められる．

他の人のを見ると，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;
}