Znzryb's Blog
0%

CF Round 1101 Div2 C2 - Seating Arrangement

Posted on Edited on

题目大意

有 x 张桌子，每张桌子有 s 个座位。朋友按固定顺序排队进场，Alice 对每个人只能选择安排到某张桌子，或者把他踢出派对；一旦坐下，之后不能移动。

每个人有三种性格：

  • I：只能坐在当前为空的桌子上。

  • E：只能坐在当前非空且未坐满的桌子上。

  • A：可以坐在任意未坐满的桌子上。

目标是在不改变队伍顺序的前提下，最大化最终坐下的人数。

这页只做赛时代码复盘，不展开完整题解。

思路讲解

补充洞见：从单向状态变化里拆角色

如果题目里有一个资源状态只发生一次单向变化，就尝试按「触发变化的人」和「变化后享受资源的人」拆角色。

这题里，桌子的状态只有一次不可逆变化：

1
空桌 -> 非空桌

所以每张桌子天然可以拆成两类位置：

角色 含义 能坐的人
starter 第一个坐下、把空桌变成非空桌的人 I / A
follower 在桌子已经非空之后坐下的人 E / A

这个抽象的重点不是换名字，而是把「桌子状态」变成「角色资源」：开一张桌本质上是消耗一个 starter 名额，并产生 s-1 个 follower 槽位。于是 A 的特殊性也变清楚了：它不是普通万能牌，而是可以在 starter / follower 两种角色之间延迟定型的弹性资源。

以后遇到类似结构，可以先问一句：资源有没有「第一次操作改变状态，后续操作享受改变后状态」这种单向过程？如果有，就优先尝试拆成「触发者 / 享受者」两类角色。

一句话

这页不是完整题解，只记录一个赛时 WA 的方向性错误：对拍发现 I 的直接分配不够优秀之后，应该重做 I 的分配策略，而不是在错误分配后用剩下的 A 做回退回补。

AC 代码

AC 提交链接

心路历程（WA，TLE，MLE……）

赛时代码的错误方向

赛时代码的思路大概是先从左到右扫一遍：I 能坐空桌就直接坐，E 尽量接到已有桌子上，A 暂时存起来；后面再看剩下的 A 能不能把之前没利用好的桌子补起来。

这个方向的问题是，I 是否占用一张空桌不是一个局部收益。它会改变后面整段 A/E/I 的可行结构。一个早期 I 坐下去，看似马上多了 1，但可能把后面更有价值的“空桌开局”直接堵死。

当对拍发现“I 直接分配不够优秀”时，正确反应应该是重做 I 的选择策略；如果继续沿着旧贪心做回退，本质上是在已经丢掉的状态空间里补洞。

反例记忆

art
1
2
9 2 4
AAIAEIEEI

一种最优安排是跳过较早的 I：

坐下位置 字符 分配
0 A 第一桌第 1 人
1 A 第一桌第 2 人
3 A 第一桌第 3 人
4 E 第一桌第 4 人
5 I 第二桌第 1 人
6 E 第二桌第 2 人
7 E 第二桌第 3 人

答案是 7。

赛时代码会在位置 2 遇到 I 时立刻占掉一张空桌，于是后面再用 A 回补，也已经回不到这个方案了。

这次该记住的坑

  • 对拍其实已经指出：I 直接分配会错。

  • 赛时修偏了方向：试图通过后面的 A 回退回补，而不是重新处理 I 的分配。

  • 这个问题的本质是状态空间被前面的贪心删掉了；后处理只能在剩余状态里修，修不回被删掉的最优路径。

  • 如果对拍暴露的是“某个局部贪心决策本身不成立”，不要先想着给它补丁。先判断这个决策有没有删掉未来可能的状态；如果删掉了，就应该换状态设计。

另一种错误贪心：能开 starter 就开

这版代码的想法很直接：维护还能开的 starter 数量，以及已经开出来的 follower 槽位。遇到 I 就开 starter，遇到 A 时只要还能开 starter，也优先开 starter。

关键代码是：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ll follower = 0, starter = X;
ll ans = 0;
for (int i = 0; i < N; ++i) {
    if (A[i] == 'E') {
        if (follower == 0) continue;
        --follower;
        ++ans;
    } else if (A[i] == 'I') {
        if (starter == 0) continue;
        starter--;
        follower += S - 1;
        ++ans;
    } else {
        if (follower == 0 && starter == 0) continue;
        if (starter > 0) {
            starter--;
            follower += S - 1;
            ++ans;
        } else if (follower > 0) {
            --follower;
            ++ans;
        }
    }
}

这个贪心的问题是：它把 A 过早固定成 starter 了。A 明明既可以当 starter，也可以当 follower；如果它先抢掉 starter 名额，后面的 I 就没法坐，因为 I 没有 follower 这个身份可以退。

一个很小的反例：

art
1
2
3
1
3 2 2
AAI

这份代码会这样走：

位置 字符 决策 starter follower ans
0 A 优先开 starter 1 1 1
1 A 继续优先开 starter 0 2 2
2 I 没有 starter，踢掉 0 2 2

但最优是 A 开第一桌，第二个 A 当 follower，最后的 I 再开第二桌，答案是 3。

所以这里真正要保护的不是“看到能开桌就开桌”，而是 starter 名额要尽量留给刚性的 I，A 的身份需要延迟决定。A 坐下以后不应该立刻永久绑定为 starter；它最好能作为一个可反悔的弹性资源，后面根据 E/I 的到来再决定到底补 follower 还是改成 starter。

附件

暂无。