E - Calendar Validator

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。

N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を(向きを変えずに)切り出したものであるかを判定してください。

制約

  • 1 \leq N \leq 10^4
  • 1 \leq M \leq 7
  • 1 \leq B_{i,j} \leq 10^9
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

出力

B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。


入力例 1

2 3
1 2 3
8 9 10

出力例 1

Yes

与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。


入力例 2

2 1
1
2

出力例 2

No

与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。


入力例 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

出力例 3

Yes

Score : 300 points

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

  • 1 \leq N \leq 10^4
  • 1 \leq M \leq 7
  • 1 \leq B_{i,j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

Output

If B is some rectangular part of A, print Yes; otherwise, print No.


Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.


Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.


Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes
F - Sowing Stones

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N まで番号がつけられた N 個のマスが一列に並んでいます。最初、 M 個のマスに石が入っており、マス X_i には A_i 個 (1 \leq i \leq M) の石が入っています。

あなたは以下の操作を好きな回数( 0 回でもよい)行うことができます。

  • マス i (1 \leq i \leq N-1) に石があるとき、マス i から石を 1 つマス i+1 に移動させる。

N 個のマスすべてに石がちょうど 1 個ずつ入っている状態にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は -1 を出力してください。

制約

  • 2 \leq N \leq 2 \times 10^{9}
  • 1 \leq M \leq 2 \times 10^{5}
  • M \leq N
  • 1 \leq X_i \leq N (1 \leq i \leq M)
  • X_i \neq X_j (1 \leq i < j \leq M)
  • 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M
X_1 X_2 \ldots X_M
A_1 A_2 \ldots A_M

出力

答えを出力せよ。


入力例 1

5 2
1 4
3 2

出力例 1

4

以下の 4 回の操作で、5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることができます。

  • マス 1 の石を 1 つマス 2 に移動させる。
  • マス 2 の石を 1 つマス 3 に移動させる。
  • マス 4 の石を 1 つマス 5 に移動させる。
  • マス 1 の石を 1 つマス 2 に移動させる。

また、3 回以下の操作では 5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、4 を出力します。


入力例 2

10 3
1 4 8
4 2 4

出力例 2

-1

どのように操作を行っても 10 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、-1 を出力します。

Score : 300 points

Problem Statement

There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).

You can perform the following operation any number of times (possibly zero):

  • If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.

Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.

Constraints

  • 2 \leq N \leq 2 \times 10^{9}
  • 1 \leq M \leq 2 \times 10^{5}
  • M \leq N
  • 1 \leq X_i \leq N (1 \leq i \leq M)
  • X_i \neq X_j (1 \leq i < j \leq M)
  • 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M
X_1 X_2 \ldots X_M
A_1 A_2 \ldots A_M

Output

Print the answer.


Sample Input 1

5 2
1 4
3 2

Sample Output 1

4

You can reach a state where each of the five cells contains exactly one stone with four operations as follows:

  • Move one stone from cell 1 to cell 2.
  • Move one stone from cell 2 to cell 3.
  • Move one stone from cell 4 to cell 5.
  • Move one stone from cell 1 to cell 2.

It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.


Sample Input 2

10 3
1 4 8
4 2 4

Sample Output 2

-1

No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.

G - Between Two Arrays

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ n の数列 S = (s_1, s_2, \dots, s_n) がすべての i (1 \leq i \leq n - 1) に対して s_i \leq s_{i+1} を満たすとき、かつそのときに限り「数列 S は広義単調増加である」と呼びます。

広義単調増加な長さ N の整数列 A = (a_1, a_2, \dots, a_N), B = (b_1, b_2, \dots, b_N) が与えられます。
このとき、次の条件を満たす広義単調増加な長さ N の整数列 C = (c_1, c_2, \dots, c_N) を考えます。

  • すべての i (1 \leq i \leq N) に対して a_i \leq c_i \leq b_i が成り立つ。

整数列 C としてあり得る数列の個数を 998244353 で割ったあまりを求めてください。

制約

  • 1 \leq N \leq 3000
  • 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
  • 整数列 A,B は広義単調増加である。
  • 入力はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 \dots a_N
b_1 b_2 \dots b_N

出力

C としてあり得る数列の個数を 998244353 で割ったあまりを出力せよ。


入力例 1

2
1 1
2 3

出力例 1

5

C としてあり得る数列は次の 5 個です。

  • (1, 1)
  • (1, 2)
  • (1, 3)
  • (2, 2)
  • (2, 3)

数列 (2, 1) は広義単調増加でないため条件を満たさないことに注意してください。


入力例 2

3
2 2 2
2 2 2

出力例 2

1

C としてあり得る数列は次の 1 個です。

  • (2, 2, 2)

入力例 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

出力例 3

978222082

個数を 998244353 で割ったあまりを求めることに注意してください。

Score : 400 points

Problem Statement

A sequence of n numbers, S = (s_1, s_2, \dots, s_n), is said to be non-decreasing if and only if s_i \leq s_{i+1} holds for every i (1 \leq i \leq n - 1).

Given are non-decreasing sequences of N integers each: A = (a_1, a_2, \dots, a_N) and B = (b_1, b_2, \dots, b_N).
Consider a non-decreasing sequence of N integers, C = (c_1, c_2, \dots, c_N), that satisfies the following condition:

  • a_i \leq c_i \leq b_i for every i (1 \leq i \leq N).

Find the number, modulo 998244353, of sequences that can be C.

Constraints

  • 1 \leq N \leq 3000
  • 0 \leq a_i \leq b_i \leq 3000 (1 \leq i \leq N)
  • The sequences A and B are non-decreasing.
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 \dots a_N
b_1 b_2 \dots b_N

Output

Print the number, modulo 998244353, of sequences that can be C.


Sample Input 1

2
1 1
2 3

Sample Output 1

5

There are five sequences that can be C, as follows.

  • (1, 1)
  • (1, 2)
  • (1, 3)
  • (2, 2)
  • (2, 3)

Note that (2, 1) does not satisfy the condition since it is not non-decreasing.


Sample Input 2

3
2 2 2
2 2 2

Sample Output 2

1

There is one sequence that can be C, as follows.

  • (2, 2, 2)

Sample Input 3

10
1 2 3 4 5 6 7 8 9 10
1 4 9 16 25 36 49 64 81 100

Sample Output 3

978222082

Be sure to find the count modulo 998244353.

H - Tree and Hamilton Path 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

AtCoder国には 1 から N の番号がついた N 個の街と 1 から N-1 の番号がついた N-1 本の道路があります。

道路 i は街 A_i と街 B_i を双方向に結び、長さは C_i です。どの街同士も、いくつかの道路を通って互いに行き来することができます。

いずれかの街を出発し、道路による移動で全ての街を 1 度以上訪れるための移動距離の最小値を求めてください。

制約

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • 1 \leq C_i \leq 10^9
  • 入力は全て整数である
  • どの街同士も、いくつかの道路を通って互いに行き来できる

入力

入力は以下の形式で標準入力から与えられる。

N
A_1 B_1 C_1
\vdots
A_{N-1} B_{N-1} C_{N-1}

出力

答えを出力せよ。


入力例 1

4
1 2 2
1 3 3
1 4 4

出力例 1

11

4 \to 1 \to 2 \to 1 \to 3 と移動すると移動距離の合計は 11 となり、これが最小値です。

最初の街に戻ってくる必要はないことに注意してください。


入力例 2

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

出力例 2

9000000000

オーバーフローに注意してください。

Score : 500 points

Problem Statement

In the nation of AtCoder, there are N cities numbered 1 to N and N-1 roads numbered 1 to N-1.

Road i connects cities A_i and B_i bidirectionally, and its length is C_i. Any pair of cities can be reached from each other by traveling through some roads.

Find the minimum travel distance required to start from a city and visit all cities at least once using the roads.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 1 \leq A_i, B_i \leq N
  • 1 \leq C_i \leq 10^9
  • All input values are integers.
  • Any pair of cities can be reached from each other by traveling through some roads.

Input

The input is given from Standard Input in the following format:

N
A_1 B_1 C_1
\vdots
A_{N-1} B_{N-1} C_{N-1}

Output

Print the answer.


Sample Input 1

4
1 2 2
1 3 3
1 4 4

Sample Output 1

11

If you travel as 4 \to 1 \to 2 \to 1 \to 3, the total travel distance is 11, which is the minimum.

Note that you do not need to return to the starting city.


Sample Input 2

10
10 9 1000000000
9 8 1000000000
8 7 1000000000
7 6 1000000000
6 5 1000000000
5 4 1000000000
4 3 1000000000
3 2 1000000000
2 1 1000000000

Sample Output 2

9000000000

Beware overflow.

I - Useless for LIS

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

長さ N の整数列 A が与えられます。

t = 1, 2, \dots ,N について、 A_t が A の最長増加部分列に含まれることがあるか判定してください。

A_t が A の最長増加部分列に含まれることがあるとは、以下のことをいいます。

  • 最長増加部分列の長さを L とする。各要素が 1 以上 N 以下の単調増加な整数列 i = (i_1, i_2, \dots ,i_L) \ (i_1 < i_2 < \dots < i_L) であって以下をすべて満たすものが存在する。

    • A_{i_1} < A_{i_2} < \dots < A_{i_L}
    • ある k \ (1 \leq k \leq L) が存在して i_k = t である

T 個のテストケースが与えられるので、それぞれについて答えを求めてください。

最長増加部分列とは?

列 A の部分列とは A の要素をいくつか抜き出して元の順に並べてできる列を指します。

列 A の最長増加部分列とは、 A の狭義単調増加な部分列のうち列の長さが最大のものを指します。

制約

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 全てのテストケースにおける N の総和は 2 \times 10^5 以下

入力

入力は以下の形式で標準入力から与えられる。

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

ここで \mathrm{case_i} は i 番目のケースの入力を意味する。各ケースは以下の形式で与えられる。

N
A_1 A_2 \cdots A_N

出力

以下の形式で出力せよ。

\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T

ここで \mathrm{answer}_i は i 番目のケースの出力を意味する。各ケースについては、次の通りである。

A_t が A の最長増加部分列に含まれることがある t が m 個存在し、昇順に i_1, i_2, \dots ,i_m であったとする。このとき、以下の形式で出力せよ。

m
i_1 i_2 \cdots i_m

入力例 1

1
5
2 1 4 5 3

出力例 1

4
1 2 3 4

最長増加部分列の 1 つは (2, 4, 5) で、長さは 3 です。(1, 4, 5) も最長増加部分列の 1 つです。しかし、 A_5 を含む最長増加部分列はありません。

よって、 1, 2, 3, 4 を出力します。


入力例 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

出力例 2

5
1 3 4 5 6
2
4 5

Score : 525 points

Problem Statement

You are given an integer sequence A of length N.

For each t = 1, 2, \dots, N, determine whether A_t is included in a longest increasing subsequence of A.

Here, A_t is included in a longest increasing subsequence of A if and only if the following holds:

  • Let L be the length of a longest increasing subsequence of A. There exists a strictly increasing integer sequence i = (i_1, i_2, \dots, i_L) \ (i_1 < i_2 < \dots < i_L), where each element is between 1 and N, inclusive, that satisfies all of the following conditions:

    • A_{i_1} < A_{i_2} < \dots < A_{i_L}.
    • i_k = t for some k \ (1 \leq k \leq L).

You are given T test cases; solve each of them.

What is a longest increasing subsequence?

A subsequence of a sequence A is a sequence that can be derived by extracting some elements from A without changing the order.

A longest increasing subsequence of a sequence A is a subsequence of A that is strictly increasing with the greatest possible length.

Constraints

  • 1 \leq T \leq 2 \times 10^5
  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • The sum of N across all test cases is at most 2 \times 10^5.

Input

The input is given from Standard Input in the following format:

T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T

Here, \mathrm{case_i} represents the input for the i-th case. Each case is given in the following format:

N
A_1 A_2 \cdots A_N

Output

Print the answers in the following format:

\mathrm{answer}_1
\mathrm{answer}_2
\vdots
\mathrm{answer}_T

Here, \mathrm{answer}_i represents the output for the i-th case. For each case, let there be m indices t such that A_t is included in a longest increasing subsequence of A, which are i_1, i_2, \dots, i_m in ascending order. Print these in the following format:

m
i_1 i_2 \cdots i_m

Sample Input 1

1
5
2 1 4 5 3

Sample Output 1

4
1 2 3 4

One of the longest increasing subsequences is (2, 4, 5), with a length of 3. Another longest increasing subsequence is (1, 4, 5). However, no longest increasing subsequence includes A_5.

Therefore, print 1, 2, 3, 4.


Sample Input 2

2
6
2 5 3 4 3 4
5
10000 1000 100 1 10

Sample Output 2

5
1 3 4 5 6
2
4 5