D - Optimal Path on a Triangular Board Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

三角形状に並べられた数が書かれたボードがあります。上から i 段目には i 個のマスが横一列に並んでおり、i 段目の左から p 番目（1 \leq p \leq i）のマスに書かれた数を A_{i,p} とします。ボードは全部で N 段あります。

非負整数 x に対して、x の十進表記における各桁の数字の和を S(x) と定義します。例えば S(0) = 0, S(19) = 10, S(999) = 27 です。

さらに、非負整数 V に対して、f(V) = \max_{0 \leq Y \leq V} S(Y) と定義します。すなわち、f(V) は 0 以上 V 以下の整数の中で桁和が最大となるものの桁和です。

高橋君は、あるマスにコマを置き、以下の 3 つの操作のうち 1 つを選んで行うことを繰り返します。

  • とどまる：現在のマスにとどまる。（現在の段によらず常に選択可能。）
  • 真下に移動：現在 i 段目の左から p 番目のマスにいるとき、i+1 段目の左から p 番目のマスへ移動する。（i < N のときのみ選択可能。）
  • 右下に移動：現在 i 段目の左から p 番目のマスにいるとき、i+1 段目の左から p+1 番目のマスへ移動する。（i < N のときのみ選択可能。）

Q 個の問い合わせが与えられます。j 番目の問い合わせでは、開始段 L_j、開始位置 P_j、操作回数 T_j が与えられます。

P_j > L_j の場合、L_j 段目には左から P_j 番目のマスが存在しないため、この問い合わせに対しては NA を出力してください。

P_j \leq L_j の場合、コマを L_j 段目の左から P_j 番目のマスに置き、ちょうど T_j 回の操作を行います。T_j 回の操作列として考えうるすべての選び方を考えたとき、最終的にコマが位置しうるマス全体の集合を到達可能なマスの集合と呼びます。（例えば「とどまる」を T_j 回選べば開始マスに到達できるため、開始マスは常に到達可能です。）

到達可能なマスの集合に含まれるすべてのマスについて、そのマスに書かれた値 A_{i,p} に対する f(A_{i,p}) の値を求め、その中の最大値を出力してください。

制約

  • 1 \leq N \leq 1000
  • 1 \leq Q \leq 10^5
  • NQ \leq 10^7
  • 0 \leq A_{i,p} \leq 10^{18}
  • 1 \leq L_j \leq N
  • 1 \leq P_j \leq N（P_j > L_j の場合は開始マスが存在しない）
  • 0 \leq T_j \leq 10^9
  • 入力はすべて整数である

入力

N Q
A_{1,1}
A_{2,1} A_{2,2}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
L_1 P_1 T_1
L_2 P_2 T_2
\vdots
L_Q P_Q T_Q
  • 1 行目には、ボードの段数を表す整数 N と、問い合わせの個数を表す整数 Q が、スペース区切りで与えられる。
  • 続く N 行には、各段のマスに書かれた数が順に与えられる。
  • 1 + i 行目には、i 段目の i 個の値 A_{i,1}, A_{i,2}, \ldots, A_{i,i} がスペース区切りで与えられる。
  • 続く Q 行には、問い合わせが与えられる。
  • 1 + N + j 行目には、j 番目の問い合わせの開始段 L_j、開始位置 P_j、操作回数 T_j がスペース区切りで与えられる。

出力

Q 行出力せよ。

j 行目には、j 番目の問い合わせに対する答えを出力せよ。

開始マスが存在しない場合は NA を、そうでない場合は答えとなる整数を出力せよ。

入力例 1

4 5
5
12 30
7 99 100
0 19 88 123
1 1 0
1 1 1
2 1 2
3 2 10
4 4 1

出力例 1

5
11
18
18
18

入力例 2

3 5
8
10 29
1000 909 555
1 2 0
2 3 5
1 1 2
3 1 0
2 2 1

出力例 2

NA
NA
27
27
26

入力例 3

7 10
0
9 10
18 99 100
123 4567 890 9999
1000000000000000000 999999999999999999 123456789012345678 400000000000000000 101010101010101010
1 20 300 4000 50000 600000
987654321 123456789 111111111 222222222 333333333 444444444 555555555
1 1 6
2 2 3
3 1 0
3 4 1
5 3 2
6 6 1000000000
7 1 5
4 2 1
2 1 4
7 7 0

出力例 3

162
162
9
NA
153
76
80
162
162
76

入力例 4

12 20
42
7 88
1234 99999 100000
314159 271828 161803 141421
999999999999999999 1000000000000000000 987654321098765432 123456789012345678 555555555555555555
0 1 8 17 26 35
44 53 62 71 80 89 98
107 116 125 134 143 152 161 170
179 188 197 206 215 224 233 242 251
260 269 278 287 296 305 314 323 332 341
350 359 368 377 386 395 404 413 422 431 440
449 458 467 476 485 494 503 512 521 530 539 548
1 1 11
1 2 5
2 1 0
2 2 100
3 3 2
4 1 8
5 2 7
5 6 1
6 4 3
7 7 0
8 3 1000000000
9 9 4
10 5 2
11 1 1
12 12 0
12 1 100
4 4 10
6 1 5
3 1 9
10 11 0

出力例 4

162
NA
7
162
161
162
162
NA
19
17
22
22
22
21
22
21
157
20
162
NA

入力例 5

1 4
1000000000000000000
1 1 0
1 1 1
1 1 1000000000
1 1 999999999

出力例 5

162
162
162
162

Score : 400 pts

Problem Statement

There is a board with numbers arranged in a triangular shape. The i-th row from the top contains i cells arranged in a horizontal line, and the number written in the p-th cell from the left in the i-th row (1 \leq p \leq i) is denoted A_{i,p}. The board has N rows in total.

For a non-negative integer x, define S(x) as the sum of the digits in the decimal representation of x. For example, S(0) = 0, S(19) = 10, S(999) = 27.

Furthermore, for a non-negative integer V, define f(V) = \max_{0 \leq Y \leq V} S(Y). That is, f(V) is the maximum digit sum among all integers from 0 to V inclusive.

Takahashi places a piece on a cell and repeatedly performs one of the following 3 operations:

  • Stay: Stay on the current cell. (Can always be chosen regardless of the current row.)
  • Move directly below: When currently on the p-th cell from the left in row i, move to the p-th cell from the left in row i+1. (Can only be chosen when i < N.)
  • Move diagonally right-down: When currently on the p-th cell from the left in row i, move to the (p+1)-th cell from the left in row i+1. (Can only be chosen when i < N.)

Q queries are given. The j-th query provides a starting row L_j, a starting position P_j, and a number of operations T_j.

If P_j > L_j, then the P_j-th cell from the left does not exist in row L_j, so output NA for this query.

If P_j \leq L_j, place the piece on the P_j-th cell from the left in row L_j and perform exactly T_j operations. Considering all possible choices of sequences of T_j operations, the set of all cells where the piece can ultimately be located is called the set of reachable cells. (For example, choosing "Stay" T_j times reaches the starting cell, so the starting cell is always reachable.)

For all cells in the set of reachable cells, compute f(A_{i,p}) for the value A_{i,p} written on that cell, and output the maximum among these values.

Constraints

  • 1 \leq N \leq 1000
  • 1 \leq Q \leq 10^5
  • NQ \leq 10^7
  • 0 \leq A_{i,p} \leq 10^{18}
  • 1 \leq L_j \leq N
  • 1 \leq P_j \leq N (if P_j > L_j, the starting cell does not exist)
  • 0 \leq T_j \leq 10^9
  • All inputs are integers

Input

N Q
A_{1,1}
A_{2,1} A_{2,2}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
L_1 P_1 T_1
L_2 P_2 T_2
\vdots
L_Q P_Q T_Q
  • The first line contains the integer N representing the number of rows in the board and the integer Q representing the number of queries, separated by a space.
  • The following N lines give the numbers written on the cells of each row in order.
  • The (1 + i)-th line contains the i values A_{i,1}, A_{i,2}, \ldots, A_{i,i} of the i-th row, separated by spaces.
  • The following Q lines give the queries.
  • The (1 + N + j)-th line contains the starting row L_j, starting position P_j, and number of operations T_j for the j-th query, separated by spaces.

Output

Output Q lines.

The j-th line should contain the answer to the j-th query.

If the starting cell does not exist, output NA; otherwise, output the integer that is the answer.

Sample Input 1

4 5
5
12 30
7 99 100
0 19 88 123
1 1 0
1 1 1
2 1 2
3 2 10
4 4 1

Sample Output 1

5
11
18
18
18

Sample Input 2

3 5
8
10 29
1000 909 555
1 2 0
2 3 5
1 1 2
3 1 0
2 2 1

Sample Output 2

NA
NA
27
27
26

Sample Input 3

7 10
0
9 10
18 99 100
123 4567 890 9999
1000000000000000000 999999999999999999 123456789012345678 400000000000000000 101010101010101010
1 20 300 4000 50000 600000
987654321 123456789 111111111 222222222 333333333 444444444 555555555
1 1 6
2 2 3
3 1 0
3 4 1
5 3 2
6 6 1000000000
7 1 5
4 2 1
2 1 4
7 7 0

Sample Output 3

162
162
9
NA
153
76
80
162
162
76

Sample Input 4

12 20
42
7 88
1234 99999 100000
314159 271828 161803 141421
999999999999999999 1000000000000000000 987654321098765432 123456789012345678 555555555555555555
0 1 8 17 26 35
44 53 62 71 80 89 98
107 116 125 134 143 152 161 170
179 188 197 206 215 224 233 242 251
260 269 278 287 296 305 314 323 332 341
350 359 368 377 386 395 404 413 422 431 440
449 458 467 476 485 494 503 512 521 530 539 548
1 1 11
1 2 5
2 1 0
2 2 100
3 3 2
4 1 8
5 2 7
5 6 1
6 4 3
7 7 0
8 3 1000000000
9 9 4
10 5 2
11 1 1
12 12 0
12 1 100
4 4 10
6 1 5
3 1 9
10 11 0

Sample Output 4

162
NA
7
162
161
162
162
NA
19
17
22
22
22
21
22
21
157
20
162
NA

Sample Input 5

1 4
1000000000000000000
1 1 0
1 1 1
1 1 1000000000
1 1 999999999

Sample Output 5

162
162
162
162