题解 AT3855 【[AGC020A] Move and Win】

原题传送门

在这里要和审核的管理员大大说抱歉。因为作者的孤陋寡闻和疏忽，排版出现问题。这是已经更改好的最终版，希望能够通过审核。管理员们辛苦了！

首先观察题目，棋盘是一条线。

我们先不管 \text{n} ，考虑如果两个棋子分别在两端的情况。

由于走回头路的情况等于没走，题目转换为两者相遇（这里的相遇不是重叠）时，谁走下一步。

显然这时行棋的一方输了。

考虑 \text{n=2} 时，先手方败；\text{n=3} 时，后手方败。

注意这里的 \text{n} 不是题目中的 \text{n} ，而是上述情况的 \text{n} 。

由于不能走回头路，问题最终转化为上述两种情况。

因为实际上，走回头路，对手往你这逼近两格，和你们相向一人走一格是一样的。

那么问题转换求为这个棋盘的格子数的奇偶性，奇数则先手方胜。

所以这个 \text{n} 是没用的，跟你在两头，走回头路的情况相同。

那么有没有可能这两人都不逼近对方呢？答案是否定的，因为一定有人有必胜策略，所以一定有人会赢，而且赢的人只要一直逼近对手即可。

然后这题就非常好做了，只要当两个棋子之间的距离为奇数时，输出先手的Alice，否则输出后手的Borys即可。