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
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"; }