题解：AT_arc209_a [ARC209A] Bracket Game

· · 题解

第一次打 ARC，打的还挺好，写题解记录一下。

接下来称 Taro 为先手，称 Jiro 为后手，一个合法的括号序列成为一个匹配的括号序列。

显然如果某个人叫停可以获得胜利则必定叫停，所以我们只考虑先手手里的括号匹配的，后手手里的括号序列失配的情况。

发现后手必须要通过一次操作使得这个括号序列匹配，考虑何时能够达成这个目标。

观察样例可以发现，如果序列是形如 (A) 的形式时，后手可以通过删除与先手相反的一侧的字符使这个括号保持匹配。如果序列是形如 ()A() 的形式时，后手可以通过删除与先手同侧的字符使这个括号序列匹配。

显然操作次数越多对先手越不利，故先手一定会选择操作次数最少的一种方式。首先双方会将最外侧包裹着的括号删除掉。随后，由于删哪个括号的主动权掌握在先手手中，先手肯定是会选择 () 较少的一侧并删除那一侧的所有括号。这时，后手必定无法将其调整为匹配的括号序列。

综上，可以计算出当先手主动叫停时的序列长度并与 K 比较，根据大小关系分讨即可。代码十分好写，不放了。

博弈论怎么这么难讲啊！