問題文

古代遺跡の奥深く、魔法少女うなは宝石が眠る広間へと足を踏み入れた。
うなは、この遺跡に眠る宝石をできるだけ多く回収したいと考えている。

古代遺跡の床はグリッド状になっている。遺跡は $N \times N$ のグリッドで表される。
グリッドの各マスには宝石が置かれており、その価値は非負整数で与えられる。

遺跡の床は非常に脆く、一度踏んだマスは崩壊してしまう。
したがって、同じマスを二度通ることはできない。

また、遺跡の崩壊は徐々に進んでおり、長く探索しすぎると崩壊に巻き込まれてしまう。
そのため、うなが探索できるのは最大で $T$ マスである。

うなは任意のマスから探索を開始し、隣接するマスへ移動しながら宝石を回収していく。
回収できる宝石の価値の合計を最大化するような経路を求めよ。

問題設定

グリッドの左上のマスを $(0,0)$ とし、そこから下に $i$ マス、右に $j$ マス移動したマスの座標を $(i,j)$ とする。

各マス $(i,j)$ には宝石の価値を表す非負整数 $A_{i,j}$ が書かれている。

あなたは長さ $L$ の経路（$1 \le L \le T$）を 1 つ選ぶことができる。
この経路は次の条件を満たさなければならない。

• 最初に好きなマス $(i_0, j_0)$ を一つ選ぶ
• すべての $k$ ($0 \le k < L-1$) について、$(i_k, j_k)$ と $(i_{k+1}, j_{k+1})$ は上下左右に隣接している
• すべての $(i_k, j_k)$ は互いに異なる（同じマスを二度訪れてはならない）

得点

訪れたマスを $$ (i_0, j_0), (i_1, j_1), \ldots, (i_{L-1}, j_{L-1}) $$ とすると、得点はマスの価値の合計、すなわち $$ \mathrm{Score} = \sum_{k=0}^{L-1} A_{i_k, j_k} $$ で定義される。

合計で 50 個のテストケースがあり、各テストケースの得点の合計が提出の得点となる。

入力生成方法

各テストケースは以下のように生成される。

• $T$ は $1$ 以上 $N^2$ 以下の整数から一様ランダムに生成される
• 各マス $(i,j)$ について独立に次のように生成される
  • $x_{i,j}$ を $[0,3]$ の一様乱数（実数）として生成する
  • $A_{i,j} = \lfloor 10^{x_{i,j}} \rfloor$ とする

入力

$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}$

制約

• $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$
• 入力はすべて整数である

出力

長さ $L$ の経路を以下の形式で出力せよ。

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

ビジュアライザ・テストケースダウンロード

以下のページで、入出力をアニメーションとして可視化できます。
また、このページからテストケースを生成してダウンロードすることも可能です。

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

サンプルコード

何から書けばよいかわからない場合は、まずは以下のコードをそのまま提出してみてください。
このコードは、グリッドを左上からジグザグに移動し、上から順に $T$ マスだけ訪れる単純な解法です。

スコアはあまり高くありませんが、問題の形式に従った正しい出力を行うため、AC（正解）になります。

このコードを出発点として、

• 価値の高いマスを優先して訪れるにはどうすればよいか
• 経路をどのように改善できるか

などを考えていくと、より高得点を目指すことができます。

#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;
}

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)

サンプル

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

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