POJ 2441: Arrange the Bulls

概要

牡牛がN頭いて,M個のコートに1頭ずつ割り当てたい.
牡牛はそれぞれ好むコートが決まっている.
割り当て方は何通りあるか.

解法

bitDPやるだけ.
ただし,愚直に実装するとMLEを起こすはずなので,配列の再利用をする.

int N, M;
int P[30];
int B[30][30];
int dp[2][1 << 20];
int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < N; ++i){
        scanf("%d", P+i);
        for(int j=0;j<P[i];++j){
            scanf("%d", B[i]+j);
            --B[i][j];
        }
    }
    memset(dp, 0, sizeof(dp));
    int *prev = dp[0], *next = dp[1];
    prev[0] = 1;
    for(int i = 0; i < N; ++i){
        memset(next, 0, sizeof(dp[0]));
        for(int s = 0; s < (1 << M); ++s){
            if(!prev[s]) continue;
            for(int j = 0; j < P[i]; ++j){
                int f = 1 << B[i][j];
                if(!(f & s)){
                    next[s | f] += prev[s];
                }
            }
        }
        swap(prev, next);
    }
    int res = 0;
    for(int i = 0; i < (1 << M); ++i){
        res += prev[i];
    }
    printf("%d\n", res);
    return 0;
}

POJ 2886: Who Gets the Most Candies?

POJ100問AC記念.

概要

N人の子供が一枚ずつカードを持っていて,輪になって並んでいる.
K番目の子供からスタートする.まず,現在選んでいる子供を輪から除外する.除外した子供が持っていたカードに書かれている番号だけずれた子供を選ぶ.これを繰り返す.
i番目の操作で除外された子供は,iの約数の数だけキャンディをもらえる.
一番多くキャンディをもらえる子供は誰か.

解法

約数の個数は篩みたいにするとうまく計算できる.
子供を除外してずれる番号は,BITをうまく利用して管理する.
次に選ぶ子供はBIT上で二分探索をして求めることができる.

注意

同じ個数を得る子供は,先に輪の外に出た方を出力.
カードの番号が負の時の扱いに注意

const int MN = 500010;

int N, K;
int A[500010];
char name[500010][16];
int bit[500010];
bool isPrime[500010];
ll F[500010];

void update(int i, int v){
	++i;
	while(i <= N){
		bit[i] += v;
		i += i & -i;
	}
}
int get(int i){
	++i;
	int res = 0;
	while(i>0){
		res += bit[i];
		i -= i & -i;
	}
	return res;
}
int find(int num){
	int lb = -1, ub = N;
	while(ub - lb > 1){
		int mid = (ub + lb) / 2;
		if(get(mid)-1 < num){
			lb = mid;
		}
		else{
			ub = mid;
		}
	}
	return ub;
}
void solve(){
	memset(bit, 0, sizeof(bit));
	for(int i=0;i<N;++i)update(i,1);
	int mx = 0, ridx = 0, idx = --K;

	for(int k=0;k<N;++k){
		if(F[k+1] > mx){
			mx = F[k+1];
			ridx = idx;
		}
		update(idx, -1);
		if(k == N - 1) break;
		int num = N - k - 1;
		if(A[idx] > 0){
			K = (K + A[idx] - 1) % num;
		}else{
			K = (K + A[idx]) % num;
		}
		if(K < 0) K += num;
		idx = find(K);
	}
	printf("%s %d\n", name[ridx], mx);
}
main(){
    for(int i = 0; i < MN; ++i) F[i] = 1;
    for(int i = 2; i < MN; ++i) if(!isPrime[i]){
		for(int j = i; j < MN; j += i){
			int k = 0;
			for(int l=j; l % i == 0; l /= i, ++k);
			isPrime[j] = true;
			F[j] *= k + 1;
		}
    }
	while(~scanf("%d%d", &N, &K)){
		for(int i=0;i<N;++i){
			scanf("%s%d", name+i, A+i);
		}
		solve();
	}
	return 0;
}

POJ2155: Matrix

概要

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

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