AtCoder Daily Training HARD 2026/02/05 18:30start

E - Odd One Subsequence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
1\leq i<j<k\leq N をみたす整数の組 (i,j,k) であって、次の条件をみたすものの個数を求めてください。

A_i,A_j,A_k の中にちょうど 2 種類の値が含まれる。すなわち、A_i,A_j,A_k の中のいずれか 2 つは等しく、残りの 1 つは異なる。

制約

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq N
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

条件をみたす整数の組の個数を出力せよ。

入力例 1

5
3 2 5 2 2

出力例 1

例えば、(i,j,k)=(1,2,4) は、A_1=3, A_2=2, A_4=2 の中に 2,3 のちょうど 2 種類の値が含まれるため、条件をみたします。
これを含めて、(i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) の 6 組が条件をみたします。
よって、6 を出力します。

入力例 2

3
1 1 1

出力例 2

条件をみたす組が存在しない可能性もあります。

Score : 300 points

Problem Statement

You are given an integer sequence of length N, A=(A_1,A_2,\ldots,A_N).
Find the number of triples of integers (i,j,k) satisfying 1\leq i<j<k\leq N that satisfy the following condition:

Exactly two distinct values are contained in A_i,A_j,A_k. That is, two of A_i,A_j,A_k are equal, and the remaining one is different.

Constraints

3 \leq N \leq 2\times 10^5
1 \leq A_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 number of triples of integers that satisfy the condition.

Sample Input 1

5
3 2 5 2 2

Sample Output 1

For example, (i,j,k)=(1,2,4) satisfies the condition because exactly two distinct values, 2 and 3, are contained in A_1=3, A_2=2, and A_4=2.
Including this, the six triples (i,j,k)=(1,2,4),(1,2,5),(1,4,5),(2,3,4),(2,3,5),(3,4,5) satisfy the condition.
Therefore, print 6.

Sample Input 2

3
1 1 1

Sample Output 2

There may be no triples that satisfy the condition.

F - Buy Balls

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個の黒色のボールと M 個の白色のボールがあります。
ボールにはそれぞれ価値がつけられており、i\ (1\leq i\leq N) 個目の黒色のボールの価値は B_i、j\ (1\leq j\leq M) 個目の白色のボールの価値は W_j です。

黒色のボールの個数が白色のボールの個数以上になるようにボールを 0 個以上選ぶとき、選んだボールの価値の総和としてありうる最大値を求めてください。

制約

1\leq N,M\leq 2\times 10^5
-10^9\leq B_i,W_j\leq 10^9
入力は全て整数

入力

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

N M
B_1 B_2 \ldots B_N
W_1 W_2 \ldots W_M

出力

答えを出力せよ。

入力例 1

4 3
8 5 -1 3
3 -2 -4

出力例 1

1,2,4 個目の黒色のボールと 1 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 8+5+3+3=19 となりこれが最大です。

入力例 2

4 3
5 -10 -2 -5
8 1 4

出力例 2

1,3 個目の黒色のボールと 1,3 個目の白色のボールを選ぶとき、選んだボールの価値の総和は 5+(-2)+8+4=15 となりこれが最大です。

入力例 3

3 5
-36 -33 -31
12 12 28 24 27

出力例 3

ボールを 1 つも選ばないことも可能です。

Score : 300 points

Problem Statement

There are N black balls and M white balls.
Each ball has a value. The value of the i-th black ball (1 \le i \le N) is B_i, and the value of the j-th white ball (1 \le j \le M) is W_j.

Choose zero or more balls so that the number of black balls chosen is at least the number of white balls chosen. Among all such choices, find the maximum possible sum of the values of the chosen balls.

Constraints

1 \leq N,M \leq 2\times 10^5
-10^9 \leq B_i, W_j \leq 10^9
All input values are integers.

Input

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

N M
B_1 B_2 \ldots B_N
W_1 W_2 \ldots W_M

Output

Print the answer.

Sample Input 1

4 3
8 5 -1 3
3 -2 -4

Sample Output 1

If you choose the 1st, 2nd, and 4th black balls, and the 1st white ball, the sum of their values is 8+5+3+3=19, which is the maximum.

Sample Input 2

4 3
5 -10 -2 -5
8 1 4

Sample Output 2

If you choose the 1st and 3rd black balls, and the 1st and 3rd white balls, the sum of their values is 5+(-2)+8+4=15, which is the maximum.

Sample Input 3

3 5
-36 -33 -31
12 12 28 24 27

Sample Output 3

It is possible to choose no balls.

G - Restricted Permutation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

(1, 2, \dots, N) を並び替えて得られる数列 P であって以下の条件を満たすもののうち、辞書順で最小のものを求めてください。

i = 1, \dots, M に対し、P において A_i は B_i よりも先に現れる。

ただし、そのような P が存在しない場合は -1 と出力してください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
A_i \neq B_i
入力は全て整数である。

入力

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

N M
A_1 B_1
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

出力例 1

2 1 3 4

条件を満たす P は (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1) の 5 つです。これらのうち辞書順で最小のものは (2, 1, 3, 4) です。

入力例 2

出力例 2

-1

条件を満たす P は存在しません。

Score : 400 points

Problem Statement

Among the sequences P that are permutations of (1, 2, \dots, N) and satisfy the condition below, find the lexicographically smallest sequence.

For each i = 1, \dots, M, A_i appears earlier than B_i in P.

If there is no such P, print -1.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
A_i \neq B_i
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

Sample Output 1

2 1 3 4

The following five permutations P satisfy the condition: (2, 1, 3, 4), (2, 3, 1, 4), (2, 3, 4, 1), (3, 2, 1, 4), (3, 2, 4, 1). The lexicographically smallest among them is (2, 1, 3, 4).

Sample Input 2

Sample Output 2

-1

No permutations P satisfy the condition.

H - Heavy Buckets

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 人の人がおり、N 個のバケツがあります。人とバケツにはそれぞれ 1, 2, \ldots, N の番号が付けられています。

人 i ははじめバケツ i のみを持っており、バケツ i には何も入っていません。

これから、以下の操作を 10^9 回行います。

i = 1, 2, \ldots, N について同時に、人 i が持っているバケツすべてに水を i ずつ入れ、それらのバケツを人 A_i に渡す。

ただし、バケツに入れることのできる水の量に制限はありません。

i = 1, 2, \ldots, Q について以下の形式のクエリに答えてください。

T_i 回目の操作の直後にバケツ B_i に入っている水の量を求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq A_i \leq N
1 \leq T_i \leq 10^9
1 \leq B_i \leq N
入力される値はすべて整数

入力

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

N Q
A_1 A_2 \ldots A_N
T_1 B_1
T_2 B_2
\vdots
T_Q B_Q

出力

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

入力例 1

5 6
3 4 2 2 5
4 3
6 5
1 4
10 1
10 2
1000000000 1

出力例 1

1 番目のクエリに対する説明を行います。

はじめ、バケツ 3 は人 3 が持っています。

1 回目の操作の直後、バケツ 3 は人 2 が持っており、水が 3 入っています。

2 回目の操作の直後、バケツ 3 は人 4 が持っており、水が 5 入っています。

3 回目の操作の直後、バケツ 3 は人 2 が持っており、水が 9 入っています。

4 回目の操作の直後、バケツ 3 は人 4 が持っており、水が 11 入っています。

したがって、1 番目のクエリに対する答えは 11 となります。

Score : 475 points

Problem Statement

There are N people and N buckets. Both the people and buckets are numbered 1, 2, \ldots, N.

Initially, person i holds only bucket i, and bucket i is empty.

From now on, the following operation will be performed 10^9 times:

For i = 1, 2, \ldots, N simultaneously, person i adds i units of water to each of the buckets they are holding and passes those buckets to person A_i.

Here, there is no limit on the amount of water that can be put in a bucket.

For i = 1, 2, \ldots, Q, answer the following queries:

Find the amount of water in bucket B_i immediately after the T_i-th operation.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq Q \leq 2 \times 10^5
1 \leq A_i \leq N
1 \leq T_i \leq 10^9
1 \leq B_i \leq N
All input values are integers.

Input

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

N Q
A_1 A_2 \ldots A_N
T_1 B_1
T_2 B_2
\vdots
T_Q B_Q

Output

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

Sample Input 1

5 6
3 4 2 2 5
4 3
6 5
1 4
10 1
10 2
1000000000 1

Sample Output 1

We will explain the first query.

Initially, bucket 3 is held by person 3.

Immediately after the 1-st operation, bucket 3 is held by person 2 and contains 3 units of water.

Immediately after the 2-nd operation, bucket 3 is held by person 4 and contains 5 units of water.

Immediately after the 3-rd operation, bucket 3 is held by person 2 and contains 9 units of water.

Immediately after the 4-th operation, bucket 3 is held by person 4 and contains 11 units of water.

Thus, the answer to the first query is 11.

I - Breakdown

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

N 個の頂点と M 本の辺からなる単純な無向グラフが与えられます。 i = 1, 2, \ldots, M について、i 番目の辺は頂点 u_i と頂点 v_i を結ぶ辺です。また、i = 1, 2, \ldots, N について、頂点 i には正整数 W_i が割り当てられており、A_i 個のコマが置かれています。

グラフ上にコマが存在する限り、下記の操作を繰り返します。

まず、グラフ上のコマを 1 個選んで取り除き、そのコマが置かれていた頂点を x とおく。
x に隣接するいくつかの頂点からなる（空でも良い）集合 S であって、\sum_{y \in S} W_y \lt W_x であるものを選び、S に含まれる頂点それぞれに 1 個ずつコマを置く。

操作を行う回数としてあり得る最大値を出力してください。

なお、どのように操作を行っても、有限回の操作の後にはグラフ上にコマが存在しない状態に至ることが証明出来ます。

制約

入力される値はすべて整数
2 \leq N \leq 5000
1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
1 \leq u_i, v_i \leq N
u_i \neq v_i
i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
1 \leq W_i \leq 5000
0 \leq A_i \leq 10^9

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

出力

答えを出力せよ。

入力例 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

出力例 1

以下の説明では、各頂点にあるコマの個数を、数列 A = (A_1, A_2, \ldots, A_N) として表します。はじめ、A = (1, 0, 0, 0, 0, 1) です。

下記の手順で操作を行うことを考えます。

頂点 1 にあるコマを 1 個取り除き、頂点 2, 3 にコマを 1 個ずつ置く。その結果、A = (0, 1, 1, 0, 0, 1) となる。
頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 1) となる。
頂点 6 にあるコマを 1 個取り除く。その結果、A = (0, 0, 1, 0, 0, 0) となる。
頂点 3 にあるコマを 1 個取り除き、頂点 2 にコマを 1 個置く。その結果、A = (0, 1, 0, 0, 0, 0) となる。
頂点 2 にあるコマを 1 個取り除く。その結果、A = (0, 0, 0, 0, 0, 0) となる。

上記の手順で操作を行う回数は 5 回であり、これが操作を行う回数としてあり得る最大値です。

入力例 2

出力例 2

この入力例では、はじめからグラフ上にコマが存在しません。

入力例 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1

出力例 3

Score: 475 points

Problem Statement

You are given a simple undirected graph consisting of N vertices and M edges. For i = 1, 2, \ldots, M, the i-th edge connects vertices u_i and v_i. Also, for i = 1, 2, \ldots, N, vertex i is assigned a positive integer W_i, and there are A_i pieces placed on it.

As long as there are pieces on the graph, repeat the following operation:

First, choose and remove one piece from the graph, and let x be the vertex on which the piece was placed.
Choose a (possibly empty) set S of vertices adjacent to x such that \sum_{y \in S} W_y \lt W_x, and place one piece on each vertex in S.

Print the maximum number of times the operation can be performed.

It can be proved that, regardless of how the operation is performed, there will be no pieces on the graph after a finite number of iterations.

Constraints

All input values are integers.
2 \leq N \leq 5000
1 \leq M \leq \min \lbrace N(N-1)/2, 5000 \rbrace
1 \leq u_i, v_i \leq N
u_i \neq v_i
i \neq j \implies \lbrace u_i, v_i \rbrace \neq \lbrace u_j, v_j \rbrace
1 \leq W_i \leq 5000
0 \leq A_i \leq 10^9

Input

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M
W_1 W_2 \ldots W_N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

6 6
1 2
2 3
3 1
3 4
1 5
5 6
9 2 3 1 4 4
1 0 0 0 0 1

Sample Output 1

In the following explanation, let A = (A_1, A_2, \ldots, A_N) represent the numbers of pieces on the vertices. Initially, A = (1, 0, 0, 0, 0, 1).

Consider performing the operation as follows:

Remove one piece from vertex 1 and place one piece each on vertices 2 and 3. Now, A = (0, 1, 1, 0, 0, 1).
Remove one piece from vertex 2. Now, A = (0, 0, 1, 0, 0, 1).
Remove one piece from vertex 6. Now, A = (0, 0, 1, 0, 0, 0).
Remove one piece from vertex 3 and place one piece on vertex 2. Now, A = (0, 1, 0, 0, 0, 0).
Remove one piece from vertex 2. Now, A = (0, 0, 0, 0, 0, 0).

In this procedure, the operation is performed five times, which is the maximum possible number of times.

Sample Input 2

Sample Output 2

In this sample input, there are no pieces on the graph from the beginning.

Sample Input 3

10 20
4 8
1 10
1 7
5 9
9 10
8 10
7 5
1 4
7 3
8 7
2 8
5 8
4 2
5 1
7 2
8 3
3 4
8 9
7 10
2 3
25 5 1 1 16 5 98 3 21 1
35 39 32 11 35 37 14 29 36 1