SRM593 Div1

easyだけ通った

easy : 絵を書くと、N * N全てを塗る場合でも3色で済むことがわかるので、二部グラフ判定するだけ. 六角座標はクソ(確信)

const int dx[] = {-1,0,1,1,0,-1};
const int dy[] = {1,1,0,-1,-1,0};

class HexagonalBoard{
    public:
	int n;
	vector<string> v;
	int st[60][60];

	bool dfs(int y, int x, int c){
	    st[y][x] = c;
	    rep(i, 6){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(!(ny >= 0 && ny < n && nx >= 0 && nx < n && v[ny][nx] == 'X')) continue;

		if(st[ny][nx] == c) return false;
		if(st[ny][nx] == 0 && !dfs(ny, nx, -c)) return false;
	    }

	    return true;
	}

	bool ch(){
	    bool ok = true;
	    rep(i, n){
		rep(j, n){
		    if(v[i][j] == '-') continue;
		    if(st[i][j] == 0){
			if(!dfs(i, j, 1)) ok = false;
		    }
		}
	    }
	    return ok;
	}

	int minColors(vector <string> b){
	    n = b.size();
	    v = b;
	    bool a1 = false, a2 = false;

	    memset(st, 0, sizeof(st));
	    rep(i, n){
		rep(j, n){
		    if(b[i][j] == '-') continue;
		    a1 = true;
		    rep(k, 6){
			int ny = i + dy[k];
			int nx = j + dx[k];
			if(ny >= 0 && ny < n && nx >= 0 && nx < n && b[ny][nx] == 'X') a2 = true;
		    }
		}
	    }
	    if(a1 == false) return 0;
	    if(a2 == false) return 1;
	    if(ch()) return 2;
	    return 3;
	}
};

Med :
まず、Sに含まれる方が最速で走り, Tに含まれる方が最遅で走る時またはその逆の時の、差の絶対値の大きい方がmaxdiff(S, T)となることがわかる。
次に式変形をすると
sum(B of S) - sum(A of T) = sum(B of all) - sum(A + B of T)
sum(A of S) - sum(B of T) = sum(A of all) - sum(A + B of T)
がわかるので、
部分集合で作りうるA + Bの和をdpで計算して調べるだけ。

class MayTheBestPetWin{
    public:
	int n;
	int sa, sb;
	int a[60], b[60], s[60];
	bool dp[1010010];

	int calc(vector <int> A, vector <int> B){
	    n = A.size();
	    sa = 0; sb = 0;
	    int ret = INT_MAX;
	    memset(dp, false, sizeof(dp));
	    dp[0] = true;

	    rep(i, n){
		a[i] = A[i]; b[i] = B[i];
		sa += a[i]; sb += b[i];
		s[i] = a[i] + b[i];
		for(int j = sa + sb; j >= 0; --j) if(dp[j]) dp[j + s[i]] = true;
	    }

	    for(int i = 0; i <= sa + sb; ++i) if(dp[i]) ret = min(ret, max(abs(sb - i), abs(sa - i)));

	    return ret;
	}
};