実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は武術家です。 武術家の覚えられる技は N 個あり、技 1, 2, \ldots, N と名前がついています。 1 \leq i \leq N について、技 i を習得するには時間 T_i の修練が必要で、 さらに、修練の開始時点で技 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} をすでに習得している必要があります。 ここで、1 \leq j \leq K_i について、A_{i,j} < i であることが保証されます。
高橋君は時刻 0 の時点で技を 1 つも覚えていません。 高橋君は同時に 1 つの技に対する修練しかできず、また、一度始めた修練を途中でやめることもできません。 高橋君が技 N を習得するのに必要な時間の最小値を求めてください。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq K_i < i
- 1 \leq A_{i,j} < i
- \sum_{i=1}^N K_i \leq 2\times 10^5
- A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} はすべて異なる。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
T_1 K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
T_2 K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
T_N K_N A_{N,1} A_{N,2} \ldots A_{N,K_N}
出力
技 N を習得するのに必要な時間の最小値を出力せよ。
入力例 1
3 3 0 5 1 1 7 1 1
出力例 1
10
例えば高橋君は次のように行動することができます。
- 高橋君は時刻 0 に技 1 の修練を開始し、時刻 3 に技 1 を習得します。
- その後、時刻 3 に技 3 の修練を開始し、時刻 10 に技 3 を習得します。
このときが最短で、高橋君が技 3 を習得するのに必要な時間は 3+7=10 となります。 技 3 の習得のためには、技 2 を習得する必要はありません。
入力例 2
5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4
出力例 2
5000000000
答えが 32 bit 整数に収まらないことがある事に注意してください。
Score : 300 points
Problem Statement
Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.
Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq T_i \leq 10^9
- 0 \leq K_i < i
- 1 \leq A_{i,j} < i
- \sum_{i=1}^N K_i \leq 2\times 10^5
- A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} are all distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
T_1 K_1 A_{1,1} A_{1,2} \ldots A_{1,K_1}
T_2 K_2 A_{2,1} A_{2,2} \ldots A_{2,K_2}
\vdots
T_N K_N A_{N,1} A_{N,2} \ldots A_{N,K_N}
Output
Print the minimum number of minutes needed for Takahashi to learn Move N.
Sample Input 1
3 3 0 5 1 1 7 1 1
Sample Output 1
10
Here is one possible plan for Takahashi.
- At time 0, start practicing for Move 1 to learn Move 1 at time 3.
- Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.
Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.
Sample Input 2
5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4
Sample Output 2
5000000000
Note that the answer may not fit into a 32-bit integer.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
H_1 行 W_1 列の行列 A と、H_2 行 W_2 列の行列 B が与えられます。
- 1 \leq i \leq H_1 かつ 1 \leq j \leq W_1 を満たす整数の組 (i, j) について、行列 A の i 行目 j 列目の要素は A_{i, j} です。
- 1 \leq i \leq H_2 かつ 1 \leq j \leq W_2 を満たす整数の組 (i, j) について、行列 B の i 行目 j 列目の要素は B_{i, j} です。
行列 A に対して、下記の 2 つの操作のうちどちらかを行うことを、好きなだけ（ 0 回でも良い）繰り返すことができます。
- A の行を任意に 1 つ選んで削除する。
- A の列を任意に 1 つ選んで削除する。
行列 A を行列 B に一致させることができるかどうかを判定して下さい。
制約
- 1 \leq H_2 \leq H_1 \leq 10
- 1 \leq W_2 \leq W_1 \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 1 \leq B_{i, j} \leq 10^9
- 入力中の値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}
出力
行列 A を行列 B に一致させることができる場合は Yes を、
一致させることができない場合は No を出力せよ。
ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。
入力例 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 6 8 9 16 18 19
出力例 1
Yes
初期状態の行列 A から 2 列目を削除すると、行列 A は
1 3 4 5 6 8 9 10 11 13 14 15 16 18 19 20
となります。そこからさらに 3 行目を削除すると、行列 A は
1 3 4 5 6 8 9 10 16 18 19 20
となります。そこからさらに 1 行目を削除すると、行列 A は
6 8 9 10 16 18 19 20
となります。そこからさらに 4 列目を削除すると、行列 A は
6 8 9 16 18 19
となります。これは行列 B と一致します。
操作の繰り返しによって行列 A を行列 B に一致させることができるので Yes を出力します。
入力例 2
3 3 1 1 1 1 1 1 1 1 1 1 1 2
出力例 2
No
どのように操作を行っても、 行列 A を行列 B に一致させることはできません。
よって、No を出力します。
Score : 300 points
Problem Statement
You are given a matrix A with H_1 rows and W_1 columns, and a matrix B with H_2 rows and W_2 columns.
- For all integer pairs (i, j) such that 1 \leq i \leq H_1 and 1 \leq j \leq W_1, the element at the i-th row and j-th column of matrix A is A_{i, j}.
- For all integer pairs (i, j) such that 1 \leq i \leq H_2 and 1 \leq j \leq W_2, the element at the i-th row and j-th column of matrix B is B_{i, j}.
You may perform the following operations on the matrix A any number of (possibly 0) times in any order:
- Choose an arbitrary row of A and remove it.
- Choose an arbitrary column of A and remove it.
Determine if it is possible to make the matrix A equal the matrix B.
Constraints
- 1 \leq H_2 \leq H_1 \leq 10
- 1 \leq W_2 \leq W_1 \leq 10
- 1 \leq A_{i, j} \leq 10^9
- 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:
H_1 W_1
A_{1, 1} A_{1, 2} \ldots A_{1, W_1}
A_{2, 1} A_{2, 2} \ldots A_{2, W_1}
\vdots
A_{H_1, 1} A_{H_1, 2} \ldots A_{H_1, W_1}
H_2 W_2
B_{1, 1} B_{1, 2} \ldots B_{1, W_2}
B_{2, 1} B_{2, 2} \ldots B_{2, W_2}
\vdots
B_{H_2, 1} B_{H_2, 2} \ldots B_{H_2, W_2}
Output
Print Yes if it is possible to make the matrix A equal the matrix B;
print No otherwise.
Note that the judge is case-sensitive.
Sample Input 1
4 5 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 2 3 6 8 9 16 18 19
Sample Output 1
Yes
Removing the 2-nd column from the initial A results in:
1 3 4 5 6 8 9 10 11 13 14 15 16 18 19 20
Then, removing the 3-rd row from A results in:
1 3 4 5 6 8 9 10 16 18 19 20
Then, removing the 1-st row from A results in:
6 8 9 10 16 18 19 20
Then, removing the 4-th column from A results in:
6 8 9 16 18 19
Now the matrix equals the matrix B.
Thus, we can make the matrix A equal the matrix B by repeating the operations, so Yes should be printed.
Sample Input 2
3 3 1 1 1 1 1 1 1 1 1 1 1 2
Sample Output 2
No
Regardless of how we perform the operations, we cannot make the matrix A equal the matrix B,
so No should be printed.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
N 以下の正整数からなる長さ M の数列の組 (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)) が 良い数列の組である とは、(S, T) が次の条件を満たすことを言います。
- 0,1 からなる長さ N の数列 X = (X_1, X_2, \dots, X_N) であって次の条件を満たすものが存在する。
- i=1, 2, \dots, M それぞれについて、X_{S_i} \neq X_{T_i} が成立する。
N 以下の正整数からなる長さ M の数列の組 (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)) が与えられます。(A, B) が良い数列の組である場合は Yes を、そうでない場合は No を出力してください。
制約
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M B_1 B_2 \dots B_M
出力
(A, B) が良い数列の組である場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
3 2 1 2 2 3
出力例 1
Yes
X=(0,1,0) とすると、X は 0,1 からなる長さ N の数列で、 X_{A_1} \neq X_{B_1} かつ X_{A_2} \neq X_{B_2} を満たします。
よって、(A,B) は良い数列の組としての条件を満たしています。
入力例 2
3 3 1 2 3 2 3 1
出力例 2
No
条件を満たすような数列 X は存在しないので、(A, B) は良い数列の組ではありません。
入力例 3
10 1 1 1
出力例 3
No
入力例 4
7 8 1 6 2 7 5 4 2 2 3 2 7 2 1 2 3 3
出力例 4
Yes
Score : 400 points
Problem Statement
A pair of sequences of length M consisting of positive integers at most N, (S, T) = ((S_1, S_2, \dots, S_M), (T_1, T_2, \dots, T_M)), is said to be a good pair of sequences when (S, T) satisfies the following condition.
- There exists a sequence X = (X_1, X_2, \dots, X_N) of length N consisting of 0 and 1 that satisfies the following condition:
- X_{S_i} \neq X_{T_i} for each i=1, 2, \dots, M.
You are given a pair of sequences of length M consisting of positive integers at most N: (A, B) = ((A_1, A_2, \dots, A_M), (B_1, B_2, \dots, B_M)). If (A, B) is a good pair of sequences, print Yes; otherwise, print No.
Constraints
- 1 \leq N, M \leq 2 \times 10^5
- 1 \leq A_i, B_i \leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M B_1 B_2 \dots B_M
Output
If (A, B) is a good pair of sequences, print Yes; otherwise, print No.
Sample Input 1
3 2 1 2 2 3
Sample Output 1
Yes
If we set X=(0,1,0), then X is a sequence of length N consisting of 0 and 1 that satisfies X_{A_1} \neq X_{B_1} and X_{A_2} \neq X_{B_2}.
Thus, (A, B) satisfies the condition of being a good pair of sequences.
Sample Input 2
3 3 1 2 3 2 3 1
Sample Output 2
No
No sequence X satisfies the condition, so (A, B) is not a good pair of sequences.
Sample Input 3
10 1 1 1
Sample Output 3
No
Sample Input 4
7 8 1 6 2 7 5 4 2 2 3 2 7 2 1 2 3 3
Sample Output 4
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
T 個のテストケースについて、次の問題を解いてください。
整数 N と文字列 S が与えられるので、以下の条件を全て満たす文字列 X の数を 998244353 で割った余りを求めてください。
- X は英大文字のみからなる長さ N の文字列
- X は回文
- 辞書順で X \le S
- すなわち、 X=S であるか、辞書順で X が S より前に来る
制約
- 1 \le T \le 250000
- N は 1 以上 10^6 以下の整数
- ひとつの入力について、含まれるテストケースの N の総和は 10^6 を超えない
- S は英大文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
ただし、 \mathrm{case}_i は i 個目のテストケースを表す。
各テストケースは以下の形式で与えられる。
N S
出力
全体で T 行出力せよ。
i 行目には i 個目のテストケースに対する答えを整数として出力せよ。
入力例 1
5 3 AXA 6 ABCZAZ 30 QWERTYUIOPASDFGHJKLZXCVBNMQWER 28 JVIISNEOXHSNEAAENSHXOENSIIVJ 31 KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
出力例 1
24 29 212370247 36523399 231364016
この入力には 5 個のテストケースが含まれます。
1 個目のテストケース:
問題文中の条件を満たす文字列は AAA, ABA, ACA,..., AXA の 24 個です。
2 個目のテストケース:
S が回文であるとは限りません。
3 個目のテストケース:
998244353 で割った余りを求めることに注意してください。
Score : 500 points
Problem Statement
Solve the following problem for T test cases.
Given an integer N and a string S, find the number of strings X that satisfy all of the conditions below, modulo 998244353.
- X is a string of length N consisting of uppercase English letters.
- X is a palindrome.
- X \le S in lexicographical order.
- That is, X=S or X is lexicographically smaller than S.
Constraints
- 1 \le T \le 250000
- N is an integer between 1 and 10^6 (inclusive).
- In a single input, the sum of N over the test cases is at most 10^6.
- S is a string of length N consisting of uppercase English letters.
Input
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 i-th test case.
Each test case is in the following format:
N S
Output
Print T lines. The i-th line should contain the answer for the i-th test case as an integer.
Sample Input 1
5 3 AXA 6 ABCZAZ 30 QWERTYUIOPASDFGHJKLZXCVBNMQWER 28 JVIISNEOXHSNEAAENSHXOENSIIVJ 31 KVOHEEMSOZZASHENDIGOJRTJVMVSDWW
Sample Output 1
24 29 212370247 36523399 231364016
This input contains five test cases.
Test case #1:
The 24 strings satisfying the conditions are AAA, ABA, ACA,..., AXA.
Test case #2:
S may not be a palindrome.
Test case #3:
Be sure to find the count modulo 998244353.
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 行 N 列のマス目があり、上から i \, (1 \leq i \leq N) 行目、左から j \, (1 \leq j \leq N) 列目のマスを (i, j) と表します。
マス (i, j) には非負整数 a_{i, j} が書かれています。
マス (i, j) にいるとき、マス (i+1, j), (i, j+1) のいずれかに移動することができます。ただし、マス目の外に出るような移動はできません。
マス (1, 1) から移動を繰り返してマス (N, N) にたどり着く方法であって、通ったマス（マス (1, 1), (N, N) を含む）に書かれた整数の排他的論理和が 0 となるようなものの総数を求めてください。
排他的論理和とは
整数 a, b の排他的論理和 a \oplus b は、以下のように定義されます。- a \oplus b を二進表記した際の 2^k \, (k \geq 0) の位の数は、a, b を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の整数 p_1, \dots, p_k の排他的論理和は (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k) と定義され、これは p_1, \dots, p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 20
- 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}
出力
答えを出力せよ。
入力例 1
3 1 5 2 7 0 5 4 2 3
出力例 1
2
次の二通りの方法が条件を満たします。
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3)
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3)
入力例 2
2 1 2 2 1
出力例 2
0
入力例 3
10 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0
出力例 3
24307
Score : 500 points
Problem Statement
There is a grid with N rows and N columns. We denote by (i, j) the square at the i-th (1 \leq i \leq N) row from the top and j-th (1 \leq j \leq N) column from the left.
Square (i, j) has a non-negative integer a_{i, j} written on it.
When you are at square (i, j), you can move to either square (i+1, j) or (i, j+1). Here, you are not allowed to go outside the grid.
Find the number of ways to travel from square (1, 1) to square (N, N) such that the exclusive logical sum of the integers written on the squares visited (including (1, 1) and (N, N)) is 0.
What is the exclusive logical sum?
The exclusive logical sum a \oplus b of two integers a and b is defined as follows.- The 2^k's place (k \geq 0) in the binary notation of a \oplus b is 1 if exactly one of the 2^k's places in the binary notation of a and b is 1; otherwise, it is 0.
In general, the exclusive logical sum of k integers p_1, \dots, p_k is defined as (\cdots ((p_1 \oplus p_2) \oplus p_3) \oplus \cdots \oplus p_k). We can prove that it is independent of the order of p_1, \dots, p_k.
Constraints
- 2 \leq N \leq 20
- 0 \leq a_{i, j} \lt 2^{30} \, (1 \leq i, j \leq N)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N
a_{1, 1} \ldots a_{1, N}
\vdots
a_{N, 1} \ldots a_{N, N}
Output
Print the answer.
Sample Input 1
3 1 5 2 7 0 5 4 2 3
Sample Output 1
2
The following two ways satisfy the condition:
- (1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (3, 3);
- (1, 1) \rightarrow (2, 1) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (3, 3).
Sample Input 2
2 1 2 2 1
Sample Output 2
0
Sample Input 3
10 1 0 1 0 0 1 0 0 0 1 0 0 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 0 0 0 1 0 0 0 1 1 0 0 1 0 0 1 1 0 1 1 0 1 0 1 0 0 0 1 0 0 1 1 0 1 1 1 0 0 0 1 1 0 0 0 1 1 0 0 1 1 0 1 0 1 0 1 1 0 0 0 0 0 0 1 0 1 1 0 0 1 1 1 0
Sample Output 3
24307