概要

各マスの値 \(A_{i,p}\) をそのまま使うのではなく、まず \(f(A_{i,p})=\max_{0\le Y\le A_{i,p}}S(Y)\) に変換しておき、
各クエリでは「到達可能な三角形領域」の最大値を高速に求める問題です。
行ごとの RMQ（Sparse Table）を作ることで、クエリを効率よく処理できます。

考察

この問題の難しさは主に2つあります。

1. \(f(V)\) をどう高速に求めるか
2. 各クエリで到達可能な全マスの最大値をどう高速に取るか

---

1. \(f(V)\) の計算

定義は \(f(V)=\max_{0\le Y\le V}S(Y)\) です。
愚直に \(Y=0\) から \(V\) まで全探索は不可能です（\(V\) は最大 \(10^{18}\)）。

ここで有名な桁DP的な観察を使います。
最大候補は次の形だけ見れば十分です。

• \(Y=V\)（そのまま）
• ある桁を 1 減らし、その右側を全部 9 にした数

例：\(V=5273\) なら候補は - 5273（桁和 17） - 4999（22） - 5199（24） - 5269（22） など。
この中の最大が \(f(V)\) になります。

実装では文字列化して、前計算した prefix 和を使って各候補の桁和を \(O(1)\) で計算し、全体で \(O(\text{桁数})\) です。

---

2. クエリの到達可能領域

開始位置 \((L,P)\) から 1 回の移動でできるのは

• 段を変えない（とどまる）
• 1 段下の同じ列
• 1 段下の右隣列

なので、\(r\) 段下（つまり行 \(i=L+r\)）にいるとき列は
\([P,\;P+r]\) の範囲になります。
また、下に進めるのは最大で \(N-L\) 段なので、実際に見る行は \(i\in[L,\;\min(N,L+T)]\)。

つまりクエリは
各行 \(i\) の区間 \([P,\;P+(i-L)]\) の最大値を取り、その全行で最大を取る
問題に変形できます。

---

素朴解法が厳しい理由

各クエリごとに到達領域の全マスをなめると、最悪で三角形サイズになり重すぎます。
\(Q\) は最大 \(10^5\) なので到底間に合いません。

そこで「行ごとの区間最大」を高速にするため、各行に Sparse Table を作ります。
これで任意区間最大を \(O(1)\) で取得可能。
クエリは行を上から下へ見るだけになるので、1クエリ \(O(\text{到達行数})\) で処理できます。
制約に \(NQ\le 10^7\) があるため、この方針で十分通ります。

アルゴリズム

1. 入力された各 \(A_{i,p}\) について \(B_{i,p}=f(A_{i,p})\) を計算して保存。
2. 各行 \(i\)（長さ \(i\)）に対して Sparse Table を構築。
   • st[i][k][p] = 行 \(i\) の区間 \([p,\;p+2^k-1]\) の最大値
3. 各クエリ \((L,P,T)\) を処理：
   • \(P>L\) なら開始マス不存在なので NA
   • それ以外は
     • maxRow = L + min(T, N-L)
     • 各行 \(i=L..maxRow\) について区間 \([P,\;P+(i-L)]\) の最大を RMQ で取得
     • その最大を答えとして出力

計算量

• 時間計算量:
  
  • 前処理（\(f\) 計算）: \(O(N^2 \cdot D)\)（\(D\) は桁数、最大 19 で定数扱い可）
    
  • Sparse Table 構築: \(\sum_{i=1}^N O(i\log i)=O(N^2\log N)\)
    
  • クエリ処理: \(\sum O(\min(N-L_j, T_j)+1)\)、最悪評価で \(O(NQ)\)（制約より \(\le 10^7\)）
• 空間計算量: \(O(N^2\log N)\)（行ごとの Sparse Table）

実装のポイント

• P > L のときは即 NA。

• maxRow は L + min(T, N-L) で切る（T は大きいので long long）。

• 区間最大取得時の長さ len=r-l+1 に対し、k=floor(log2(len)) を使い
  max(st[k][l], st[k][r-2^k+1]) で取得。

• \(f(V)\) では「ある桁を 1 減らして右を全部 9」による候補を忘れず全桁試す。
  先頭桁が 0 になるケースも桁和計算上は問題ありません。

  ソースコード

#include <bits/stdc++.h>
using namespace std;

static inline int digit_sum_u64(unsigned long long x) {
    int s = 0;
    while (x > 0) {
        s += int(x % 10);
        x /= 10;
    }
    return s;
}

static inline int f_max_digit_sum(unsigned long long V) {
    // f(V) = max_{0<=Y<=V} S(Y)
    // Candidates:
    // 1) Y = V
    // 2) For each position, reduce that digit by 1 and set all lower digits to 9.
    string s = to_string(V);
    int n = (int)s.size();

    vector<int> pref(n + 1, 0);
    for (int i = 0; i < n; i++) pref[i + 1] = pref[i] + (s[i] - '0');

    int ans = pref[n]; // S(V)
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d == 0) continue;
        int cand = pref[i] + (d - 1) + 9 * (n - i - 1);
        if (cand > ans) ans = cand;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, Q;
    cin >> N >> Q;

    vector<vector<int>> B(N + 1);
    for (int i = 1; i <= N; i++) {
        B[i].resize(i + 1);
        for (int p = 1; p <= i; p++) {
            unsigned long long a;
            cin >> a;
            B[i][p] = f_max_digit_sum(a);
        }
    }

    // dpL[L][r][p]: row = L+r, max over columns [p, p+r]
    // Size O(N^3/2) with N<=1000 => about 167M ints max, but we store by L only needed.
    // Since NQ<=1e7, O(N^3) preprocessing is too much.
    // For each L, build sparse table over each row segment lengths via DP in O((N-L+1)^2).
    // Total O(N^3/3) still heavy. Instead use per-query O(N) with NQ<=1e7 acceptable.
    // Query: reachable rows i in [L, min(N, L+T)], and at row i columns in [P, P+(i-L)].
    // Need max over triangular region. We'll process row-wise with RMQ per row O(1).

    int K = 0;
    while ((1 << (K + 1)) <= N) K++;
    vector<int> lg(N + 1);
    for (int i = 2; i <= N; i++) lg[i] = lg[i >> 1] + 1;

    // Sparse table per row
    vector<vector<vector<int>>> st(N + 1);
    for (int i = 1; i <= N; i++) {
        int m = i;
        int kmax = lg[m] + 1;
        st[i].assign(kmax, vector<int>(m + 1, 0));
        for (int p = 1; p <= m; p++) st[i][0][p] = B[i][p];
        for (int k = 1; k < kmax; k++) {
            int len = 1 << k;
            int half = len >> 1;
            for (int p = 1; p + len - 1 <= m; p++) {
                st[i][k][p] = max(st[i][k - 1][p], st[i][k - 1][p + half]);
            }
        }
    }

    auto range_max_row = [&](int row, int l, int r) -> int {
        int len = r - l + 1;
        int k = lg[len];
        return max(st[row][k][l], st[row][k][r - (1 << k) + 1]);
    };

    for (int qi = 0; qi < Q; qi++) {
        int L, P;
        long long T;
        cin >> L >> P >> T;

        if (P > L) {
            cout << "NA\n";
            continue;
        }

        int maxRow = L + (int)min<long long>(T, N - L);
        int ans = 0;

        for (int i = L; i <= maxRow; i++) {
            int r = i - L;
            int left = P;
            int right = P + r; // <= i because P<=L
            ans = max(ans, range_max_row(i, left, right));
        }

        cout << ans << '\n';
    }

    return 0;
}

---

この解説は gpt-5.3-codex によって生成されました。