POJいろいろ8/3

3109
http://poj.org/problem?id=3109

座標圧縮+平面走査segtree。実装ややこしいはずだけど一発で通って気持ちがいい。実装ちゃんと練ればすんなりいくんだね。

3735
http://poj.org/problem?id=3735

1+B+B^2...の形が出てくるので行列の累乗和を貼って終了、と思ったらTLE。適当に定数倍であがいても通らない。
よくよく考えてみると定数項として一列行列を増やすと累乗和なんてやらずにいける。それで通るらしい。

3233
http://poj.org/problem?id=3233

3735で使った累乗和そのもの。

2674
http://poj.org/problem?id=2674

衝突があってもx座標の大きい順は変わらないことに注目する。
変な出力でWAだしてふざけんなよって思ったけど、コードも間違っていた…

2886
http://poj.org/problem?id=2886

BITの機能を拡張して累積和Sについてのlower_boundをできるようにする。BITの理解が深まった。
正負をうまく統合してやろうと思ったけど結局うまくいかず時間がかかった。普通に場合分けした方が早かった。

下は2886のコード

struct BIT { //1-origin!!!
	int n, b; vi bit;
	void init(int mx) {
		n = mx;
		b = 1;
		while(b * 2 <= n) b *= 2;
		bit = vi(n + 1, 0);
	}
	BIT(int mx = 0) { init(mx); } 

	ll get(int i) {
		ll s = 0;
		while(i > 0) { s += bit[i]; i -= i & -i; }
		return s;
	}
	void update(int i, ll x) {
		while(i <= n) { bit[i] += x; i += i & -i; }
	}

	int get_index(ll x) { //something like lower_bound(all(sum), a). O(logn)
		x--;
		int r = b;
		int res = 0;
		while(r > 0) {
			if((r | res) <= n) {
				int rv = bit[r | res];
				if(x >= rv) {
					x -= rv;
					res += r;
				}
			}
			r >>= 1;
		}
		return res + 1;
	}

	int range_sum(int a, int b) { //[a, b]
		return get(b) - get(a - 1);
	}
};

int N, S;
BIT bit;
char name[MAX_N][11];
int A[MAX_N];
int G[MAX_N];
int T[MAX_N];

int main() { //1-origin
	scanf("%d%d", &N, &S);
	rep(i, 1, N + 1) scanf("%s%d", name[i], &A[i]);
	bit.init(N);
	rep(i, 1, N + 1) bit.update(i, 1);

	int at = S;
	G[1] = at;
	rep(i, 1, N) {
		bit.update(at, -1);
		int a = A[at];
		if(a >= 0) {
			a %= (N - i);
		}
		else {
			a *= -1;
			a %= (N - i);
			a = N - i + 1 - a;
		}
		if(a == 0) a = N - i;
		if(a > N - i) a = 1;
		int tsum = bit.range_sum(at + 1, N);
		if(tsum >= a) {
			at = bit.get_index(N - i - tsum + a);
		}
		else {
			a -= tsum;
			at = bit.get_index(a);
		}
		G[i + 1] = at;
	}

	for(int i = 1; i <= N; i++) {
		for(int j = i; j <= N; j += i) {
			T[j]++;
		}
	}

	int res = -inf, rat = -1;
	rep(i, 1, N + 1) {
		if(res < T[i]) {
			res = T[i]; rat = i;
		}
	}
	printf("%s %d\n", name[G[rat]], T[rat]);

	return 0;