AtCoder Daily Training HARD 2025/10/08 16:00start

E - Σ

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

長さ N の正整数列 A=(A_1,A_2,\dots,A_N) および正整数 K が与えられます。

1 以上 K 以下の整数のうち、A の中に一度も現れないものの総和を求めてください。

制約

1\leq N \leq 2\times 10^5
1\leq K \leq 2\times 10^9
1\leq A_i \leq 2\times 10^9
入力は全て整数

入力

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

N K
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 5
1 6 3 1

出力例 1

1 以上 5 以下の整数のうち、A の中に一度も現れないものは 2,4,5 の 3 つです。

よって、それらの総和である 2+4+5=11 を出力します。

入力例 2

1 3
346

出力例 2

入力例 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

出力例 3

12523196466007058

Score: 250 points

Problem Statement

You are given a sequence of positive integers A=(A_1,A_2,\dots,A_N) of length N and a positive integer K.

Find the sum of the integers between 1 and K, inclusive, that do not appear in the sequence A.

Constraints

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

Input

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

N K
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 5
1 6 3 1

Sample Output 1

Among the integers between 1 and 5, three numbers, 2, 4, and 5, do not appear in A.

Thus, print their sum: 2+4+5=11.

Sample Input 2

1 3
346

Sample Output 2

Sample Input 3

10 158260522
877914575 24979445 623690081 262703497 24979445 1822804784 1430302156 1161735902 923078537 1189330739

Sample Output 3

12523196466007058

F - Bib

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 から N の番号がついた N 人の人がいます。

人 i は数 Q_i が書かれたゼッケンを着けており、人 P_i を見つめています。

i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を、i=1,2,\ldots,N のそれぞれについて求めてください。

制約

2 \leq N \leq 3\times 10^5
1 \leq P_i \leq N
P_i は相異なる
1 \leq Q_i \leq N
Q_i は相異なる
入力は全て整数である

入力

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

N
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

出力

i が書かれたゼッケンを着けている人が見つめている人の着けているゼッケンにかかれている数を S_i とする。
S_1,S_2,\ldots,S_N をこの順に空白区切りで出力せよ。

入力例 1

4
4 3 2 1
2 3 1 4

出力例 1

3 4 1 2

人 3 は 1 が書かれたゼッケンを着けており、人 3 が見つめている人 2 は 3 が書かれたゼッケンを着けています。よって i=1 に対する答えは 3 になります。

入力例 2

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

出力例 2

4 8 6 5 3 10 9 2 1 7

Score : 300 points

Problem Statement

There are N people numbered from 1 to N.

Person i is wearing a bib with the number Q_i and is staring at person P_i.

For each i = 1,2,\ldots,N, find the number written on the bib of the person that the person wearing the bib with number i is staring at.

Constraints

2 \leq N \leq 3\times 10^5
1 \leq P_i \leq N
The values of P_i are distinct.
1 \leq Q_i \leq N
The values of Q_i are distinct.
All input values are integers.

Input

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

N
P_1 P_2 \dots P_N
Q_1 Q_2 \dots Q_N

Output

Let S_i be the number written on the bib of the person that the person wearing the bib with number i is staring at.
Print S_1, S_2, \ldots, S_N in this order, separated by a single space.

Sample Input 1

4
4 3 2 1
2 3 1 4

Sample Output 1

3 4 1 2

Person 3 is wearing the bib with the number 1, and the person that person 3 is staring at, person 2, is wearing the bib with the number 3. Thus, the answer for i = 1 is 3.

Sample Input 2

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

Sample Output 2

4 8 6 5 3 10 9 2 1 7

G - I Hate Non-integer Number

Time Limit: 2.5 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

項数が N の正整数列 A=(a_1,\ldots,a_N) が与えられます。
A の項を 1 個以上選ぶ方法は 2^N-1 通りありますが、そのうち選んだ項の平均値が整数であるものが何通りかを 998244353 で割った余りを求めてください。

制約

1 \leq N \leq 100
1 \leq a_i \leq 10^9
入力はすべて整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

3
2 6 2

出力例 1

A の項を選ぶ方法それぞれに対する平均値は以下のようになります。

a_1 のみを選んだ場合、平均値は \frac{a_1}{1}=\frac{2}{1} = 2 であり、整数である。
a_2 のみを選んだ場合、平均値は \frac{a_2}{1}=\frac{6}{1} = 6 であり、整数である。
a_3 のみを選んだ場合、平均値は \frac{a_3}{1}=\frac{2}{1} = 2 であり、整数である。
a_1 と a_2 を選んだ場合、平均値は \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4 であり、整数である。
a_1 と a_3 を選んだ場合、平均値は \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2 であり、整数である。
a_2 と a_3 を選んだ場合、平均値は \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4 であり、整数である。
a_1 と a_2 と a_3 を選んだ場合、平均値は \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3} であり、整数ではない。

以上より、6 通りの選び方が条件を満たします。

入力例 2

5
5 5 5 5 5

出力例 2

どのように A の項を 1 個以上選んでも平均値が 5 になります。

Score : 400 points

Problem Statement

You are given a sequence of positive integers A=(a_1,\ldots,a_N) of length N.
There are (2^N-1) ways to choose one or more terms of A. How many of them have an integer-valued average? Find the count modulo 998244353.

Constraints

1 \leq N \leq 100
1 \leq a_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

3
2 6 2

Sample Output 1

For each way to choose terms of A, the average is obtained as follows:

If just a_1 is chosen, the average is \frac{a_1}{1}=\frac{2}{1} = 2, which is an integer.
If just a_2 is chosen, the average is \frac{a_2}{1}=\frac{6}{1} = 6, which is an integer.
If just a_3 is chosen, the average is \frac{a_3}{1}=\frac{2}{1} = 2, which is an integer.
If a_1 and a_2 are chosen, the average is \frac{a_1+a_2}{2}=\frac{2+6}{2} = 4, which is an integer.
If a_1 and a_3 are chosen, the average is \frac{a_1+a_3}{2}=\frac{2+2}{2} = 2, which is an integer.
If a_2 and a_3 are chosen, the average is \frac{a_2+a_3}{2}=\frac{6+2}{2} = 4, which is an integer.
If a_1, a_2, and a_3 are chosen, the average is \frac{a_1+a_2+a_3}{3}=\frac{2+6+2}{3} = \frac{10}{3}, which is not an integer.

Therefore, 6 ways satisfy the condition.

Sample Input 2

5
5 5 5 5 5

Sample Output 2

Regardless of the choice of one or more terms of A, the average equals 5.

H - Count A%B=C

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 475 点

問題文

整数の組 (a, b, c) であって以下の条件を満たすものの個数を 998244353 で割ったあまりを求めてください。

1 \leq a,b,c \leq N
a,b,c は相異なる。
a を b で割ったあまりは c に等しい。

制約

3 \leq N \leq 10^{12}
N は整数

入力

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

出力

答えを 1 行で出力せよ。

入力例 1

出力例 1

条件を満たす整数の組 (a,b,c) は以下の 12 通り存在します。

(3,2,1)
(4,3,1)
(5,2,1)
(5,3,2)
(5,4,1)
(6,4,2)
(6,5,1)
(7,2,1)
(7,3,1)
(7,4,3)
(7,5,2)
(7,6,1)

入力例 2

出力例 2

入力例 3

411111111114

出力例 3

462474062

Score : 475 points

Problem Statement

Find the number, modulo 998244353, of integer tuples (a, b, c) that satisfy the following conditions.

1 \leq a,b,c \leq N
a,b,c are pairwise distinct.
The remainder when a is divided by b is equal to c.

Constraints

3 \leq N \leq 10^{12}
N is an integer.

Input

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

Output

Output the answer in one line.

Sample Input 1

Sample Output 1

There are 12 integer tuples (a,b,c) that satisfy the conditions:

(3,2,1)
(4,3,1)
(5,2,1)
(5,3,2)
(5,4,1)
(6,4,2)
(6,5,1)
(7,2,1)
(7,3,1)
(7,4,3)
(7,5,2)
(7,6,1)

Sample Input 2

Sample Output 2

Sample Input 3

411111111114

Sample Output 3

462474062

I - Many Lamps

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 550 点

問題文

頂点に 1 から N の、辺に 1 から M の番号がついた N 頂点 M 辺の単純グラフがあります。辺 i は頂点 u_i と頂点 v_i を結んでいます。
各頂点にはランプが 1 個ずつ載っています。はじめ、全てのランプは消えています。

以下の操作を 0 回以上 M 回以下行うことで、ランプがちょうど K 個ついた状態にできるかどうかを判定してください。

辺を 1 本選ぶ。辺の両端点を u, v とする。u, v に載っているランプの状態を反転させる。つまり、ランプがついていたら消して、消えていたらつける。

また、ちょうど K 個のランプがついた状態にすることが可能な場合は、そのような操作の手順を出力してください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
0 \leq K \leq N
1 \leq u_i \lt v_i \leq N
入力で与えられるグラフは単純
入力される値は全て整数

入力

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

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

ちょうど K 個のランプがついた状態にすることが不可能な場合は No を出力せよ。
可能な場合はまず Yes を出力して、その後に操作の手順を以下の形式で出力せよ。

X
e_1 e_2 \dots e_X

ここで、X は操作回数を、e_i は i 番目の操作で選ぶ辺の番号を意味する。これらは次を満たす必要がある。

0 \leq X \leq M
1 \leq e_i \leq M

条件を満たす操作の手順が複数ある場合は、どれを出力しても正解とみなされる。

入力例 1

出力例 1

Yes
3
3 4 5

出力例に従って操作を行うと次のようになります。

辺 3 を選ぶ。頂点 2 と頂点 4 に載っているランプをつける。
辺 4 を選ぶ。頂点 3 と頂点 5 に載っているランプをつける。
辺 5 を選ぶ。頂点 1 に載っているランプをつけて、頂点 5 に載っているランプを消す。

操作を全て終了した時点で頂点 1,2,3,4 に載っているランプがついています。よってこの操作の手順は条件を満たしています。

条件を満たす操作の手順としては他に X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1) などが挙げられます。(同じ辺を 2 回以上選んでもよいです。)

入力例 2

出力例 2

No

入力例 3

出力例 3

Yes
3
10 9 6

Score: 550 points

Problem Statement

There is a simple graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertices u_i and v_i.
Each vertex has one lamp on it. Initially, all the lamps are off.

Determine whether it is possible to turn exactly K lamps on by performing the following operation between 0 and M times, inclusive.

Choose one edge. Let u and v be the endpoints of the edge. Toggle the states of the lamps on u and v. That is, if the lamp is on, turn it off, and vice versa.

If it is possible to turn exactly K lamps on, print a sequence of operations that achieves this state.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq \min\left( 2 \times 10^5, \frac{N(N-1)}{2} \right)
0 \leq K \leq N
1 \leq u_i < v_i \leq N
The given graph is simple.
All input values are integers.

Input

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

N M K
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

If it is impossible to turn exactly K lamps on, print No.
Otherwise, first print Yes, and then print a sequence of operations in the following format:

X
e_1 e_2 \dots e_X

Here, X is the number of operations, and e_i is the number of the edge chosen in the i-th operation. These must satisfy the following:

0 \leq X \leq M
1 \leq e_i \leq M

If multiple sequences of operations satisfy the conditions, any of them will be considered correct.

Sample Input 1

Sample Output 1

Yes
3
3 4 5

If we operate according to the sample output, it will go as follows:

Choose edge 3. Turn on the lamps on vertex 2 and vertex 4.
Choose edge 4. Turn on the lamps on vertex 3 and vertex 5.
Choose edge 5. Turn on the lamp on vertex 1 and turn off the lamp on vertex 5.

After completing all operations, the lamps on vertices 1, 2, 3, and 4 are on. Therefore, this sequence of operations satisfies the conditions.

Other possible sequences of operations that satisfy the conditions include X = 4, (e_1,e_2,e_3,e_4) = (3,4,3,1). (It is allowed to choose the same edge more than once.)

Sample Input 2

Sample Output 2

No

Sample Input 3

Sample Output 3

Yes
3
10 9 6