概要

三角形ボード上で、指定された開始位置から一定回数の操作で到達可能な全マスについて、各マスの値に対する \(f\)（0からその値以下で最大の桁和）の最大値を求める問題です。

考察

到達可能なマスの特定

開始マスが \((L, P)\)（\(L\) 段目の左から \(P\) 番目）で操作回数が \(T\) のとき、到達可能なマスを考えます。

• 段 \(r\) に到達するには、最低 \(r - L\) 回の下方向への移動が必要です（残りは「とどまる」で消費）。
• よって到達可能な段は \(L \leq r \leq \min(N, L + T)\) です。
• 段 \(r\) に到達するとき、\(r - L\) 回の下方向移動のうち「真下」と「右下」の選び方により、列は \(P\) から \(P + (r - L)\) の範囲になります（ただし段 \(r\) には \(r\) 列しかないので \(\min(P + (r-L),\ r)\) が上限）。

つまり、各段 \(r\) での到達可能列は 連続した区間 \([P,\ \min(P + (r-L),\ r)]\) です。

\(f(V)\) の計算

\(f(V) = \max_{0 \leq Y \leq V} S(Y)\) を求めるには、\(V\) の十進表記の各桁 \(i\) について「その桁を1減らし、それ以降を全て9にした数」の桁和を候補として比較します。例えば \(V = 523\) のとき： - 位置0: \((5-1) + 9 \times 2 = 22\)（つまり 499） - 位置1: \(5 + (2-1) + 9 \times 1 = 14\)（つまり 519） - そのまま: \(5 + 2 + 3 = 10\)（つまり 523）

最大は 22 なので \(f(523) = 22\) です。

区間最大値クエリの高速化

各クエリで各段の連続区間の最大値を求める必要があるため、各段にスパーステーブルを構築し \(O(1)\) で区間最大値を取得します。

アルゴリズム

1. 前処理: 全マス \((i, p)\) について \(f(A_{i,p})\) を計算する。
2. スパーステーブル構築: 各段について \(f\) 値の区間最大クエリに答えるためのスパーステーブルを構築。
3. クエリ処理: 各クエリ \((L, P, T)\) について：
   • \(P > L\) なら NA を出力。
   • そうでなければ、段 \(r = L, L+1, \ldots, \min(N, L+T)\) をループし、各段での到達可能列区間の最大 \(f\) 値をスパーステーブルで \(O(1)\) 取得し、全体の最大値を出力。

計算量

• 時間計算量: 前処理 \(O(N^2 \log N)\)、クエリ全体 \(O(NQ)\)（制約より \(NQ \leq 10^7\)）
• 空間計算量: \(O(N^2 \log N)\)（スパーステーブル用）

実装のポイント

• \(f(V)\) の計算: 各桁を走査し、「その桁を1減らして残りを全て9にする」候補と「元の数そのもの」の桁和を比較します。\(d = 0\) の桁は減らせないのでスキップ。

• 0-indexed と 1-indexed の変換: 問題文は1-indexed、コード内部は0-indexedなので P-1 に変換して処理します。

• \(T\) が非常に大きい場合: \(L + T\) が \(N\) を超えることがありますが、min(N, L+T) で制限すれば問題ありません。

• __lg(len): GCCの組み込み関数で \(\lfloor \log_2(\text{len}) \rfloor\) を高速に計算でき、スパーステーブルのクエリで使用します。

  ソースコード

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

int compute_f(long long V) {
    if (V <= 0) return 0;
    string s = to_string(V);
    int n = s.size();
    int best = 0;
    int prefix_sum = 0;
    for (int i = 0; i < n; i++) {
        int d = s[i] - '0';
        if (d > 0) {
            int candidate = prefix_sum + (d - 1) + 9 * (n - 1 - i);
            best = max(best, candidate);
        }
        prefix_sum += d;
    }
    best = max(best, prefix_sum);
    return best;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, Q;
    cin >> N >> Q;
    
    vector<vector<int>> fval(N);
    // Sparse table for each row
    vector<vector<vector<int>>> sparse(N);
    
    for (int i = 0; i < N; i++) {
        fval[i].resize(i + 1);
        for (int p = 0; p <= i; p++) {
            long long a;
            cin >> a;
            fval[i][p] = compute_f(a);
        }
        int len = i + 1;
        int LOG = 1;
        while ((1 << LOG) <= len) LOG++;
        sparse[i].resize(LOG);
        sparse[i][0] = fval[i];
        for (int k = 1; k < LOG; k++) {
            int sz = len - (1 << k) + 1;
            if (sz <= 0) break;
            sparse[i][k].resize(sz);
            for (int j = 0; j < sz; j++) {
                sparse[i][k][j] = max(sparse[i][k-1][j], sparse[i][k-1][j + (1 << (k-1))]);
            }
        }
    }
    
    auto query_max = [&](int row, int l, int r) -> int {
        // range [l, r] inclusive, 0-indexed
        if (l > r) return 0;
        int len = r - l + 1;
        int k = __lg(len);
        return max(sparse[row][k][l], sparse[row][k][r - (1 << k) + 1]);
    };
    
    for (int q = 0; q < Q; q++) {
        int L, P;
        long long T;
        cin >> L >> P >> T;
        if (P > L) {
            cout << "NA\n";
            continue;
        }
        long long max_row_ll = min((long long)N, (long long)L + T);
        int max_row = (int)max_row_ll;
        int ans = 0;
        for (int r = L; r <= max_row; r++) {
            int cs = P - 1; // 0-indexed left
            int ce = P - 1 + (r - L); // 0-indexed right
            // row r (1-indexed) has r columns, 0-indexed: 0 to r-1
            if (ce >= r) ce = r - 1;
            int row_idx = r - 1;
            int rm = query_max(row_idx, cs, ce);
            ans = max(ans, rm);
        }
        cout << ans << "\n";
    }
    
    return 0;
}

---

この解説は claude4.6opus-thinking によって生成されました。