C - Align

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

整数が N 個与えられます。i 個目の整数は A_i です。 これらを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を求めてください。

制約

  • 2 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • 入力はすべて整数である

入力

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

N
A_1
:
A_N

出力

与えられた整数たちを好きな順に一列に並べるとき、隣り合う要素の差の合計の最大値を出力せよ。

入力例 1

5
6
8
1
2
3

出力例 1

21

3,8,1,6,2 の順に並べたとき、隣り合う要素の差の合計は 21 になり、 これが達成できる最大の値です。

入力例 2

6
3
1
4
1
5
9

出力例 2

25

入力例 3

3
5
5
1

出力例 3

8

Score : 400 points

Problem Statement

You are given N integers; the i-th of them is A_i. Find the maximum possible sum of the absolute differences between the adjacent elements after arranging these integers in a row in any order you like.

Constraints

  • 2 \leq N \leq 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_N

Output

Print the maximum possible sum of the absolute differences between the adjacent elements after arranging the given integers in a row in any order you like.

Sample Input 1

5
6
8
1
2
3

Sample Output 1

21

When the integers are arranged as 3,8,1,6,2, the sum of the absolute differences between the adjacent elements is |3 - 8| + |8 - 1| + |1 - 6| + |6 - 2| = 21. This is the maximum possible sum.

Sample Input 2

6
3
1
4
1
5
9

Sample Output 2

25

Sample Input 3

3
5
5
1

Sample Output 3

8
D - Crossing

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

整数 N が与えられます。\{1,2,...N\} の部分集合の組 (S_1,S_2,...,S_k) であって、以下の条件を満たすものが存在するか判定し、 存在する場合はひとつ構成してください。

  • 1,2,...,N のうちどの整数も、S_1,S_2,...,S_k のうちちょうど 2 つに含まれる
  • S_1,S_2,...,S_k のうちどの 2 つの集合をとっても、それらに共通して含まれる要素はちょうど 1 つである

制約

  • 1 \leq N \leq 10^5
  • N は整数である

入力

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

N

出力

条件を満たす部分集合の組が存在しない場合、No を出力せよ。 存在する場合、まず Yes を出力し、次いで以下の形式で部分集合の情報を出力せよ。 ただし、S_i=\{S_{i,1},S_{i,2},...,S_{i,|S_i|}\} とする。

条件を満たすものが複数ある場合、どれを出力しても構わない。

k
|S_1| S_{1,1} S_{1,2} ... S_{1,|S_1|}
:
|S_k| S_{k,1} S_{k,2} ... S_{k,|S_k|}

入力例 1

3

出力例 1

Yes
3
2 1 2
2 3 1
2 2 3

(S_1,S_2,S_3)=(\{1,2\},\{3,1\},\{2,3\}) とすれば、条件を満たすことが確認できます。

入力例 2

4

出力例 2

No

Score : 500 points

Problem Statement

You are given an integer N. Determine if there exists a tuple of subsets of \{1,2,...N\}, (S_1,S_2,...,S_k), that satisfies the following conditions:

  • Each of the integers 1,2,...,N is contained in exactly two of the sets S_1,S_2,...,S_k.
  • Any two of the sets S_1,S_2,...,S_k have exactly one element in common.

If such a tuple exists, construct one such tuple.

Constraints

  • 1 \leq N \leq 10^5
  • N is an integer.

Input

Input is given from Standard Input in the following format:

N

Output

If a tuple of subsets of \{1,2,...N\} that satisfies the conditions does not exist, print No. If such a tuple exists, print Yes first, then print such subsets in the following format:

k
|S_1| S_{1,1} S_{1,2} ... S_{1,|S_1|}
:
|S_k| S_{k,1} S_{k,2} ... S_{k,|S_k|}

where S_i={S_{i,1},S_{i,2},...,S_{i,|S_i|}}.

If there are multiple such tuples, any of them will be accepted.

Sample Input 1

3

Sample Output 1

Yes
3
2 1 2
2 3 1
2 2 3

It can be seen that (S_1,S_2,S_3)=(\{1,2\},\{3,1\},\{2,3\}) satisfies the conditions.

Sample Input 2

4

Sample Output 2

No
E - Equilateral

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

xy 平面上にコインがいくつかあります。 コインの配置は H 行 W 列のグリッドを用いて表され、グリッドの i 行 j 列目の文字 s_{ij} が # のとき座標 (i,j) にコインがひとつあることを、 . のとき座標 (i,j) にコインがないことを表します。 その他に xy 平面上にコインは存在しません。

相異なるコインの 3 つ組であって、以下の条件を満たすものの個数を求めてください。

  • 3 つのうちどの 2 つのコインをとっても、それらの存在する座標の間のマンハッタン距離が一定である

ただし、座標 (x,y),(x',y') の間のマンハッタン距離は、|x-x'|+|y-y'| で表されます。 また、コインの順番を入れ替えただけの組は同じものとみなします。

制約

  • 1 \leq H,W \leq 300
  • s_{ij} は # または . である

入力

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

H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}

出力

条件を満たす組の個数を出力せよ。

入力例 1

5 4
#.##
.##.
#...
..##
...#

出力例 1

3

((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)),((1,3),(3,1),(4,4)) が条件を満たします。

入力例 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

出力例 2

870

Score : 700 points

Problem Statement

There are some coins in the xy-plane. The positions of the coins are represented by a grid of characters with H rows and W columns. If the character at the i-th row and j-th column, s_{ij}, is #, there is one coin at point (i,j); if that character is ., there is no coin at point (i,j). There are no other coins in the xy-plane.

There is no coin at point (x,y) where 1\leq i\leq H,1\leq j\leq W does not hold. There is also no coin at point (x,y) where x or y (or both) is not an integer. Additionally, two or more coins never exist at the same point.

Find the number of triples of different coins that satisfy the following condition:

  • Choosing any two of the three coins would result in the same Manhattan distance between the points where they exist.

Here, the Manhattan distance between points (x,y) and (x',y') is |x-x'|+|y-y'|. Two triples are considered the same if the only difference between them is the order of the coins.

Constraints

  • 1 \leq H,W \leq 300
  • s_{ij} is # or ..

Input

Input is given from Standard Input in the following format:

H W
s_{11}...s_{1W}
:
s_{H1}...s_{HW}

Output

Print the number of triples that satisfy the condition.

Sample Input 1

5 4
#.##
.##.
#...
..##
...#

Sample Output 1

3

((1,1),(1,3),(2,2)),((1,1),(2,2),(3,1)) and ((1,3),(3,1),(4,4)) satisfy the condition.

Sample Input 2

13 27
......#.........#.......#..
#############...#.....###..
..............#####...##...
...#######......#...#######
...#.....#.....###...#...#.
...#######....#.#.#.#.###.#
..............#.#.#...#.#..
#############.#.#.#...###..
#...........#...#...#######
#..#######..#...#...#.....#
#..#.....#..#...#...#.###.#
#..#######..#...#...#.#.#.#
#..........##...#...#.#####

Sample Output 2

870
F - Circular

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 900 点

問題文

整数 N 個からなる列 A_1,A_2,...,A_N が与えられます。

1,2,...,N の並び替え p_1,p_2,...,p_N であって、 次の操作を何度か行うことでこの列を A_1,A_2,...,A_N に変換できるようなものの個数を 998244353 で割ったあまりを求めてください。

  • 各 1\leq i\leq N に対し、q_i=min(p_{i-1},p_{i}) とする。ただし、p_0=p_N とする。列 p を列 q で置き換える。

制約

  • 1 \leq N \leq 3 × 10^5
  • 1 \leq A_i \leq N
  • 入力はすべて整数である

入力

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

N
A_1
:
A_N

出力

条件を満たす列の個数を 998244353 で割ったあまりを出力せよ。

入力例 1

3
1
2
1

出力例 1

2

(2,3,1),(3,2,1) が条件を満たします。

入力例 2

5
3
1
4
1
5

出力例 2

0

入力例 3

8
4
4
4
1
1
1
2
2

出力例 3

24

入力例 4

6
1
1
6
2
2
2

出力例 4

0

Score : 900 points

Problem Statement

You are given a sequence of N integers: A_1,A_2,...,A_N.

Find the number of permutations p_1,p_2,...,p_N of 1,2,...,N that can be changed to A_1,A_2,...,A_N by performing the following operation some number of times (possibly zero), modulo 998244353:

  • For each 1\leq i\leq N, let q_i=min(p_{i-1},p_{i}), where p_0=p_N. Replace the sequence p with the sequence q.

Constraints

  • 1 \leq N \leq 3 × 10^5
  • 1 \leq A_i \leq N
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1
:
A_N

Output

Print the number of the sequences that satisfy the condition, modulo 998244353.

Sample Input 1

3
1
2
1

Sample Output 1

2

(2,3,1) and (3,2,1) satisfy the condition.

Sample Input 2

5
3
1
4
1
5

Sample Output 2

0

Sample Input 3

8
4
4
4
1
1
1
2
2

Sample Output 3

24

Sample Input 4

6
1
1
6
2
2
2

Sample Output 4

0