题目详情题解（0）讨论（0）提交记录（0）

AT_ahc035_a.[AHC035A] Breed Improvement

NOI/NOI+/CTSC

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

有一个用 N×NN\times N 格子表示的农田。农田最左上角的格子的坐标为 (0,0)(0,0)，从该格子向下移动 ii 格、向右移动 jj 格后的位置为 (i,j)(i,j)。

给定 2N(N−1)2N(N-1) 粒谷物种子。存在 MM 个评价项目，每粒种子 kk 都有一个表示各评价项目优劣的非负整数向量 xk=(xk,0, xk,1, ⋯ , xk,M−1)\boldsymbol{x_k}=(x_{k,0},\ x_{k,1},\ \cdots,\ x_{k,M-1})（下称“评价项目向量”）。种子 kk 的价值 VkV_k 定义为 Vk=∑l=0M−1xk,lV_k=\sum_{l=0}^{M-1}x_{k,l}。

通过以下操作重复 TT 次，使手中种子的最大价值 max⁡(V0, V1, ⋯ , V2N(N−1)−1)\max(V_0,\ V_1,\ \cdots,\ V_{2N(N-1)-1}) 尽可能大。

  • 在农田的 N2N^2 个格子中，每个格子各种下一粒种子。同一粒种子不能种在多个格子，未被种下的 2N(N−1)−N22N(N-1)-N^2 粒种子全部丢弃。之后，对于上下左右相邻的格子中所种的种子对 (k, k′)(k,\ k')，会生成一粒新的种子，其评价项目向量的第 ll 个元素值会从原种子的 xk,lx_{k,l} 和 xk′,lx_{k',l} 中等概率随机选取。这样共生成 2N(N−1)2N(N-1) 粒新种子，作为新的手中种子。

    新种子的生成示例
    例如，当 M=3M=3 时，将种子 00 种在格子 (0,0)(0,0)，种子 11 种在格子 (0,1)(0,1)。若种子 00 的评价项目向量为 x0=(1,2,3)\boldsymbol{x_0}=(1,2,3)，种子 11 的评价项目向量为 x1=(4,5,6)\boldsymbol{x_1}=(4,5,6)，则新种子的评价项目向量可能为以下 88 种之一：

    • (1,2,3)(1,2,3)
    • (1,2,6)(1,2,6)
    • (1,5,3)(1,5,3)
    • (1,5,6)(1,5,6)
    • (4,2,3)(4,2,3)
    • (4,2,6)(4,2,6)
    • (4,5,3)(4,5,3)
    • (4,5,6)(4,5,6)

    从这 88 个评价项目向量中等概率随机选取 11 个，作为新种子的评价项目向量。

输入格式

※本题为交互式题目。请阅读以下内容，并与评测程序进行交互。

首先，从标准输入读入农田大小 NN、评价项目数 MM、操作次数 TT，以及所有种子的评价项目向量 xk=(xk,0, xk,1, ⋯ , xk,M−1)\boldsymbol{x_k}=(x_{k,0},\ x_{k,1},\ \cdots,\ x_{k,M-1})，格式如下：

NN MM TT
x0,0x_{0,0} ⋯\cdots x0,M−1x_{0,M-1}
⋮\vdots
x2N(N−1)−1,0x_{2N(N-1)-1,0} ⋯\cdots x2N(N−1)−1,M−1x_{2N(N-1)-1,M-1}

其中，输入满足以下约束：

  • N=6N=6
  • M=15M=15
  • T=10T=10
  • 0≤xk,l≤1000\le x_{k,l}\le 100
  • 所有输入均为整数

读取上述信息后，重复以下处理 TT 轮：

每一轮，首先将每个格子种植的种子编号按如下格式输出到标准输出：

A0,0A_{0,0} ⋯\cdots A0,N−1A_{0,N-1}
⋮\vdots
AN−1,0A_{N-1,0} ⋯\cdots AN−1,N−1A_{N-1,N-1}

其中，Ai,jA_{i,j} 表示种在格子 (i,j)(i,j) 的种子编号，需满足 0≤Ai,j<2N(N−1)0\le A_{i,j}<2N(N-1)，且同一轮内不能重复使用同一编号。

输出后，会从标准输入读入新生成的 2N(N−1)2N(N-1) 粒种子的评价项目向量，格式如下：

x0,0x_{0,0} ⋯\cdots x0,M−1x_{0,M-1}
⋮\vdots
x2N(N−1)−1,0x_{2N(N-1)-1,0} ⋯\cdots x2N(N−1)−1,M−1x_{2N(N-1)-1,M-1}

其中，每个元素均为 0≤xk,l≤1000\le x_{k,l}\le 100 的整数。

每次输出后必须换行，并且刷新标准输出。 否则可能会导致 TLE。

解答程序可以在输出中包含以 # 开头的注释行。使用网页版可视化工具时，这些注释会在相应时机显示，便于调试和分析。评测程序会忽略所有注释行，因此可以直接提交包含注释的程序。

输出格式

见上文“输入格式”部分的说明。

说明/提示

故事背景

AtCoder 公司正在致力于谷物品种改良。谷物有美味、产量、抗病性等多个评价项目，社长高桥希望培育出在所有评价项目上都很优秀的谷物。

在格状农田中种植谷物种子后，相邻格子的两粒种子会随机继承各自的评价项目值，生成新的种子。通过多次种植和收获，希望你能培育出尽可能优秀的谷物种子。

得分

对于初始给定的 2N(N−1)2N(N-1) 粒种子，评价项目向量第 ll 项的最大值为 Xl=max⁡(x0,l, x1,l, ⋯ , x2N(N−1)−1,l)X_l=\max(x_{0,l},\ x_{1,l},\ \cdots,\ x_{2N(N-1)-1,l})。经过 TT 次操作后，手中种子的最大价值为 W=max⁡(V0, V1, ⋯ , V2N(N−1)−1)W=\max(V_0,\ V_1,\ \cdots,\ V_{2N(N-1)-1})，则得分为 round(106×W/∑l=0M−1Xl)\mathrm{round}(10^6\times W/\sum_{l=0}^{M-1}{X_l})。

共 300 个测试用例，所有测试用例得分之和为提交的总得分。若有任一测试用例输出非法或超时，则整体判定为 WA 或 TLE。比赛期间以最高得分计入最终排名，赛后不再进行系统测试。得分相同者排名并列。

输入输出示例

以下为不满足实际约束的说明用输入示例。

回合 Output Input     事前信息  ```

3 5 10
42 45 29 50 53
19 35 91 0 11
35 83 30 9 31
28 18 20 28 88
0 52 21 66 51
24 9 35 10 89
57 27 13 73 24
22 2 5 78 59
66 67 27 18 12
81 38 24 21 32
89 21 32 16 19
6 27 9 67 68


   0 ```

5 4 7
8 9 0
11 2 6


0 52 21 10 89
0 52 21 78 59
66 67 24 18 32
81 38 24 50 32
6 27 30 67 31
57 27 13 73 24
24 9 27 10 12
81 52 24 21 51
42 45 5 50 53
66 27 27 67 68
35 83 30 9 31
42 27 13 73 53

1 ```

6 8 11
3 9 1
7 2 5

42 45 5 10 12
42 45 13 73 53
66 38 24 50 32
66 52 27 67 68
81 52 24 18 32
66 67 13 18 32
81 38 27 10 12
42 27 5 50 68
0 52 13 78 53
81 52 24 50 32
66 67 27 67 32
0 52 13 78 59


   $ \vdots $     9 ```

2 6 10
8 1 9
11 4 3


42 27 5 50 68
42 27 5 50 32
0 67 27 50 68
42 27 5 50 68
42 27 24 50 32
42 67 5 50 68
42 67 24 50 68
42 27 27 50 68
0 27 5 50 32
0 67 24 50 68
42 67 5 50 68
42 27 5 50 32

在此例中，W=V6=42+67+24+50+68=251W=V_6=42+67+24+50+68=251，∑l=0M−1Xl=89+83+91+78+89=430\sum_{l=0}^{M-1}{X_l}=89+83+91+78+89=430，因此得分为 583721583721。

查看示例

示例程序（Python）

以下为 Python 解答示例。该程序每次将第 00 到 3535 号种子按左上到右下顺序依次种下。

N, M, T = map(int, input().split())
SEED_COUNT = 2 * N * (N - 1)
X = []

for i in range(SEED_COUNT):
    X.append(list(map(int, input().split())))

for t in range(T):
    A = [[0] * N for i in range(N)]

    for i in range(N):
        for j in range(N):
            A[i][j] = i * N + j

    for i in range(N):
        print(' '.join(map(str, A[i])), flush=True)

    X = []

    for i in range(SEED_COUNT):
        X.append(list(map(int, input().split())))

示例程序（C++）

以下为 C++ 解答示例。该程序每次将第 00 到 3535 号种子按左上到右下顺序依次种下。

#include <iostream>
#include <vector>

using namespace std;

int main() {
    int N, M, T;
    cin >> N >> M >> T;

    int seed_count = 2 * N * (N - 1);
    vector<vector<int>> X(seed_count, vector<int>(M, 0));

    for (int i = 0; i < seed_count; i++) {
        for (int j = 0; j < M; j++) {
            cin >> X[i][j];
        }
    }

    for (int t = 0; t < T; t++) {
        vector<vector<int>> A(N, vector<int>(N, 0));

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                A[i][j] = i * N + j;
            }
        }

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                cout << A[i][j];

                if (j < N - 1) {
                    cout << " ";
                } else {
                    cout << endl;
                }
            }
        }

        cout.flush();

        for (int i = 0; i < seed_count; i++) {
            for (int j = 0; j < M; j++) {
                cin >> X[i][j];
            }
        }
    }

    return 0;
}

输入生成方法

定义从标准正态分布生成值的函数为 randnormal()\mathrm{randnormal}()。

对于每个 k=0,1,⋯ ,2N(N−1)k=0,1,\cdots,2N(N-1)，如下生成 xk=(xk,0, xk,1, ⋯ , xk,M−1)\boldsymbol{x_k}=(x_{k,0},\ x_{k,1},\ \cdots,\ x_{k,M-1})：

生成 MM 维向量 (xk,0′,⋯ ,xk,M−1′)(x_{k,0}',\cdots,x_{k,M-1}')，其中 xk,l′=∣randnormal()∣x_{k,l}'=|\mathrm{randnormal}()|。令 pk=100∑l=0M−1xk,l′2p_k=\frac{100}{\sqrt{\sum_{l=0}^{M-1}x_{k,l}'^2}}，再令 xk,l=round(pkxk,l′)x_{k,l}=\mathrm{round}(p_kx_{k,l}')。

工具（输入生成器、本地测试器、可视化工具）

比赛期间，禁止分享可视化结果、解法及相关讨论，请注意。

工具所用输入文件格式说明

本地测试器使用如下格式的输入文件：

NN MM TT
x0,0x_{0,0} ⋯\cdots x0,M−1x_{0,M-1}
⋮\vdots
x2N(N−1)−1,0x_{2N(N-1)-1,0} ⋯\cdots x2N(N−1)−1,M−1x_{2N(N-1)-1,M-1}
u0,0,0u_{0,0,0} ⋯\cdots u0,0,N−2u_{0,0,N-2}
⋮\vdots
u0,N−1,0u_{0,N-1,0} ⋯\cdots u0,N−1,N−2u_{0,N-1,N-2}
v0,0,0v_{0,0,0} ⋯\cdots v0,0,N−1v_{0,0,N-1}
⋮\vdots
v0,N−2,0v_{0,N-2,0} ⋯\cdots v0,N−2,N−1v_{0,N-2,N-1}
⋮\vdots
uT−1,0,0u_{T-1,0,0} ⋯\cdots uT−1,0,N−2u_{T-1,0,N-2}
⋮\vdots
uT−1,N−1,0u_{T-1,N-1,0} ⋯\cdots uT−1,N−1,N−2u_{T-1,N-1,N-2}
vT−1,0,0v_{T-1,0,0} ⋯\cdots vT−1,0,N−1v_{T-1,0,N-1}
⋮\vdots
vT−1,N−2,0v_{T-1,N-2,0} ⋯\cdots vT−1,N−2,N−1v_{T-1,N-2,N-1}

其中，ut,i,ju_{t,i,j} 和 vt,i,jv_{t,i,j} 是由 0、1 组成的 MM 字符串，含义如下：

  • 若 ut,i,ju_{t,i,j} 的第 ll 位为 0，则第 tt 轮操作中，(i,j)(i,j) 与 (i,j+1)(i,j+1) 所种的种子 Ai,jA_{i,j} 和 Ai,j+1A_{i,j+1} 生成的新种子的第 ll 项取 xAi,j,lx_{A_{i,j},l}；若为 1，则取 xAi,j+1,lx_{A_{i,j+1},l}。
  • 若 vt,i,jv_{t,i,j} 的第 ll 位为 0，则第 tt 轮操作中，(i,j)(i,j) 与 (i+1,j)(i+1,j) 所种的种子 Ai,jA_{i,j} 和 Ai+1,jA_{i+1,j} 生成的新种子的第 ll 项取 xAi,j,lx_{A_{i,j},l}；若为 1，则取 xAi+1,j,lx_{A_{i+1,j},l}。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页