AtCoder Daily Training MEDIUM 2025/04/08 17:30start

Please sign in first.

C - Adjacency Matrix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。

G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。

i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。

ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。

制約

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
入力される値はすべて整数

入力

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

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

出力

N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。

入力例 1

出力例 1

頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。

同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。

入力例 2

2
0 0
0 0

出力例 2

G に辺が存在しないこともあります。

入力例 3

出力例 3

Score: 150 points

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
All input values are integers.

Input

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

N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}

Output

Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.

Sample Input 1

Sample Output 1

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

Sample Output 3

D - Better Students Are Needed!

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

入学試験の受験者が N 人います。
試験の結果、 i 番の受験生は数学で A_i 点、英語で B_i 点を取りました。

試験の合格者は次のように決められます。

数学の点が高い方から X 人を合格とする。
次に、この時点でまだ合格となっていない受験者のうち、英語の点が高い方から Y 人を合格とする。
次に、この時点でまだ合格となっていない受験者のうち、数学と英語の合計点が高い方から Z 人を合格とする。
ここまでで合格となっていない受験者は、不合格とする。

ただし、 1. から 3. までのどの段階についても、同点であった場合は受験生の番号の小さい方を優先します。入出力例も参照してください。

以上の手順で合格者を決める時、合格となった受験生の番号を小さい方から順に改行区切りで出力してください。

制約

入力は全て整数
1 \le N \le 1000
0 \le X,Y,Z \le N
1 \le X+Y+Z \le N
0 \le A_i,B_i \le 100

入力

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

N X Y Z
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

出力

合格となった受験生の番号を小さい方から順に改行区切りで出力せよ。

入力例 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

出力例 1

1
4
5

まず、数学の点が高い方から 1 人が合格となります。
- 数学の最高点は 80 点で 1 番の受験生と 3 番の受験生が並んでいますが、受験生の番号が小さい方が優先され 1 番の受験生が合格となります。
次に、まだ合格となっていない受験者のうち、英語の点が高い方から 0 人が合格となります。
- 明らかに、ここで合格者が増えることはありません。
次に、まだ合格となっていない受験者のうち、数学と英語の合計点が高い方から 2 人が合格となります。
- まず、まだ合格となっていない受験者の中で、合計点が 160 点と最も高い 5 番の受験生が合格となります。
- 次に、まだ合格となっていない受験者の中で、合計点が 150 点の 4 番の受験生と 6 番の受験生が並んでいます。受験生の番号の小さい方が優先され、 4 番の受験生が合格となります。

以上より、合格となる受験生の番号は 1,4,5 なので、小さい方から出力してください。

入力例 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

出力例 2

全員が合格となることもあります。

入力例 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

出力例 3

Score : 200 points

Problem Statement

N examinees took an entrance exam.
The examinee numbered i scored A_i points in math and B_i points in English.

The admissions are determined as follows.

X examinees with the highest math scores are admitted.
Then, among the examinees who are not admitted yet, Y examinees with the highest English scores are admitted.
Then, among the examinees who are not admitted yet, Z examinees with the highest total scores in math and English are admitted.
Those examinees who are not admitted yet are rejected.

Here, in each of the steps 1. to 3., ties are broken by examinees' numbers: an examinee with the smaller examinee's number is prioritized. See also Sample Input and Output.

Print the examinees' numbers of the admitted examinees determined by the steps above in ascending order, separated by newlines.

Constraints

All values in input are integers.
1 \le N \le 1000
0 \le X,Y,Z \le N
1 \le X+Y+Z \le N
0 \le A_i,B_i \le 100

Input

Input is given from Standard Input in the following format:

N X Y Z
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N

Output

Print the examinees' number of the admitted examinees in ascending order, separated by newlines.

Sample Input 1

6 1 0 2
80 60 80 60 70 70
40 20 50 90 90 80

Sample Output 1

1
4
5

First, 1 examinee with the highest math score is admitted.
- Examinee 1 is tied with Examinee 3, scoring the highest 80 points in math, and the tie is broken by the examinees' numbers, so Examinee 1 is admitted.
Then, among the examinees who are not admitted yet, 0 examinees with the highest English scores are admitted.
- Obviously, it does not affect the admissions.
Then, among the examinees who are not admitted yet, 2 examinees with the highest total scores in math and English are admitted.
- First, among the examinees who are not admitted yet, Examinee 5 is admitted, scoring the highest total score of 160 points.
- Next, among the examinees who are not admitted yet, Examinee 4 is tied with Examinee 6, scoring a total score of 150 points. The tie is broken by the examinees' numbers, and Examinee 4 is admitted.

Therefore, the examinees' numbers of the admitted examinees are 1, 4, and 5. Print them in ascending order.

Sample Input 2

5 2 1 2
0 100 0 100 0
0 0 100 100 0

Sample Output 2

All examinees may be admitted.

Sample Input 3

15 4 3 2
30 65 20 95 100 45 70 85 20 35 95 50 40 15 85
0 25 45 35 65 70 80 90 40 55 20 20 45 75 100

Sample Output 3

E - Gap Existence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。

制約

2 \leq N \leq 2\times 10^5
-10^9 \leq A_i \leq 10^9
-10^9 \leq X \leq 10^9
入力は全て整数である

入力

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

N X
A_1 \ldots A_N

出力

1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。

入力例 1

6 5
3 1 4 1 5 9

出力例 1

Yes

A_6-A_3=9-4=5 です。

入力例 2

6 -4
-2 -7 -1 -8 -2 -8

出力例 2

No

A_i-A_j=-4 となる組 (i,j) は存在しません。

入力例 3

2 0
141421356 17320508

出力例 3

Yes

A_1-A_1=0 です。

Score : 300 points

Problem Statement

You are given a sequence of N numbers: A=(A_1,\ldots,A_N).

Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.

Constraints

2 \leq N \leq 2\times 10^5
-10^9 \leq A_i \leq 10^9
-10^9 \leq X \leq 10^9
All values in the input are integers.

Input

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

N X
A_1 \ldots A_N

Output

Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.

Sample Input 1

6 5
3 1 4 1 5 9

Sample Output 1

Yes

We have A_6-A_3=9-4=5.

Sample Input 2

6 -4
-2 -7 -1 -8 -2 -8

Sample Output 2

No

There is no pair (i,j) such that A_i-A_j=-4.

Sample Input 3

2 0
141421356 17320508

Sample Output 3

Yes

We have A_1-A_1=0.

F - Consecutive

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字のみからなる長さ N の文字列 S = S_1S_2\ldots S_N が与えられます。

また、S に関する Q 個の質問が与えられます。 i = 1, 2, \ldots, Q について、i 番目の質問は 2 つの整数 l_i, r_i で表される下記の質問です。

S の l_i 文字目から r_i 文字目までからなる部分文字列 S_{l_i}S_{l_i+1}\ldots S_{r_i} において、同じ英小文字が 2 つ隣りあう箇所は何個ありますか？すなわち、l_i \leq p \leq r_i-1 かつ S_p = S_{p+1}を満たす整数 p は何個ありますか？

Q 個の質問それぞれの答えを出力してください。

制約

N, Q は整数
1 \leq N, Q \leq 3 \times 10^5
S は英小文字のみからなる長さ N の文字列
l_i, r_i は整数
1 \leq l_i \leq r_i \leq N

入力

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

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

出力

Q 行出力せよ。 i = 1, 2, \ldots, Q について、i 行目には i 番目の質問に対する答えを出力せよ。

入力例 1

11 4
mississippi
3 9
4 10
4 6
7 7

出力例 1

4 個の質問それぞれに対する答えは下記の通りです。

1 個目の質問に関して、S_3S_4\ldots S_9 = ssissip で同じ英小文字が隣り合う箇所は、S_3S_4 = ss と S_6S_7 = ss の 2 個です。
2 個目の質問に関して、S_4S_5\ldots S_{10} = sissipp で同じ英小文字が隣り合う箇所は、S_6S_7 = ss と S_9S_{10} = pp の 2 個です。
3 個目の質問に関して、S_4S_5S_6 = sis で同じ英小文字が隣り合う箇所は 0 個です。
4 個目の質問に関して、S_7 = s で同じ英小文字が隣り合う箇所は 0 個です。

入力例 2

5 1
aaaaa
1 5

出力例 2

S_1S_2\ldots S_5 = aaaaa で同じ英小文字が隣り合う箇所は、 S_1S_2 = aa 、S_2S_3 = aa 、S_3S_4 = aa 、S_4S_5 = aa の 4 個です。

Score : 300 points

Problem Statement

You are given a string S = S_1S_2\ldots S_N of length N consisting of lowercase English letters.

Additionally, you are given Q queries about the string S. For i = 1, 2, \ldots, Q, the i-th query is represented by two integers l_i, r_i and asks the following.

In the substring S_{l_i}S_{l_i+1}\ldots S_{r_i} of S, which ranges from the l_i-th to the r_i-th character, how many places are there where the same lowercase English letter occurs twice in a row? In other words, how many integers p satisfy l_i \leq p \leq r_i-1 and S_p = S_{p+1}?

Print the answer for each of the Q queries.

Constraints

N and Q are integers.
1 \leq N, Q \leq 3 \times 10^5
S is a string of length N consisting of lowercase English letters.
l_i and r_i are integers.
1 \leq l_i \leq r_i \leq N

Input

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

N Q
S
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

Output

Print Q lines. For i = 1, 2, \ldots, Q, the i-th line should contain the answer to the i-th query.

Sample Input 1

11 4
mississippi
3 9
4 10
4 6
7 7

Sample Output 1

The answers to the four queries are as follows.

For the first query, S_3S_4\ldots S_9 = ssissip has two places where the same lowercase English letter occurs twice in a row: S_3S_4 = ss and S_6S_7 = ss.
For the second query, S_4S_5\ldots S_{10} = sissipp has two places where the same lowercase English letter occurs twice in a row: S_6S_7 = ss and S_9S_{10} = pp.
For the third query, S_4S_5S_6 = sis has zero places where the same lowercase English letter occurs twice in a row.
For the fourth query, S_7 = s has zero places where the same lowercase English letter occurs twice in a row.

Sample Input 2

5 1
aaaaa
1 5

Sample Output 2

S_1S_2\ldots S_5 = aaaaa has four places where the same lowercase English letter occurs twice in a row: S_1S_2 = aa, S_2S_3 = aa, S_3S_4 = aa, and S_4S_5 = aa.

G - 1D Country

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

数直線上に N 個の村があります。i 番目の村は座標 X_i にあり、P_i 人の村人がいます。

Q 個のクエリに答えてください。i 番目のクエリは以下の形式です。

整数 L_i,R_i が与えられる。座標が L_i 以上 R_i 以下の村に住んでいる村人の人数の総数を求めよ。

制約

1\leq N,Q\leq 2\times 10^5
-10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
1\leq P_i\leq 10^9
-10^9\leq L_i \leq R_i \leq 10^9
入力される数値は全て整数

入力

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

N
X_1 \ldots X_N
P_1 \ldots P_N
Q
L_1 R_1
\vdots
L_Q R_Q

出力

Q 行出力せよ。

i\ (1\leq i \leq Q) 行目には、i 番目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

1 番目のクエリについて考えます。座標が 1 以上 1 以下の村は、座標 1 にある村で、村人は 1 人います。よって答えは 1 です。

2 番目のクエリについて考えます。座標が 2 以上 6 以下の村は、座標 3 にある村と座標 5 にある村で、村人はそれぞれ 2 人と 3 人います。よって答えは 2+3=5 です。

入力例 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

出力例 2

Score : 350 points

Problem Statement

There are N villages on a number line. The i-th village is located at coordinate X_i, and has P_i villagers.

Answer Q queries. The i-th query is in the following format:

Given integers L_i and R_i, find the total number of villagers living in villages located between coordinates L_i and R_i, inclusive.

Constraints

1\leq N,Q\leq 2\times 10^5
-10^9\leq X_1 < X_2 < \ldots < X_N \leq 10^9
1\leq P_i\leq 10^9
-10^9\leq L_i \leq R_i \leq 10^9
All input values are integers.

Input

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

N
X_1 \ldots X_N
P_1 \ldots P_N
Q
L_1 R_1
\vdots
L_Q R_Q

Output

Print Q lines.

The i-th line(1\leq i \leq Q) should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

Consider the first query. The villages between coordinates 1 and 1 are the village at coordinate 1, with 1 villager. Hence, the answer is 1.

Consider the second query. The villages between coordinates 2 and 6 are the villages at coordinates 3 and 5, with 2 and 3 villagers, respectively. Hence, the answer is 2+3=5.

Sample Input 2

7
-10 -5 -3 -1 0 1 4
2 5 6 5 2 1 7
8
-7 7
-1 5
-10 -4
-8 10
-5 0
-10 5
-8 7
-8 -3

Sample Output 2