某岛

… : "…アッカリ～ン . .. . " .. .
November 1, 2022

Educational Codeforces Round 138

Problem D. Letter Picking

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(2e3) + 9;
char s[N]; bool f[N][N];
int n;

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
Rush {
n = strlen(RS(s));

REP(i, n+1) f[i][i] = 0;

for(int l=2;l<=n;l+=2) {
REP(i, n-l+1) {
int j = i+l;
bool ll = f[i+2][j] || (s[i] > s[i+1]);
bool lr = f[i+1][j-1] || (s[i] > s[j-1]);
bool rl = f[i+1][j-1] || (s[j-1] > s[i]);
bool rr = f[i][j-2] || (s[j-1] > s[j-2]);
f[i][j] = (ll && lr) || (rl && rr);
}
}
puts(f[0][n] ? "Alice" : "Draw");
}
}
```

Problem E. Red-Black Pepper

```#include <lastweapon/io>
using namespace lastweapon;

const int N = int(3e5) + 9;
int a[N], b[N], x0; LL f[N];
int n;

LL exgcd(LL a, LL b, LL &x, LL &y){
if (!b){
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}

LL query() {
LL a, b, x, y; RD(a, b);
LL d = exgcd(a, b, x, y);
if (n % d) return -1;
x *= n/d*a; d = a/d*b;
x -= ceil(max(0ll, x-x0), d) * d;
x += max(0ll, x0-x) / d * d;
LL z = -1; if (x >= 0) checkMax(z, f[x]);
x += d; if (x <= n) checkMax(z, f[x]);
return z;
}

void init() {
RD(n); LL s = 0; REP(i, n) RD(a[i], b[i]), s += b[i];
REP(i, n) a[i] -= b[i]; sort(a, a+n, greater<int>());
f[0] = s; REP(i, n) f[i+1] = f[i] + a[i];
x0 = upper_bound(a, a+n, 0, greater<int>()) - a - 1;
}

int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
init(); Rush OT(query());
}
```