概要

三角形のボード上で、与えられた開始地点から指定された操作回数以内で到達可能なマスの集合を特定し、それらのマスに書かれた数 \(A_{i,p}\) から得られる値 \(f(A_{i,p})\) の最大値を求める問題です。

考察

1. 関数 \(f(V)\) の性質

\(f(V)\) は「\(0\) 以上 \(V\) 以下の整数の中で最大の桁和」です。 桁和を大きくするには、できるだけ多くの桁を \(9\) にするのが得策です。例えば \(V = 123\) の場合、以下の候補が考えられます。 - \(V\) そのもの：\(1+2+3 = 6\) - \(122\) 以下の最大桁和：\(1+2+1\) (末尾を \(9\) にできないか検討) \(\to 1+1+9 = 11\) - \(119\) 以下の最大桁和：\(0+9+9 = 18\)

一般に、ある桁を \(1\) 減らしてそれより下の桁をすべて \(9\) にした数は \(V\) 以下になります。この性質を利用して、各桁について「その桁を \(1\) 減らし、下位桁をすべて \(9\) にする」という操作を試すことで、\(f(V)\) を \(O(\log V)\) で求められます。

2. 到達可能なマスの範囲

開始地点を \((L, P)\)、操作回数を \(T\) とします。 - 段数 \(i\) の範囲: 「とどまる」操作があるため、開始段 \(L\) から最大 \(L+T\) 段目まで到達可能です。ただし、ボードは \(N\) 段までなので、\(L \leq i \leq \min(L+T, N)\) となります。 - 各段における位置 \(p\) の範囲: - \(i\) 段目に到達するには、少なくとも \(i-L\) 回の「真下に移動」または「右下に移動」が必要です。 - 「右下に移動」を \(0\) 回行えば位置は \(P\) のまま、「右下に移動」を最大限（\(i-L\) 回）行えば位置は \(P + (i-L)\) になります。 - したがって、\(i\) 段目において到達可能な位置は \(P \leq p \leq P + (i-L)\) です。

3. 高速化の必要性

クエリごとに到達可能なすべてのマスを走査すると、最悪ケースで \(1\) クエリあたり \(O(T^2)\) かかり、全体で \(O(QT^2)\) となり間に合いません。 しかし、各段 \(i\) における \(p\) の範囲は連続した区間 \([P, P+i-L]\) です。この区間内の \(f(A_{i,p})\) の最大値を高速に取得できれば、クエリあたりの計算量を \(O(\text{移動した段数})\)、つまり \(O(N)\) に抑えることができます。

アルゴリズム

1. 前処理 (\(f(V)\) の計算): ボードの全マス \((i, p)\) について \(f(A_{i,p})\) を計算します。
2. 前処理 (Sparse Table の構築): 各段（行）ごとに、静的な区間最大値クエリ (RMQ) を \(O(1)\) で処理できるよう Sparse Table を構築します。
   • st[i][k][j] : \(i\) 段目の左から \(j\) 番目から長さ \(2^k\) の範囲の \(f(A_{i,p})\) の最大値。
3. クエリ処理: 各クエリ \((L, P, T)\) に対して：
   • \(P > L\) なら NA を出力。
   • \(i = L\) から \(\min(L+T, N)\) までループを回す。
   • 各 \(i\) について、区間 \([P, P+i-L]\) の最大値を Sparse Table を使って \(O(1)\) で取得。
   • 全体の最大値を更新して出力。

計算量

• 時間計算量: \(O(N^2 \log N + NQ)\)
  • \(f(V)\) の計算: \(O(N^2 \log (\max A))\)
  • Sparse Table 構築: \(O(N^2 \log N)\)
  • クエリ処理: 制約 \(NQ \leq 10^7\) より、各クエリで最大 \(N\) 行走査しても十分に間に合います。
• 空間計算量: \(O(N^2 \log N)\)
  • Sparse Table の保持に必要です。\(N=1000\) のとき、\(1000 \times 11 \times 1000 \times 4\) バイト \(\approx 44\) MB 程度であり、メモリ制限内です。

実装のポイント

• Sparse Table: 構築時に 31 - __builtin_clz(len) 等を使って \(2\) のべき乗を計算すると高速です。

• 入出力: クエリ数が多いため、cin.tie(nullptr); ios::sync_with_stdio(false); による高速化が推奨されます。

• \(f(V)\) の計算: \(V=0\) の場合や、各桁を処理する際の digit > 0 の判定に注意してください。

  ソースコード

#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;
}

この解説は gemini-3-flash-thinking によって生成されました。