AtCoder Regular Contest 167

A - Toasts for Breakfast Party

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 枚のトーストと M 枚の皿があります。M は \frac{N}{2} 以上 N 以下の整数です。i 枚目のトーストの美味しさは A_{i} です。

この N 枚のトーストを以下の 2 つの条件を満たすように M 枚の皿にのせます。

1 枚の皿にのせることができるトーストは高々 2 枚
どのトーストも必ずどれか 1 つの皿にのっている

j 枚目の皿にのっているトーストの美味しさの総和 (皿に 1 枚もトーストがのっていない場合は 0 ) を B_{j} として、 アンバランス度を \sum_{j=1}^{M} B_{j}^{2} とします。

アンバランス度としてありうる最小の値を求めてください。

制約

1\leq N\leq 2\times 10^{5}
\frac{N}{2}\leq M\leq N
1\leq A_{i}\leq 2\times 10^{5}
入力は全て整数

入力

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

N M
A_{1} A_{2} \cdots A_{N}

出力

答えを出力してください。

入力例 1

5 3
1 1 1 6 7

出力例 1

1,2 枚目のトーストを 1 枚目の皿に、 3,4 枚目のトーストを 2 枚目の皿に、 5 枚目のトーストを 3 枚目の皿にのせると、 (1+1)^{2}+(1+6)^{2}+7^2=102 より、アンバランス度が 102 になります。

アンバランス度が 102 未満になるのせ方は存在しないため、 102 を出力します。

1,2,3 枚目のトーストを全て同じ皿にのせることはできないことに注意してください。

入力例 2

2 1
167 924

出力例 2

入力例 3

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

出力例 3

61968950639

Score : 300 points

Problem Statement

We have N slices of toast and M plates. M is an integer between \frac{N}{2} and N, inclusive. The i-th slice of toast has a deliciousness of A_{i}.

Let us put the N slices of toast on the M plates to satisfy the following two conditions.

Each plate can have at most two slices of toast on it.
Every slice of toast is on some plate.

Let B_{j} be the sum of the deliciousness of the toast on the j-th plate (0 if the plate has no toast on it). Then, let the unbalancedness be \sum_{j=1}^{M} B_{j}^{2}.

Find the minimum possible value of the unbalancedness.

Constraints

1\leq N\leq 2\times 10^{5}
\frac{N}{2}\leq M\leq N
1\leq A_{i}\leq 2\times 10^{5}
All input values are integers.

Input

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

N M
A_{1} A_{2} \cdots A_{N}

Output

Print the answer.

Sample Input 1

5 3
1 1 1 6 7

Sample Output 1

If you put the first and second slices on the first plate, the third and fourth slices on the second plate, and the fifth slice on the third plate, we have (1+1)^{2}+(1+6)^{2}+7^2=102, so the unbalancedness is 102.

There is no way to put them to make the unbalancedness less than 102, so print 102.

Note that you cannot put the first, second, and third slices on the same plate.

Sample Input 2

2 1
167 924

Sample Output 2

Sample Input 3

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

Sample Output 3

61968950639

B - Product of Divisors

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

A^{B} の正の約数の総積は A で最大何回割り切れますか。

制約から割り切れる回数が有限回であることが示せるので、その答えを 998244353 で割ったあまりを求めてください。

制約

2\leq A\leq 10^{12}
0\leq B\leq 10^{18}
入力は全て整数

入力

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

A B

出力

答えを出力してください。

入力例 1

2 3

出力例 1

A^{B}=8 の正の約数は 1,2,4,8 で、その総積は 64 となります。 64 は 2 で 6 回割り切れるので、6 を出力します。

入力例 2

924 167

出力例 2

867046524

入力例 3

167167167167 0

出力例 3

Score : 500 points

Problem Statement

At most how many times can the product of all positive divisors of A^{B} be divided by A?

It can be shown from the constraints that this count is finite, so find it modulo 998244353.

Constraints

2\leq A\leq 10^{12}
0\leq B\leq 10^{18}
All input values are integers.

Input

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

A B

Output

Print the answer.

Sample Input 1

2 3

Sample Output 1

The positive divisors of A^{B}=8 are 1, 2, 4, and 8, whose product is 64. 64 can be divided by 2 at most six times, so print 6.

Sample Input 2

924 167

Sample Output 2

867046524

Sample Input 3

167167167167 0

Sample Output 3

C - MST on Line++

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

正整数 N,K と長さ N の正整数列 A=(A_{1},A_{2},\dots,A_{N}) が与えられます。

(1,2,\dots ,N) の順列 P=(P_{1},P_{2},\dots ,P_{N}) に対して以下の「問題 MST on Line」について考え、その答えを f(P) と書きます。

問題 MST on Line

頂点に 1 から N までの番号がついた頂点数 N の重み付き無向グラフ G があります。G について 1\leq i\lt j\leq N を満たす任意の整数の組 (i,j) に対して以下が成り立ちます。

j-i\leq K ならば頂点 i と頂点 j の間に辺が存在して、その辺の重みは \max(A_{P_{i}},A_{P_{j}})

j-i\gt K ならば頂点 i と頂点 j の間に辺は存在しない

G の最小全域木の辺の重みの和を求めてください。

全ての (1,2,\dots ,N) の順列 P=(P_{1},P_{2},\dots ,P_{N}) に対する f(P) の総和を 998244353 で割ったあまりを求めてください。

制約

1\leq K\lt N\leq 5000
1\leq A_{i}\leq 10^{9}
入力は全て整数

入力

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

N K
A_{1} A_{2} \cdots A_{N}

出力

答えを出力してください。

入力例 1

5 2
3 4 5 2 1

出力例 1

P=(1,2,3,4,5) としたとき、

頂点 1 と 2 の間に存在する、重み 4 の辺、

頂点 2 と 3 の間に存在する、重み 5 の辺、

頂点 2 と 4 の間に存在する、重み 4 の辺、

頂点 4 と 5 の間に存在する、重み 2 の辺、

という 4 つの辺は G の全域木となり、辺の重みの和は 15 です。

これ以上辺の重みの和を少なくするように全域木をとることはできないので、f(P)=15 となります。

以上のように全ての (1,2,3,4,5) の順列 P に対する f(P) の総和を求めると 1740 になるので、これを出力します。

入力例 2

2 1
167 924

出力例 2

入力例 3

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

出力例 3

660459584

Score : 700 points

Problem Statement

You are given positive integers N and K, and a sequence of N positive integers: A=(A_{1},A_{2},\dots,A_{N}).

For a permutation P=(P_{1},P_{2},\dots,P_{N}) of (1,2,\dots,N), consider the following problem "MST on Line," and let f(P) the answer.

Problem: MST on Line

We have a weighted undirected graph G with N vertices numbered 1 to N. For every integer pair (i,j) such that 1\leq i\lt j\leq N, the following holds for G.

If j-i\leq K, there is an edge between vertex i and vertex j, whose weight is \max(A_{P_{i}},A_{P_{j}}).

If j-i\gt K, there is no edge between vertex i and vertex j.

Find the total weight of the edges of a minimum spanning tree of G.

Find the sum, modulo 998244353, of f(P) over all permutations P=(P_{1},P_{2},\dots ,P_{N}) of (1,2,\dots,N).

Constraints

1\leq K\lt N\leq 5000
1\leq A_{i}\leq 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} \cdots A_{N}

Output

Print the answer.

Sample Input 1

5 2
3 4 5 2 1

Sample Output 1

For P=(1,2,3,4,5), the following edges form a spanning tree of G:

the edge between vertices 1 and 2 of weight 4,

the edge between vertices 2 and 3 of weight 5,

the edge between vertices 2 and 4 of weight 4, and

the edge between vertices 4 and 5 of weight 2,

for a total weight of 15.

It is impossible to take a spanning tree with a smaller total edge weight, so f(P)=15.

In this way, it can be seen that the sum of f(P) over all permutations P of (1,2,3,4,5) is 1740, which should be printed.

Sample Input 2

2 1
167 924

Sample Output 2

Sample Input 3

12 9
22847 98332 854 68844 81080 46058 40949 62493 76561 52907 88628 99740

Sample Output 3

660459584

D - Good Permutation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

この問題では順列と言った際には (1,2,\dots ,N) の順列を指すものとします。

順列 P=(P_{1},P_{2},\dots ,P_{N}) が与えられます。

ここで、以下の条件を満たす順列 Q=(Q_{1},Q_{2},\dots ,Q_{N}) を良い順列とします。

任意の整数 1\leq x\leq N について、 x\leftarrow Q_{x} という置換を好きな回数繰り返すことで、 x を 1 にすることができる。

P に対して、以下の操作を 0 回以上行うことで、 P を良い順列にしたいです。

1\leq i\lt j \leq N を満たす整数 i,j を選んで、 P_{i} と P_{j} を入れ替える

P を良い順列にするのに必要な最小の操作回数を M としたとき、 P に対し操作を M 回行うことで得られる良い順列のうち、辞書式順序で最小のものを求めてください。

1 つの入力ファイルにつき T 個のテストケースが与えられるので、それぞれについて解いてください。

数列の辞書順とは？

数列 S = (S_1,S_2,\ldots,S_{|S|}) が数列 T = (T_1,T_2,\ldots,T_{|T|}) より辞書順で小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。ここで、|S|, |T| はそれぞれ S, T の長さを表します。

|S| \lt |T| かつ (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|})。
ある整数 1 \leq i \leq \min\lbrace |S|, |T| \rbrace が存在して、下記の 2 つがともに成り立つ。
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1})
- S_i が T_i より（数として）小さい。

制約

1\leq T\leq 10^{5}
2\leq N\leq 2\times 10^{5}
(P_{1},P_{2},\dots ,P_{N}) は (1,2,\dots ,N) の順列
1 つの入力ファイルにつき、 N の総和は 2\times 10^{5} を超えない
入力は全て整数

入力

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

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

各ケースは以下の形式で与えられます。

N
P_{1} P_{2} \cdots P_{N}

出力

T 行出力してください。 i 行目には \text{case}_{i} に対する答えの良い順列を空白区切りで出力してください。

入力例 1

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

出力例 1

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

1 つ目のテストケースについて

P は良い順列ではありません。P_{1} と P_{3} を入れ替えると P=(4,1,2,3) となりますがこのとき P は良い順列となるので、 M=1 です。他にも P_{2} と P_{4} を入れ替えると P=(2,3,4,1) となりますが、これは M=1 回の操作で得られる良い順列のうち辞書順で最も小さいものになるため、これが答えです。

Score : 700 points

Problem Statement

In this problem, when we say just a "permutation", it refers to a permutation of (1,2,\dots,N).

You are given a permutation P=(P_{1},P_{2},\dots,P_{N}).

A permutation Q=(Q_{1},Q_{2},\dots,Q_{N}) is said to be a good permutation when the following holds.

For every integer 1\leq x\leq N, it is possible to make x equal 1 by repeating the substitution x\leftarrow Q_{x} some number of times.

You want to make P a good permutation by performing the following operation on P zero or more times.

Choose integers i and j such that 1\leq i\lt j \leq N, and swap P_{i} and P_{j}.

Let M be the minimum number of times you must perform the operation to make P a good permutation. Find the lexicographically smallest good permutation that can be obtained by performing the operation M times on P.

For each input file, you have T test cases to solve.

What is lexicographical order on sequences?

A sequence S = (S_1,S_2,\ldots,S_{|S|}) is said to be lexicographically smaller than a sequence T = (T_1,T_2,\ldots,T_{|T|}) when one of the following 1. or 2. holds. Here, |S| and |T| denote the lengths of S and T, respectively.

|S| \lt |T| and (S_1,S_2,\ldots,S_{|S|}) = (T_1,T_2,\ldots,T_{|S|}).
There is an integer 1 \leq i \leq \min\lbrace |S|, |T| \rbrace that satisfies both of the following.
- (S_1,S_2,\ldots,S_{i-1}) = (T_1,T_2,\ldots,T_{i-1}).
- S_i is smaller than T_i (as a number).

Constraints

1\leq T\leq 10^{5}
2\leq N\leq 2\times 10^{5}
(P_{1},P_{2},\dots ,P_{N}) is a permutation of (1,2,\dots ,N).
For each input file, the sum of N does not exceed 2\times 10^{5}.
All input values are integers.

Input

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

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

Each case is given in the following format:

N
P_{1} P_{2} \cdots P_{N}

Output

Print T lines. The i-th line should contain the permutation that is the answer for \text{case}_{i}, separated by spaces.

Sample Input 1

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

Sample Output 1

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

For the first test case:

P is not a good permutation. Swapping P_{1} and P_{3} makes P=(4,1,2,3), which is a good permutation, so M=1. Other than that, swapping P_{2} and P_{4} makes P=(2,3,4,1), which is the lexicographically smallest good permutation that can be obtained in M=1 operation, so this is the answer.

E - One Square in a Triangle

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

以下の条件を全て満たす xy 平面上の三角形 ABC を良い三角形とします。

頂点 A,B,C はいずれも、x 座標 \cdot y 座標がどちらも 0 以上 10^{8} 以下の格子点である。
全ての頂点が格子点である面積 1 の正方形のうち、三角形 ABC の内部 (周上及び頂点を含む) に全体が含まれているものはちょうど 1 つ

正の整数 S が与えられます。

良い三角形のうち面積が \frac{S}{2} であるものが存在するか判定し、存在するなら 1 つ構築してください。

1 つの入力ファイルにつき T 個のテストケースが与えられるので、それぞれについて解いてください。

制約

1\leq T\leq 10^{5}
1\leq S\leq 10^{8}
入力は全て整数

入力

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

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

各ケースは以下の形式で与えられます。

出力

各ケースに対し、面積 \frac{S}{2} の良い三角形が存在しない場合は No と、存在する場合は以下の形式で答えを出力してください。

Yes
AX AY BX BY CX CY

ただし、 AX,BX,CX を A,B,C の x 座標、 AY,BY,CY を A,B,C の y 座標とします。

Yes, No を出力する際、各文字は英大文字・小文字のいずれでも良いです。解が複数存在する場合はどれを出力しても正解とみなされます。

入力例 1

出力例 1

No
Yes
1 1 1 3 3 3
Yes
5 1 7 8 4 5

図の左側の三角形は 2 番目のテストケース、右側の三角形は 3 番目のテストケースに対応しています。

Score : 800 points

Problem Statement

A triangle ABC on the xy-plane is said to be a good triangle when it satisfies all of the following conditions.

Each of the vertices A, B, and C is a lattice point whose x- and y-coordinates are between 0 and 10^{8}, inclusive.
The triangle ABC (including the perimeter and vertices) wholly contains exactly one square of area 1 whose vertices are all lattice points.

You are given a positive integer S.

Determine if there is a good triangle of area \frac{S}{2}, and construct one if it exists.

For each input file, you have T test cases to solve.

Constraints

1\leq T\leq 10^{5}
1\leq S\leq 10^{8}
All input values are integers.

Input

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

T
\text{case}_{1}
\text{case}_{2}
\vdots
\text{case}_{T}

Each case is given in the following format:

Output

For each case, print No if there is no good triangle of area \frac{S}{2}, and such a triangle in the following format if there is one.

Yes
AX AY BX BY CX CY

Here, AX, BX, CX are the x-coordinates of A, B, C, and AY, BY, CY are the y-coordinates of A, B, C, respectively.

When printing Yes or No, you may use either uppercase or lowercase English letters. If multiple solutions exist, any of them will be accepted.

Sample Input 1

Sample Output 1

No
Yes
1 1 1 3 3 3
Yes
5 1 7 8 4 5

In the figure, the left and right triangles correspond to the second and third test cases, respectively.

F - Tree Tree Tree

Time Limit: 5 sec / Memory Limit: 1024 MB

配点 : 1200 点

問題文

2\leq K\leq N を満たす整数 N,K が与えられます。

問題 potato

1 から N までの番号がついた頂点数 N の重み付き根付き木があります。頂点 1 が根です。

2\leq i\leq N に対して、頂点 i の親は p_{i}\;(1\leq p_{i}<i)で、 i と p_{i} を結ぶ辺の重みは q_{i-1} です。

ただし、q=(q_{1},q_{2},\dots,q_{N-1}) は (1,2,\dots,N-1) の順列です。

ここで cost(u,v) を頂点 u,v を結ぶ単純パスに含まれる辺の重みの最大値とします。

\sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v) を求めてください。

問題 tomato

1\leq a\lt K を満たす整数 a が与えられます。「問題 potato」の p,q として p_{K}=a を満たすものは \frac{((N-1)!)^{2}}{K-1} 通り考えられますが、その全てに対する「問題 potato」の答えの和を 998244353 で割ったあまりを求めてください。

a=1,\dots,K-1 について、「問題 tomato」の答えを求めてください。

制約

2\leq K\leq N\leq 10^{5}
入力は全て整数

入力

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

N K

出力

K-1 行出力してください。i 行目には a=i としたときの「問題 tomato」の答えを出力してください。

入力例 1

4 4

出力例 1

170
170
172

入力例 2

3 2

出力例 2

入力例 3

16 7

出力例 3

Score : 1200 points

Problem Statement

You are given integers N and K such that 2\leq K\leq N.

Problem: potato

We have a weighted rooted tree with N vertices numbered 1 to N. Vertex 1 is the root.

For each 2\leq i\leq N, the parent of vertex i is p_{i}\;(1\leq p_{i}<i), and the edge connecting i and p_{i} has a weight of q_{i-1}.

Here, q=(q_{1},q_{2},\dots,q_{N-1}) is a permutation of (1,2,\dots,N-1).

Let cost(u,v) be the maximum weight of an edge in the simple path connecting vertices u and v.

Find \sum_{u=1}^{N} \sum_{v=u+1}^{N} cost(u,v).

Problem: tomato

You are given an integer a such that 1\leq a\lt K. There are \frac{((N-1)!)^{2}}{K-1} possible pairs of p and q in the problem "potato" such that p_{K}=a. Find the sum, modulo 998244353, of the answers to the problem over all those pairs.

For each a=1,\dots,K-1, find the answer to the problem "tomato".

Constraints

2\leq K\leq N\leq 10^{5}
All input values are integers.

Input

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

N K

Output

Print K-1 lines. The i-th line should contain the answer to the problem "tomato" for a=i.

Sample Input 1

4 4

Sample Output 1

170
170
172

Sample Input 2

3 2

Sample Output 2

Sample Input 3

16 7

Sample Output 3