実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A の異なる 2 要素の和として表せる値の中に偶数が存在するか判定し、存在する場合その最大値を求めてください。
制約
- 2\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- A の要素は相異なる
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の異なる 2 要素の和として表せる値の中に偶数が存在しない場合、-1 を出力せよ。
偶数が存在する場合、その最大値を出力せよ。
入力例 1
3 2 3 4
出力例 1
6
A の異なる 2 要素の和として表せる値は 5,6,7 です。この中に偶数は存在し、その最大値は 6 です。
入力例 2
2 1 0
出力例 2
-1
A の異なる 2 要素の和として表せる値は 1 です。この中に偶数は存在しないので、 -1 を出力してください。
Score : 300 points
Problem Statement
You are given a sequence A=(A_1,A_2,\ldots,A_N) of length N consisting of non-negative integers.
Determine if there is an even number represented as the sum of two different elements of A. If it exists, find the maximum such number.
Constraints
- 2\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- The elements of A are distinct.
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \ldots A_N
Output
Print -1 if there is no even number represented as the sum of two different elements of A.
If such an even number exists, print the maximum such number.
Sample Input 1
3 2 3 4
Sample Output 1
6
The values represented as the sum of two distinct elements of A are 5, 6, and 7. We have an even number here, and the maximum is 6.
Sample Input 2
2 1 0
Sample Output 2
-1
The value represented as the sum of two distinct elements of A is 1. We have no even number here, so -1 should be printed.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。
注釈
単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが 単純 であるとは、グラフが自己ループや多重辺を含まないことをいいます。
あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが 連結 であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。
制約
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq u_i, v_i \leq N
- 入力で与えられるグラフは単純
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 u_2 v_2 \vdots u_M v_M
出力
答えを出力せよ。
入力例 1
5 3 1 2 1 3 4 5
出力例 1
2
与えられるグラフに含まれる連結成分は次の 2 個です。
- 頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
- 頂点 4, 5 および辺 3 からなる部分グラフ
入力例 2
5 0
出力例 2
5
入力例 3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
出力例 3
1
Score : 300 points
Problem Statement
You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.
Notes
A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.
A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.
Constraints
- 1 \leq N \leq 100
- 0 \leq M \leq \frac{N(N - 1)}{2}
- 1 \leq u_i, v_i \leq N
- The given graph is simple.
- All values in the input are integers.
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
Output
Print the answer.
Sample Input 1
5 3 1 2 1 3 4 5
Sample Output 1
2
The given graph contains the following two connected components:
- a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
- a subgraph formed from vertices 4, 5, and edge 3.
Sample Input 2
5 0
Sample Output 2
5
Sample Input 3
4 6 1 2 1 3 1 4 2 3 2 4 3 4
Sample Output 3
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
2N 個のボールがあります。各ボールには 1 以上 N 以下の整数によって表される色が塗られており、各色で塗られたボールはちょうど 2 個ずつ存在します。
これらのボールが、底が地面と平行になるように置かれた M 本の筒に入れられています。はじめ、i \ (1 \leq i \leq M) 本目の筒には k_i 個のボールが入っており、上から j \ (1 \leq j \leq k_i) 番目のボールの色は a_{i, j} です。
あなたの目標は、以下の操作を繰り返すことで M 本の筒全てを空にすることです。
- 異なる 2 本の空でない筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。ここで、取り出して捨てた 2 つのボールは同じ色で塗られている必要がある。
目標が達成可能かを判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq k_i\ (1 \leq i \leq M)
- 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
- \sum_{i=1}^{M} k_i = 2N
- 全ての x\ (1 \leq x \leq N) について、1 \leq i \leq M かつ 1 \leq j \leq k_i かつ a_{i,j}=x なる整数の組 (i,j) はちょうど 2 つ存在する
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}
出力
目標が達成可能なら Yes を、達成不可能なら No を出力せよ。
入力例 1
2 2 2 1 2 2 1 2
出力例 1
Yes
以下のように操作を行えばよいです。
- 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 1 であり等しいので、この操作は有効である。
- 1 つ目の筒と 2 つ目の筒を選び、それぞれの筒の一番上にあるボールを取り出して捨てる。捨てられるボールの色は共に 2 であり等しいので、この操作は有効である。
入力例 2
2 2 2 1 2 2 2 1
出力例 2
No
そもそも一度も操作を行うことができないため、目標を達成する、すなわち M 本の筒全てを空にすることは不可能です。
Score : 400 points
Problem Statement
We have 2N balls. Each ball has a color represented by an integer between 1 and N (inclusive). For each of the N colors, there are exactly two balls of that color.
These balls are contained in M cylinders placed perpendicularly to the floor. Initially, the i-th cylinder (1 \leq i \leq M) contains k_i balls, the j-th of which from the top (1 \leq j \leq k_i) has the color a_{i, j}.
Your objective is to empty all M cylinders by repeating the following operation.
- Choose two different non-empty cylinders and remove the topmost ball from each of them. Here, the two balls removed must be of the same color.
Determine whether the objective is achievable.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 2 \leq M \leq 2 \times 10^5
- 1 \leq k_i\ (1 \leq i \leq M)
- 1 \leq a_{i,j} \leq N\ (1 \leq i \leq M,1 \leq j \leq k_i)
- \sum_{i=1}^{M} k_i = 2N
- For every x\ (1 \leq x \leq N), there exists exactly two pairs of integers (i,j) such that 1 \leq i \leq M, 1 \leq j \leq k_i, and a_{i,j}=x.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M
k_1
a_{1,1} a_{1,2} \ldots a_{1,k_1}
k_2
a_{2,1} a_{2,2} \ldots a_{2,k_2}
\hspace{2.1cm}\vdots
k_M
a_{M,1} a_{M,2} \ldots a_{M,k_M}
Output
If the objective is achievable, print Yes; otherwise, print No.
Sample Input 1
2 2 2 1 2 2 1 2
Sample Output 1
Yes
The objective can be achieved as follows.
- Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 1.
- Choose the first and second cylinders to remove the topmost ball from each of them, which is allowed since the removed balls have the same color: 2.
Sample Input 2
2 2 2 1 2 2 2 1
Sample Output 2
No
No operation can be done at all, which means it is impossible to achieve the objective of emptying the M cylinders.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ N の整数列 A = (A_1, A_2, \dots, A_N) が与えられます。
A の連続するとは限らない、長さが 2 以上である部分列 A'=(A'_1,A'_2,\ldots,A'_k) のうち以下の条件を満たすものの個数を求めてください。
- A'_1 \leq A'_k
なお、この値は非常に大きくなることがあるため、998244353 で割ったあまりを出力してください。
ただし、2 つの部分列は、列として同じであっても、取り出す添字が異なる場合は区別されます。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
A の連続するとは限らない、長さが 2 以上である部分列のうち問題文中の条件を満たすものの個数を、998244353 で割ったあまりを出力せよ。
入力例 1
3 1 2 1
出力例 1
3
A=(1,2,1) の連続するとは限らない、長さが 2 以上である部分列は (1,2), (1,1), (2,1), (1,2,1) の 4 通りあります。
そのうち問題文中の条件を満たすものは、(1,2), (1,1), (1,2,1) の 3 通りです。
入力例 2
3 1 2 2
出力例 2
4
列として同じであっても、取り出す添字が異なる場合 2 つの部分列は区別されることに注意してください。
この入出力例において、問題文中の条件を満たすような部分列は (1,2), (1,2), (2,2), (1,2,2) の 4 通りです。
入力例 3
3 3 2 1
出力例 3
0
問題文中の条件を満たすような部分列が存在しない場合もあります。
入力例 4
10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
出力例 4
830
Score : 500 points
Problem Statement
Given is a sequence of N integers: A = (A_1, A_2, \dots, A_N).
Find the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the following condition:
- A'_1 \leq A'_k.
Since the count can be enormous, print it modulo 998244353.
Here, two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 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 A_2 \ldots A_N
Output
Print the number of (not necessarily contiguous) subsequences A'=(A'_1,A'_2,\ldots,A'_k) of length at least 2 that satisfy the condition in Problem Statement.
Sample Input 1
3 1 2 1
Sample Output 1
3
A=(1,2,1) has four (not necessarily contiguous) subsequences of length at least 2: (1,2), (1,1), (2,1), (1,2,1).
Three of them, (1,2), (1,1), (1,2,1), satisfy the condition in Problem Statement.
Sample Input 2
3 1 2 2
Sample Output 2
4
Note that two subsequences are distinguished when they originate from different sets of indices, even if they are the same as sequences.
In this Sample, there are four subsequences, (1,2), (1,2), (2,2), (1,2,2), that satisfy the condition.
Sample Input 3
3 3 2 1
Sample Output 3
0
There may be no subsequence that satisfies the condition.
Sample Input 4
10 198495780 28463047 859606611 212983738 946249513 789612890 782044670 700201033 367981604 302538501
Sample Output 4
830
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
長さ L のパンが 1 つあり、これを N 人の子供たちに切り分けます。 i 番目 (1\leq i\leq N) の子供は長さ A_i のパンを欲しがっています。
そこで、高橋君は次の操作を繰り返して、長さ A_1,A_2,\ldots,A_N のパンを切り出して配ることにしました。
長さ k のパン 1 つと 1 以上 k-1 以下の整数 x を選ぶ。選んだパンを長さ x のパンと 長さ k-x のパンに切り分ける。
このとき、x の値によらずコストが k かかる。
それぞれの子供に配るパンは長さがちょうど A_i のパン 1 つである必要がありますが、誰にも配られずに余るパンがいくつあっても構いません。
このとき、全ての子供たちにパンを配るために必要な最小のコストを求めてください。
制約
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N L A_1 A_2 \ldots A_N
出力
全ての子供たちにパンを配るために必要な最小のコストを出力せよ。
入力例 1
5 7 1 2 1 2 1
出力例 1
16
高橋君は次のようにしてパンを切り分けて配ることができます。
- 長さ 7 のパンと整数 x=3 を選ぶ。パンは長さ 3 のパンと長さ 4 のパンに切り分けられる。 (コスト 7 )
- 長さ 3 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパンと長さ 2 のパンに切り分けられる。前者を 1 番目の子供に配る。 (コスト 3 )
- 長さ 2 のパンと整数 x=1 を選ぶ。パンは長さ 1 のパン 2 つに切り分けられる。これを 3,5 番目の子供に配る。 (コスト 2 )
- 長さ 4 のパンと整数 x=2 を選ぶ。パンは長さ 2 のパン 2 つに切り分けられる。これを 2,4 番目の子供に配る。 (コスト 4 )
このとき、コストは 7+3+2+4=16 かかり、これが最小です。 また、余るパンはありません。
入力例 2
3 1000000000000000 1000000000 1000000000 1000000000
出力例 2
1000005000000000
それぞれの子供に配るパンの長さはちょうど A_i でなければならない事に注意してください。
Score : 500 points
Problem Statement
We have a loaf of bread of length L, which we will cut and distribute to N children.
The i-th child (1\leq i\leq N) wants a loaf of length A_i.
Now, Takahashi will repeat the operation below to cut the loaf into lengths A_1, A_2, \ldots, A_N for the children.
Choose a loaf of length k and an integer x between 1 and k-1 (inclusive). Cut the loaf into two loaves of length x and k-x.
This operation incurs a cost of k regardless of the value of x.
Each child i must receive a loaf of length exactly A_i, but it is allowed to leave some loaves undistributed.
Find the minimum cost needed to distribute loaves to all children.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1\leq A_i\leq 10^9
- A_1+A_2+\cdots+A_N\leq L\leq 10^{15}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N L A_1 A_2 \ldots A_N
Output
Print the minimum cost needed to distribute loaves to all children.
Sample Input 1
5 7 1 2 1 2 1
Sample Output 1
16
Takahashi can cut the loaf for the children as follows.
- Choose the loaf of length 7 and x=3, cutting it into loaves of length 3 and 4 for a cost of 7.
- Choose the loaf of length 3 and x=1, cutting it into loaves of length 1 and 2 for a cost of 3. Give the former to the 1-st child.
- Choose the loaf of length 2 and x=1, cutting it into two loaves of length 1 for a cost of 2. Give them to the 3-rd and 5-th children.
- Choose the loaf of length 4 and x=2, cutting it into two loaves of length 2 for a cost of 4. Give them to the 2-nd and 4-th children.
This incurs a cost of 7+3+2+4=16, which is the minimum possible. There will be no leftover loaves.
Sample Input 2
3 1000000000000000 1000000000 1000000000 1000000000
Sample Output 2
1000005000000000
Note that each child i must receive a loaf of length exactly A_i.