AtCoder Daily Training MEDIUM 2025/06/26 18:30start

C - Couples

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 150 点

問題文

2N 人の人が横一列に並んでおり、左から i 番目の人は色 A_i の服を着ています。ここで、服の色は 1 から N の N 色であり、それぞれの色についてちょうど 2 人の人がその色の服を着ています。

i=1,2,\ldots,N のうち、以下の条件を満たすものは何通りあるか求めてください。

色 i の服を着た二人の人の間にはちょうど一人いる。

制約

2\leq N\leq 100
1\leq A_i \leq N
A には 1 以上 N 以下の整数全てがそれぞれ 2 個ずつ含まれる
入力される数値は全て整数

入力

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

N 
A_1 A_2 \ldots A_{2N}

出力

答えを出力せよ。

入力例 1

3
1 2 1 3 2 3

出力例 1

条件を満たす i は 1 と 3 の 2 個です。

実際、色 1 の服を着ているのは左から 1 番目の人と左から 3 番目の人で、間にちょうど一人います。

入力例 2

2
1 1 2 2

出力例 2

条件を満たす i が存在しない場合もあります。

入力例 3

4
4 3 2 3 2 1 4 1

出力例 3

Score : 150 points

Problem Statement

There are 2N people standing in a row, and the person at the i-th position from the left is wearing clothes of color A_i. Here, the clothes have N colors from 1 to N, and exactly two people are wearing clothes of each color.

Find how many of the integers i=1,2,\ldots,N satisfy the following condition:

There is exactly one person between the two people wearing clothes of color i.

Constraints

2 \leq N \leq 100
1 \leq A_i \leq N
Each integer from 1 through N appears exactly twice in A.
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{2N}

Output

Print the answer.

Sample Input 1

3
1 2 1 3 2 3

Sample Output 1

There are two values of i that satisfy the condition: 1 and 3.

In fact, the people wearing clothes of color 1 are at the 1st and 3rd positions from the left, with exactly one person in between.

Sample Input 2

2
1 1 2 2

Sample Output 2

There may be no i that satisfies the condition.

Sample Input 3

4
4 3 2 3 2 1 4 1

Sample Output 3

D - Product Calculator

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は電卓を持っています。電卓には最初 1 が表示されています。
高橋君は電卓に対して N 回操作を行います。
i 回目 (1\leq i\leq N) の操作では、その時点で画面に表示されている数に正の整数 A_i をかけます。
しかし、電卓には K 桁までしか表示できないため、計算結果が (K+1) 桁以上になる場合、代わりに 1 が画面に表示されます。そうでない場合は正しく計算結果が表示されます。

N 回の操作の後に電卓に表示されている数を求めてください。

制約

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
入力はすべて整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

N 回の操作の後に電卓に表示されている数を出力せよ。

入力例 1

5 2
7 13 3 2 5

出力例 1

今回電卓は 2 桁まで表示することができ、最初 1 が表示されています。これに対して、次のように高橋君は操作を行います。

1 回目の操作で、7 をかけます。1\times 7=7 であり、電卓には 7 が表示されます。
2 回目の操作で、13 をかけます。7\times 13=91 であり、電卓には 91 が表示されます。
3 回目の操作で、3 をかけます。91\times 3=273 であり、3 桁になってしまうため、電卓には 1 が表示されます。
4 回目の操作で、2 をかけます。1\times 2=2 であり、電卓には 2 が表示されます。
5 回目の操作で、5 をかけます。2\times 5=10 であり、電卓には 10 が表示されます。

入力例 2

2 1
2 5

出力例 2

Score : 200 points

Problem Statement

Takahashi has a calculator that initially displays 1.
He will perform N operations on the calculator.
In the i-th operation (1 \leq i \leq N), he multiplies the currently displayed number by a positive integer A_i.
However, the calculator can display at most K digits. If the result of the multiplication has (K+1) or more digits, the display shows 1 instead; otherwise, the result is shown correctly.

Find the number showing on the calculator after the N operations.

Constraints

1 \leq N \leq 100
1 \leq K \leq 18
1 \leq A_i < 10^K
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Output the number shown on the calculator after the N operations.

Sample Input 1

5 2
7 13 3 2 5

Sample Output 1

This calculator can display at most two digits and initially shows 1. Takahashi operates as follows:

The 1st operation multiplies by 7. Since 1 \times 7 = 7, the calculator shows 7.
The 2nd operation multiplies by 13. Since 7 \times 13 = 91, the calculator shows 91.
The 3rd operation multiplies by 3. Since 91\times 3=273, which has three digits, the calculator shows 1.
The 4th operation multiplies by 2. Since 1\times 2=2, the calculator shows 2.
The 5th operation multiplies by 5. Since 2\times 5=10, the calculator shows 10.

Sample Input 2

2 1
2 5

Sample Output 2

E - Snake Queue

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

ヘビの待ち行列があります。最初、列は空です。

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

タイプ 1 : 1 l の形式で与えられる。長さ l のヘビが列の末尾に追加される。このとき追加するヘビの頭の位置は、元の列が空の場合は座標 0、そうでない場合は最後尾のヘビの頭の座標に最後尾のヘビの長さを加えた座標となる。
タイプ 2 : 2 の形式で与えられる。列の先頭にいるヘビが列から抜ける。このとき、列が空でないことは保証される。抜けたヘビの長さを m として、列に残っている全てのヘビの頭の座標が m だけ減少する。
タイプ 3 : 3 k の形式で与えられる。列の先頭から数えて k 番目にいるヘビの頭の座標を出力せよ。このとき、列には少なくとも k 匹のヘビがいることが保証される。

制約

1 \leq Q \leq 3 \times 10^{5}
タイプ 1 のクエリにおいて、1 \leq l \leq 10^{9}
タイプ 2 のクエリにおいて、列が空でないことが保証される
タイプ 3 のクエリにおいて、列にいるヘビの数を n として、1 \leq k \leq n
入力は全て整数

入力

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

ただし、\text{query}_i は i 個目のクエリを表し、以下のいずれかの形式である。

1 l

3 k

出力

タイプ 3 のクエリの個数を q として、q 行出力せよ。i 行目には、i 個目のタイプ 3 のクエリに対する答えを出力せよ。

入力例 1

出力例 1

5
10

1 個目のクエリ : 長さ 5 のヘビが列に追加される。列にヘビはいないため、追加されたヘビの頭の座標は 0 となる。
2 個目のクエリ : 長さ 7 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 0 で長さが 5 のため、追加されたヘビの頭の座標は 5 となる。
3 個目のクエリ : 前から 2 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 5 であるため、5 を出力する。
4 個目のクエリ : 長さ 3 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 5 で長さが 7 のため、追加されたヘビの頭の座標は 12 となる。
5 個目のクエリ : 長さ 4 のヘビが列に追加される。追加する前の最後尾のヘビの頭の座標が 12 で長さが 3 のため、追加されたヘビの頭の座標は 15 となる。
6 個目のクエリ : 先頭のヘビが列から抜ける。抜けたヘビの長さが 5 であるため、列にいるヘビの頭の座標は 5 だけ減少する。列に残っているヘビの頭の座標は先頭から順に 0,7,10 となる。
7 個目のクエリ : 前から 3 番目にいるヘビの頭の座標を出力する。列にいるヘビの頭の座標は前から順に 0, 7, 10 であるため、10 を出力する。

入力例 2

出力例 2

タイプ 3 のクエリが 1 つもない場合もあります。

入力例 3

出力例 3

20
5

Score : 300 points

Problem Statement

There is a queue of snakes. Initially, the queue is empty.

You are given Q queries, which should be processed in the order they are given. There are three types of queries:

Type 1: Given in the form 1 l. A snake of length l is added to the end of the queue. If the queue was empty before adding, the head position of the newly added snake is 0; otherwise, it is the sum of the head coordinate of the last snake in the queue and the last snake’s length.
Type 2: Given in the form 2. The snake at the front of the queue leaves the queue. It is guaranteed that the queue is not empty at this time. Let m be the length of the snake that left, then the head coordinate of every snake remaining in the queue decreases by m.
Type 3: Given in the form 3 k. Output the head coordinate of the snake that is k-th from the front of the queue. It is guaranteed that there are at least k snakes in the queue at this time.

Constraints

1 \leq Q \leq 3 \times 10^{5}
For a query of type 1, 1 \leq l \leq 10^{9}
For a query of type 2, it is guaranteed that the queue is not empty.
For a query of type 3, let n be the number of snakes in the queue, then 1 \leq k \leq n.
All input values are integers.

Input

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

Q
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q

Here, \text{query}_i is the i-th query in one of the following forms:

1 l

3 k

Output

Let q be the number of queries of type 3. Print q lines. The i-th line should contain the answer to the i-th type 3 query.

Sample Input 1

Sample Output 1

5
10

1st query: A snake of length 5 is added to the queue. Since the queue was empty, the head coordinate of this snake is 0.
2nd query: A snake of length 7 is added to the queue. Before adding, the last snake has head coordinate 0 and length 5, so the newly added snake’s head coordinate is 5.
3rd query: Output the head coordinate of the snake that is 2nd from the front. Currently, the head coordinates of the snakes in order are 0, 5, so output 5.
4th query: A snake of length 3 is added to the queue. Before adding, the last snake has head coordinate 5 and length 7, so the new snake’s head coordinate is 12.
5th query: A snake of length 4 is added to the queue. Before adding, the last snake has head coordinate 12 and length 3, so the new snake’s head coordinate is 15.
6th query: The snake at the front leaves the queue. The length of the snake that left is 5, so the head coordinate of each remaining snake decreases by 5. The remaining snake’s head coordinate becomes 0, 7, 10.
7th query: Output the head coordinate of the snake that is 3rd from the front. Currently, the head coordinates of the snakes in order are 0, 7, 10, so output 10.

Sample Input 2

Sample Output 2

It is possible that there are no queries of type 3.

Sample Input 3

Sample Output 3

20
5

F - Variety Split Easy

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

この問題は F 問題の簡易版です。

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

A を 1 か所で区切って 2 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。

より厳密には、1 \leq i \leq N-1 を満たす整数 i について (A_1,A_2,\ldots,A_i), (A_{i+1},A_{i+2},\ldots,A_N) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。

制約

2 \leq N \leq 3 \times 10^5
1 \leq A_i \leq N (1 \leq i \leq N)
入力はすべて整数である

入力

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

N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

5
3 1 4 1 5

出力例 1

i=1 としたとき、(3) と (1,4,1,5) のそれぞれに含まれる整数の種類数は 1,3 で、これらの和は 4 です。
i=2 としたとき、(3,1) と (4,1,5) のそれぞれに含まれる整数の種類数は 2,3 で、これらの和は 5 です。
i=3 としたとき、(3,1,4) と (1,5) のそれぞれに含まれる整数の種類数は 3,2 で、これらの和は 5 です。
i=4 としたとき、(3,1,4,1) と (5) のそれぞれに含まれる整数の種類数は 3,1 で、これらの和は 4 です。

よって、 i=2,3 のときに、最大値 5 を取ります。

入力例 2

10
2 5 6 5 2 1 7 9 7 2

出力例 2

Score : 350 points

Problem Statement

This problem is a simplified version of Problem F.

You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).

When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.

More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).

Constraints

2 \leq N \leq 3 \times 10^5
1 \leq A_i \leq N (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5
3 1 4 1 5

Sample Output 1

For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.

Therefore, the maximum sum is 5 for i=2,3.

Sample Input 2

10
2 5 6 5 2 1 7 9 7 2

Sample Output 2

G - Play Train

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

高橋君は電車のおもちゃを連結させたり分離させたりして遊んでいます。
電車は N 個あり、電車 1 、電車 2 、\ldots 、電車 N と名前がついています。
はじめ電車どうしは連結しておらず全てバラバラです。

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

1 x y ：電車 x の後部と、電車 y の前部を連結させる。
以下のことが保証されます。
- x \neq y
- クエリを処理する直前に、電車 x の後部と連結している電車は存在しない
- クエリを処理する直前に、電車 y の前部と連結している電車は存在しない
- クエリを処理する直前に、電車 x と電車 y は異なる連結成分に属する
2 x y ：電車 x の後部と、電車 y の前部を分離させる。
以下のことが保証されます。
- x \neq y
- クエリを処理する直前に、電車 x の後部と電車 y の前部は直接連結している
3 x ：電車 x が含まれる連結成分に属する電車の番号を、先頭から順番に全て出力する。

制約

2 \leq N \leq 10^5
1 \leq Q \leq 10^5
1 \leq x \leq N
1 \leq y \leq N
入力は全て整数
クエリは全て問題文の条件を満たす
3 x の形式のクエリで出力する電車の番号の個数の合計は 10^6 以下

入力

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

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

i 番目のクエリ \mathrm{query}_i では、まずクエリの種類 c_i（ 1, 2, 3 のいずれか）が与えられる。
c_i = 1,2 の場合は x,y が追加で与えられ、c_i =3 の場合は x が追加で与えられる。

すなわち、各クエリは以下に示す 3 つの形式のいずれかである。

1 x y

2 x y

3 x

出力

ある c_i = 3 のタイプのクエリにおいて、出力すべき値が j_1, j_2, \ldots , j_M であるとする。
このとき以下の形式で 1 行に出力せよ。

M j_1 j_2 \ldots j_M

c_i = 3 のタイプのクエリの数を q として、q 行出力せよ。
k (1 \leq k \leq q) 行目では k 番目のそのようなクエリに対する答えを出力せよ。

入力例 1

出力例 1

5 6 3 5 2 7
2 4 1
5 6 3 5 2 7
4 1 5 2 7
1 4
2 6 3

\mathrm{query}_5 まで処理した時、電車は以下のようになっています。
この時、たとえば電車 2 は、電車 3,5,6,7 と同じ連結成分に属していますが、電車 1,4 とは同じ連結成分に属していません。

\mathrm{query}_{11} まで処理した時、電車は以下のようになっています。

Score : 400 points

Problem Statement

Takahashi is playing with toy trains, connecting and disconnecting them.
There are N toy train cars, with car numbers: Car 1, Car 2, \ldots, Car N.
Initially, all cars are separated.

You will be given Q queries. Process them in the order they are given. There are three kinds of queries, as follows.

1 x y: Connect the front of Car y to the rear of Car x.
It is guaranteed that:
- x \neq y
- just before this query, no train is connected to the rear of Car x;
- just before this query, no train is connected to the front of Car y;
- just before this query, Car x and Car y belong to different connected components.
2 x y: Disconnect the front of Car y from the rear of Car x.
It is guaranteed that:
- x \neq y;
- just before this query, the front of Car y is directly connected to the rear of Car x.
3 x: Print the car numbers of the cars belonging to the connected component containing Car x, from front to back.

Constraints

2 \leq N \leq 10^5
1 \leq Q \leq 10^5
1 \leq x \leq N
1 \leq y \leq N
All values in input are integers.
All queries satisfy the conditions in the Problem Statement.
The queries of the format 3 x ask to print at most 10^6 car numbers in total.

Input

Input is given from Standard Input in the following format:

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

The i-th query \mathrm{query}_i begins with an integer c_i (1, 2, or 3) representing the kind of the query, followed by x and y if c_i = 1 or 2, and followed by x if c_i = 3.

In short, each query is in one of the following three formats:

1 x y

2 x y

3 x

Output

If a query with c_i = 3 asks to print the values j_1, j_2, \ldots, j_M, output the following line:

M j_1 j_2 \ldots j_M

Your output should consist of q lines, where q is the number of queries with c_i = 3.
The k-th line (1 \leq k \leq q) should contain the response to the k-th such query.

Sample Input 1

Sample Output 1

5 6 3 5 2 7
2 4 1
5 6 3 5 2 7
4 1 5 2 7
1 4
2 6 3

The figure below shows the cars when the first 5 queries are processed.
For example, Car 2 belongs to the same connected component as Cars 3, 5, 6, 7, which is different from the connected component containing Cars 1, 4.

The figure below shows the cars when the first 11 queries are processed.