AGC020

https://beta.atcoder.jp/contests/agc020

A
A-Bの偶奇です

B
条件を満たすものは区間で表せるので端の値を持てばいいです。

C
和をSとしてS/2以上で一番小さいものを選べばいいです。証明はSの部分列をA、B=S/Aとするとsum(A)<=S/2,sum(B)>=S/2となることからです。
bitのdpでできて、64倍高速化できます。
64倍高速化ってこうやるのか…

int N;
int A[MAX_N];
bitset<2000 * 2000 + 10> dp[2]; 

void solve() {
	cin >> N;
	rep(i, 0, N) cin >> A[i];
	dp[0][0] = 1;
	int s = 0;
	int now = 0, nex = 1;
	rep(i, 0, N) {
		dp[nex] = dp[now] << A[i];
		dp[nex] |= dp[now];
		swap(now, nex);
		s += A[i];
	}
	s = (s + 1) / 2;
	for(int i = s; ; i++) {
		if(dp[now][i]) {
			cout << i << "\n";
			return;
		}
	}
}

E
sの圧縮の仕方をg(s)、そのうち(s')*nで表せる方法をf(s)としてmap, bool>でdpします。
sとしてありうるものは少なそうだなぁと思ってそのままコードにしたら通ってしまいました…

でもよくよく考えてみると、f(s)の遷移先g(s')は|s|/2>=|s'|を満たすからですね。

map<vi, ll> G;
map<vi, ll> F;

ll loopf(vector<int> vec);

ll loopg(vector<int> vec) {
	int n = sz(vec);
	if(G.find(vec) != G.end()) return G[vec];

	vector<vl> f(n + 1, vl(n + 1, 0));
	rep(i, 0, n) {
		rep(j, i + 1, n + 1) {
			if(i == 0 && j == n) continue;
			f[i][j] = loopf(vi(vec.begin() + i, vec.begin() + j));
		}
	}
	vl dp(n + 1, 0);
	dp[0] = 1;
	rep(i, 1, n + 1) {
		rep(j, 0, i) ADD(dp[i], dp[j] * f[j][i] % mod);
	}
	return G[vec] = (dp[n] + loopf(vec)) % mod;
}

ll loopf(vector<int> vec) {
	int n = sz(vec);
	if(n == 1) {
		if(vec[0] == 0) return 1;
		else return 2;
	}
	if(F.find(vec) != F.end()) return F[vec];

	ll ans = 0;
	rep(i, 1, n) {
		if(n % i) continue;
		vi res(i, 1);
		rep(j, 0, n) {
			res[j % i] &= vec[j];
		}
		ADD(ans, loopg(res));
	}
	return F[vec] = ans;
}

void solve() {
	string str;
	cin >> str;
	int n = sz(str);
	vector<int> vec(n);
	rep(i, 0, n) vec[i] = str[i] - '0';
	cout << loopg(vec) << "\n";
}