Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
すぬけ君は、長さ N の整数列 A を持っています。
すぬけ君は、整数 b を自由に選びます。 この時、A_i と b+i が離れているとすぬけ君は悲しいです。 より具体的には、すぬけ君の悲しさの値は、次の式で計算されます。 なおここで、abs(x) は x の絶対値を返す関数です。
- abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))
すぬけ君の悲しさの値の最小値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
すぬけ君の悲しさの値の最小値を出力せよ。
入力例 1
5 2 2 3 5 5
出力例 1
2
b=0 とすれば、すぬけ君の悲しさの値は、abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2 となります。 b をどのように選んでも、すぬけ君の悲しさの値を 2 未満にすることは出来ないので、答えは 2 になります。
入力例 2
9 1 2 3 4 5 6 7 8 9
出力例 2
0
入力例 3
6 6 5 4 3 2 1
出力例 3
18
入力例 4
7 1 1 1 1 2 3 4
出力例 4
6
Score : 300 points
Problem Statement
Snuke has an integer sequence A of length N.
He will freely choose an integer b. Here, he will get sad if A_i and b+i are far from each other. More specifically, the sadness of Snuke is calculated as follows:
- abs(A_1 - (b+1)) + abs(A_2 - (b+2)) + ... + abs(A_N - (b+N))
Here, abs(x) is a function that returns the absolute value of x.
Find the minimum possible sadness of Snuke.
Constraints
- 1 \leq N \leq 2 \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 ... A_N
Output
Print the minimum possible sadness of Snuke.
Sample Input 1
5 2 2 3 5 5
Sample Output 1
2
If we choose b=0, the sadness of Snuke would be abs(2-(0+1))+abs(2-(0+2))+abs(3-(0+3))+abs(5-(0+4))+abs(5-(0+5))=2. Any choice of b does not make the sadness of Snuke less than 2, so the answer is 2.
Sample Input 2
9 1 2 3 4 5 6 7 8 9
Sample Output 2
0
Sample Input 3
6 6 5 4 3 2 1
Sample Output 3
18
Sample Input 4
7 1 1 1 1 2 3 4
Sample Output 4
6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
すぬけ君は、長さ N の整数列 A を持っています。
すぬけ君は A を 3 箇所で切って、4 つの（空でない）連続する部分列 B,C,D,E に分解します。 切る位置は自由に選ぶことができます。
ここで、整数列 B,C,D,E について、その要素の総和をそれぞれ P,Q,R,S とおきます。 すぬけ君は、P,Q,R,S の最大値と最小値の差の絶対値が小さいほど嬉しいです。 P,Q,R,S の最大値と最小値の差の絶対値としてあり得る最も小さい値を求めてください。
制約
- 4 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 ... A_N
出力
P,Q,R,S の最大値と最小値の差の絶対値としてあり得る最も小さい値を出力せよ。
入力例 1
5 3 2 4 1 2
出力例 1
2
B,C,D,E=(3),(2),(4),(1,2) と分割すれば、P=3,Q=2,R=4,S=1+2=3 となります。 このとき、P,Q,R,S の最大値は 4、最小値は 2 で、その差の絶対値は 2 です。 最大値と最小値の差の絶対値を 2 未満にすることは出来ないため、2 が答えになります。
入力例 2
10 10 71 84 33 6 47 23 25 52 64
出力例 2
36
入力例 3
7 1 2 3 1000000000 4 5 6
出力例 3
999999994
Score : 600 points
Problem Statement
Snuke has an integer sequence A of length N.
He will make three cuts in A and divide it into four (non-empty) contiguous subsequences B, C, D and E. The positions of the cuts can be freely chosen.
Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is happier when the absolute difference of the maximum and the minimum among P,Q,R,S is smaller. Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.
Constraints
- 4 \leq N \leq 2 \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 ... A_N
Output
Find the minimum possible absolute difference of the maximum and the minimum among P,Q,R,S.
Sample Input 1
5 3 2 4 1 2
Sample Output 1
2
If we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here, the maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute difference of 2. We cannot make the absolute difference of the maximum and the minimum less than 2, so the answer is 2.
Sample Input 2
10 10 71 84 33 6 47 23 25 52 64
Sample Output 2
36
Sample Input 3
7 1 2 3 1000000000 4 5 6
Sample Output 3
999999994
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ 2^N の整数列 A_0, A_1, ..., A_{2^N-1} があります。（添字が 0 から始まることに注意）
1 \leq K \leq 2^N-1 を満たすすべての整数 K について、次の問題を解いてください。
- i,j を整数とする。0 \leq i < j \leq 2^N-1, (i or j) \leq K のとき、A_i + A_j の最大値を求めよ。 ただしここで or はビットごとの論理和を表す。
制約
- 1 \leq N \leq 18
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_0 A_1 ... A_{2^N-1}
出力
2^N-1 行出力せよ。 i 行目には、K=i のときの上記の問題の答えを出力せよ。
入力例 1
2 1 2 3 1
出力例 1
3 4 5
K=1 のとき、i,j としてあり得る組合せは (i,j)=(0,1) のみなので、答えは A_0+A_1=1+2=3 となります。
K=2 のとき、i,j としてあり得る組合せは (i,j)=(0,1),(0,2) です。 (i,j)=(0,2) のとき、A_i+A_j=1+3=4 となり、これが最大なので、答えは 4 です。
K=3 のとき、i,j としてあり得る組合せは (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) です。 (i,j)=(1,2) のとき、A_i+A_j=2+3=5 となり、これが最大なので、答えは 5 です。
入力例 2
3 10 71 84 33 6 47 23 25
出力例 2
81 94 155 155 155 155 155
入力例 3
4 75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32
出力例 3
101 120 147 156 156 178 194 194 194 194 194 194 194 194 194
Score : 700 points
Problem Statement
There is an integer sequence of length 2^N: A_0, A_1, ..., A_{2^N-1}. (Note that the sequence is 0-indexed.)
For every integer K satisfying 1 \leq K \leq 2^N-1, solve the following problem:
- Let i and j be integers. Find the maximum value of A_i + A_j where 0 \leq i < j \leq 2^N-1 and (i or j) \leq K. Here, or denotes the bitwise OR.
Constraints
- 1 \leq N \leq 18
- 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_0 A_1 ... A_{2^N-1}
Output
Print 2^N-1 lines. In the i-th line, print the answer of the problem above for K=i.
Sample Input 1
2 1 2 3 1
Sample Output 1
3 4 5
For K=1, the only possible pair of i and j is (i,j)=(0,1), so the answer is A_0+A_1=1+2=3.
For K=2, the possible pairs of i and j are (i,j)=(0,1),(0,2). When (i,j)=(0,2), A_i+A_j=1+3=4. This is the maximum value, so the answer is 4.
For K=3, the possible pairs of i and j are (i,j)=(0,1),(0,2),(0,3),(1,2),(1,3),(2,3) . When (i,j)=(1,2), A_i+A_j=2+3=5. This is the maximum value, so the answer is 5.
Sample Input 2
3 10 71 84 33 6 47 23 25
Sample Output 2
81 94 155 155 155 155 155
Sample Input 3
4 75 26 45 72 81 47 97 97 2 2 25 82 84 17 56 32
Sample Output 3
101 120 147 156 156 178 194 194 194 194 194 194 194 194 194
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 1100 点
問題文
整数 N と K、そして長さ M の整数列 A が与えられます。
各要素が 1 以上 K 以下の整数である整数列がカラフルであるとは、 その整数列の長さ K の連続する部分列であって、1 から K までの整数を 1 個ずつ含むものが存在することを意味します。
すべての長さ N のカラフルな整数列について、その連続する部分列であって A に一致するものの個数を数えて、その総和を求めてください。 ただし、答えは非常に大きくなることがあるので、10^9+7 で割った余りを求めてください。
制約
- 1 \leq N \leq 25000
- 1 \leq K \leq 400
- 1 \leq M \leq N
- 1 \leq A_i \leq K
- 入力はすべて整数である。
入力
入力は以下の形式で標準入力から与えられる。
N K M A_1 A_2 ... A_M
出力
すべての長さ N のカラフルな整数列について、その連続する部分列であって A に一致するものの個数を数えて、 その総和を 10^9+7 で割った余りを出力せよ。
入力例 1
3 2 1 1
出力例 1
9
長さ 3 のカラフルな整数列は、(1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1) の 6 個です。 これらの整数列の、連続する部分列であって A=(1) に一致するものの個数は、それぞれ 2, 2, 1, 2, 1, 1 個です。 よって、これらの合計である 9 が答えになります。
入力例 2
4 2 2 1 2
出力例 2
12
入力例 3
7 4 5 1 2 3 1 2
出力例 3
17
入力例 4
5 4 3 1 1 1
出力例 4
0
入力例 5
10 3 5 1 1 2 3 3
出力例 5
1458
入力例 6
25000 400 4 3 7 31 127
出力例 6
923966268
入力例 7
9954 310 12 267 193 278 294 6 63 86 166 157 193 168 43
出力例 7
979180369
Score : 1100 points
Problem Statement
You are given integers N, K, and an integer sequence A of length M.
An integer sequence where each element is between 1 and K (inclusive) is said to be colorful when there exists a contiguous subsequence of length K of the sequence that contains one occurrence of each integer between 1 and K (inclusive).
For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then find the sum of all the counts. Here, the answer can be extremely large, so find the sum modulo 10^9+7.
Constraints
- 1 \leq N \leq 25000
- 1 \leq K \leq 400
- 1 \leq M \leq N
- 1 \leq A_i \leq K
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K M A_1 A_2 ... A_M
Output
For every colorful integer sequence of length N, count the number of the contiguous subsequences of that sequence which coincide with A, then print the sum of all the counts modulo 10^9+7.
Sample Input 1
3 2 1 1
Sample Output 1
9
There are six colorful sequences of length 3: (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2) and (2,2,1). The numbers of the contiguous subsequences of these sequences that coincide with A=(1) are 2, 2, 1, 2, 1 and 1, respectively. Thus, the answer is their sum, 9.
Sample Input 2
4 2 2 1 2
Sample Output 2
12
Sample Input 3
7 4 5 1 2 3 1 2
Sample Output 3
17
Sample Input 4
5 4 3 1 1 1
Sample Output 4
0
Sample Input 5
10 3 5 1 1 2 3 3
Sample Output 5
1458
Sample Input 6
25000 400 4 3 7 31 127
Sample Output 6
923966268
Sample Input 7
9954 310 12 267 193 278 294 6 63 86 166 157 193 168 43
Sample Output 7
979180369