Overview

This problem asks you to identify the set of cells reachable from a given starting position within a specified number of operations on a triangular board, and find the maximum value of \(f(A_{i,p})\) among the numbers \(A_{i,p}\) written on those cells.

Analysis

1. Properties of the function \(f(V)\)

\(f(V)\) is “the maximum digit sum among all integers from \(0\) to \(V\).” To maximize the digit sum, it is best to make as many digits as possible equal to \(9\). For example, if \(V = 123\), the following candidates can be considered: - \(V\) itself: \(1+2+3 = 6\) - Maximum digit sum at most \(122\): \(1+2+1\) (consider whether we can make the last digit \(9\)) \(\to 1+1+9 = 11\) - Maximum digit sum at most \(119\): \(0+9+9 = 18\)

In general, a number obtained by decreasing a certain digit by \(1\) and setting all lower digits to \(9\) is at most \(V\). Using this property, by trying the operation “decrease that digit by \(1\) and set all lower digits to \(9\)” for each digit, we can compute \(f(V)\) in \(O(\log V)\).

2. Range of reachable cells

Let the starting position be \((L, P)\) and the number of operations be \(T\). - Range of row \(i\): Since there is a “stay” operation, rows from the starting row \(L\) up to at most row \(L+T\) are reachable. However, since the board has only \(N\) rows, we have \(L \leq i \leq \min(L+T, N)\). - Range of position \(p\) in each row: - To reach row \(i\), at least \(i-L\) “move directly down” or “move diagonally down-right” operations are needed. - If “move diagonally down-right” is performed \(0\) times, the position remains \(P\); if performed the maximum number of times (\(i-L\) times), the position becomes \(P + (i-L)\). - Therefore, the reachable positions in row \(i\) are \(P \leq p \leq P + (i-L)\).

3. Need for optimization

If we scan all reachable cells for each query, the worst case costs \(O(T^2)\) per query, resulting in \(O(QT^2)\) overall, which is too slow. However, the range of \(p\) in each row \(i\) is a contiguous interval \([P, P+i-L]\). If we can quickly retrieve the maximum value of \(f(A_{i,p})\) within this interval, we can reduce the computation per query to \(O(\text{number of rows traversed})\), i.e., \(O(N)\).

Algorithm

1. Preprocessing (computing \(f(V)\)): Compute \(f(A_{i,p})\) for all cells \((i, p)\) on the board.
2. Preprocessing (building Sparse Table): For each row, build a Sparse Table to answer static range maximum queries (RMQ) in \(O(1)\).
   • st[i][k][j]: the maximum value of \(f(A_{i,p})\) in the range of length \(2^k\) starting from the \(j\)-th position from the left in row \(i\).
3. Query processing: For each query \((L, P, T)\):
   • If \(P > L\), output NA.
   • Loop \(i\) from \(L\) to \(\min(L+T, N)\).
   • For each \(i\), retrieve the maximum value in the interval \([P, P+i-L]\) in \(O(1)\) using the Sparse Table.
   • Update and output the overall maximum.

Complexity

• Time complexity: \(O(N^2 \log N + NQ)\)
  • Computing \(f(V)\): \(O(N^2 \log (\max A))\)
  • Sparse Table construction: \(O(N^2 \log N)\)
  • Query processing: Given the constraint \(NQ \leq 10^7\), scanning at most \(N\) rows per query is fast enough.
• Space complexity: \(O(N^2 \log N)\)
  • Required for storing the Sparse Table. When \(N=1000\), this is approximately \(1000 \times 11 \times 1000 \times 4\) bytes \(\approx 44\) MB, which fits within the memory limit.

Implementation Notes

• Sparse Table: Using 31 - __builtin_clz(len) etc. to compute powers of \(2\) during construction is efficient.

• I/O: Since the number of queries is large, optimization with cin.tie(nullptr); ios::sync_with_stdio(false); is recommended.

• Computing \(f(V)\): Be careful with the case \(V=0\) and the digit > 0 check when processing each digit.

  Source Code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/**
 * 三角形ボードの最適経路
 * 
 * 問題の要点:
 * 1. 各マス (i, p) に書かれた数 A_{i,p} に対し、f(V) = max_{0 <= Y <= V} S(Y) を求める。
 * 2. クエリ (L, P, T) に対して、開始位置 (L, P) からちょうど T 回の操作で到達可能なマスの集合における f(A_{i,p}) の最大値を求める。
 * 3. 操作は「とどまる」「真下に移動」「右下に移動」の 3 つ。
 * 
 * 到達可能なマスの集合:
 * row i: L <= i <= min(L + T, N)
 * col p: P <= p <= P + (i - L)
 * 
 * 計算量:
 * 各行に対して Sparse Table を構築することで、各行の範囲最大値クエリ (RMQ) を O(1) で行える。
 * 全体の計算量は O(N^2 log N + NQ) となり、NQ <= 10^7 の制約下で十分に高速。
 */

// 非負整数 v に対して、0 以上 v 以下の整数の中で桁和が最大となるものの桁和 f(v) を計算する
inline int f(long long v) {
    if (v == 0) return 0;
    int digits[20];
    int n = 0;
    long long temp = v;
    while (temp > 0) {
        digits[n++] = (int)(temp % 10);
        temp /= 10;
    }
    // 桁を上位から順に並べる
    for (int i = 0; i < n / 2; ++i) swap(digits[i], digits[n - 1 - i]);
    
    int max_s = 0;
    int current_prefix_sum = 0;
    for (int i = 0; i < n; ++i) {
        int digit = digits[i];
        if (digit > 0) {
            // 現在の桁を 1 減らし、それ以降の桁をすべて 9 にしたときの桁和を候補とする
            max_s = max(max_s, current_prefix_sum + (digit - 1) + 9 * (n - 1 - i));
        }
        current_prefix_sum += digit;
    }
    // 数 v 自体の桁和も候補とする
    max_s = max(max_s, current_prefix_sum);
    return max_s;
}

// Sparse Table を用いて各行の RMQ を管理
// st[row][k][column] は row 行目の column から長さ 2^k の範囲の最大値を保持する
int st[1001][11][1001];

int main() {
    // 入出力の高速化
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    if (!(cin >> N >> Q)) return 0;

    // ボードの各マスの f(A_{i,p}) を計算し、各行ごとに Sparse Table を構築
    for (int i = 1; i <= N; ++i) {
        for (int j = 1; j <= i; ++j) {
            long long a;
            cin >> a;
            st[i][0][j] = f(a);
        }
        // 行 i の Sparse Table を構築
        int levels = 31 - __builtin_clz(i);
        for (int k = 1; k <= levels; ++k) {
            int range = 1 << k;
            int half = 1 << (k - 1);
            for (int j = 1; j + range - 1 <= i; ++j) {
                st[i][k][j] = max(st[i][k - 1][j], st[i][k - 1][j + half]);
            }
        }
    }

    // クエリの処理
    for (int q = 0; q < Q; ++q) {
        int L, P;
        long long T;
        cin >> L >> P >> T;

        // 開始位置が存在しない場合
        if (P > L) {
            cout << "NA\n";
            continue;
        }

        // 到達可能な行の範囲は [L, min(L + T, N)]
        int max_row = (int)min((long long)N, (long long)L + T);
        int overall_max_f = 0;

        // 各行 i について、到達可能な列の範囲 [P, P + (i - L)] の最大値を求める
        for (int i = L; i <= max_row; ++i) {
            int p1 = P;
            int p2 = P + (i - L);
            
            // 行 i における列 p1 から p2 までの RMQ
            int len = p2 - p1 + 1;
            int k = 31 - __builtin_clz(len);
            int row_max_f = max(st[i][k][p1], st[i][k][p2 - (1 << k) + 1]);
            
            if (row_max_f > overall_max_f) {
                overall_max_f = row_max_f;
            }
        }
        cout << overall_max_f << "\n";
    }

    return 0;
}

This editorial was generated by gemini-3-flash-thinking.