Atcoder abc229

發表於 更新於 分類於 ， Disqus： 文章字數： 2.9k 所需閱讀時間 ≈ 10 分鐘
G(二分)H(博弈论,非公平博弈论, surreal number)

https://atcoder.jp/contests/abc229/tasks

G - Longest Y

一个包含字符’Y’和’.’的长n字符串S,

可以操作[0,k] 次,交换S中的两个相邻字符

问可以得到的最终S的内部最长的连续Y的长度

范围

n 2e5

k 1e12

2s

1024mb

我的思路

考虑移动

最终假设是[l..r]

那么对于初始这些y的位置的大范围是[l0..r0]

那么一定可以分成两部分

[l0..m0][m0+1..r0]

一部分向右,一部分向左

显然有个点不需要动

如果选定了第i个点p[i]和期望个数c那么,移动代价为min( 左侧k0, 右侧k1个), k0+k1+1=c

= min(sum(p[i]-k0..p[i]-1) - sum(p[i-k0]..p[i-1]) + sum(p[i+1]..p[i+k1]) - sum(p[i]+1..p[i]+k1))

换个角度

所有值变成p[i]-cnt1[i]

那么就是找一个值, 尽量多的数变成它, 且代价和 <= K

显然每多一个,代价的增量是非严格递增的

是个凸函数(下凹)

但感觉, 这样看起来, 其实左侧右侧影响不大,而是距离影响更大,

所以直接枚举中点,二分距离(选定的点的最大距离) => 去计算距离和范围,以及点数范围

这里 < 距离的必选, >距离必定不选, =距离可选可不选

似乎就没了?

代码

https://atcoder.jp/contests/abc229/submissions/34483869

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)

ll read(){ll r;scanf("%lld",&r);return r;} // read

char s[200010];
ll k;

vector<int> v;
vector<ll> pre = {0};

tuple<ll,ll,ll> calc(ll x,ll d){ // value = x, distance = d , return { < d 的和, < d 的个数, =m的个数}
  // [x-d,x+d]
  int i  = lower_bound(v.begin(),v.end(),x    ) - v.begin();
  int i0 = lower_bound(v.begin(),v.end(),x-d  ) - v.begin();
  int i1 = lower_bound(v.begin(),v.end(),x-d+1) - v.begin();
  int i2 = lower_bound(v.begin(),v.end(),x+d  ) - v.begin();
  int i3 = lower_bound(v.begin(),v.end(),x+d+1) - v.begin();
  if(d == 0) return {0,0,i1-i0};
  // [i0 [i1 i  i2] i3]
  // [i1..i-1] + [i..i2-1]
  ll sum = (i-i1) * x - (pre[i] - pre[i1])
    + (pre[i2] - pre[i]) - (i2-i) * x;
  return {sum, i2-i1, (i1-i0)+(i3-i2) };
}

ll f(ll x){
  ll l = 0;
  ll r = max(x-v[0],v.back()-x)+1;
  while(l+1 < r){
    ll mid = (l+r)/2;
    (get<0>(calc(x, mid)) > k ? r : l) = mid;
  }
  auto [sum, c0, c1] = calc(x, l);
  return c0 + (l==0 ? c1 : min((k-sum)/l,c1));
}

int main(){
  scanf("%s",s);
  int n = strlen(s);
  k = read();
  rep(i,0,n) if(s[i] == 'Y'){ v.push_back(i-v.size()); }
  rep(i,0,v.size()) pre.push_back(pre.back() + v[i]);
  ll ans = 0;
  for(auto x:v) ans = max(ans, f(x));
  printf("%lld\n",ans);
  return 0;
}

H - Advance or Eat

n 行n列棋盘,每个格子可能三种状态 空/白/黑, 题目提供

T和S交替游戏

T, 将一个白色向上移动一格(不能重叠不能出棋盘) 或者 吃掉一个黑色

S, 将一个黑色向上移动一格(不能重叠不能出棋盘) 或者 吃掉一个白色

无法行动的输掉

范围

n <= 8

2s

1024mb

我的思路

显然需要博弈论

然后不同列之间没有关系

3^8 = 6561

如果每个状态算出sg函数也就做出来了?

但这里好像不是公平的游戏

想让对手不能走

通过移动自己的向上并不会产生影响, 因为如果原来在前面的不受影响, 在后面的要么不受影响, 要么可移动的长度更长

你能走的步数, 在不考虑被删除的情况下, 你能走的步数就是每个向上移动的步数+对手棋子数

而对手的棋子数最终都会变成你的步数

但你向上移动, 可以通过移动掉对手的棋子来增加步数, 也会受到对手的移动而减少

因此显然如果你当前指定一列要移除一个,几个对手同色的连续(可以有空格,没有其它颜色), 你移动掉的一定是最下方的那个, 更好的方案不会比这个好

f(T/S) = 对面个数+ sum( pos[i] - cnt[i]), 位置-同色第几个

游戏结束时,一定一方的棋子被完全移除了

每次T 做移动,会让一个pos-1, f(T) -1,

每次T 做删除,会让对面一个棋子消失f(T) -1,f(S)中移除某个(pos-cnt)

S 是对称的

例如游戏结束时,B被删完了,W还有剩余,f(T) = 0, f(S) > 0

T 输, 所以

可以看成每次你的值-1,你可以降低对面一个值

谁先0谁输

考虑f(T) 和 f(S) 的差的变化

所以直接贪心,每次删除对手一个最大的即可?

写了以后发现并不对

https://atcoder.jp/contests/abc229/submissions/34484702

问题在于, 当需要移W或删B时

B都是无法移动,意味删除代价为1, 移动也是1, 删B->对手删->无法移动 肯定是比 移动->对手删->删B 多步的,而这种情况, 移动不一定是能操作的

题解

哦!!! 还是SG

显然根据SG的知识, DAG上面一些点上有多个棋子, 交替操作,每次沿着一个边移动一个棋子, 不能操作的输掉

然后就是mex 和sg函数

然后也是需要Impartial game, 可以转换成DAG, 否则需要其它的额外方法

如何处理 Partisan Games

考虑同样DAG,但是边染色了(黑/白), 但是第一个玩家,只能走白边, 第二个玩家只能走黑边

但是是对每个点给予一个评估实数

对于第一个玩家(只走白)来说,每个点的值越大越好, 对于第二个玩家(只走黑)来说,每个点的值越小越好, 同时每个值随着走白边下降,走黑边增加

如何计算评估值

如果连出的边的点存在未定义,则当前未定义

否则的话 max(白出点) < eval(当前) < min(黑出点), 如果不存在这样的值 则当前为未定义

当上述存在方案时, 如果有整数满足, 则定义为绝对值最小整数

否则用分母为2的幂次,且分母最小的分数来表示

如何判断赢家

计算所有点上的值的和, 如果为正,第一个赢, 如果 <= 0, 则第二个赢

证明

对于所在的和为正时, 轮到第一个玩家操作

如果 为正, 那么可以找到一个白色路径, 让结果 >= 0

假设和的2的幂次为w, 则加和中至少一个棋子所在的分母的2的幂次w1大于等于这个幂次w(-1/2+1/2 = 0/1,-1/2+1=1/2), 那么让这个值沿着白边走, 则它的变化就是1/2^(>=w1)(因为上面的分数赋值的设计关系,最大的白色和它关系), 所以 ?/2^w - 1/2^(>=w1) >= 0

max(=1/4) < eval < min(1) => eval = 1/2

如果 为<= 0, 则一次白色边移动后 一定为负数

对于第二个玩家所在

走黑边是同理的,

因此 如果 正 => (>=0) => 正 => (>=0) ...

如果 (<=0) => (<0) => (<=0) => (<0) ...

可以看成不变量会保持了

至此证明了, 如此设置eval,以及 先后手的目标分别是让值更大, 和让值更小, 会有这个结果, 一个是 单次操作和总答案的关系是否有局部性? 第二格式为啥这个目标和原不能移动 是等价?

如何和原题联系起来?

TODO 虽然移动和结束状态等价, 为啥分别追求larger和smaller是等价的?

追求larger和smaller 为何与单步的保证上面变化序列等价

显然 如果 正 -> (<0) 那么对手一定不会让你再回到正, 所以为了最大,一定要正 => (>=0), (对称显然)

但是这里并没有说一定要 正 => (最大的>=0), 上面相当于证明了方案存在性

就是如果一个追求larger,一个追求smaller, 那么必然是按照这两种走法去走, 所以都能维持自己的状态

原题

就是不同列之间无关, 建立3^n的图, 然后算每点的eval值

然后 需要证明任何点都能有值, 其实可以按照DAG的拓扑顺序赋值, v 以前的假设都有值了

那么需要证明的就是 最大白出边v->a < 最小黑出边v->b

  1. 如果这两个边k 对应操作都是 删除一个对手的子, 那么有v 吃两个子的状态c,因为 v白a黑c, v黑b白c,满足 eval(a) < eval(c) < eval(b)
  2. 如果a和b对应的实际操作 不会互相影响, 可以先a再b和先b再a,都和上面同理
  3. 考虑会互相影响, 也就是一个删掉对手棋子(a), 另一个操作恰好是移动这个棋子(b), 但这种情况会出现 b -> a的边, 因此eval(a) < eval(b)

因此证明了可以建图,且每个点都有值

学了下snuke的代码

https://atcoder.jp/contests/abc229/submissions/27565297

有eval(状态) = -eval(状态翻转B/W)

因为 从状态在DAG上走 的结构, 和其翻转的状态在DAG上走的结构对称

所以如果它依赖的点也满足 互为相反数, 那么它就满足互为相反数(根据依赖关系, 每次取2幂次最小的绝对值最小,得证)

然后这里用long long 而不是double

这里想知道的是one = 1ll << 30 有啥办法推得吗, 虽然实际运算可以得到最高幂次, 如果不算的话有办法推得吗?

代码

TODO url

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
#define pb push_back

int read(){int r;scanf("%d",&r);return r;} // read
const ll ONE = 1ll<<7; // 1<<30 不用浮点数. TODO 30 为什么够?, 实际跑下来 1<<7就够了
const ll INF = 1ll<<60; // 实际跑下来 最大x是1024


ll eval(ll l, ll r) { // l < ret < r
  assert(l < r);
  if (l < 0 && r > 0) return 0;
  if (l < 0) return -eval(-r,-l);
  ll b = ONE; // 1/2^k
  while (1) { // 幂次最小的 绝对值最小 的 l < x < r
    ll x = (l/b+1)*b; //  0 <= l < x <? r
    if (x < r) {
      return x;
    }
    b >>= 1; // k+=1
  }
  assert(false);
  return 0;
}

map<string,ll> mp; // 字符 -> eval 记忆化
ll f(string s) {
  if (mp.count(s)) return mp[s]; // 记忆化
  vector<ll> d; // max(白边), min(黑边)
  rep(ri,0,2) { // 第一轮计算 移W,删B, 第二轮翻转计算 移B删W
    ll x = -INF;
    rep(i,0,s.size()) {
      if (s[i] == 'B') { // 删除B
        string ns = s;
        ns[i] = '.';
        x = max(x,f(ns));
      }
      if (s[i] == 'W' && i && s[i-1] == '.') { // W 上移
        string ns = s;
        ns[i] = '.'; ns[i-1] = 'W';
        x = max(x,f(ns));
      }
    }
    d.push_back(ri ? -x : x);
    rep(i,0,s.size()) if (s[i] != '.') s[i] ^= 'B'^'W'; // 翻转B,W
  }
  return mp[s] = eval(d[0],d[1]); // d[0] < mp[s] < d[1], 没有后置状态则 -INF < mp[s] < INF, 而对于只是一方没有后置状态的, 可能是 0 < max < mp[s], mp[s] < min < 0 产生的非零值
}

int main() {
  int n = read();
  vector<string> s(n); // 每列
  rep(i,0,n) {
    string t;
    cin >> t;
    rep(j,0,n) s[j] += t[j];
  }
  ll x = 0;
  rep(i,0,n) x += f(s[i]);
  printf("%s\n",x > 0?"Takahashi":"Snuke");
  return 0;
}
// https://atcoder.jp/contests/abc229/submissions/27565297

总结

G

没啥难的

H

算是会了基础的SG函数, 但是对于这种Partisan Games还是没学过, 又学了一手, 另外加深一下对博弈论建立DAG的理解

然后这里的 eval存在性需要保证

然后上面证明的细节还是不会(据说要 surreal number相关知识, orz)

TODO < winning ways for your mathematical plays >

TODO < surreal number >

参考

官方题解