概要

各問い合わせについて、開始マスからちょうど \(T\) 回操作した後に到達可能なマス全体を考え、それらのマスに書かれた値 \(A_{i,p}\) に対する \(f(A_{i,p})\) の最大値を求めます。

到達可能な範囲は三角形状になるため、各段ごとの区間最大値を高速に求められるよう前処理します。

考察

到達可能なマスの形

開始マスを \((L, P)\) とします。

1 回の操作では、

• とどまる
• 真下に移動
• 右下に移動

のいずれかを選べます。

ここで、実際に下方向へ移動した回数を \(d\) 回とします。

• \(d\) 回下に移動すると、最終的な段は \(L+d\) 段目になります。
• そのうち右下に移動した回数を \(r\) 回とすると、位置は \(P+r\) になります。
• \(r\) は \(0 \leq r \leq d\) の範囲で自由に選べます。

したがって、\(d\) 回下に移動した場合に到達可能なマスは

\[ (L+d, P), (L+d, P+1), \ldots, (L+d, P+d) \]

です。

また、操作回数はちょうど \(T\) 回ですが、「とどまる」を使えば余った操作回数を消費できます。
そのため、下方向への移動回数 \(d\) は

\[ 0 \leq d \leq \min(T, N-L) \]

の範囲で可能です。

よって、到達可能なマスの集合は、各 \(d\) について

\[ L+d \text{ 段目の } [P, P+d] \]

という区間の集まりになります。

例えば、\((L, P) = (2, 1)\), \(T = 2\) のとき、到達可能な範囲は

• \(d=0\): \(2\) 段目の \(1\) 番目
• \(d=1\): \(3\) 段目の \(1\) 番目から \(2\) 番目
• \(d=2\): \(4\) 段目の \(1\) 番目から \(3\) 番目

となります。

素朴な方法の問題点

到達可能なマスをすべて列挙すると、問い合わせ 1 つあたり最大で

\[ 1 + 2 + \cdots + N = O(N^2) \]

個のマスを見ることになります。

\(Q\) 個の問い合わせに対してこれを行うと \(O(N^2Q)\) となり、間に合いません。

そこで、各段について「区間の最大値」を高速に求められるようにしておきます。
すると、各 \(d\) に対して

\[ L+d \text{ 段目の } [P, P+d] \]

の最大値を \(O(1)\) で求められるため、問い合わせ 1 つあたり \(O(N)\) で処理できます。

制約に \(NQ \leq 10^7\) があるため、これは十分高速です。

\(f(V)\) の求め方

\(f(V)\) は、\(0 \leq Y \leq V\) を満たす整数 \(Y\) の中で、桁和 \(S(Y)\) が最大になる値です。

\(V\) の十進表記を考えます。

\(Y \leq V\) であるため、\(Y\) が \(V\) より小さくなる最初の桁を考えると、その桁を \(V\) の対応する桁より \(1\) 小さくし、それ以降の桁をすべて \(9\) にするのが桁和を最大にします。

つまり、候補は次のようになります。

• \(V\) 自身
• ある桁を \(1\) 減らし、それより右側をすべて \(9\) にした数

例えば \(V=5123\) の場合、

• \(5123\)
• \(4999\)
• \(5099\)
• \(5119\)
• \(5122\)

などが候補になります。

これらの桁和の最大値を取れば \(f(V)\) が求まります。

\(V \leq 10^{18}\) なので桁数は高々 \(19\) 桁であり、各マスについて十分高速に計算できます。

アルゴリズム

まず、各マスの値 \(A_{i,p}\) を直接使うのではなく、

\[ B_{i,p} = f(A_{i,p}) \]

を前計算しておきます。

その後、各段ごとに区間最大値を高速に求めるため、Sparse Table を構築します。

Sparse Table では、

\[ \text{st}[k][i][p] \]

を

\[ i \text{ 段目の } p \text{ 番目から長さ } 2^k \text{ の区間の最大値} \]

として管理します。

遷移は次の通りです。

\[ \text{st}[k][i][p] = \max( \text{st}[k-1][i][p], \text{st}[k-1][i][p+2^{k-1}] ) \]

これにより、任意の区間 \([l, r]\) の最大値を \(O(1)\) で求められます。

区間長を \(\text{len}=r-l+1\) とし、

\[ k = \lfloor \log_2 \text{len} \rfloor \]

とすると、

\[ \max([l,r]) = \max( \text{st}[k][row][l], \text{st}[k][row][r-2^k+1] ) \]

で求められます。

各問い合わせでは、次のように処理します。

1. \(P > L\) なら開始マスが存在しないので NA を出力する。
2. そうでなければ、

$\( D = \min(T, N-L) \)$

とする。 3. 各 \(d = 0, 1, \ldots, D\) について、

$\( L+d \text{ 段目の区間 } [P, P+d] \)$

の最大値を求める。 4. それらの最大値を答えとして出力する。

計算量

• 時間計算量: \(O(N^2 \log N + NQ)\)
  • 各マスの \(f(A_{i,p})\) の計算は桁数が高々 \(19\) なので、全体で \(O(N^2)\)
  • Sparse Table の構築に \(O(N^2 \log N)\)
  • 各問い合わせは最大 \(O(N)\)、かつ \(NQ \leq 10^7\) より全体で \(O(NQ)\)
• 空間計算量: \(O(N^2 \log N)\)

実装のポイント

• \(T\) は最大 \(10^9\) と大きいですが、実際に下方向へ移動できるのは最大でも \(N-L\) 回なので、

$\( D = \min(T, N-L) \)$

として扱います。

• \(A_{i,p}\) は最大 \(10^{18}\) なので、入力には long long を使います。

• \(f(A_{i,p})\) の値は桁和なので高々数百程度であり、int で十分です。

• Sparse Table 用の配列サイズは、制約の \(N\) に合わせて十分大きく取る必要があります。
  \(N \leq 1000\) なら、MAXN は少なくとも 1000 以上にします。

  ソースコード

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

const int MAXN = 500;
const int LOG = 10;

static int st[LOG][MAXN + 2][MAXN + 2];
int lg2_table[MAXN + 2];

int calc_f(long long v) {
    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];
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d > 0) {
            ans = max(ans, pref[i] + (d - 1) + 9 * (n - i - 1));
        }
    }
    return ans;
}

int row_max(int row, int l, int r) {
    int len = r - l + 1;
    int k = lg2_table[len];
    return max(st[k][row][l], st[k][row][r - (1 << k) + 1]);
}

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

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

    for (int i = 1; i <= N; i++) {
        for (int p = 1; p <= i; p++) {
            long long x;
            cin >> x;
            st[0][i][p] = calc_f(x);
        }
    }

    lg2_table[1] = 0;
    for (int i = 2; i <= N; i++) {
        lg2_table[i] = lg2_table[i / 2] + 1;
    }

    for (int k = 1; k < LOG; k++) {
        int len = 1 << k;
        if (len > N) break;
        int half = 1 << (k - 1);

        for (int row = 1; row <= N; row++) {
            for (int p = 1; p + len - 1 <= row; p++) {
                st[k][row][p] = max(st[k - 1][row][p], st[k - 1][row][p + half]);
            }
        }
    }

    while (Q--) {
        int L, P;
        long long T;
        cin >> L >> P >> T;

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

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

        for (int d = 0; d <= D; d++) {
            int row = L + d;
            ans = max(ans, row_max(row, P, P + d));
        }

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

    return 0;
}

---

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