実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は商店街の福引イベントの係員をしています。このイベントには N 人の来場者が順番に福引を引きます。
各来場者には2種類の番号があります。i 番目 (1 \leq i \leq N) に福引を引いた来場者には、福引を引いた順に 整理番号 i が割り当てられます。また、各来場者は受付時に参加券を受け取っており、i 番目に福引を引いた来場者の 参加券の番号 は A_i です。なお、異なる来場者の参加券の番号が同じである場合もあります。
高橋君の任務は、整理番号が K の倍数（すなわち K, 2K, 3K, \ldots）である来場者全員に景品を渡すことです。K \leq N であるため、景品を受け取る来場者は必ず 1 人以上存在します。
景品を受け取る来場者の参加券の番号を、整理番号が小さい順にすべて出力してください。参加券の番号が同じ来場者が複数いる場合は、その番号を重複を除かずそのまま出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- 入力はすべて整数
入力
N K A_1 A_2 \ldots A_N
- 1 行目には、来場者の人数を表す整数 N と、景品を渡す基準となる整数 K が、スペース区切りで与えられる。整理番号が K の倍数である来場者に景品が渡される。
- 2 行目には、i 番目に福引を引いた来場者の参加券の番号を表す整数 A_i が N 個、スペース区切りで与えられる。
出力
景品を受け取る来場者の参加券の番号を、整理番号が小さい順にスペース区切りで 1 行で出力し、末尾に改行を出力してください。
入力例 1
6 2 10 20 30 40 50 60
出力例 1
20 40 60
入力例 2
10 3 100 200 300 400 500 600 700 800 900 1000
出力例 2
300 600 900
入力例 3
15 4 1000000000 999999999 123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 100000007 314159265
出力例 3
987654321 444444444 888888888
Score : 200 pts
Problem Statement
Takahashi is a staff member at a shopping district's lottery event. In this event, N visitors draw the lottery one by one in order.
Each visitor has two types of numbers. The i-th (1 \leq i \leq N) visitor to draw the lottery is assigned a sequence number i in the order they drew. Additionally, each visitor received a participation ticket at registration, and the participation ticket number of the i-th visitor to draw the lottery is A_i. Note that different visitors may have the same participation ticket number.
Takahashi's task is to give a prize to every visitor whose sequence number is a multiple of K (i.e., K, 2K, 3K, \ldots). Since K \leq N, there is at least one visitor who receives a prize.
Output all participation ticket numbers of the visitors who receive prizes, in ascending order of their sequence numbers. If multiple visitors have the same participation ticket number, output that number as-is without removing duplicates.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
- All inputs are integers
Input
N K A_1 A_2 \ldots A_N
- The first line contains an integer N representing the number of visitors and an integer K representing the criterion for giving prizes, separated by a space. Prizes are given to visitors whose sequence numbers are multiples of K.
- The second line contains N integers A_i, each representing the participation ticket number of the i-th visitor to draw the lottery, separated by spaces.
Output
Output the participation ticket numbers of the visitors who receive prizes in ascending order of their sequence numbers, separated by spaces on a single line, followed by a newline.
Sample Input 1
6 2 10 20 30 40 50 60
Sample Output 1
20 40 60
Sample Input 2
10 3 100 200 300 400 500 600 700 800 900 1000
Sample Output 2
300 600 900
Sample Input 3
15 4 1000000000 999999999 123456789 987654321 111111111 222222222 333333333 444444444 555555555 666666666 777777777 888888888 999999998 100000007 314159265
Sample Output 3
987654321 444444444 888888888
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 266 点
問題文
高橋君と青木君は、ベルトコンベアで流れてくる宝石を分配するゲームをしています。
ゲームのはじめに、正の整数 K が決められています。これは、高橋君が取る宝石の価値の合計の上限です。
N 個の宝石が 1 番目から N 番目まで順番にベルトコンベアで流れてきます。i 番目に流れてくる宝石の価値は A_i（正の整数）です。
高橋君は、宝石が流れてくるたびに、以下のルールに従ってその宝石を取るかどうかが決まります：
- その宝石を取ったとしても、これまでに取った宝石の価値の合計（その宝石を含む）が K 以下であるならば、その宝石を取る。
- そうでない場合（その宝石を取ると合計が K を超えてしまう場合）は、その宝石を取らない。
すなわち、高橋君は先頭から順に、合計が K を超えない限り貪欲に宝石を取り続けます。
青木君は、高橋君が取らなかった宝石をすべて受け取ります。青木君に選択権はありません。
N 個の宝石がすべて流れ終わった後、高橋君が取った宝石の価値の合計と、青木君が受け取った宝石の価値の合計を比較します。合計が大きい方が勝ちで、合計が同じ場合は引き分けとなります。
宝石の個数 N、上限値 K、および N 個の宝石の価値の列 A_1, A_2, \ldots, A_N が与えられたとき、ゲームの結果を判定してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 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 が、スペース区切りで与えられる。
出力
高橋君が勝つ場合は Takahashi 、青木君が勝つ場合は Aoki 、引き分けの場合は Draw を 1 行で出力してください。
入力例 1
5 10 3 4 2 8 1
出力例 1
Takahashi
入力例 2
6 5 2 4 3 1 5 3
出力例 2
Aoki
入力例 3
8 15 5 3 4 6 2 7 1 2
出力例 3
Draw
Score : 266 pts
Problem Statement
Takahashi and Aoki are playing a game where they distribute gems flowing on a conveyor belt.
At the beginning of the game, a positive integer K is determined. This is the upper limit on the total value of gems that Takahashi can take.
N gems flow on the conveyor belt in order, from the 1-st to the N-th. The value of the i-th gem is A_i (a positive integer).
Each time a gem flows by, whether Takahashi takes it is determined according to the following rules:
- If taking the gem would keep the total value of gems he has taken so far (including this gem) at most K, he takes the gem.
- Otherwise (if taking the gem would cause the total to exceed K), he does not take the gem.
In other words, Takahashi greedily takes gems in order from the first, as long as the total does not exceed K.
Aoki receives all the gems that Takahashi did not take. Aoki has no choice in the matter.
After all N gems have flowed by, the total value of gems Takahashi took and the total value of gems Aoki received are compared. The one with the greater total wins, and if the totals are equal, it is a draw.
Given the number of gems N, the upper limit K, and the sequence of values of the N gems A_1, A_2, \ldots, A_N, determine the result of the game.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq 10^{15}
- 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 the integer N representing the number of gems and the integer K representing the upper limit on the total value of gems Takahashi can take, separated by a space.
- The second line contains the values of the N gems A_1, A_2, \ldots, A_N in the order they flow by, separated by spaces.
Output
If Takahashi wins, print Takahashi; if Aoki wins, print Aoki; if it is a draw, print Draw, on a single line.
Sample Input 1
5 10 3 4 2 8 1
Sample Output 1
Takahashi
Sample Input 2
6 5 2 4 3 1 5 3
Sample Output 2
Aoki
Sample Input 3
8 15 5 3 4 6 2 7 1 2
Sample Output 3
Draw
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は遠足に持っていくおやつを選んでいます。お店には N 種類のおやつがあり、おやつ i（1 \le i \le N）の値段は 1 個あたり P_i 円です。どの種類のおやつも十分な個数が売られています。
高橋君は、N 種類のおやつの中から好きな種類を選び、選んだ種類のおやつをそれぞれちょうど T 個ずつ買います。選ばなかった種類のおやつは 1 個も買いません。
おやつの購入に使える金額は合計で E 円以下です。この予算の範囲内でおやつの種類を選ぶとき、最大で何種類のおやつを買うことができるでしょうか。
すなわち、買う種類の集合 S \subseteq \{1, 2, \ldots, N\} を選び、\displaystyle \sum_{i \in S} P_i \times T \le E を満たすときの |S| の最大値を求めてください。
制約
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^4
- 1 \leq E \leq 10^{14}
- 1 \leq P_i \leq 10^9
- 入力はすべて整数
入力
N T E P_1 P_2 \ldots P_N
- 1 行目には、おやつの種類数を表す整数 N、各種類を買う個数を表す整数 T（個）、予算を表す整数 E（円）が、スペース区切りで与えられる。
- 2 行目には、各おやつの 1 個あたりの値段を表す整数 P_1, P_2, \ldots, P_N（円）が、スペース区切りで与えられる。
出力
買うことができるおやつの種類数の最大値を 1 行で出力せよ。
入力例 1
5 2 20 3 5 1 4 7
出力例 1
3
入力例 2
8 3 100 10 20 5 15 8 30 12 25
出力例 2
3
入力例 3
10 10000 100000000000000 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 999999992 999999991
出力例 3
10
Score : 300 pts
Problem Statement
Takahashi is choosing snacks to bring on a field trip. The store has N types of snacks, and snack i (1 \le i \le N) costs P_i yen per piece. Each type of snack is available in sufficient quantity.
Takahashi selects some types from the N types of snacks, and buys exactly T pieces of each selected type. He does not buy any pieces of the types he did not select.
The total amount spent on snacks must be at most E yen. Within this budget, what is the maximum number of types of snacks he can buy?
In other words, find the maximum value of |S| when choosing a set S \subseteq \{1, 2, \ldots, N\} of types to buy such that \displaystyle \sum_{i \in S} P_i \times T \le E.
Constraints
- 1 \leq N \leq 10^5
- 1 \leq T \leq 10^4
- 1 \leq E \leq 10^{14}
- 1 \leq P_i \leq 10^9
- All inputs are integers
Input
N T E P_1 P_2 \ldots P_N
- The first line contains an integer N representing the number of types of snacks, an integer T (pieces) representing the number of pieces to buy of each selected type, and an integer E (yen) representing the budget, separated by spaces.
- The second line contains integers P_1, P_2, \ldots, P_N (yen) representing the price per piece of each snack, separated by spaces.
Output
Print the maximum number of types of snacks that can be bought, in a single line.
Sample Input 1
5 2 20 3 5 1 4 7
Sample Output 1
3
Sample Input 2
8 3 100 10 20 5 15 8 30 12 25
Sample Output 2
3
Sample Input 3
10 10000 100000000000000 1000000000 999999999 999999998 999999997 999999996 999999995 999999994 999999993 999999992 999999991
Sample Output 3
10
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 366 点
問題文
高橋君は、横に長い一枚の壁にペンキを塗る作業を行っています。
壁は数直線全体に広がっているものとし、数直線上の各地点について、最初はペンキが 0 回塗られた状態です。高橋君は N 回のペンキ塗り作業を行いました。i 回目 (1 \leq i \leq N) の作業では、区間 [L_i, R_i]（ただし L_i < R_i）の範囲にペンキを 1 回塗りました。すなわち、L_i \leq x \leq R_i を満たすすべての実数 x に対応する地点で、ペンキの塗られた回数が 1 増加しました。
ペンキが K 回以上塗られた部分は十分な厚みがあり合格とみなされますが、K 回未満の部分は塗りが薄く不合格となります。
すべての作業が終わった後、ペンキの塗られた回数が K 以上である地点全体からなる集合の合計の長さ（すなわち、その集合を構成する各区間の長さの総和）を求めてください。
例えば、塗られた回数が K 以上となる地点全体の集合が区間 [1, 5] と区間 [7, 9] の和集合であれば、答えは (5 - 1) + (9 - 7) = 6 です。
なお、L_i, R_i はすべて整数であるため、塗られた回数が変化する境界は整数座標でのみ起こります。したがって、答えは必ず整数になります。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq L_i < R_i \leq 10^9
- 入力はすべて整数である
入力
N K L_1 R_1 L_2 R_2 \vdots L_N R_N
- 1 行目には、ペンキ塗り作業の回数を表す整数 N と、合格とみなされる塗り回数の閾値を表す整数 K が、スペース区切りで与えられる。
- 続く N 行のうち i 番目の行 (1 \leq i \leq N) には、i 回目の作業で塗る区間の左端 L_i と右端 R_i が、スペース区切りで与えられる。
出力
ペンキの塗られた回数が K 以上である地点全体の合計の長さを、整数で 1 行に出力してください。
入力例 1
3 2 1 5 3 7 6 9
出力例 1
3
入力例 2
2 2 0 3 5 8
出力例 2
0
入力例 3
8 3 0 10 2 8 4 12 1 6 5 15 7 9 3 11 10 14
出力例 3
10
入力例 4
15 4 0 100 10 90 20 80 30 70 40 60 5 50 15 85 25 75 35 65 45 55 0 30 50 100 60 95 70 88 3 47
出力例 4
85
入力例 5
1 1 0 1000000000
出力例 5
1000000000
Score : 366 pts
Problem Statement
Takahashi is painting a long horizontal wall with paint.
The wall extends across the entire number line, and initially, every point on the number line has been painted 0 times. Takahashi performed N painting operations. In the i-th operation (1 \leq i \leq N), he painted the interval [L_i, R_i] (where L_i < R_i) once. That is, for every point corresponding to a real number x satisfying L_i \leq x \leq R_i, the number of times it has been painted increased by 1.
Parts that have been painted K or more times are considered sufficiently thick and pass inspection, while parts painted fewer than K times are too thin and fail.
After all operations are completed, find the total length of the set of all points that have been painted K or more times (that is, the sum of the lengths of each interval that constitutes this set).
For example, if the set of all points painted K or more times is the union of intervals [1, 5] and [7, 9], the answer is (5 - 1) + (9 - 7) = 6.
Note that since all L_i and R_i are integers, the boundaries where the paint count changes occur only at integer coordinates. Therefore, the answer is always an integer.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq K \leq N
- 0 \leq L_i < R_i \leq 10^9
- All input values are integers
Input
N K L_1 R_1 L_2 R_2 \vdots L_N R_N
- The first line contains an integer N representing the number of painting operations and an integer K representing the threshold number of coats required to pass inspection, separated by a space.
- The i-th of the following N lines (1 \leq i \leq N) contains the left endpoint L_i and right endpoint R_i of the interval painted in the i-th operation, separated by a space.
Output
Output the total length of the set of all points painted K or more times, as an integer on a single line.
Sample Input 1
3 2 1 5 3 7 6 9
Sample Output 1
3
Sample Input 2
2 2 0 3 5 8
Sample Output 2
0
Sample Input 3
8 3 0 10 2 8 4 12 1 6 5 15 7 9 3 11 10 14
Sample Output 3
10
Sample Input 4
15 4 0 100 10 90 20 80 30 70 40 60 5 50 15 85 25 75 35 65 45 55 0 30 50 100 60 95 70 88 3 47
Sample Output 4
85
Sample Input 5
1 1 0 1000000000
Sample Output 5
1000000000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 466 点
問題文
高橋君は気象観測所で働いており、ある地域の N 日間の日ごとの最高気温を記録しています。i 日目（ 1 \leq i \leq N ）の最高気温は A_i ℃です。
高橋君は、連続する日の区間を選んで気温の変動幅を調べたいと考えています。l 日目から r 日目までの区間（ 1 \leq l \leq r \leq N ）に対して、その区間の「変動幅」を
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r)
と定義します。特に、l = r のとき（1日だけからなる区間）の変動幅は 0 です。
正整数 N と非負整数 K、および N 日間の最高気温の列 A_1, A_2, \dots, A_N が与えられたとき、変動幅がちょうど K となる区間の個数、すなわち
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) = K
を満たす整数の組 (l, r)（ 1 \leq l \leq r \leq N ）の個数を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- 入力はすべて整数である
入力
N K A_1 A_2 \dots A_N
1 行目には、日数を表す正整数 N と、変動幅として指定された非負整数 K が、スペース区切りで与えられる。2 行目には、各日の最高気温を表す整数 A_1, A_2, \dots, A_N が、スペース区切りで与えられる。
出力
変動幅がちょうど K となる組 (l, r) の個数を 1 行で出力せよ。
入力例 1
5 3 1 4 2 5 3
出力例 1
6
入力例 2
7 0 3 3 3 5 5 3 3
出力例 2
12
入力例 3
10 5 2 -1 3 7 4 0 6 1 5 -2
出力例 3
2
Score : 466 pts
Problem Statement
Takahashi works at a weather observatory and is recording the daily maximum temperatures over N days for a certain region. The maximum temperature on day i (1 \leq i \leq N) is A_i ℃.
Takahashi wants to select a contiguous interval of days and examine the temperature fluctuation range. For an interval from day l to day r (1 \leq l \leq r \leq N), the "fluctuation range" of that interval is defined as:
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r)
In particular, when l = r (an interval consisting of only one day), the fluctuation range is 0.
Given a positive integer N, a non-negative integer K, and a sequence of maximum temperatures over N days A_1, A_2, \dots, A_N, find the number of intervals whose fluctuation range is exactly K. That is, find the number of integer pairs (l, r) (1 \leq l \leq r \leq N) satisfying:
\max(A_l, A_{l+1}, \dots, A_r) - \min(A_l, A_{l+1}, \dots, A_r) = K
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq K \leq 10^9
- -10^9 \leq A_i \leq 10^9
- All inputs are integers
Input
N K A_1 A_2 \dots A_N
The first line contains a positive integer N representing the number of days and a non-negative integer K representing the specified fluctuation range, separated by a space. The second line contains integers A_1, A_2, \dots, A_N representing the maximum temperature on each day, separated by spaces.
Output
Output the number of pairs (l, r) whose fluctuation range is exactly K, on a single line.
Sample Input 1
5 3 1 4 2 5 3
Sample Output 1
6
Sample Input 2
7 0 3 3 3 5 5 3 3
Sample Output 2
12
Sample Input 3
10 5 2 -1 3 7 4 0 6 1 5 -2
Sample Output 3
2