2014-09-08

POJ2155: Matrix

POJ 蟻本

概要

N次正方行列があり，初期状態ではすべての成分が0である．
T個のクエリが来て，内容は

(x1,y1),(x2,y2)で定まる矩形領域に反転操作を行う．
(x1,y1)の成分を答える

である．

解法

2次元のBITを用意する．これは，(1,1),(x,y)によって定まる矩形領域の値を合計したものを返す．
更新のときは，(x1,y1),(x1,y2+1),(x2+1,y1),(x2+1,y2+1)のそれぞれに1を加える．（中央二つは引き算のため．2を法とする演算であるから，加算と減算は等価である）
こうすると，(1,1),(x,y)の範囲の合計が(x,y)の値になる．

二次元平面上に矩形上に値vを足しこむとき，左下と右上にvをたし，左上と右下に-vを足しておいて最後にまとめて計算するテクニックをBITに応用したもの．

const int MAX_T = 50010;

int X, N, T;
int q[MAX_T];
int X1[MAX_T], Y1[MAX_T], X2[MAX_T], Y2[MAX_T];
int bit[1010][1010];

int get(int x, int y){
    int res = 0;
    int tx = x;
    while(y>0){
        x = tx;
        while(x>0){
            res = (res + bit[y][x]) % 2;
            x -= x & -x;
        }
        y -= y & -y;
    }
    return res;
}
void update(int x, int y, int v){
    int tx = x;
    while(y<=N){
        x = tx;
        while(x<=N){
            bit[y][x] = (bit[y][x] + v) % 2;
            x += x & -x;
        }
        y += y & -y;
    }
}

void solve(){
    memset(bit, 0, sizeof(bit));
    for(int i = 0; i < T; ++i){
        if(q[i] == 'Q'){
            int x = X1[i], y = Y1[i];
            printf("%d\n", get(x, y));
        }
        else{
            update(X1[i], Y1[i], 1);
            update(X1[i], Y2[i]+1, 1);    // v-1=v+1 (mod 2)
            update(X2[i]+1, Y1[i], 1);
            update(X2[i]+1, Y2[i]+1, 1);
        }
    }
}
int main(){
    scanf("%d", &X);
    for(;X>0;--X){
        scanf("%d%d", &N, &T);
        for(int i = 0; i < T; ++i){
            char buf[8];
            scanf("%s%d%d", buf, X1+i, Y1+i);
            q[i] = buf[0];
            if(q[i] == 'C'){
                scanf("%d%d", X2+i, Y2+i);
            }
        }
        solve();
        if(X > 1) printf("\n");
    }
    return 0;
}

2014-09-07

POJ 3109: Inner Vertices

POJ 蟻本

概要

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

2014-09-06

POJ 1990: MooFest

POJ 蟻本

概要

一次元座標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;
}

2014-09-04

POJ 2674: Linear World

POJ 蟻本

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

概要

線分の上を物体がある方向に向かって動く．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]);
    }
}

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