Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder 王国では、これから N 日間のお祭りが開催されます。そのうち、A_1 日目、A_2 日目、\dots、A_M 日目の M 日では花火が上がります。ここで、お祭りの最終日には花火が上がることが保証されます。(つまり、A_M=N が保証されます。)
i=1,2,\dots,N に対して、以下の問題を解いてください。
- i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後か？ただし、i 日目に花火が上がる場合 0 日後とする。
制約
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
N 行出力せよ。
i(1 \le i \le N) 行目には、i 日目以降で初めて花火が上がるのは、i 日目から数えて何日後かを整数として出力せよ。
入力例 1
3 2 2 3
出力例 1
1 0 0
AtCoder 王国ではお祭りを 3 日間開催し、2,3 日目に花火が上がります。
- 1 日目以降で初めて花火が上がるのは 2 日目なので、1 日目から数えて 1 日後です。
- 2 日目以降で初めて花火が上がるのは 2 日目なので、2 日目から数えて 0 日後です。
- 3 日目以降で初めて花火が上がるのは 3 日目なので、3 日目から数えて 0 日後です。
入力例 2
8 5 1 3 4 7 8
出力例 2
0 1 0 0 2 1 0 0
Score : 250 points
Problem Statement
The AtCoder Kingdom holds a festival for N days. On M of these days, namely on the A_1-th, A_2-th, \dots, A_M-th days, fireworks will be launched. It is guaranteed that fireworks will be launched on the last day of the festival. (In other words, A_M=N is guaranteed.)
For each i=1,2,\dots,N, solve the following problem.
- How many days later from the i-th day will fireworks be launched for the first time on or after the i-th day? If fireworks are launched on the i-th day, it is considered to be 0 days later.
Constraints
- 1 \le M \le N \le 2 \times 10^5
- 1 \le A_1 < A_2 < \dots < A_M = N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Print N lines.
The i-th line (1 \le i \le N) should contain an integer representing the number of days from the i-th day until fireworks are launched for the first time on or after the i-th day.
Sample Input 1
3 2 2 3
Sample Output 1
1 0 0
The kingdom holds a festival for 3 days, and fireworks are launched on the 2-nd and 3-rd days.
- From the 1-st day, the first time fireworks are launched is the 2-nd day of the festival, which is 1 day later.
- From the 2-nd day, the first time fireworks are launched is the 2-nd day of the festival, which is 0 days later.
- From the 3-rd day, the first time fireworks are launched is the 3-rd day of the festival, which is 0 days later.
Sample Input 2
8 5 1 3 4 7 8
Sample Output 2
0 1 0 0 2 1 0 0
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
6 個の整数 h_1, h_2, h_3, w_1, w_2, w_3 が与えられます。
縦横 3 \times 3 のマス目に、以下の条件をすべて満たすように各マスに正の整数を 1 つずつ書きこむことを考えます。
- i=1,2,3 について、上から i 行目に書きこんだ数の和が h_i になる。
- j=1,2,3 について、左から j 列目に書きこんだ数の和が w_j になる。
例えば (h_1, h_2, h_3) = (5, 13, 10), (w_1, w_2, w_3) = (6, 13, 9) のとき、以下の 3 通りの書きこみ方はすべて条件を満たしています。(条件を満たす書きこみ方は他にもあります)
さて、条件を満たす書きこみ方は全部で何通り存在しますか？
制約
- 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
h_1 h_2 h_3 w_1 w_2 w_3
出力
条件を満たす書きこみ方が何通りあるかを出力せよ。
入力例 1
3 4 6 3 3 7
出力例 1
1
条件を満たす数の書きこみ方は次の 1 通りのみです。よって 1 を出力します。
入力例 2
3 4 5 6 7 8
出力例 2
0
条件を満たす書きこみ方が存在しないこともあります。
入力例 3
5 13 10 6 13 9
出力例 3
120
入力例 4
20 25 30 22 29 24
出力例 4
30613
Score : 300 points
Problem Statement
You are given six integers: h_1, h_2, h_3, w_1, w_2, and w_3.
Consider writing a positive integer on each square of a 3 \times 3 grid so that all of the following conditions are satisfied:
- For i=1,2,3, the sum of numbers written in the i-th row from the top is h_i.
- For j=1,2,3, the sum of numbers written in the j-th column from the left is w_i.
For example, if (h_1, h_2, h_3) = (5, 13, 10) and (w_1, w_2, w_3) = (6, 13, 9), then all of the following three ways satisfy the conditions. (There are other ways to satisfy the conditions.)
How many ways are there to write numbers to satisfy the conditions?
Constraints
- 3 \leq h_1, h_2, h_3, w_1, w_2, w_3 \leq 30
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
h_1 h_2 h_3 w_1 w_2 w_3
Output
Print the number of ways to write numbers to satisfy the conditions.
Sample Input 1
3 4 6 3 3 7
Sample Output 1
1
The following is the only way to satisfy the conditions. Thus, 1 should be printed.
Sample Input 2
3 4 5 6 7 8
Sample Output 2
0
There may not be a way to satisfy the conditions.
Sample Input 3
5 13 10 6 13 9
Sample Output 3
120
Sample Input 4
20 25 30 22 29 24
Sample Output 4
30613
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
頂点に 1 から N の番号が付いた N 頂点の重み付き無向完全グラフが与えられます。頂点 i と頂点 j\ (i< j) を結ぶ辺の重みは D_{i,j} です。
以下の条件を満たすように何本かの辺を選ぶとき、選んだ辺の重みの総和としてあり得る最大値を求めてください。
- 選んだ辺の端点はどの 2 個も相異なる。
制約
- 2\leq N\leq 16
- 1\leq D_{i,j} \leq 10^9
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
D_{1,2} D_{1,3} \ldots D_{1,N}
D_{2,3} \ldots D_{2,N}
\vdots
D_{N-1,N}
出力
答えを整数として出力せよ。
入力例 1
4 1 5 4 7 8 6
出力例 1
13
頂点 1 と頂点 3 を結ぶ辺、頂点 2 と頂点 4 を結ぶ辺を選ぶと、辺の重みの総和が 5+8=13 となります。
これが達成可能な最大値であることが示せます。
入力例 2
3 1 2 3
出力例 2
3
N が奇数の場合もあります。
入力例 3
16 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 8 7 7 9 8 1 9 6 10 8 8 6 10 3 10 5 8 1 10 7 8 4 8 6 5 1 10 7 4 1 4 5 4 5 10 1 5 1 2 2 9 9 7 6 2 2 8 3 5 2 9 10 3 1 1 2 10 7 7 5 10 6 1 8 9 3 2 4 2 10 10 8 9 2 10 7 9 5 8 8 7 5 8 2 4 2 2 6 8 3 2 7 3 10 3 5 7 10 3 8 5 7 9 1 4
出力例 3
75
Score : 400 points
Problem Statement
You are given a weighted undirected complete graph with N vertices numbered from 1 to N. The edge connecting vertices i and j (i< j) has a weight of D_{i,j}.
When choosing some number of edges under the following condition, find the maximum possible total weight of the chosen edges.
- The endpoints of the chosen edges are pairwise distinct.
Constraints
- 2\leq N\leq 16
- 1\leq D_{i,j} \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
D_{1,2} D_{1,3} \ldots D_{1,N}
D_{2,3} \ldots D_{2,N}
\vdots
D_{N-1,N}
Output
Print the answer as an integer.
Sample Input 1
4 1 5 4 7 8 6
Sample Output 1
13
If you choose the edge connecting vertices 1 and 3, and the edge connecting vertices 2 and 4, the total weight of the edges is 5+8=13.
It can be shown that this is the maximum achievable value.
Sample Input 2
3 1 2 3
Sample Output 2
3
N can be odd.
Sample Input 3
16 5 6 5 2 1 7 9 7 2 5 5 2 4 7 6 8 7 7 9 8 1 9 6 10 8 8 6 10 3 10 5 8 1 10 7 8 4 8 6 5 1 10 7 4 1 4 5 4 5 10 1 5 1 2 2 9 9 7 6 2 2 8 3 5 2 9 10 3 1 1 2 10 7 7 5 10 6 1 8 9 3 2 4 2 10 10 8 9 2 10 7 9 5 8 8 7 5 8 2 4 2 2 6 8 3 2 7 3 10 3 5 7 10 3 8 5 7 9 1 4
Sample Output 3
75
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の整数列 A = (A_1, \dots, A_N) と整数 M, K が与えられます。
i = 1, \dots, N - M + 1 に対して、次の独立な問題を解いてください。
M 個の整数 A_i, A_{i + 1}, \dots, A_{i + M - 1} を昇順に並べ替えたときの先頭 K 個の値の総和を求めよ。
制約
- 1 \leq K \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力される値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K A_1 A_2 \ldots A_N
出力
i = k のときの問題の答えを \mathrm{answer}_k として、次の形式で出力せよ。
\mathrm{answer}_1 \mathrm{answer}_2 \ldots \mathrm{answer}_{N-M+1}
入力例 1
6 4 3 3 1 4 1 5 9
出力例 1
5 6 10
- i = 1 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 1, 3, 4 となり、小さい方から 3 個の値の総和は 5 です。
- i = 2 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 1, 4, 5 となり、小さい方から 3 個の値の総和は 6 です。
- i = 3 のとき、A_i, A_{i+1}, A_{i+2}, A_{i+3} を小さい順に並べると 1, 4, 5, 9 となり、小さい方から 3 個の値の総和は 10 です。
入力例 2
10 6 3 12 2 17 11 19 8 4 3 6 20
出力例 2
21 14 15 13 13
Score : 500 points
Problem Statement
You are given an integer sequence A = (A_1, \dots, A_N) of length N, and integers M and K.
For each i = 1, \dots, N - M + 1, solve the following independent problem.
Find the sum of the first K values in the sorted list of the M integers A_i, A_{i + 1}, \dots, A_{i + M - 1} in ascending order.
Constraints
- 1 \leq K \leq M \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K A_1 A_2 \ldots A_N
Output
Let \mathrm{answer}_k be the answer to the problem for i = k, and print them in the following format:
\mathrm{answer}_1 \mathrm{answer}_2 \ldots \mathrm{answer}_{N-M+1}
Sample Input 1
6 4 3 3 1 4 1 5 9
Sample Output 1
5 6 10
- For i = 1, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 3, 4, where the sum of the first three values is 5.
- For i = 2, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 1, 4, 5, where the sum of the first three values is 6.
- For i = 3, sorting A_i, A_{i+1}, A_{i+2}, A_{i+3} in ascending order yields 1, 4, 5, 9, where the sum of the first three values is 10.
Sample Input 2
10 6 3 12 2 17 11 19 8 4 3 6 20
Sample Output 2
21 14 15 13 13
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
2N 人の生徒が一列に並んでおり、左から順に生徒 1 , 生徒 2 , \ldots , 生徒 2N と番号が付いています。 2N 人の生徒はどの 2 人も互いに仲が良いか悪いかのどちらかであり、 具体的には 1\leq i\leq M について生徒 A_i と生徒 B_i の仲が良く、これら以外のどの 2 人も仲が悪いです。
先生は以下の操作を N 回繰り返して、 2 人組のペアを N 組作ることにしました。
- 隣り合う 2 人であって仲が良いような 2 人をペアとして選び、列から抜く。
- 抜けた 2 人が列の端でなかったならば、その後、列を詰める。すなわち、抜けた 2 人の左右にいた 2 人が新しく隣り合う。
このとき、 N 回の操作方法としてあり得るものの数を 998244353 で割った余りを求めてください。 ただし N 回の操作方法が異なるとは、ある 1\leq i\leq N が存在して、 i 回目の操作で 選ばれた 2 人組がペアとして異なることをいいます。
制約
- 1 \leq N \leq 200
- 0 \leq M \leq N(2N-1)
- 1 \leq A_i < B_i \leq 2N
- (A_i, B_i) はすべて異なる。
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
出力
操作方法としてあり得るものの数を 998244353 で割った余りを出力せよ。
入力例 1
2 3 1 2 1 4 2 3
出力例 1
1
1 度目の操作で生徒 2 と生徒 3 を選び、
2 度目の操作で生徒 1 と生徒 4 を選ぶのが
唯一の操作方法です。
1 度目の操作で生徒 1 と生徒 2 を選ぶと、
生徒 3 と生徒 4 が残りますが、この 2 人は仲が悪いため 2 度目の操作でペアにすることができません。
よって、 1 を出力します。
入力例 2
2 2 1 2 3 4
出力例 2
2
1 度目の操作で生徒 1 と生徒 2 を選び、 2 度目の操作で生徒 3 と生徒 4 を選ぶのが 1 通り、 1 度目の操作で生徒 3 と生徒 4 を選び、 2 度目の操作で生徒 1 と生徒 2 を選ぶのが 1 通りであわせて 2 通りあります。 この 2 つが区別されることに注意してください。
入力例 3
2 2 1 3 2 4
出力例 3
0
1 度目の操作で選べるペアが無いため条件をみたす操作方法は無く、 0 を出力します。
Score : 500 points
Problem Statement
There are 2N students standing in a row, numbered 1, 2, \ldots, 2N from left to right. For all pairs of two students, they are on good or bad terms. Specifically, for each 1\leq i\leq M, Student A_i and Student B_i are on good terms; for the remaining pairs of two students, they are on bad terms.
The teacher is going to do the following operation N times to form N pairs of two students.
- Choose two adjacent students who are on good terms, pair them, and remove them from the row.
- If the removed students were not at an end of the row, close up the gap so that the two students who were to the left and right of the removed students are now adjacent.
Find the number, modulo 998244353, of possible ways to do the operation N times. Two ways to do the operation N times are considered different when there exists 1\leq i\leq N such that the pair of students chosen in the i-th operation is different in those two ways.
Constraints
- 1 \leq N \leq 200
- 0 \leq M \leq N(2N-1)
- 1 \leq A_i < B_i \leq 2N
- All pairs (A_i, B_i) are distinct.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 B_1 A_2 B_2 \vdots A_M B_M
Output
Print the number of possible ways to complete the procedure, modulo 998244353.
Sample Input 1
2 3 1 2 1 4 2 3
Sample Output 1
1
The only way to complete the procedure is to choose Students 2 and 3 in the first and Students 1 and 4 in the second.
If Students 1 and 2 are chosen in the first operation, Students 3 and 4 will remain, who are on bad terms and thus cannot be paired in the second operation.
Thus, you should print 1.
Sample Input 2
2 2 1 2 3 4
Sample Output 2
2
There are two ways to complete the procedure: one way is to choose Students 1 and 2 in the first operation and Students 3 and 4 in the second, and the other way is to choose Students 3 and 4 in the first operation and Students 1 and 2 in the second. Note that these two ways are distinguished.
Sample Input 3
2 2 1 3 2 4
Sample Output 3
0
Since no pair can be chosen in the first operation, there is no way to complete the procedure, so you should print 0.