atcoder

• \(ARC143\)

A
给定三个整数，一次可以将两个数或三个数减一，问最少几步能减完。

设一开始三个数为 \(A,B,C(A\leq B\leq C)\)，如果 \(A+B<C\)，那么说明一定是无法满足条件的，因为 \(C\) 至多被减掉 \((A+B)\)，此时 \(C-A-B>0\)。

如果 \(A+B=C\)，那么很显然答案就是 \(C\)。

如果 \(A+B>C\)，其实也可以满足条件。我们发现要令其变为 \(A+B=C\) 的形式，那么我们在 \(A+B=C\) 中构造的是 \((A,C)\)，\((B,C)\) 分别分组减，那么 \(C\) 会被减两次。

我们可以通过一次将三个数一起减，使 \(C\) 每次被减的次数少 \(1\)。我们一共需要 \(C\) 被减的次数少 \(A+B-C\)。

所以我们先进行 \(A+B-C\) 次减三个数的操作，数据变为 \(C-B,C-A,2C-A-B\)，发现此时就能满足条件了。一共用 \(A+B-C+2C-A-B=C\) 次操作。

B
给定一个整数 \(N\)，问能构造出多少个 \(N\times N\) 的矩阵，其中填入 \(1\) 到 \(N^2\) 的所有数，使得每一行中最大的数不为该数所在列中最小的数。

正难则反，我们考虑用总方案数减掉不合法的方案数。

总方案数显然就是 \((N\times N)!\)

不合法的方案数考虑在 \((a,b)\) 位置，那么与其相关需要考虑的数共 \(2N-1\) 个。

其中列的 \(N-1\) 个数与行的 \(N-1\) 个数可以乱排，所以答案乘上 \((N-1)!^2\)

其中不与其相关的共 \(N^2-2N+1\) 个数可以乱排，所以答案乘上 \((N^2-2N+1)!\)

考虑 \((a,b)\) 位置可以随意，共 \(N^2\) 中选择，所以答案乘上 \(N^2\)

考虑 \(2N-1\) 个数的选择，从 \(N^2\) 个数中选出 \(2N-1\) 个数，每一种选择都能选择最中间的数使得满足条件，所以共 \({N^2\choose 2N-1}\) 种选择。

答案就是 \({N^2\choose 2N-1}\times (N-1)!^2 \times (N^2-2N+1)! \times N^2\)

C
给定整数 \(n\)， 给定 \(n\) 堆石子的个数 \(A_i\)，两个人一人先手，一次可以拿任意堆石子，每一堆拿不超过 \(X\) 个，另一个人后手，一次可以拿任意堆石子，每一堆拿不超过 \(Y\) 个，问谁能赢。

我们考虑一种局面，此时有石子的个数 \(B_i=A_i\bmod{(X+Y)}\)，且每一堆石子至多可以有一人取一次。

如果存在一堆石子使得 \(X>B_i\geq Y\)，那么说明该堆石子 \(X\) 无法取得，而 \(Y\) 能取得，且所有 \(X\) 能取得的石子堆 \(Y\) 都能取得，\(Y\) 必胜。

否则，现在场上的局面一定是每一堆石子，要不都拿不了，要不都能拿，那么此时只需要有一堆石子 \(X\) 能拿，那么 \(X\) 可以把所有能拿的石子都拿走， \(Y\) 无法再拿， \(X\) 必胜。

否则就是 \(Y\) 必胜。