题解：AT_agc072_c [AGC072C] Human Exercise

meowjiao · 2025-07-23 14:49:47 · 题解

[AGC072C] Human Exercise 题解

前言

本题解部分内容参考了 AtCoder 官方题解。

题目翻译使用 DeepSeek-V3 完成。

题目翻译

AtCoder 城市由一个 N \times N 的网格表示。用 (i, j) 表示从上往下第 i 行（1 \le i \le N）、从左往右第 j 列（1 \le j \le N）的单元格。青木为了马拉松比赛，进行了以下练习 K 次：

从单元格 (1, 1) 出发。
重复以下动作 2N-2 次，最终到达单元格 (N, N)：

向下或向右移动一格。如果两种移动都可行，则选择目标单元格在之前的练习中被访问次数较少的方向。如果次数相同，则优先向下移动。

请输出第 K 次练习所走的路径。

提示

观察样例解释 1 的图片中红色箭头表示的路线，有什么性质？
如果我们已经知道了前 K - 1 次锻炼后每个点的访问次数，怎么求出第 K 次锻炼的路线？
我们按照题意模拟一次，就能求出答案。那么，前 K - 1 次锻炼后每个点的访问次数该怎么求？
观察样例解释 1 的图片中每次经过点 (1, 1) 后行走的方向，有什么规律？
尝试将提示 4 中的规律推广到所有点。
尝试利用提示 5 中的性质构建动态规划，来求前 K - 1 次锻炼后每个点的访问次数。

初步观察

首先，我们看一下样例解释 1 的图片（下图为 AtCoder 官方提供的英文版本）。

我们发现图中红色箭头表示的路线关于副对角线对称，由此可以将问题转化为求副对角线上方的答案。这个转化让我们不必考虑副对角线上方和下方性质的不同。

从这里开始，我们只考虑副对角线上方的部分。

接下来，我们注意到，如果我们已经知道了前 K - 1 次锻炼后每个点的访问次数，那么按按照题意模拟一次，就能求出答案。

那么问题就转换成了求前 K - 1 次锻炼后每个点的访问次数。

再次观察样例解释 1 的图片，如果你注意力惊人，那么会发现到达单元格 (1, 1) 后的行走方向是周期性的，并且还能发现以下两个适用于单元格 (1, 1) 的性质：

第一次到达单元格 (1, 1) 后向下走，第二次向右，第三次向下，第四次向右。行走方向构成的循环节长度为 1 + 1 = 2。
第一次到达单元格 (1, 1) 后向下走，第二次向右，第三次向下，第四次向右。行走方向构成的每个循环节中向下走 1 次，向右走 1 次。

本题的正解就基于这两个性质。

进一步观察

我们很容易用脚写出这段 Python 代码（用 Python 写是因为方便，下面正解用的是 C++）。

if __name__ == '__main__':
    n, k = map(int, input().split())
    vis = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, k + 1):
        x, y = 1, 1
        path = [(1, 1)]
        vis[1][1] += 1
        while (x, y) != (n, n):
            if x < n and y < n:
                if vis[x + 1][y] < vis[x][y + 1]:
                    x += 1
                elif vis[x + 1][y] > vis[x][y + 1]:
                    y += 1
                else:
                    x += 1
            elif x < n:
                x += 1
            else:
                y += 1
            path.append((x, y))
            vis[x][y] += 1
        for j in path:
            print(f'{j[0]} {j[1]}')
        print()

对于每组输入，这段代码会依次输出第 1 次到第 K 次锻炼经过的路径上的点坐标。

我们可以多试几个数据，然后就能把刚才发现的两个性质推广到所有单元格。

性质 1：到达单元格 (x, y) 后的行走方向构成的循环节长度为 x + y。

性质 2：对于每个到达单元格 (x, y) 后的行走方向构成的循环节中，前 x 个是向下走，后 y 个是向右走。

最终求解

现在，问题已经转换成了求前 K - 1 次锻炼后每个点的访问次数。

由于访问次数不具有后效性，且满足最优子结构和子问题重叠，因此可以用动态规划求解。

首先，朴素地考虑每次锻炼后单元格 (i, j) 的访问次数肯定会超时。

但是根据性质 1 和性质 2，我们可以直接考虑第 K - 1 次锻炼后每个单元格被访问的次数。

设 dp_{i, j} 表示第 K - 1 次锻炼后 (i, j) 单元格被访问的次数。

假设单元格 (i, j) 被访问了 z 次，根据性质 2，我们可以求出完整的循环节个数 p。

然后根据性质 3，我们可以求出每个循环节中向下走的次数 q 和向右走的次数 r，以及剩余的不完整的循环节中向下走的个数 s 和向右走的次数 t。

然后状态转移方程就推导出来了。

dp_{i + 1, j} \gets dp_{i + 1, j} + p \times q + s \\ dp_{i, j + 1} \gets dp_{i, j + 1} + p \times r + t

初始化很简单，dp_{1, 1} \gets K - 1。

注意这里应该以 i + j 从大到小的顺序枚举，因为 i + j = t 时的答案依赖 i + j = t - 1 的答案，这样枚举可以避免访问到未计算的单元格。

动态规划结束后，我们用 O(n) 模拟一遍就可以。

但是，到目前为止，我们只计算了副对角线上方的路线。我们还需要利用刚才说的对称性，把路线对称一遍，得到最终答案。

总时间复杂度为 O(n ^ 2)。

神秘 AC 代码

#include <iostream>
using namespace std;

long long dp[110][110];

int main() {
    int n;
    long long k;
    cin >> n >> k;
    dp[0][0] = k - 1;
    for (int s = 0;s < n - 1;s++) {
        for (int i = 0;i <= s;i++) {
            int j = s - i;
            long long p = dp[i][j] / (s + 2);
            int q = dp[i][j] % (s + 2);
            dp[i + 1][j] += (i + 1) * p + min(i + 1,q);
            dp[i][j + 1] += (j + 1) * p + max(q - i - 1,0);
        }
    }
    int x = 0,y = 0;
    string ans = "";
    for (int i = 0;i < n - 1;i++) {
        if (dp[x + 1][y] <= dp[x][y + 1]) {
            ans += 'D';
            x++;
        }
        else {
            ans += 'R';
            y++;
        }
    }
    for (int i = n - 2;i >= 0;i--) {
        if (ans[i] == 'D') {
            ans += 'R';
        }
        else {
            ans += 'D';
        }
    }
    cout << ans;
    return 0;
}