AtCoder-ARC112A B=C
在 \(C\) 处计算答案，有：
\[ans=\sum_{C=L}^{R-L} (R-L+1)-C=\dfrac{(R-2L+1)(R-2L+2)}{2}
\]
提交记录：Submission - AtCoder
AtCoder-ARC112B -- - B
操作一定是尽量使用减法，再开始或最后取相反数来扩大可以覆盖到的数。
对 \(B\) 的正负分别讨论。
如果 \(B=0\)，那么负数部分使用减法，正数部分是在最后取相反数。
\[ans=1+\left\lfloor\dfrac{C}{2}\right\rfloor+\left\lfloor\dfrac{C-1}{2}\right\rfloor
\]
如果 \(B>0\)，那么大于 \(B\) 和小于 \(-B\) 的部分都是通过先取相反数再使用简法，不同的是大于 \(B\) 的相反数取回来。在 \(-B\) 到 \(B\) 之间的正数是直接减法，取相反数就是负数。
\[ans=2+\left\lfloor\dfrac{C-1}{2}\right\rfloor+\left\lfloor\dfrac{C-2}{2}\right\rfloor+\min\left(B,\left\lfloor\dfrac{C}{2}\right\rfloor\right)+\min\left(B-1,\left\lfloor\dfrac{C-1}{2}\right\rfloor\right)
\]
\(B<0\) 的情况类似。
\[ans=2+\left\lfloor\dfrac{C}{2}\right\rfloor+\left\lfloor\dfrac{C-1}{2}\right\rfloor+\min\left(-B,\left\lfloor\dfrac{C-1}{2}\right\rfloor\right)+\min\left(-B-1,\left\lfloor\dfrac{C-2}{2}\right\rfloor\right)
\]
提交记录：Submission - AtCoder
AtCoder-ARC112C DFS Game
为数不多能做出来的博弈论题
取硬币的顺序就是在 DFS，不妨设 \(f_u\) 为从 \(u\) 节点开始 DFS \(u\) 子树，在最优策略下，先手比后手多获得多少硬币。
考虑转移，先手取走 \(u\) 的硬币后由后手决定遍历哪棵子树。发现从 \(u\) 去到 \(v\)，再遍历 \(v\) 的过程中，每条边操作 \(2\) 次，每个节点操作 \(1\) 次，因此子树大小的奇偶性决定了 DFS 之后是否会切换操作顺序。
按照子树大小奇偶性讨论，偶数的不会改变操作顺序，DFS 后仍为后手选择子树，那么后手一定会把 \(f_v\le 0\) 且 \(siz_v\bmod 2=0\) 的全部 DFS 完，剩下 \(f_v>0\) 的双方都会避免走入。奇数的部分每次都会切换，因此一定是 \(f_v\) 从小到大依次遍历，那么这样 DFS 完所有子树大小为奇数的之后，进入 \(f_v>0\) 且 \(siz_v\bmod 2=0\) 的一方就固定了。
提交记录：Submission - AtCoder