UNICORNProgramming Contest2026(AtCoder Beginner Contest 477)

A - Traffic Light

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある信号機の色は B（青）、Y（黄）、R（赤）、B（青）、Y（黄）、R（赤）\dots という順に、周期的に変化します。

現在の信号機の色を表す文字 c が与えられます。次の信号機の色を出力してください。

制約

c は B、Y、R のいずれか

入力

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

出力

次の信号機の色を表す文字を出力せよ。

入力例 1

出力例 1

B（青）の次は Y（黄）です。よって Y を出力してください。

入力例 2

出力例 2

赤の次は青です。

入力例 3

出力例 3

Score : 100 points

Problem Statement

The color of a certain traffic light changes periodically in the order B (blue), Y (yellow), R (red), B (blue), Y (yellow), R (red), \dots.

You are given a character c representing the current color of the traffic light. Output the next color of the traffic light.

Constraints

c is one of B, Y, and R.

Input

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

Output

Output the character representing the next color of the traffic light.

Sample Input 1

Sample Output 1

The color after B (blue) is Y (yellow). Thus, output Y.

Sample Input 2

Sample Output 2

The color after red is blue.

Sample Input 3

Sample Output 3

B - Standing Outliers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

数直線上に N 人の人がいます。人には 1 から N までの番号がついており、人 i は座標 X_i にいます。ただし、同じ座標に複数の人がいる場合もあります。

ある人が「一線を画す」とは、自分以外のどの人との距離も D 以上であることをいいます。

厳密には、人 i が「一線を画す」とは、すべての j ~ (1 \leq j \leq N,\ j \neq i) に対して |X_i-X_j| \geq D が成り立つことをいいます。

「一線を画す」人の番号をすべて昇順に出力してください。

制約

2 \le N \le 100
1 \le D \le 10^9
1 \le X_i \le 10^9
入力される値は全て整数

入力

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

N D
X_1 X_2 \dots X_N

出力

一線を画す人の人数を K、その人たちの番号を昇順に並べた列を (P_1,P_2,\dots,P_K) とする。以下の形式で出力せよ。

K
P_1 P_2 \dots P_K

ただし K=0 の場合、2 行目は空行とせよ。

入力例 1

3 3
1 5 7

出力例 1

1
1

人 1 は、人 2 との距離が 4 、人 3 との距離が 6 で、自分以外のどの人との距離も D 以上です。よって「一線を画す」人です。
人 2 は人 3 との距離が 2 ですから、「一線を画す」人ではありません。
同様に、人 3 も人 2 との距離が 2 ですから、「一線を画す」人ではありません。

よって、「一線を画す」人は人 1 のみです。

入力例 2

3 2
1 1 1

出力例 2

同じ座標の人がいることもあります。また、「一線を画す」人がいない場合は 2 行目は空行としてください。

入力例 3

8 3
4 77 20 26 9 26 22 40

出力例 3

4
1 2 5 8

「一線を画す人」の番号は昇順に出力してください。

Score : 200 points

Problem Statement

There are N people on a number line. The people are numbered 1 to N, and person i is at coordinate X_i. Multiple people may be at the same coordinate.

A person is said to "stand apart" if their distance to every other person is at least D.

Formally, person i is said to "stand apart" if |X_i-X_j| \geq D holds for all j ~ (1 \leq j \leq N,\ j \neq i).

Output the numbers of all people who "stand apart" in ascending order.

Constraints

2 \le N \le 100
1 \le D \le 10^9
1 \le X_i \le 10^9
All input values are integers.

Input

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

N D
X_1 X_2 \dots X_N

Output

Let K be the number of people who stand apart, and let (P_1,P_2,\dots,P_K) be the sequence of their numbers sorted in ascending order. Output them in the following format:

K
P_1 P_2 \dots P_K

If K=0, the second line should be empty.

Sample Input 1

3 3
1 5 7

Sample Output 1

1
1

Person 1 has distance 4 to person 2 and distance 6 to person 3, so their distance to every other person is at least D. Thus, person 1 "stands apart".
Person 2 has distance 2 to person 3, so person 2 does not "stand apart".
Similarly, person 3 has distance 2 to person 2, so person 3 does not "stand apart" either.

Thus, only person 1 "stands apart".

Sample Input 2

3 2
1 1 1

Sample Output 2

There may be people at the same coordinate. Also, if no one "stands apart", the second line should be empty.

Sample Input 3

8 3
4 77 20 26 9 26 22 40

Sample Output 3

4
1 2 5 8

Output the numbers of the people who "stand apart" in ascending order.

C - Range Search Query

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

文字列 S, T が与えられます。
Q 個のクエリを処理してください。
クエリでは L, R が与えられるので、S の L 文字目から R 文字目までからなる部分文字列に、T が部分文字列として含まれるかを判定してください。

部分文字列とは

S の部分文字列とは、S の先頭から 0 文字以上、末尾から 0 文字以上削除して得られる文字列のことをいいます。
例えば、ab は abc の部分文字列ですが、ac は abc の部分文字列ではありません。

制約

S は長さ 1 以上 4 \times 10^5 以下の英小文字からなる文字列
T は長さ 1 以上 10 以下の英小文字からなる文字列
1 \leq Q \leq 2 \times 10^5
1 \leq L \leq R \leq |S|
Q, L, R は整数

入力

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

Q
S
T
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_q は以下の形式で与えられる。

L R

出力

Q 行出力せよ。q 行目には q 番目のクエリについて、S の L 文字目から R 文字目までからなる部分文字列に、T が部分文字列として含まれれば Yes を、含まれなければ No を出力せよ。

入力例 1

3
abcdabc
bc
2 6
3 5
3 7

出力例 1

Yes
No
Yes

1 番目のクエリについて考えます。S の 2 文字目から 6 文字目までからなる部分文字列は bcdab です。bcdab の 1 文字目から 2 文字目までからなる部分文字列は T と一致するので、bcdab は T を含みます。よって答えは Yes です。

入力例 2

10
bbbaaabbbaaaaaabbbab
bbb
5 16
5 6
2 16
6 7
17 19
3 7
7 16
7 20
17 19
2 6

出力例 2

Yes
No
Yes
No
No
No
Yes
Yes
No
No

Score : 300 points

Problem Statement

You are given strings S and T.
Process Q queries.
In each query, you are given L and R. Determine whether the substring of S consisting of the L-th through R-th characters contains T as a substring.

What is a substring?

A substring of S is a string obtained by deleting zero or more characters from the beginning and zero or more characters from the end of S.
For example, ab is a substring of abc, but ac is not a substring of abc.

Constraints

S is a string of length between 1 and 4 \times 10^5, inclusive, consisting of lowercase English letters.
T is a string of length between 1 and 10, inclusive, consisting of lowercase English letters.
1 \leq Q \leq 2 \times 10^5
1 \leq L \leq R \leq |S|
Q, L, R are integers.

Input

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

Q
S
T
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_q is given in the following format:

L R

Output

Output Q lines. The q-th line should contain Yes if, for the q-th query, the substring of S consisting of the L-th through R-th characters contains T as a substring, and No otherwise.

Sample Input 1

3
abcdabc
bc
2 6
3 5
3 7

Sample Output 1

Yes
No
Yes

Consider the first query. The substring of S consisting of the 2-nd through 6-th characters is bcdab. The substring of bcdab consisting of the 1-st through 2-nd characters matches T, so bcdab contains T. Thus, the answer is Yes.

Sample Input 2

10
bbbaaabbbaaaaaabbbab
bbb
5 16
5 6
2 16
6 7
17 19
3 7
7 16
7 20
17 19
2 6

Sample Output 2

Yes
No
Yes
No
No
No
Yes
Yes
No
No

D - Masking Tape

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N 個のマスが横一列に並んでおり、左から順にマス 1 からマス N までの番号がついています。色は英小文字で表されます。

はじめ、すべてのマスの色は a で、各マスには何も置かれていません。

Q 個のクエリが与えられるので、与えられた順に処理してください。各クエリは以下の 2 種類のいずれかです。

1 X : マス X にタイルが置かれていなければタイルを置き、置かれていれば取り除く。
2 C : タイルが置かれていないすべてのマスの色を C に変更する。

すべてのクエリを処理した後の各マスの色を（タイルが置かれているかどうかにかかわらず）求めてください。

制約

1 \le N,Q \le 3\times 10^5
各クエリはタイプ 1 またはタイプ 2 のいずれか
タイプ 1 のクエリにおいて、X は 1 \le X \le N を満たす整数
タイプ 2 のクエリにおいて、C は英小文字 1 文字

入力

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_i ~ (1 \le i \le Q) は

1 X

または、

2 C

の形で与えられる。

出力

最終的な各マスの色を、左から順につなげた長さ N の文字列として出力せよ。

入力例 1

出力例 1

bcc

タイルの状態について、置かれているならば #、そうでないならば . として左から順につなげた文字列で表現をすることにします。

クエリによって、以下のようにマスの色・タイルの状態が変化します。はじめの状態は aaa と ... です。

1 つ目のクエリを処理すると、マス 2 にタイルが置かれる。状態は aaa と .#. となる。
2 つ目のクエリを処理すると、タイルの置かれていないマスの色が b に変更される。状態は bab と .#. となる。
3 つ目のクエリを処理すると、マス 1 にタイルが置かれる。状態は bab と ##. となる。
4 つ目のクエリを処理すると、マス 2 のタイルが取り除かれる。状態は bab と #.. となる。
5 つ目のクエリを処理すると、タイルの置かれていないマスの色が c に変更される。状態は bcc と #.. となる。

よって bcc と出力してください。マス 1 にはタイルが置かれたままですが、その場合であってもマスの色を出力します。

入力例 2

出力例 2

dkmfkqfazk

Score : 400 points

Problem Statement

There are N squares arranged in a horizontal row, numbered square 1 to square N from left to right. Colors are represented by lowercase English letters.

Initially, the color of every square is a, and nothing is placed on any square.

You are given Q queries; process them in the given order. Each query is of one of the following two types:

1 X : If no tile is placed on square X, place a tile on it; if a tile is placed on it, remove it.
2 C : Change the color of every square on which no tile is placed to C.

Find the color of each square after processing all queries (regardless of whether a tile is placed on it).

Constraints

1 \le N,Q \le 3\times 10^5
Each query is of type 1 or type 2.
In type-1 queries, X is an integer satisfying 1 \le X \le N.
In type-2 queries, C is a single lowercase English letter.

Input

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

N Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_i ~ (1 \le i \le Q) is given in the form

1 X

2 C

Output

Output the final colors of the squares as a string of length N, concatenated from left to right.

Sample Input 1

Sample Output 1

bcc

We represent the state of tiles as a string formed by concatenating, from left to right, # if a tile is placed and . otherwise.

The queries change the colors of the squares and the state of tiles as follows. The initial state is aaa and ....

Processing the 1-st query places a tile on square 2. The state becomes aaa and .#..
Processing the 2-nd query changes the color of the squares without tiles to b. The state becomes bab and .#..
Processing the 3-rd query places a tile on square 1. The state becomes bab and ##..
Processing the 4-th query removes the tile on square 2. The state becomes bab and #...
Processing the 5-th query changes the color of the squares without tiles to c. The state becomes bcc and #...

Thus, output bcc. A tile remains placed on square 1, but even in that case, output the color of the square.

Sample Input 2

Sample Output 2

dkmfkqfazk

E - Wheel Distance

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 450 点

問題文

頂点に 1 から N+1 の番号がついた N+1 頂点の辺重み付き無向グラフが与えられます。
1 \leq i \leq N を満たす整数 i について、頂点 i と頂点 (i \bmod N) + 1 を結ぶ重み A_i の辺があります。
また、1 \leq i \leq N を満たす整数 i について、頂点 i と頂点 N+1 を結ぶ重み B_i の辺があります。これ以外の辺はありません。

Q 個のクエリを処理してください。クエリでは S, T が与えられるので、頂点 S から頂点 T への最短経路の長さを求めてください。

制約

3 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq A_i, B_i \leq 10^9
1 \leq S \lt T \leq N+1
入力される値は全て整数

入力

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

N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_q は以下の形式で与えられる。

S T

出力

Q 行出力せよ。q 行目には q 番目のクエリの答えを出力せよ。

入力例 1

出力例 1

6
5
6

1 番目のクエリについて、頂点 2 から頂点 5 への最短経路の一つは 2\to1\to5 であり、その長さは A_1+A_5=1+5=6 です。

入力例 2

10 12
95786828 55052989 7398452 90695030 73248844 120697567 77915140 68865651 15301338 68674005
690874817 21524935 244587369 529970100 736247510 757265588 993115119 576136368 21553212 219853538
5 6
5 8
2 6
3 7
1 3
3 4
8 11
1 10
2 6
6 8
8 9
5 8

出力例 2

Score : 450 points

Problem Statement

You are given an edge-weighted undirected graph with N+1 vertices numbered 1 to N+1.
For each integer i satisfying 1 \leq i \leq N, there is an edge of weight A_i connecting vertex i and vertex (i \bmod N) + 1.
Also, for each integer i satisfying 1 \leq i \leq N, there is an edge of weight B_i connecting vertex i and vertex N+1. There are no other edges.

Process Q queries. In each query, you are given S and T; find the length of the shortest path from vertex S to vertex T.

Constraints

3 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq A_i, B_i \leq 10^9
1 \leq S \lt T \leq N+1
All input values are integers.

Input

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

N Q
A_1 A_2 \dots A_N
B_1 B_2 \dots B_N
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_q is given in the following format:

S T

Output

Output Q lines. The q-th line should contain the answer to the q-th query.

Sample Input 1

Sample Output 1

6
5
6

For the first query, one shortest path from vertex 2 to vertex 5 is 2\to1\to5, and its length is A_1+A_5=1+5=6.

Sample Input 2

10 12
95786828 55052989 7398452 90695030 73248844 120697567 77915140 68865651 15301338 68674005
690874817 21524935 244587369 529970100 736247510 757265588 993115119 576136368 21553212 219853538
5 6
5 8
2 6
3 7
1 3
3 4
8 11
1 10
2 6
6 8
8 9
5 8

Sample Output 2

F - Count Cells in a Window

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 525 点

問題文

N 行 M 列のグリッドが与えられます。上から i 行目では、左から L_i 列目から R_i 列目までのマスが黒く塗られており、それ以外のマスは白く塗られています。

Q 個のクエリが与えられます。各クエリでは、以下の問題に答えてください。

整数 A,B,C,D が与えられます。上から A 行目から B 行目まで、左から C 列目から D 列目までの長方形領域に含まれる黒いマスの個数を求めてください。

制約

1 \le N,M,Q \le 2\times10^5
1 \le L_i \le R_i \le M
各クエリについて、1 \le A \le B \le N
各クエリについて、1 \le C \le D \le M
入力される値はすべて整数

入力

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

N M Q
L_1 R_1
L_2 R_2
\vdots
L_N R_N
\mathrm{query}_1
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_i ~ (1 \le i \le Q) は

A B C D

の形で与えられる。

出力

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

入力例 1

出力例 1

4
3
0

黒いマスは上図のような範囲にあり、1 番目のクエリでは左上の青い長方形、2 番目のクエリでは右下の赤い長方形、3 番目のクエリでは右上の緑の長方形の範囲の黒のマスの数を聞かれています。

よって、それぞれ 4, 3, 0 を出力すればよいです。

入力例 2

出力例 2

Score : 525 points

Problem Statement

You are given a grid with N rows and M columns. In the i-th row from the top, the squares from the L_i-th through R_i-th columns from the left are painted black, and the other squares are painted white.

You are given Q queries. For each query, answer the following question.

You are given integers A,B,C,D. Find the number of black squares contained in the rectangular region from the A-th through B-th rows from the top and from the C-th through D-th columns from the left.

Constraints

1 \le N,M,Q \le 2\times10^5
1 \le L_i \le R_i \le M
For each query, 1 \le A \le B \le N.
For each query, 1 \le C \le D \le M.
All input values are integers.

Input

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

N M Q
L_1 R_1
L_2 R_2
\vdots
L_N R_N
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_i ~ (1 \le i \le Q) is given in the form

A B C D

Output

Output Q lines. The i-th line should contain the answer to the i-th query.

Sample Input 1

Sample Output 1

4
3
0

The black squares are located as shown in the figure above. The 1-st query asks for the number of black squares within the blue rectangle at the upper left, the 2-nd query within the red rectangle at the lower right, and the 3-rd query within the green rectangle at the upper right.

Thus, output 4, 3, 0, respectively.

Sample Input 2

Sample Output 2

G - Frequency Query on Tree

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 625 点

問題文

頂点に 1 から N の番号がついた N 頂点の木が与えられます。i 番目の辺は頂点 u_i と頂点 v_i を結んでいます。また、頂点 i には整数 x_i が書かれています。
Q 個のクエリを処理してください。クエリでは整数 s,t,a,b が与えられるので、以下の条件を満たす整数 y の個数を求めてください。

頂点 s と頂点 t を結ぶパス上にある頂点のうち、整数 y が書かれた頂点の個数を f とする。この時、a \leq f \leq b が成り立つ。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq u_i \lt v_i \leq N
入力で与えられるグラフは木
1 \leq x_i \leq N
1 \leq s \lt t \leq N
1 \leq a \leq b \leq N
入力される値は全て整数

入力

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

N Q
x_1 x_2 \dots x_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

各クエリ \mathrm{query}_q は以下の形式で与えられる。

s t a b

出力

Q 行出力せよ。q 行目には q 番目のクエリの答えを出力せよ。

入力例 1

出力例 1

1 番目のクエリを考えます。
頂点 1 と頂点 5 を結ぶパス上の頂点は順に頂点 1、頂点 2、頂点 3、頂点 4、頂点 5 です。
各頂点に書かれている整数は順に 1, 2, 3, 1, 2 です。よって、条件を満たす整数 y は 1,2,3 の 3 個です。

入力例 2

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

出力例 2

Score : 625 points

Problem Statement

You are given a tree with N vertices numbered 1 to N. The i-th edge connects vertex u_i and vertex v_i. Also, integer x_i is written on vertex i.
Process Q queries. In each query, you are given integers s,t,a,b; find the number of integers y satisfying the following condition.

Let f be the number of vertices with integer y written on them among the vertices on the path connecting vertex s and vertex t. Then, a \leq f \leq b holds.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq u_i \lt v_i \leq N
The given graph is a tree.
1 \leq x_i \leq N
1 \leq s \lt t \leq N
1 \leq a \leq b \leq N
All input values are integers.

Input

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

N Q
x_1 x_2 \dots x_N
u_1 v_1
u_2 v_2
\vdots
u_{N-1} v_{N-1}
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query \mathrm{query}_q is given in the following format:

s t a b

Output

Output Q lines. The q-th line should contain the answer to the q-th query.

Sample Input 1

Sample Output 1

Consider the first query.
The vertices on the path connecting vertex 1 and vertex 5 are, in order, vertex 1, vertex 2, vertex 3, vertex 4, and vertex 5.
The integers written on these vertices are, in order, 1, 2, 3, 1, 2. Thus, there are three integers y satisfying the condition: 1,2,3.

Sample Input 2

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

Sample Output 2