SRM 595 DIV1 本番 - antaの競技プログラミング練習日記

朝のSRM。少し眠くて心配だったが緊張で眠気は吹き飛んだ。

Coding

900がMedより簡単なこと稀にあるよなーとか考え、Medより前に900を開こうと考えた。

Easy (250)

最初に、「2^(他の[L[j],R[j] ]に被覆されないiの数)？」と考えた。実際にはこれは合っていた。
しかしどうもそれが納得できなくて、罠ありそうだなーと考えてしまった。
次に「同じ色で塗らないといけないセルをまとめて、そのグループの数を数えればいい？」とおもった。
これはUnionFind(無駄に動的)でやった。
何も塗られない場所のグループは1、それ以外は2を答えに掛け算する。
結構テストして、心配ながらも提出。

Hard (900)

まず期待値といえば期待値の線形性だよな、と考えた。
それには凸包を分解する。三角形分解を考えて、それを足せばいいんじゃないか？と思った。
しかし肝心の「この三角形が凸包の三角形分解」になる確率がわからず、さらにそれは重複して数えてしまうことに気づいた。
そしてわからなくなった。Mediumが時間かかるもので解けないとだめだと思い、あきらめてMediumへ。

Medium (500)

とりあえず左右を別個に「left[i][j] = 区間[i,j)で右側の連続するG(途中でminGreen個以上出てるならminGreenで固定)」と「right[i][j] = 区間[i,j)で左側の連続するG(同上)」というように2つ計算すればいいと、割と素直に考えられた。
これの計算は普通に区間を拡張してく感じで計算してけばいい。
さて、左と右を組み合わせなければいけない。
左の区間を[i,j]とすると、この区間に対応できる右の区間は{ [k,l) | j <= k, right[k][l] >= minGreen - left[i][j] }となる。これを高速に数えるにはどうしたらいいだろうか？
この答えも素直に思いつけた。Fenwick木を動的に使えばいい。tをFenwick木とする。
jを右端から左へ移動させる。ループ中では全てのlに対してtのright[j][l]の位置をインクリメントする。
その後各i,jに対してtの[minGreen - left[i][j],∞)のsumを求めればよい。このsumが答えとなる。
テストを何回かした。その時システムが不調でテストに時間がかかって、それで30ptくらい減った。しかしテストは重要なので良い。落ちたら0点なのだから、数十点で一喜一憂してはいけない。

Challenge

4人落とされてたけど、読んでもなんで落ちたのかわからなかった。その程度のChallenge力。これは改善すべき。

SystemTest

通ってよかった。

結果

Easy: 204.51 / 250
Medium: 379.92 / 500
Hard: Opened / 900
Challenge: 0/0 = +0
Division Place: 23/455
Rating: 1820→1957

練習を続けよう。Challenge練習もしたいところ。
今回はMediumを速く解けたのでよかったけれど、Hardを先に開くのはやはり自分には少し早い気もする。やめよう。

コード

謎コード

Easy

#include <vector>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
using namespace std;
typedef long long ll;   
struct UnionFind {
	vector<int> data;
	UnionFind(int size_) : data(size_, -1) { }
	bool unionSet(int x, int y) {
		x = root(x); y = root(y);
		if (x != y) {
			if (data[y] < data[x]) swap(x, y);
			data[x] += data[y]; data[y] = x;
		}
		return x != y;
	}
	bool findSet(int x, int y) { return root(x) == root(y); }
	int root(int x) { return data[x] < 0 ? x : data[x] = root(data[x]); }
	int size(int x) { return -data[root(x)]; }
};

struct LittleElephantAndIntervalsDiv1 {
	long long getNumber(int M, vector <int> L, vector <int> R) {
		int n = L.size();
		UnionFind uf(M+1);
		rer(p, 1, M) {
			bool white = true;
			rep(i, n) white &= !(L[i] <= p && p <= R[i]);
			if(white) uf.unionSet(0, p);
		}
		rer(p, 1, M) rer(q, 1, M) {
			bool b = true;
			rep(i, n) {
				bool x = L[i] <= p && p <= R[i], y = L[i] <= q && q <= R[i];
				if(x && y)
					b = true;
				if(x ^ y)
					b = false;
			}
			if(b) uf.unionSet(p, q);
		}
		ll r = 1;
		rer(p, 0, M) if(uf.root(p) == p) {
			if(uf.findSet(p, 0)) r *= 1;
			else r *= 2;
		}
		return r;
	}
};

Medium

#include <string>
#include <vector>
#include <cstring>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
#define each(it,o) for(auto it = (o).begin(); it != (o).end(); ++ it)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef long long ll;

struct FenwickTree {
	typedef ll T;
	vector<T> v;
	FenwickTree(int n): v(n, 0) {}
	void add(int i, T x) {
		for(; i < v.size(); i |= i+1) v[i] += x;
	}
	T sum(int i) {	//[0, i)
		T r = 0;
		for(-- i; i >= 0; i = (i & (i+1)) - 1) r += v[i];
		return r;
	}
	T sum(int left, int right) {	//[left, right)
		return sum(right) - sum(left);
	}
};

struct LittleElephantAndRGB {
	long long getNumber(vector <string> list_, int minGreen) {
		string s;
		each(i, list_) s += *i;
		int n = s.size();
		static short dpleft[2501][2501], dpright[2501][2501];
		mset(dpleft, 0);
		rep(i, n) {
			dpleft[i][i] = 0;
			rer(j, i+1, n) {
				int x = dpleft[i][j-1];
				if(x == minGreen) dpleft[i][j] = minGreen;
				else if(s[j-1] == 'G') dpleft[i][j] = x + 1 >= minGreen ? minGreen : x + 1;
				else dpleft[i][j] = 0;
			}
		}
		mset(dpright, 0);
		rer(j, 1, n) {
			dpright[j][j] = 0;
			for(int i = j-1; i >= 0; i --) {
				int x = dpright[i+1][j];
				if(x == minGreen) dpright[i][j] = minGreen;
				else if(s[i] == 'G') dpright[i][j] = x + 1 >= minGreen ? minGreen : x + 1;
				else dpright[i][j] = 0;
			}
		}
		FenwickTree t(minGreen+1);
		ll r = 0;
		for(int j = n; j >= 1; j --) {
			rer(l, j+1, n) t.add(dpright[j][l], 1);
			rep(i, j) {
				int x = dpleft[i][j];
				r += t.sum(minGreen - x, minGreen+1);	//j <= l, dpright[l][k] >= minGreen - x
			}
		}
		return r;
	}
};