実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 233 点
問題文
高橋君は山岳地帯をハイキングしています。目の前には N 個の山が一列に並んでおり、左から順に 1, 2, \ldots, N と番号が付けられています。山 i の標高は A_i です。
高橋君は、山脈の中で「独立峰」と呼べる山を探しています。山 i が「独立峰」であるとは、i 以外のすべての山 j（1 \leq j \leq N, \, j \neq i）に対して A_i > A_j が成り立つことを指します。すなわち、独立峰とは N 個の山の中で標高が狭義に最大である山のことです。
独立峰は高々 1 つしか存在しません。最大の標高を持つ山が複数ある場合、条件は狭義の不等号（>）であるため、それらの山はいずれも独立峰にはなりません。一方、N = 1 の場合は、唯一の山が独立峰となります。
N 個の山の標高が与えられるので、独立峰が存在する場合はその標高を、独立峰が存在しない場合は 0 を出力してください。
制約
- 1 \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- 入力はすべて整数である。
入力
N A_1 A_2 \ldots A_N
- 1 行目には、山の個数を表す整数 N が与えられる。
- 2 行目には、各山の標高を表す N 個の整数 A_1, A_2, \ldots, A_N がスペース区切りで与えられる。
出力
独立峰が存在する場合はその標高を、存在しない場合は 0 を、1 行に出力してください。
入力例 1
5 3 1 5 2 4
出力例 1
5
入力例 2
4 3 5 5 2
出力例 2
0
入力例 3
10 14 7 23 9 42 18 42 5 31 12
出力例 3
0
入力例 4
20 100 250 300 450 123 678 999 234 567 890 111 222 333 444 555 666 777 888 1000000000 999999999
出力例 4
1000000000
入力例 5
1 1
出力例 5
1
Score : 233 pts
Problem Statement
Takahashi is hiking in a mountainous area. In front of him, N mountains are lined up in a row, numbered 1, 2, \ldots, N from left to right. The elevation of mountain i is A_i.
Takahashi is looking for a mountain that can be called an "independent peak" in the mountain range. Mountain i is an "independent peak" if A_i > A_j holds for every other mountain j (1 \leq j \leq N, \, j \neq i). In other words, an independent peak is a mountain whose elevation is strictly the maximum among all N mountains.
There exists at most one independent peak. If multiple mountains share the maximum elevation, none of them qualifies as an independent peak because the condition uses a strict inequality (>). On the other hand, if N = 1, the only mountain is an independent peak.
Given the elevations of N mountains, output the elevation of the independent peak if one exists, or 0 if no independent peak exists.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq A_i \leq 10^9
- All input values are integers.
Input
N A_1 A_2 \ldots A_N
- The first line contains an integer N, representing the number of mountains.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the elevation of each mountain.
Output
If an independent peak exists, output its elevation; otherwise, output 0, on a single line.
Sample Input 1
5 3 1 5 2 4
Sample Output 1
5
Sample Input 2
4 3 5 5 2
Sample Output 2
0
Sample Input 3
10 14 7 23 9 42 18 42 5 31 12
Sample Output 3
0
Sample Input 4
20 100 250 300 450 123 678 999 234 567 890 111 222 333 444 555 666 777 888 1000000000 999999999
Sample Output 4
1000000000
Sample Input 5
1 1
Sample Output 5
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は会社の会議室を予約しようとしています。会議室の利用可能な時間帯は、はじめ、整数 L 以上 R 以下の各時刻、すなわち時刻 L, L+1, \ldots, R の R - L + 1 個です。
高橋君が予約システムの履歴を確認したところ、N 件の利用制限が順番に登録されていることがわかりました。i 番目の利用制限は「会議室を利用できるのは時刻 l_i 以上 r_i 以下のみに制限する」というものです。
利用制限が登録されるたびに、実際に利用可能な時刻の集合は、それまでの利用可能な時刻の集合と新たな制限の共通部分に更新されます。すなわち、k 番目の利用制限までが登録された時点で利用可能な時刻の個数は、整数の集合
[L, R] \cap [l_1, r_1] \cap [l_2, r_2] \cap \cdots \cap [l_k, r_k]
の要素数です。ここで [a, b] は a 以上 b 以下の整数全体の集合を表します。この共通部分が空集合である場合、利用可能な時刻の個数は 0 です。
i = 1, 2, \ldots, N のそれぞれについて、i 番目の利用制限が登録された直後の利用可能な時刻の個数を求めてください。
制約
- 0 \leq L \leq R \leq 10^9
- 1 \leq N \leq 10^5
- 0 \leq l_i \leq r_i \leq 10^9
- 入力はすべて整数である
入力
L R N l_1 r_1 l_2 r_2 \vdots l_N r_N
- 1 行目には、初期の利用可能範囲の左端 L と右端 R が、スペース区切りで与えられる。
- 2 行目には、利用制限の個数 N が与えられる。
- 続く N 行のうち i 行目には、i 番目の利用制限の左端 l_i と右端 r_i が、スペース区切りで与えられる。
出力
N 行出力せよ。i 行目には、i 番目の利用制限が登録された直後の利用可能な時刻の個数を出力せよ。
入力例 1
1 10 3 3 8 4 6 2 5
出力例 1
6 3 2
入力例 2
0 5 4 1 4 2 3 5 5 0 2
出力例 2
4 2 0 0
入力例 3
10 30 8 8 25 12 28 15 22 14 20 18 18 0 100 19 30 17 17
出力例 3
16 14 8 6 1 1 0 0
入力例 4
123456789 987654321 12 100000000 900000000 200000000 950000000 300000000 800000000 250000000 850000000 400000000 750000000 450000000 700000000 500000000 680000000 550000000 600000000 560000000 590000000 570000000 580000000 575000000 576000000 576000001 576000010
出力例 4
776543212 700000001 500000001 500000001 350000001 250000001 180000001 50000001 30000001 10000001 1000001 0
入力例 5
0 0 1 0 0
出力例 5
1
Score : 300 pts
Problem Statement
Takahashi is trying to reserve a meeting room at his company. The available time slots for the meeting room are initially all integer times from L to R inclusive, namely the R - L + 1 times L, L+1, \ldots, R.
When Takahashi checked the reservation system's history, he found that N usage restrictions had been registered in order. The i-th usage restriction is: "The meeting room can only be used at times from l_i to r_i inclusive."
Each time a usage restriction is registered, the set of actually available times is updated to the intersection of the previously available set of times and the new restriction. In other words, the number of available times after the first k usage restrictions have been registered is the number of elements in the set of integers
[L, R] \cap [l_1, r_1] \cap [l_2, r_2] \cap \cdots \cap [l_k, r_k]
where [a, b] denotes the set of all integers from a to b inclusive. If this intersection is empty, the number of available times is 0.
For each i = 1, 2, \ldots, N, find the number of available times immediately after the i-th usage restriction is registered.
Constraints
- 0 \leq L \leq R \leq 10^9
- 1 \leq N \leq 10^5
- 0 \leq l_i \leq r_i \leq 10^9
- All input values are integers.
Input
L R N l_1 r_1 l_2 r_2 \vdots l_N r_N
- The first line contains the left endpoint L and right endpoint R of the initial available range, separated by a space.
- The second line contains the number of usage restrictions N.
- The i-th of the following N lines contains the left endpoint l_i and right endpoint r_i of the i-th usage restriction, separated by a space.
Output
Print N lines. The i-th line should contain the number of available times immediately after the i-th usage restriction is registered.
Sample Input 1
1 10 3 3 8 4 6 2 5
Sample Output 1
6 3 2
Sample Input 2
0 5 4 1 4 2 3 5 5 0 2
Sample Output 2
4 2 0 0
Sample Input 3
10 30 8 8 25 12 28 15 22 14 20 18 18 0 100 19 30 17 17
Sample Output 3
16 14 8 6 1 1 0 0
Sample Input 4
123456789 987654321 12 100000000 900000000 200000000 950000000 300000000 800000000 250000000 850000000 400000000 750000000 450000000 700000000 500000000 680000000 550000000 600000000 560000000 590000000 570000000 580000000 575000000 576000000 576000001 576000010
Sample Output 4
776543212 700000001 500000001 500000001 350000001 250000001 180000001 50000001 30000001 10000001 1000001 0
Sample Input 5
0 0 1 0 0
Sample Output 5
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の正整数からなる数列を持っています。数列の i 番目 (1 \leq i \leq N) の要素は A_i です。
高橋君は、この数列の 連続する K 個の要素からなる区間 をすべて考え、それぞれの区間に含まれる要素の積を求めたいと考えています。
連続する K 個の要素からなる区間は N - K + 1 通りあります。i = 1, 2, \ldots, N - K + 1 のそれぞれについて、i 番目から i + K - 1 番目までの K 個の要素からなる区間が取れます。
各区間に含まれる K 個の要素の積 A_i \times A_{i+1} \times \cdots \times A_{i+K-1} を計算し、すべての区間における積の総和、すなわち
\sum_{i=1}^{N-K+1} \prod_{j=i}^{i+K-1} A_j
を求めてください。
答えは非常に大きくなる可能性があるため、10^9 + 7 で割った余りを出力してください。
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、数列の長さを表す整数 N と、区間の長さを表す整数 K が、スペース区切りで与えられる。
- 2 行目には、数列の各要素を表す N 個の正整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
すべての連続する K 個の要素からなる区間における積の総和を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 1
5 2 1 2 3 4 5
出力例 1
40
入力例 2
6 3 2 3 1 4 2 5
出力例 2
66
入力例 3
10 4 100 200 300 400 500 600 700 800 900 1000
出力例 3
799992244
Score : 366 pts
Problem Statement
Takahashi has a sequence of N positive integers. The i-th element (1 \leq i \leq N) of the sequence is A_i.
Takahashi wants to consider all intervals consisting of K consecutive elements of this sequence, and compute the product of the elements in each interval.
There are N - K + 1 intervals consisting of K consecutive elements. For each i = 1, 2, \ldots, N - K + 1, we can take the interval consisting of K elements from the i-th to the (i + K - 1)-th element.
Compute the product of the K elements in each interval, A_i \times A_{i+1} \times \cdots \times A_{i+K-1}, and find the sum of the products over all intervals, namely
\sum_{i=1}^{N-K+1} \prod_{j=i}^{i+K-1} A_j
Since the answer can be very large, output the remainder when divided by 10^9 + 7.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the length of the sequence and an integer K representing the length of the interval, separated by a space.
- The second line contains N positive integers A_1, A_2, \ldots, A_N representing the elements of the sequence, separated by spaces.
Output
Output in one line the remainder when the sum of products over all intervals consisting of K consecutive elements is divided by 10^9 + 7.
Sample Input 1
5 2 1 2 3 4 5
Sample Output 1
40
Sample Input 2
6 3 2 3 1 4 2 5
Sample Output 2
66
Sample Input 3
10 4 100 200 300 400 500 600 700 800 900 1000
Sample Output 3
799992244
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
高橋君は、まっすぐな道に沿って一列に並んだ N 個の区画に植木を植える計画を立てています。区画は左から順に区画 1 , 区画 2 , \ldots , 区画 N と番号が付けられています。
高橋君はこれらの N 個の区画からちょうど K 個の区画を選び、選んだ各区画に植木を 1 本ずつ植えます（選ばなかった区画には植木を植えません）。ただし、植木の間隔を確保するため、以下のルールに従わなければなりません。
- 隣り合う 2 つの区画をどちらも選んではならない。すなわち、すべての i （1 \leq i \leq N - 1）について、区画 i と区画 i + 1 が両方とも選ばれることがあってはならない。
ルールを満たす区画の選び方は何通りありますか？ 選び方は選んだ区画の集合として区別します。答えを 10^9 + 7 で割った余りを求めてください。ルールを満たす選び方が存在しない場合、答えは 0 です。
制約
- 1 \leq N \leq 10^6
- 1 \leq K \leq N
- N, K は整数
入力
N K
区画の数を表す整数 N と、植木を植える区画の数を表す整数 K が、スペース区切りで 1 行で与えられる。
出力
ルールを満たす区画の選び方の総数を 10^9 + 7 で割った余りを 1 行で出力せよ。
入力例 1
5 2
出力例 1
6
入力例 2
4 3
出力例 2
0
入力例 3
100 30
出力例 3
228350971
入力例 4
1000000 400000
出力例 4
440859224
入力例 5
1 1
出力例 5
1
Score : 400 pts
Problem Statement
Takahashi is planning to plant trees in N plots arranged in a row along a straight road. The plots are numbered from left to right as plot 1, plot 2, \ldots, plot N.
Takahashi will choose exactly K plots from these N plots and plant one tree in each chosen plot (no trees are planted in unchosen plots). However, to ensure adequate spacing between trees, the following rule must be followed:
- No two adjacent plots may both be chosen. That is, for all i (1 \leq i \leq N - 1), plot i and plot i + 1 must not both be chosen.
How many ways are there to choose the plots while satisfying the rule? Two ways are considered different if the sets of chosen plots are different. Find the answer modulo 10^9 + 7. If there is no valid way to choose the plots, the answer is 0.
Constraints
- 1 \leq N \leq 10^6
- 1 \leq K \leq N
- N, K are integers
Input
N K
An integer N representing the number of plots and an integer K representing the number of plots in which to plant trees are given on a single line, separated by a space.
Output
Print on a single line the total number of ways to choose the plots satisfying the rule, modulo 10^9 + 7.
Sample Input 1
5 2
Sample Output 1
6
Sample Input 2
4 3
Sample Output 2
0
Sample Input 3
100 30
Sample Output 3
228350971
Sample Input 4
1000000 400000
Sample Output 4
440859224
Sample Input 5
1 1
Sample Output 5
1
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
N 人の人が左右一列に並んでおり、左から i 番目 (1 \leq i \leq N) の人の身長は H_i です。身長が同じ人が複数いることもあります。
N 人の各人はボールを 1 つずつ持っており、それぞれ右方向に投げます。i 番目の人が投げたボールは、i 番目の人より右側にいて、かつ i 番目の人よりも厳密に身長が高い人のうち、最も左にいる人がキャッチします。すなわち、j > i かつ H_j > H_i を満たす j のうち最小の j に対応する人がキャッチします。そのような人が一人もいなければ、そのボールは誰にもキャッチされません。
i 番目の人が投げたボールを j 番目の人がキャッチしたとき（i < j）、その転送のコストを、i 番目の人から j 番目の人までの間にいる全員（i 番目の人と j 番目の人自身を含む）の身長の最小値、すなわち \min(H_i, H_{i+1}, \ldots, H_j) と定義します。誰にもキャッチされなかったボールのコストは 0 とします。
N 人それぞれが投げたボールの転送コストの合計値を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- 入力はすべて整数である
入力
N H_1 H_2 \ldots H_N
- 1 行目には、人数を表す整数 N が与えられる。
- 2 行目には、左から i 番目 (i = 1, 2, \ldots, N) の人の身長を表す整数 H_i が、スペース区切りで N 個与えられる。
出力
N 人それぞれが投げたボールの転送コストの合計値を 1 行で出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
4
入力例 2
4 5 5 5 5
出力例 2
0
入力例 3
8 2 7 3 5 1 6 4 8
出力例 3
16
入力例 4
15 10 3 7 2 8 1 5 12 4 6 9 3 11 2 15
出力例 4
37
入力例 5
1 1000000000
出力例 5
0
Score : 466 pts
Problem Statement
N people are standing in a single row from left to right, and the height of the i-th person from the left (1 \leq i \leq N) is H_i. Multiple people may have the same height.
Each of the N people holds one ball and throws it to the right. The ball thrown by the i-th person is caught by the leftmost person among those who are to the right of the i-th person and are strictly taller than the i-th person. That is, the ball is caught by the person corresponding to the smallest j satisfying j > i and H_j > H_i. If no such person exists, the ball is not caught by anyone.
When the j-th person catches the ball thrown by the i-th person (i < j), the cost of this transfer is defined as the minimum height among all people between the i-th and j-th person (including the i-th and j-th person themselves), that is, \min(H_i, H_{i+1}, \ldots, H_j). The cost of a ball that is not caught by anyone is 0.
Find the total sum of the transfer costs of the balls thrown by each of the N people.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq H_i \leq 10^9
- All inputs are integers
Input
N H_1 H_2 \ldots H_N
- The first line contains an integer N representing the number of people.
- The second line contains N integers H_i separated by spaces, representing the height of the i-th person from the left (i = 1, 2, \ldots, N).
Output
Output in one line the total sum of the transfer costs of the balls thrown by each of the N people.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
4
Sample Input 2
4 5 5 5 5
Sample Output 2
0
Sample Input 3
8 2 7 3 5 1 6 4 8
Sample Output 3
16
Sample Input 4
15 10 3 7 2 8 1 5 12 4 6 9 3 11 2 15
Sample Output 4
37
Sample Input 5
1 1000000000
Sample Output 5
0