SRM 578 DIV1 本番

1文字バグ＋別のバグが、巧妙に問題なかったぱたーん

Coding

Easy (250)

「ガチョウならその周囲もガチョウ」<->「周囲dist以内の鳥と『同じ種類』」が言える(鳥は2種類なので)。
推移的な「同じ」といえばUnionFind。
そこでUnionFindでグループ分けをする。
このグループ内は必ず同じ種類で、別のグループならば独立。
あとは(i番目までのグループで, ガチョウが1匹以上, ガチョウが偶数)を状態に持つDPをした。
235.32ptで、結構速く書けたつもりだったが、同じ部屋のtouristさんが243.42ptで通してて、「やば」と感じた。
他の人のコードを見ると、普通に累乗の式になるようだ。

Medium (500)

まず、ある区間が別の区間に含まれている場合、小さい方の区間は考えなくて良い。
そうしたら区間にうまく順序がつくので、(位置, この位置までの制約は1つ分満たしてる, この位置までの制約は2つ分満たしてる)というDPをした。
しかし、((dp[...] += dp[...]) %= MOD)を((dp[...] += dp[...]) &= MOD) にするという1文字バグによって、正確な数字はわからないが数十分はデバッグに費やされた。
結局残り3分になって初めて気づき、焦りながらSubmit。
その後見返してみると明らかなバグな気がするものがあり、「落ちるな」と思っていたが、後から考えてみると、巧妙に問題なかった。
しかし焦って何故かさらに、考えがアホすぎる間違えをして、自分の「嘘撃墜ケース」を考えだして絶望していた。

Challenge

しない

SystemTest

Med落ちると思ってたら通って、自分の「嘘撃墜ケース」はアホすぎることに気づいて、しかもバグは巧妙に問題なくて、まあよかった。

結果

Easy: 235.32/250
Medium: 191.23/500
Challenge: 0/0 = +0
Division Place: 79/636
Rating: 2182→2210

コメント

赤くなったよ。よかったね。

コード

Easy

#include <string>
#include <vector>
#include <cstring>
#include <algorithm>
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define pb(x) push_back(x)
#define mset(m,v) memset(m,v,sizeof(m))
using namespace std;
typedef vector<int> vi;  

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

const int MOD = 1000000007;
int dp[2555][2][2];
struct GooseInZooDivOne {
	vi v;
	int rec(int i, bool nonzero, int evenodd) {
		if(dp[i][nonzero][evenodd] != -1)
			return dp[i][nonzero][evenodd];
		int r = 0;
		if(i == v.size()) {
			r = nonzero && evenodd == 0;
		}else {
			(r += rec(i+1, nonzero, evenodd)) %= MOD;
			(r += rec(i+1, true, (evenodd+v[i])%2)) %= MOD;
		}
		return dp[i][nonzero][evenodd] = r;
	}
	int count(vector <string> field, int dist) {
		int h = field.size(), w = field[0].size();
		UnionFind uf(h*w);
		int cc = 0;
		rep(i, h) rep(j, w) if(field[i][j] == 'v') {
			cc ++;
			rep(ii, h) rep(jj, w) if(abs(i - ii) + abs(j - jj) <= dist)
			if(field[ii][jj] == 'v')
				uf.unionSet(i*w+j, ii*w+jj);
		}

		rep(i, h) rep(j, w) if(field[i][j] == 'v')
			if(uf.root(i*w+j) == i*w+j)
				v.pb(uf.size(i*w+j));
		mset(dp, -1);
		return rec(0, false, 0);
	}
};

Medium

#include <string>
#include <vector>
#include <algorithm>
#include <sstream>
#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 reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
#define each(it,o) for(__typeof((o).begin()) it = (o).begin(); it != (o).end(); ++ it)
#define all(o) (o).begin(), (o).end()
#define pb(x) push_back(x)
#define mp(x,y) make_pair((x),(y))
#define mset(m,v) memset(m,v,sizeof(m))

using namespace std;
typedef vector<int> vi;  typedef vector<pair<int,int> > vpii;

typedef vector<string> vs; 

const int MOD = 1000000007;
struct WolfInZooDivOne {
	vi parse(const vs &v) {
		string s;
		each(i, v) s += *i;
		stringstream ss(s);
		int x;
		vi r;
		while(ss >> x) r.pb(x);
		return r;
	}
	int count(int N, vector <string> Ls, vector <string> Rs) {
		vi LL = parse(Ls), RR = parse(Rs);
		int m = LL.size();
		rep(i, m) RR[i] ++;
		vpii s;
		rep(i, m) s.pb(mp(LL[i], RR[i]));
		sort(all(s));
		s.erase(unique(all(s)), s.end());
		vpii t;
		rep(i, s.size()) {
			bool ok = true;
			rep(j, s.size()) if(i != j)
				ok &= !(s[j].first <= s[i].first && s[i].second <= s[j].second);
			if(ok) t.pb(mp(s[i].first, s[i].second));
		}
		static int right[301];
		mset(right, 0);
		rep(i, t.size()) {
			reu(j, t[i].first, (i+1 == t.size() ? N : t[i+1].first))
				right[j] = t[i].second;
				//ここで、右端が被覆されてない時にもt[右端]がおかしくなる
				//でも、それはたかだか1回分、というか、だから、問題なかった
		}
		static int dp[2][301][301];	//dp[i][j][k] = iまで行った時、jまでに1匹、kまでには2匹いることが確定
		mset(dp, 0);
		dp[0][0][0] = 1;
		int cd = 0, nd = 1;
		rep(i, N) {
			memset(dp[nd], 0, sizeof(*dp));
			rer(j, 0, N) rer(k, 0, N) if(dp[cd][j][k]) {
				(dp[nd][j][k] += dp[cd][j][k]) %= MOD;
				if(k <= i) {
					(dp[nd][right[i]][j] += dp[cd][j][k]) %= MOD;	//ここを &= MOD にしていた…
				}
			}
			swap(cd, nd);
		}
		int r = 0;
		rer(j, 0, N) rer(k, 0, N) (r += dp[cd][j][k]) %= MOD;
		return r;
	}
};