A - Remove One Character

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

長さ N の文字列 S が与えられます。 1\leq i\leq N に対して、S からその i 文字目を削除してできる文字列を S_i と表します。

整数の組 (i,j) であって、次の条件をともに満たすものの個数を求めてください。

  • 1\leq i < j\leq N
  • S_i = S_j

制約

  • 2\leq N\leq 3\times 10^5
  • S は英小文字からなる長さ N の文字列である

入力

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

N
S

出力

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

入力例 1

7
abbbcca

出力例 1

4

S_i は、順に以下の文字列となります：bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc

条件を満たす (i,j) は以下の 4 個です。

  • (i,j) = (2,3)
  • (i,j) = (2,4)
  • (i,j) = (3,4)
  • (i,j) = (5,6)

入力例 2

4
xxxx

出力例 2

6

入力例 3

2
pp

出力例 3

1

入力例 4

2
st

出力例 4

0

Score : 300 points

Problem Statement

You are given a string S of length N. For each 1\leq i\leq N, let S_i denote the string obtained by deleting the i-th character from S.

Find the number of pairs of integers (i,j) that satisfy both of the conditions below.

  • 1\leq i < j\leq N
  • S_i = S_j

Constraints

  • 2\leq N\leq 3\times 10^5
  • S is a string of length N consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the answer.

Sample Input 1

7
abbbcca

Sample Output 1

4

Here are the strings S_i in order: bbbcca, abbcca, abbcca, abbcca, abbbca, abbbca, abbbcc.

The following 4 pairs (i,j) satisfy the conditions.

  • (i,j) = (2,3)
  • (i,j) = (2,4)
  • (i,j) = (3,4)
  • (i,j) = (5,6)

Sample Input 2

4
xxxx

Sample Output 2

6

Sample Input 3

2
pp

Sample Output 3

1

Sample Input 4

2
st

Sample Output 4

0
B - Colorful Lines

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

H\times W のマス目があります。はじめ、どのマスにも色は塗られていません。

あなたはこのマス目に対して、色を塗っていくことにしました。使うことができる色には、1, 2, \ldots, C の番号で表される C 種類があります。

色を塗る工程が、Q 個のクエリとして与えられます。i 番目のクエリでは整数 t_i, n_i, c_i が与えられ、以下のように色を塗ることを表しています。

  • t_i = 1 のとき：n_i 行目のマスをすべて色 c_i で塗る。
  • t_i = 2 のとき：n_i 列目のマスをすべて色 c_i で塗る。

あるマスを色 c で塗ると、そのマスの色は直前の状態によらず常に色 c へ変化します。

色を塗る工程がすべて完了したときに色 1, 2, \ldots, C で塗られているマスの個数を求めてください。

制約

  • 2\leq H\leq 10^9
  • 2\leq W\leq 10^9
  • 1\leq C\leq 3\times 10^5
  • 1\leq Q\leq 3\times 10^5
  • t_i\in \{1,2\}
  • t_i = 1 ならば 1\leq n_i\leq H
  • t_i = 2 ならば 1\leq n_i\leq W
  • 1\leq c_i\leq C

入力

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

H W C Q
t_1 n_1 c_1
\vdots
t_Q n_Q c_Q

出力

色 1, 2, \ldots, C で塗られているマスの個数を、空白で区切って 1 行で出力してください。

入力例 1

4 5 6 5
1 1 6
1 3 3
2 2 4
2 4 2
1 1 2

出力例 1

0 8 3 3 0 0

色を塗る工程において、マス目の色は次のように変化します。ただし、. はそのマスがどの色でも塗られていないことを意味します。

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

入力例 2

1000000000 1000000000 3 5
1 1 2
1 2 2
1 3 2
1 4 2
1 5 2

出力例 2

0 5000000000 0

Score : 400 points

Problem Statement

We have an H\times W grid. Initially, the squares are unpainted.

You will paint these squares. There are C colors available, numbered 1, 2, \ldots, C.

The painting process will be given as Q queries. The i-th query contains integers t_i, n_i, c_i, which represents the following action.

  • If t_i = 1: paint all squares in the n_i-th row with Color c_i.
  • If t_i = 2: paint all squares in the n_i-th column with Color c_i.

Painting a square with Color c makes the color of that square Color c, regardless of its previous state.

Find the number of squares painted in each of Color 1, 2, \ldots, C after the whole process.

Constraints

  • 2\leq H\leq 10^9
  • 2\leq W\leq 10^9
  • 1\leq C\leq 3\times 10^5
  • 1\leq Q\leq 3\times 10^5
  • t_i\in \{1,2\}
  • 1\leq n_i\leq H if t_i = 1
  • 1\leq n_i\leq W if t_i = 2
  • 1\leq c_i\leq C

Input

Input is given from Standard Input in the following format:

H W C Q
t_1 n_1 c_1
\vdots
t_Q n_Q c_Q

Output

Print a line containing the numbers of squares painted in Color 1, 2, \ldots, C, with spaces in between.

Sample Input 1

4 5 6 5
1 1 6
1 3 3
2 2 4
2 4 2
1 1 2

Sample Output 1

0 8 3 3 0 0

The process changes the colors of the squares as follows. Here, . denotes an unpainted square.

.....   66666   66666   64666   64626   22222
.....   .....   .....   .4...   .4.2.   .4.2.
.....   .....   33333   34333   34323   34323
.....   .....   .....   .4...   .4.2.   .4.2.

Sample Input 2

1000000000 1000000000 3 5
1 1 2
1 2 2
1 3 2
1 4 2
1 5 2

Sample Output 2

0 5000000000 0
C - Digit Sum Minimization

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

正の整数 a, b が与えられます。ただし、a, b のどの桁も 0 ではありません。

a+b の各桁の和が最小になるように、a, b のそれぞれの桁を並べ替えてください。

制約

  • 1\leq a, b< 10^{100000}
  • a, b のどの桁も 0 ではない

入力

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

a
b

出力

a+b の各桁の和が最小になるように a, b のそれぞれの桁を並べ替えて、1 行目に a を、2 行目に b を出力してください。

答が複数考えられる場合には、そのどれを出力しても正解となります。

入力例 1

253
286

出力例 1

532
268

532 + 268 = 800 で、その各桁の和は 8+0+0=8 となります。

他にも、(a, b) = (325, 682) を出力しても正解となります。

入力例 2

345
556

出力例 2

435
565

435+565=1000 で、その各桁の和は 1+0+0+0=1 となります。

入力例 3

123
987987

出力例 3

312
799788

312 + 799788 = 800100 で、その各桁の和は 8+0+0+1+0+0=9 となります。

入力例 4

11111111111111111111
111111111111111111111111111111

出力例 4

11111111111111111111
111111111111111111111111111111

Score : 500 points

Problem Statement

Given are positive integers a, b, where none of the digits is 0.

Permute the digits of each of a and b so that the sum of the digits in a+b is minimized.

Constraints

  • 1\leq a, b< 10^{100000}
  • None of the digits of a and b is 0.

Input

Input is given from Standard Input in the following format:

a
b

Output

After permuting the digits of each of a and b so that the sum of the digits in a+b is minimized, print a in the first line and b in the second line.

If multiple solutions exist, printing any of them will be accepted.

Sample Input 1

253
286

Sample Output 1

532
268

We have 532 + 268 = 800, whole digits sum to 8+0+0=8.

Other solutions will also be accepted, such as (a, b) = (325, 682).

Sample Input 2

345
556

Sample Output 2

435
565

We have 435+565=1000, whole digits sum to 1+0+0+0=1.

Sample Input 3

123
987987

Sample Output 3

312
799788

We have 312 + 799788 = 800100, whole digits sum to 8+0+0+1+0+0=9.

Sample Input 4

11111111111111111111
111111111111111111111111111111

Sample Output 4

11111111111111111111
111111111111111111111111111111
D - Zigzag Tree

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 600 点

問題文

N 頂点からなる木が与えられます。頂点には 1 から N までの番号がついており、i 番目の辺は頂点 a_i と b_i を結んでいます。

正整数列 P = (P_1, P_2, \ldots, P_N) であって、以下の条件を満たすものの個数を 998244353 で割った余りを求めてください。

  • 1\leq P_i\leq N
  • i\neq j ならば P_i\neq P_j
  • 1\leq a, b, c\leq N に対して頂点 a と 頂点 b、頂点 b と頂点 c がともに隣接しているならば、P_a < P_b > P_c または P_a > P_b < P_c が成り立つ。

制約

  • 2\leq N\leq 3000
  • 1\leq a_i, b_i\leq N
  • 入力されるグラフは木である

入力

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

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

出力

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

入力例 1

3
1 2
2 3

出力例 1

4

条件を満たす P は以下の 4 通りです。

  • P = (1, 3, 2)
  • P = (2, 1, 3)
  • P = (2, 3, 1)
  • P = (3, 1, 2)

入力例 2

4
1 2
1 3
1 4

出力例 2

12

入力例 3

6
1 2
2 3
3 4
4 5
5 6

出力例 3

122

入力例 4

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

出力例 4

19080

Score : 600 points

Problem Statement

Given is a tree with N vertices. The vertices are numbered 1 to N, and the i-th edge connects Vertices a_i and b_i.

Find the number of sequences of positive integers P = (P_1, P_2, \ldots, P_N) that satisfy the conditions below, modulo 998244353.

  • 1\leq P_i\leq N
  • P_i\neq P_j if i\neq j.
  • For 1\leq a, b, c\leq N, if Vertices a and b are adjacent, and Vertices b and c are also adjacent, P_a < P_b > P_c or P_a > P_b < P_c holds.

Constraints

  • 2\leq N\leq 3000
  • 1\leq a_i, b_i\leq N
  • The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
a_2 b_2
\vdots
a_{N-1} b_{N-1}

Output

Print the answers.

Sample Input 1

3
1 2
2 3

Sample Output 1

4

The 4 sequences satisfying the conditions are:

  • P = (1, 3, 2)
  • P = (2, 1, 3)
  • P = (2, 3, 1)
  • P = (3, 1, 2)

Sample Input 2

4
1 2
1 3
1 4

Sample Output 2

12

Sample Input 3

6
1 2
2 3
3 4
4 5
5 6

Sample Output 3

122

Sample Input 4

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

Sample Output 4

19080
E - Increasing Minimum

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 800 点

問題文

N 項からなる正整数列 A = (A_1, A_2, \ldots, A_N) に対して、次の操作を行い、数列 I = (i_1, i_2, \ldots, i_K) を得ることを考えます。

  • k = 1, 2, \ldots, K の順に、次を行う。
    • A_i = \min\{A_1, A_2, \ldots, A_N\} となる i をひとつ選ぶ。
    • i_k = i と定める。
    • A_i に 1 を加える。

整数 N, K と数列 I が与えられます。

操作の結果として I を得ることが可能であるような正整数列 A が存在するかを判定してください。存在する場合には、そのようなもののうち辞書順最小のものを答えてください。

制約

  • 1\leq N, K\leq 3\times 10^5
  • 1\leq i_k\leq N

入力

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

N K
i_1 i_2 \ldots i_K

出力

操作の結果として I を得ることが可能であるような正整数列 A が存在しない場合、-1 と出力してください。 存在する場合、そのような正整数列 A のうち、辞書順最小のものを、空白で区切って 1 行で出力してください。

入力例 1

4 6
1 1 4 4 2 1

出力例 1

1 3 3 2

操作の結果として I = (1,1,4,4,2,1) を得ることが可能な正整数列 A としては、(1, 3, 3, 2), (2, 4, 5, 3) などがあります。そのうち辞書順最小のものは (1, 3, 3, 2) です。

入力例 2

4 6
2 2 2 2 2 2

出力例 2

6 1 6 6

入力例 3

4 6
1 1 2 2 3 3

出力例 3

-1

Score : 800 points

Problem Statement

Consider doing the operation below on a sequence of N positive integers A = (A_1, A_2, \ldots, A_N) to obtain a sequence I = (i_1, i_2, \ldots, i_K).

  • For each k = 1, 2, \ldots, K in this order, do the following.
    • Choose an i such that A_i = \min\{A_1, A_2, \ldots, A_N\}.
    • Let i_k = i.
    • Add 1 to A_i.

You are given integers N, K, and a sequence I.

Determine whether there exists a sequence of positive integers A for which it is possible to obtain I from the operation. If it exists, find the lexicographically smallest such sequence.

Constraints

  • 1\leq N, K\leq 3\times 10^5
  • 1\leq i_k\leq N

Input

Input is given from Standard Input in the following format:

N K
i_1 i_2 \ldots i_K

Output

If there is no sequence of positive integers A for which it is possible to obtain I from the operation, print -1. If it exists, print the lexicographically smallest among such sequences A, in one line, with spaces in between.

Sample Input 1

4 6
1 1 4 4 2 1

Sample Output 1

1 3 3 2

Some of the sequences for which it is possible to obtain I = (1,1,4,4,2,1) from the operation are (1, 3, 3, 2) and (2, 4, 5, 3). The lexicographically smallest among them is (1, 3, 3, 2).

Sample Input 2

4 6
2 2 2 2 2 2

Sample Output 2

6 1 6 6

Sample Input 3

4 6
1 1 2 2 3 3

Sample Output 3

-1
F - Replace by Average

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 1000 点

問題文

N 項からなる正整数列 A = (A_1, A_2, \ldots, A_N) が与えられます。

あなたはこの数列に対して、次の操作を何度でも行うことができます。

  • 1\leq i < j < k \leq N かつ j = \frac{i+k}{2} となる整数 i, j, k を選ぶ。A_j を \lfloor\frac{A_i+A_k}{2}\rfloor に置き換える。

操作後の \sum_{i=1}^N A_i としてありうる最小値を求めてください。

制約

  • 3\leq N\leq 3\times 10^5
  • 1\leq A_i\leq 10^{12}

入力

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

N
A_1 A_2 \ldots A_N

出力

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

入力例 1

5
2 2 5 5 4

出力例 1

13

次のように操作を行うことで、\sum_{i=1}^N A_i = 13 を実現できます。

  • (i,j,k) = (1,3,5) として操作を行う。数列 A は (2,2,3,5,4) へと変化する。
  • (i,j,k) = (3,4,5) として操作を行う。数列 A は (2,2,3,3,4) へと変化する。
  • (i,j,k) = (2,3,4) として操作を行う。数列 A は (2,2,2,3,4) へと変化する。

入力例 2

5
3 1 4 1 5

出力例 2

11

入力例 3

3
3 1 3

出力例 3

7

入力例 4

3
3 5 3

出力例 4

9

Score : 1000 points

Problem Statement

Given is a sequence of N positive integers A = (A_1, A_2, \ldots, A_N).

You can do the following operation on this sequence any number of times.

  • Choose integers i, j, k such that 1\leq i < j < k \leq N and j = \frac{i+k}{2}. Replace A_j with \lfloor\frac{A_i+A_k}{2}\rfloor.

Find the minimum possible value of \sum_{i=1}^N A_i after the operations.

Constraints

  • 3\leq N\leq 3\times 10^5
  • 1\leq A_i\leq 10^{12}

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

5
2 2 5 5 4

Sample Output 1

13

The following operations achieves \sum_{i=1}^N A_i = 13.

  • Do the operation with (i,j,k) = (1,3,5). The sequence A is now (2,2,3,5,4).
  • Do the operation with (i,j,k) = (3,4,5). The sequence A is now (2,2,3,3,4).
  • Do the operation with (i,j,k) = (2,3,4). The sequence A is now (2,2,2,3,4).

Sample Input 2

5
3 1 4 1 5

Sample Output 2

11

Sample Input 3

3
3 1 3

Sample Output 3

7

Sample Input 4

3
3 5 3

Sample Output 4

9