問題一覧 > スコア問題

No.5024 Magical Girl Una and the Treasure Hunt

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 1024 MB / スペシャルジャッジ問題 (複数の解が存在する可能性があります)
タグ : (解説公開後に AC するまで非表示) / 解いたユーザー数 37
作問者 : shell_mug / テスター : hakatashi ats5515
お気に入りにしたユーザー ProblemId : 13264 / 自分の提出
問題文最終更新日: 2026-05-02 17:04:20
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
TSG十種競技2026 ヒューリスティックコンテスト (順位表) の他の問題:

Problem Statement

Deep inside an ancient ruin, the magical girl Una has stepped into a hall where jewels lie dormant.
Una wants to collect as many of the jewels sleeping in this ruin as possible.

The floor of the ancient ruin is laid out as a grid. The ruin is represented by an $N \times N$ grid.
A jewel is placed on each cell of the grid, and its value is given as a non-negative integer.

The floor of the ruin is extremely fragile, and a cell collapses once it has been stepped on.
Therefore, the same cell cannot be passed through twice.

The collapse of the ruin is also gradually progressing, and if she explores for too long, she will be caught in it.
For this reason, Una can explore at most $T$ cells.

Una starts exploring from any cell and collects jewels while moving to adjacent cells.
Find a path that maximizes the total value of the jewels collected.

Problem Setting

Let the top-left cell of the grid be $(0,0)$, and let $(i,j)$ denote the coordinates of the cell reached by moving $i$ cells down and $j$ cells right from it.

Each cell $(i,j)$ has a non-negative integer $A_{i,j}$ written on it, representing the value of its jewel.

You may choose one path of length $L$ ($1 \le L \le T$).
This path must satisfy the following conditions.

  • First, choose any one cell $(i_0, j_0)$
  • For every $k$ ($0 \le k < L-1$), $(i_k, j_k)$ and $(i_{k+1}, j_{k+1})$ are adjacent vertically or horizontally
  • All $(i_k, j_k)$ are pairwise distinct (the same cell must not be visited twice)

Score

Let the visited cells be $$ (i_0, j_0), (i_1, j_1), \ldots, (i_{L-1}, j_{L-1}) $$ Then the score is defined as the sum of the values of the cells, that is, $$ \mathrm{Score} = \sum_{k=0}^{L-1} A_{i_k, j_k} $$

There are 50 test cases in total, and the score of a submission is the sum of the scores of the test cases.

Input Generation

Each test case is generated as follows.

  • $T$ is generated uniformly at random from the integers between $1$ and $N^2$, inclusive
  • Each cell $(i,j)$ is generated independently as follows
    • Generate $x_{i,j}$ as a uniform random real number in $[0,3]$
    • Let $A_{i,j} = \lfloor 10^{x_{i,j}} \rfloor$

Input

$N\ T$
$A_{0,0}\ A_{0,1}\ \ldots\ A_{0,N-1}$
$A_{1,0}\ A_{1,1}\ \ldots\ A_{1,N-1}$
$\vdots$
$A_{N-1,0}\ A_{N-1,1}\ \ldots\ A_{N-1,N-1}$

Constraints

  • $N = 20$
  • $1 \le T \le N^2$
  • $1 \le L \le T$
  • $0 \le A_{i,j} \le 10^3$
  • $0 \le i, j < N$
  • All input values are integers

Output

Output a path of length $L$ in the following format.

$L$
$i_0\ j_0$
$i_1\ j_1$
$\vdots$
$i_{L-1}\ j_{L-1}$

Visualizer and Test Case Download

On the following page, you can visualize the input and output as an animation.
You can also generate and download test cases from this page.

https://mug.sh/decathlon2026-heuristic-visualizer/

Sample Code

If you are not sure where to start, first try submitting the code below as is.
This code is a simple solution that moves through the grid in a zigzag from the top left, visiting only $T$ cells in order from the top.

Its score is not very high, but since it produces correct output following the problem's format, it will get AC (accepted).

Using this code as a starting point, you can aim for a higher score by thinking about questions such as

  • How can you prioritize visiting high-value cells?
  • How can the path be improved?

and so on.

Sample code in C++ (click to expand)
#include <iostream>
#include <vector>
using namespace std;

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

    vector<vector<int>> A(N, vector<int>(N));
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> A[i][j];
        }
    }

    vector<pair<int, int>> path;

    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            // 左から右へ
            for (int j = 0; j < N; j++) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        } else {
            // 右から左へ
            for (int j = N - 1; j >= 0; j--) {
                path.push_back(make_pair(i, j));
                if (path.size() == T) {
                    break;
                }
            }
        }

        if (path.size() == T) {
            break;
        }
    }

    cout << path.size() << endl;
    for (int k = 0; k < path.size(); k++) {
        cout << path[k].first << " " << path[k].second << endl;
    }

    return 0;
}
Sample code in Python (click to expand)
N, T = map(int, input().split())

A = []
for _ in range(N):
    row = list(map(int, input().split()))
    A.append(row)

path = []

for i in range(N):
    if i % 2 == 0:
        # 左から右へ
        for j in range(N):
            path.append((i, j))
            if len(path) == T:
                break
    else:
        # 右から左へ
        for j in range(N - 1, -1, -1):
            path.append((i, j))
            if len(path) == T:
                break

    if len(path) == T:
        break

print(len(path))
for i, j in path:
    print(i, j)

Sample

Sample 1
Input
20 50
82 1 6 4 161 107 474 1 18 1 4 32 1 3 89 43 4 58 268 1
261 124 10 2 744 10 1 1 348 64 263 154 40 830 13 45 307 71 384 53
129 1 4 7 1 4 2 6 80 12 12 4 6 645 87 67 3 153 3 13
930 83 46 113 337 212 4 1 8 6 4 674 425 8 92 15 554 23 6 5
48 6 56 493 15 4 983 33 1 1 2 76 237 18 1 13 973 38 818 382
1 145 110 40 6 83 2 20 22 726 424 6 31 3 546 408 7 82 67 2
193 41 216 38 1 9 1 612 432 312 8 1 430 693 1 28 1 191 198 2
26 44 6 414 18 4 41 154 4 8 967 89 20 35 2 4 10 58 4 4
1 78 4 520 379 1 5 101 4 2 640 51 26 225 264 3 1 19 18 25
153 104 896 1 16 10 384 5 3 22 18 6 5 588 21 383 44 1 995 322
807 601 351 3 28 4 15 1 13 903 6 225 23 18 744 968 46 142 2 7
805 54 42 175 1 56 32 361 2 762 1 3 60 106 5 2 468 5 60 72
18 56 37 636 4 140 5 15 103 7 8 180 1 23 989 973 1 4 6 630
439 434 12 2 317 129 68 915 91 1 282 7 97 655 2 2 2 45 6 65
142 4 79 6 29 520 345 1 18 6 1 205 81 6 167 45 19 1 1 445
514 43 318 55 2 2 8 497 244 382 497 4 5 2 218 449 16 72 2 616
392 848 270 440 1 162 9 620 255 391 270 6 230 2 413 376 4 281 24 8
243 4 1 3 9 391 795 6 84 15 877 40 657 2 815 3 771 6 2 20
153 8 65 34 14 53 5 133 1 598 41 143 168 102 12 1 98 9 8 349
144 7 8 16 16 7 2 18 662 107 510 70 7 44 1 7 19 54 92 24
Output
50
5 9
5 10
6 10
7 10
8 10
8 11
8 12
8 13
9 13
9 14
10 14
10 15
11 15
12 15
12 14
13 14
14 14
15 14
15 15
16 15
16 14
17 14
17 13
17 12
17 11
17 10
16 10
15 10
15 9
15 8
15 7
16 7
16 6
17 6
17 5
16 5
16 4
16 3
16 2
16 1
16 0
15 0
14 0
13 0
12 0
11 0
10 0
10 1
10 2
9 2

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。