実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項 は a_{i, j} です。
Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。
制約
- 1 \leq N, Q \leq 2 \times 10^5
- L_i \geq 1 \, (1 \leq i \leq N)
- \sum_{i=1}^N L_i \leq 2 \times 10^5
- 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
- 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots
s_Q t_Q
出力
Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。
入力例 1
2 2 3 1 4 7 2 5 9 1 3 2 1
出力例 1
7 5
1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。
- 1 番目の数列の第 3 項は 7 です。
- 2 番目の数列の第 1 項は 5 です。
入力例 2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
出力例 2
128 1 26535 901
Score : 200 points
Problem Statement
There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.
You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.
Constraints
- 1 \leq N, Q \leq 2 \times 10^5
- L_i \geq 1 \, (1 \leq i \leq N)
- \sum_{i=1}^N L_i \leq 2 \times 10^5
- 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
- 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots
s_Q t_Q
Output
Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.
Sample Input 1
2 2 3 1 4 7 2 5 9 1 3 2 1
Sample Output 1
7 5
The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:
- The 3-rd term of the 1-st sequence is 7.
- The 1-st term of the 2-nd sequence is 5.
Sample Input 2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
Sample Output 2
128 1 26535 901
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
1,2,\ldots,N の番号がついた N 人の人がいます。
M 回の舞踏会が行われました。 i (1\leq i \leq M) 回目の舞踏会には k_i 人が参加し、参加した人は人 x_{i,1},x_{i,2},\ldots,x_{i,k_i} でした。
どの二人も少なくとも 1 回同じ舞踏会に参加したか判定してください。
制約
- 2\leq N \leq 100
- 1\leq M \leq 100
- 2\leq k_i \leq N
- 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}
出力
どの二人も少なくとも 1 回同じ舞踏会に参加した場合 Yes を、そうでない場合 No を出力せよ。
入力例 1
3 3 2 1 2 2 2 3 2 1 3
出力例 1
Yes
人 1 と人 2 は共に 1 回目の舞踏会に参加しています。
人 2 と人 3 は共に 2 回目の舞踏会に参加しています。
人 1 と人 3 は共に 3 回目の舞踏会に参加しています。
以上よりどの二人も少なくとも 1 回同じ舞踏会に参加したので、答えは Yes です。
入力例 2
4 2 3 1 2 4 3 2 3 4
出力例 2
No
人 1 と人 3 は 1 回も同じ舞踏会に参加していないので、答えは No です。
Score : 200 points
Problem Statement
There are N people numbered 1,2,\ldots,N.
M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.
Determine if every two people attended the same party at least once.
Constraints
- 2\leq N \leq 100
- 1\leq M \leq 100
- 2\leq k_i \leq N
- 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}
Output
Print Yes if every two people attended the same party at least once; print No otherwise.
Sample Input 1
3 3 2 1 2 2 2 3 2 1 3
Sample Output 1
Yes
Both Person 1 and Person 2 attended the 1-st party.
Both Person 2 and Person 3 attended the 2-nd party.
Both Person 1 and Person 3 attended the 3-rd party.
Therefore, every two people attended the same party at least once, so the answer is Yes.
Sample Input 2
4 2 3 1 2 4 3 2 3 4
Sample Output 2
No
Person 1 and Person 3 did not attend the same party, so the answer is No.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
N 人の生徒からなるクラスがあり、i\,(1 \leq i \leq N) 番目の生徒の身長は A_i です。
j=1,2,\ldots,Q について、以下の質問に答えてください。
- N 人のうち、身長が x_j 以上の生徒は何人か？
制約
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
出力
Q 行出力せよ。
j\,(1 \leq j \leq Q) 行目には身長が x_j 以上の生徒の数を出力せよ。
入力例 1
3 1 100 160 130 120
出力例 1
2
身長が 120 以上の生徒は 2 番目の生徒と 3 番目の生徒です。
入力例 2
5 5 1 2 3 4 5 6 5 4 3 2
出力例 2
0 1 2 3 4
入力例 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
出力例 3
5 3 5 5 5
Score : 300 points
Problem Statement
There is a class with N students. The height of the i-th student (1 \leq i \leq N) is A_i.
For each j=1,2,\ldots,Q, answer the following question.
- How many of the N students have a height of at least x_j?
Constraints
- 1 \leq N,Q \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 1 \leq x_j \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N x_1 x_2 \vdots x_Q
Output
Print Q lines.
The j-th line (1 \leq j \leq Q) should contain the number of students with a height of at least x_j.
Sample Input 1
3 1 100 160 130 120
Sample Output 1
2
The students with a height of at least 120 are the 2-nd and 3-rd ones.
Sample Input 2
5 5 1 2 3 4 5 6 5 4 3 2
Sample Output 2
0 1 2 3 4
Sample Input 3
5 5 804289384 846930887 681692778 714636916 957747794 424238336 719885387 649760493 596516650 189641422
Sample Output 3
5 3 5 5 5
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
整数 N が与えられるので、以下の問題を解いてください。
f(x)= ( x 以下の正整数で、 x と桁数が同じものの数) とします。
f(1)+f(2)+\dots+f(N) を 998244353 で割った余りを求めてください。
制約
- N は整数
- 1 \le N < 10^{18}
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
16
出力例 1
73
- 1 以上 9 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 1,2,\dots,x です。
- これより、 f(1)=1,f(2)=2,...,f(9)=9 となります。
- 10 以上 16 以下の正整数 x について、 x 以下の整数で、 x と桁数が同じものは 10,11,\dots,x です。
- これより、 f(10)=1,f(11)=2,...,f(16)=7 となります。
結局、求める答えは 73 です。
入力例 2
238
出力例 2
13870
入力例 3
999999999999999999
出力例 3
762062362
998244353 で割った余りを求めることに注意してください。
Score : 300 points
Problem Statement
Given an integer N, solve the following problem.
Let f(x)= (The number of positive integers at most x with the same number of digits as x).
Find f(1)+f(2)+\dots+f(N) modulo 998244353.
Constraints
- N is an integer.
- 1 \le N < 10^{18}
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
16
Sample Output 1
73
- For a positive integer x between 1 and 9, the positive integers at most x with the same number of digits as x are 1,2,\dots,x.
- Thus, we have f(1)=1,f(2)=2,...,f(9)=9.
- For a positive integer x between 10 and 16, the positive integers at most x with the same number of digits as x are 10,11,\dots,x.
- Thus, we have f(10)=1,f(11)=2,...,f(16)=7.
The final answer is 73.
Sample Input 2
238
Sample Output 2
13870
Sample Input 3
999999999999999999
Sample Output 3
762062362
Be sure to find the sum modulo 998244353.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
このグラフのすべての連結成分が次の条件を満たすかどうかを判定してください。
- その連結成分に含まれる頂点の個数と辺の本数が等しい。
注釈
無向グラフ とは、辺に向きの無いグラフのことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i \leq v_i \leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 \vdots u_M v_M
出力
すべての連結成分が条件を満たすならば Yes と、そうでなければ No と出力せよ。
入力例 1
3 3 2 3 1 1 2 3
出力例 1
Yes
このグラフには頂点 1 のみからなる連結成分と頂点 2,3 からなる連結成分があります。
前者には 1 本の辺(辺 2 )が、後者には 2 本の辺(辺 1,3 )が含まれており、条件を満たします。
入力例 2
5 5 1 2 2 3 3 4 3 5 1 5
出力例 2
Yes
入力例 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
出力例 3
No
Score : 400 points
Problem Statement
You are given an undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Determine whether every connected component in this graph satisfies the following condition.
- The connected component has the same number of vertices and edges.
Notes
An undirected graph is a graph with edges without direction.
A subgraph of a graph is a graph formed from a subset of vertices and edges of that graph.
A graph is connected when one can travel between every pair of vertices in the graph via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq 2 \times 10^5
- 1 \leq u_i \leq v_i \leq N
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M u_1 v_1 \vdots u_M v_M
Output
If every connected component satisfies the condition, print Yes; otherwise, print No.
Sample Input 1
3 3 2 3 1 1 2 3
Sample Output 1
Yes
The graph has a connected component formed from just vertex 1, and another formed from vertices 2 and 3.
The former has one edge (edge 2), and the latter has two edges (edges 1 and 3), satisfying the condition.
Sample Input 2
5 5 1 2 2 3 3 4 3 5 1 5
Sample Output 2
Yes
Sample Input 3
13 16 7 9 7 11 3 8 1 13 11 11 6 11 8 13 2 11 3 3 8 12 9 11 1 11 5 13 3 12 6 9 1 10
Sample Output 3
No