概要

各マスの値 \(A_{i,p}\) を、あらかじめ \(f(A_{i,p})\) に変換しておきます。
各問い合わせでは、到達可能なマスが各段で「連続区間」になることを利用し、段ごとの区間最大値を高速に求めます。

考察

到達可能なマスの形

開始位置を \((L, P)\) とします。

操作には以下の \(3\) 種類があります。

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

「とどまる」は位置を変えないため、実際に段が下がる回数を \(m\) 回とすると、到達する段は \(L+m\) 段目です。

ちょうど \(T\) 回操作する必要がありますが、「とどまる」を使えば操作回数を調整できます。
したがって、下に移動する回数 \(m\) は

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

の任意の値を取れます。

また、\(m\) 回下に移動するうち、右下に移動した回数を \(k\) 回とすると、位置は

\[ (L+m,\ P+k) \]

になります。

ここで \(k\) は

\[ 0 \leq k \leq m \]

なので、\(L+m\) 段目で到達可能な位置は

\[ P, P+1, \ldots, P+m \]

という連続区間になります。

つまり、問い合わせ \((L, P, T)\) に対する到達可能なマスは、各段ごとに見ると次のようになります。

• \(L\) 段目: \([P, P]\)
• \(L+1\) 段目: \([P, P+1]\)
• \(L+2\) 段目: \([P, P+2]\)
• \(\cdots\)
• \(\min(N, L+T)\) 段目まで

例えば \(L=3, P=2, T=2\) なら、到達可能な範囲は

• \(3\) 段目: \([2,2]\)
• \(4\) 段目: \([2,3]\)
• \(5\) 段目: \([2,4]\)

です。

素朴な方法の問題点

操作列をすべて試すと、最大で \(3^T\) 通りになり、到底間に合いません。

また、到達可能なマスをすべて列挙すると、1 回の問い合わせで最大 \(O(N^2)\) 個のマスを見ることになります。
\(Q\) が大きいので、これも間に合いません。

しかし、各段で見るべき範囲は連続区間です。
そのため、各段について「区間最大値」を高速に求められれば、1 問い合わせあたり段数分、つまり \(O(N)\) で処理できます。

制約に \(NQ \leq 10^7\) があるため、各問い合わせ \(O(N)\) は十分間に合います。

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

\(f(V)\) は

\[ 0 \leq Y \leq V \]

を満たす整数 \(Y\) のうち、桁和 \(S(Y)\) が最大になるものの桁和です。

すべての \(Y\) を試すことはできません。

\(V\) の十進表記を考えます。
最大の桁和を作るには、ある桁を \(1\) 小さくして、その右側をすべて \(9\) にするのが最適です。

例えば

\[ V = 2503 \]

なら、候補として

• \(2503\) 自身、桁和 \(2+5+0+3=10\)
• \(1999\)、桁和 \(1+9+9+9=28\)
• \(2499\)、桁和 \(2+4+9+9=24\)
• \(2502\)、桁和 \(2+5+0+2=9\)

などを考えれば十分です。

一般に、ある桁の数字が \(d>0\) で、その左側の桁和が \(\mathrm{pref}\)、右側に残り \(r\) 桁あるとします。
その桁を \(d-1\) にして、右側をすべて \(9\) にすると、桁和は

\[ \mathrm{pref} + (d-1) + 9r \]

になります。

これを全桁について試し、最後に \(V\) 自身の桁和も候補に入れれば \(f(V)\) が求まります。

\(A_{i,p} \leq 10^{18}\) なので、桁数は高々 \(19\) 桁です。
したがって、各マスの \(f(A_{i,p})\) は十分高速に計算できます。

アルゴリズム

まず、各マスの値を

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

に変換します。

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

前処理

各段 \(i\) について、配列

\[ B_{i,1}, B_{i,2}, \ldots, B_{i,i} \]

を考えます。

この配列に対して、Sparse Table を作ります。

Sparse Table では、

\[ \mathrm{st}[k][p] \]

を「位置 \(p\) から長さ \(2^k\) の区間の最大値」とします。

すると、任意の区間 \([l,r]\) の最大値は、区間長を

\[ len = r-l+1 \]

として、

\[ k = \lfloor \log_2 len \rfloor \]

を選べば、

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

で求められます。

問い合わせ処理

問い合わせ \((L, P, T)\) に対して、まず \(P > L\) なら開始マスが存在しないので NA を出力します。

そうでなければ、到達できる最終段の最大値は

\[ R = \min(N, L+T) \]

です。

各段 \(r\) について、到達可能な位置は

\[ [P,\ P+(r-L)] \]

です。

この区間の最大値を、その段の Sparse Table で求め、全段について最大を取れば答えです。

具体的には、

1. ans = 0 とする
2. \(r=L\) から \(R\) まで順に見る
3. 区間 \([P, P+(r-L)]\) の最大値を取得する
4. ans を更新する
5. 最後に ans を出力する

計算量

• 時間計算量: \(O(N^2 \log N + NQ)\)
  • 各マスの \(f(A_{i,p})\) の計算は桁数が高々 \(19\) なので、全体で \(O(N^2)\)
  • 各段の Sparse Table 構築が合計で \(O(N^2 \log N)\)
  • 各問い合わせは最大 \(O(N)\)、制約より合計 \(O(NQ)\)
• 空間計算量: \(O(N^2 \log N)\)
  • 各段の Sparse Table を保持するため

実装のポイント

• \(T\) は最大 \(10^9\) と大きいですが、段数は \(N\) までしかないため、見る段は \(\min(N, L+T)\) までで十分です。

• \(P > L\) の場合は開始マスが存在しないので、計算せず NA を出力します。

• \(f(A_{i,p})\) の最大値は \(162\) です。

  • \(10^{18}\) 以下で桁和が最大になるのは \(999999999999999999\) で、桁和は \(9 \times 18 = 162\) です。
  • そのため、コードでは値を bytearray / bytes に格納してメモリを節約しています。

• 答えが \(162\) になったら、それ以上大きくならないので、その問い合わせの処理を途中で打ち切ることもできます。

  ソースコード

import sys


def max_digit_sum_token(bs):
    if bs[0] == 48:
        if len(bs) == 1:
            return 0
        bs = bs.lstrip(b'0')
        if not bs:
            return 0

    n = len(bs)
    pref = 0
    ans = 0
    rem = n - 1

    for c in bs:
        d = c - 48
        if d:
            cand = pref + d - 1 + 9 * rem
            if cand > ans:
                ans = cand
        pref += d
        rem -= 1

    if pref > ans:
        ans = pref
    return ans


def main():
    input = sys.stdin.buffer.readline

    N, Q = map(int, input().split())

    logs = [0] * (N + 2)
    for i in range(2, N + 2):
        logs[i] = logs[i >> 1] + 1

    powers = [1 << i for i in range(logs[N] + 1)]

    rmq = [None] * (N + 1)
    calc = max_digit_sum_token

    for i in range(1, N + 1):
        parts = input().split()
        row = bytearray(i + 1)

        for p, tok in enumerate(parts, 1):
            row[p] = calc(tok)

        prev = bytes(row)
        levels = [prev]
        length = 1

        while (length << 1) <= i:
            seg = length << 1
            limit = i - seg + 1
            new = bytearray(limit + 1)
            pr = prev
            h = length

            for p in range(1, limit + 1):
                a = pr[p]
                b = pr[p + h]
                new[p] = a if a >= b else b

            prev = bytes(new)
            levels.append(prev)
            length = seg

        rmq[i] = levels

    out = []
    append = out.append
    rows = rmq
    MAX_F = 162

    for _ in range(Q):
        L, P, T = map(int, input().split())

        if P > L:
            append("NA")
            continue

        if T < N - L:
            end = L + T
        else:
            end = N

        ans = 0
        length = 1
        p = P

        for r in range(L, end + 1):
            k = logs[length]
            seg = powers[k]
            arr = rows[r][k]

            v = arr[p]
            w = arr[p + length - seg]
            if w > v:
                v = w

            if v > ans:
                ans = v
                if ans == MAX_F:
                    break

            length += 1

        append(str(ans))

    sys.stdout.write("\n".join(out))


if __name__ == "__main__":
    main()

---

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