AtCoder Weekday Contest 0069 Beta

Please sign in first.

A - Stock Price Fluctuation Range

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 266 点

問題文

高橋君は証券会社のインターンシップで、複数の銘柄の株価データを分析する課題に取り組んでいます。

分析対象の銘柄は N 個あり、銘柄には 1 から N までの番号が付けられています。それぞれの銘柄について M 日分の株価データが記録されており、銘柄 i (1 \leq i \leq N) の株価データは M 個の整数値 A_{i,1}, A_{i,2}, \ldots, A_{i,M} として与えられます。ここで A_{i,j} は銘柄 i の j 日目の株価を表します。

高橋君は、ある銘柄の「変動幅」を次のように定義しました：

株価の時系列データにおいて、隣接する日の株価の差の絶対値をすべて合計したものを、その銘柄の変動幅とする。

すなわち、銘柄 i の変動幅は \displaystyle\sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}| です。

高橋君は、変動幅が最も大きい銘柄を報告書にまとめたいと考えています。変動幅が最も大きい銘柄の番号を求めてください。変動幅が最も大きい銘柄が複数ある場合は、その中で番号が最も小さい銘柄の番号を出力してください。

制約

1 \leq N \leq 100
2 \leq M \leq 100
1 \leq A_{i,j} \leq 10000 (1 \leq i \leq N,\ 1 \leq j \leq M)
入力はすべて整数である。

入力

N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}

1 行目には、銘柄の数 N と日数 M が、スペース区切りで与えられる。
続く N 行の i 番目の行 (1 \leq i \leq N) には、銘柄 i の各日の株価を表す M 個の整数 A_{i,1}, A_{i,2}, \ldots, A_{i,M} がスペース区切りで与えられる。

出力

変動幅が最も大きい銘柄の番号を 1 行で出力せよ。変動幅が最も大きい銘柄が複数ある場合は、その中で番号が最も小さいものを出力せよ。

入力例 1

3 4
100 130 120 150
200 210 220 230
150 100 200 50

出力例 1

入力例 2

出力例 2

入力例 3

5 6
500 600 550 700 650 800
1000 900 800 700 600 500
300 310 290 320 280 330
50 9999 50 9999 50 9999
100 100 100 100 100 100

出力例 3

入力例 4

8 10
120 125 130 128 135 140 138 142 145 150
500 480 510 470 520 460 530 450 540 440
300 300 300 300 300 300 300 300 300 300
1000 2000 1000 2000 1000 2000 1000 2000 1000 2000
50 60 55 65 58 70 62 75 68 80
1 10000 1 10000 1 10000 1 10000 1 10000
400 390 410 380 420 370 430 360 440 350
9999 9998 9997 9996 9995 9994 9993 9992 9991 9990

出力例 4

入力例 5

1 2
1 10000

出力例 5

Score : 266 pts

Problem Statement

Takahashi is working on a task to analyze stock price data for multiple stocks during his internship at a securities company.

There are N stocks to analyze, numbered from 1 to N. For each stock, M days of stock price data are recorded. The stock price data for stock i (1 \leq i \leq N) is given as M integer values A_{i,1}, A_{i,2}, \ldots, A_{i,M}, where A_{i,j} represents the stock price of stock i on day j.

Takahashi defined the "volatility" of a stock as follows:

The volatility of a stock is the sum of the absolute differences in stock prices between consecutive days over the entire time series.

That is, the volatility of stock i is \displaystyle\sum_{j=1}^{M-1} |A_{i,j+1} - A_{i,j}|.

Takahashi wants to include the stock with the largest volatility in his report. Find the number of the stock with the largest volatility. If there are multiple stocks with the largest volatility, output the smallest stock number among them.

Constraints

1 \leq N \leq 100
2 \leq M \leq 100
1 \leq A_{i,j} \leq 10000 (1 \leq i \leq N,\ 1 \leq j \leq M)
All input values are integers.

Input

N M
A_{1,1} A_{1,2} \ldots A_{1,M}
A_{2,1} A_{2,2} \ldots A_{2,M}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,M}

The first line contains the number of stocks N and the number of days M, separated by a space.
The i-th of the following N lines (1 \leq i \leq N) contains M integers A_{i,1}, A_{i,2}, \ldots, A_{i,M} representing the stock prices of stock i on each day, separated by spaces.

Output

Output the number of the stock with the largest volatility on a single line. If there are multiple stocks with the largest volatility, output the smallest number among them.

Sample Input 1

3 4
100 130 120 150
200 210 220 230
150 100 200 50

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

5 6
500 600 550 700 650 800
1000 900 800 700 600 500
300 310 290 320 280 330
50 9999 50 9999 50 9999
100 100 100 100 100 100

Sample Output 3

Sample Input 4

8 10
120 125 130 128 135 140 138 142 145 150
500 480 510 470 520 460 530 450 540 440
300 300 300 300 300 300 300 300 300 300
1000 2000 1000 2000 1000 2000 1000 2000 1000 2000
50 60 55 65 58 70 62 75 68 80
1 10000 1 10000 1 10000 1 10000 1 10000
400 390 410 380 420 370 430 360 440 350
9999 9998 9997 9996 9995 9994 9993 9992 9991 9990

Sample Output 4

Sample Input 5

1 2
1 10000

Sample Output 5

B - Candy Selection Contest

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は、お菓子屋さんで開催されている「お菓子選びコンテスト」に参加しています。

店内には N 個のお菓子が並んでおり、それぞれ 1 つずつしかありません。各お菓子 i（1 \leq i \leq N）には、お店が設定した基本の美味しさポイント T_i と、高橋君の好みに基づく補正値 C_i が決まっています。高橋君がお菓子 i を選んだときに得られる 満足度 は T_i + C_i です。

高橋君は、N 個のお菓子の中から ちょうど K 個 を選びます。同じお菓子を複数回選ぶことはできません。ちょうど K 個を選ぶ必要があるため、満足度が負であるお菓子を選ばざるを得ない場合もあります。

選んだ K 個のお菓子の満足度の合計を最大化するとき、その最大値を求めてください。

制約

1 \leq K \leq N \leq 2 \times 10^5
1 \leq T_i \leq 10^9
-10^9 \leq C_i \leq 10^9
入力はすべて整数

入力

N K
T_1 C_1
T_2 C_2
\vdots
T_N C_N

1 行目には、お菓子の個数を表す整数 N と、選ぶお菓子の個数を表す整数 K が、スペース区切りで与えられる。
2 行目から N + 1 行目では、各お菓子の基本の美味しさポイントと好み補正値が与えられる。
1 + i 行目（1 \leq i \leq N）には、お菓子 i の基本の美味しさポイント T_i と好み補正値 C_i が、スペース区切りで与えられる。

出力

N 個のお菓子の中からちょうど K 個を選んだときの、満足度の合計の最大値を整数として 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

12 6
1000000000 -500000000
500000000 500000000
800000000 100000000
300000000 600000000
750000000 -200000000
600000000 300000000
450000000 400000000
900000000 -100000000
200000000 700000000
650000000 150000000
550000000 250000000
700000000 0

出力例 3

5450000000

Score : 300 pts

Problem Statement

Takahashi is participating in a "Candy Selection Contest" held at a candy shop.

There are N candies lined up in the shop, each available in only one piece. For each candy i (1 \leq i \leq N), there is a base tastiness point T_i set by the shop and an adjustment value C_i based on Takahashi's preferences. The satisfaction Takahashi gains from choosing candy i is T_i + C_i.

Takahashi will choose exactly K candies from the N candies. He cannot choose the same candy more than once. Since he must choose exactly K candies, he may be forced to choose candies with negative satisfaction.

Find the maximum possible total satisfaction when choosing K candies to maximize the sum of their satisfactions.

Constraints

1 \leq K \leq N \leq 2 \times 10^5
1 \leq T_i \leq 10^9
-10^9 \leq C_i \leq 10^9
All input values are integers

Input

N K
T_1 C_1
T_2 C_2
\vdots
T_N C_N

The first line contains an integer N representing the number of candies and an integer K representing the number of candies to choose, separated by a space.
From the 2nd line to the (N + 1)-th line, the base tastiness point and preference adjustment value for each candy are given.
The (1 + i)-th line (1 \leq i \leq N) contains the base tastiness point T_i and the preference adjustment value C_i of candy i, separated by a space.

Output

Output in a single line the maximum total satisfaction as an integer when choosing exactly K candies from the N candies.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

12 6
1000000000 -500000000
500000000 500000000
800000000 100000000
300000000 600000000
750000000 -200000000
600000000 300000000
450000000 400000000
900000000 -100000000
200000000 700000000
650000000 150000000
550000000 250000000
700000000 0

Sample Output 3

5450000000

C - Light Switch Operation

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君の部屋には N 個の照明が横一列に並んでおり、左から順に照明 1, 照明 2, \ldots, 照明 N と番号が付けられています。それぞれの照明は「点灯」または「消灯」のいずれかの状態になっています。各照明の初期状態は文字列 S で与えられます。S の i 文字目が 1 ならば照明 i は点灯、0 ならば消灯であることを表します。

高橋君は、すべての照明を点灯状態にしたいと考えています。高橋君は次の操作を 0 回以上任意の回数だけ行うことができます。

操作： 整数 l（1 \leq l \leq N - K + 1）を 1 つ選び、照明 l から照明 l + K - 1 までの連続する K 個の照明すべての状態を切り替える。すなわち、点灯している照明は消灯に、消灯している照明は点灯になる。各回の操作で選ぶ l の値は自由であり、異なる回で同じ値を選んでもかまわない。

すべての照明を点灯状態にすることが可能かどうか判定し、可能な場合は必要な最小の操作回数を求めてください。

制約

1 \leq N \leq 5 \times 10^5
1 \leq K \leq N
S は長さ N の文字列であり、0 と 1 のみからなる
N, K は整数である

入力

N K
S

1 行目には、照明の個数を表す整数 N と、一度に切り替える照明の個数を表す整数 K が、スペース区切りで与えられる。
2 行目には、各照明の初期状態を表す長さ N の文字列 S が与えられる。

出力

すべての照明を点灯状態にすることが可能な場合は、必要な最小の操作回数を 1 行で出力してください。不可能な場合は -1 を出力してください。

入力例 1

5 3
00100

出力例 1

入力例 2

5 3
01000

出力例 2

-1

入力例 3

10 2
0101010101

出力例 3

-1

入力例 4

20 5
00000000001111111111

出力例 4

入力例 5

1 1
1

出力例 5

Score : 366 pts

Problem Statement

In Takahashi's room, there are N lights arranged in a horizontal row, numbered from left to right as light 1, light 2, \ldots, light N. Each light is in one of two states: "on" or "off". The initial state of each light is given by a string S. If the i-th character of S is 1, then light i is on; if it is 0, then light i is off.

Takahashi wants to turn all the lights on. He can perform the following operation any number of times (including zero times).

Operation: Choose an integer l (1 \leq l \leq N - K + 1) and toggle the states of all K consecutive lights from light l to light l + K - 1. That is, lights that are on are turned off, and lights that are off are turned on. The value of l chosen in each operation is arbitrary, and the same value may be chosen in different operations.

Determine whether it is possible to turn all the lights on, and if so, find the minimum number of operations required.

Constraints

1 \leq N \leq 5 \times 10^5
1 \leq K \leq N
S is a string of length N consisting only of 0 and 1
N, K are integers

Input

N K
S

The first line contains an integer N representing the number of lights and an integer K representing the number of lights toggled at once, separated by a space.
The second line contains a string S of length N representing the initial state of each light.

Output

If it is possible to turn all the lights on, output the minimum number of operations required in one line. If it is impossible, output -1.

Sample Input 1

5 3
00100

Sample Output 1

Sample Input 2

5 3
01000

Sample Output 2

-1

Sample Input 3

10 2
0101010101

Sample Output 3

-1

Sample Input 4

20 5
00000000001111111111

Sample Output 4

Sample Input 5

1 1
1

Sample Output 5

D - Installation of Radio Towers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、とある地域の通信インフラ整備を担当するエンジニアです。

この地域には N 個の村があり、それらは一直線の道路に沿って、互いに異なる位置に配置されています。村 i は道路の起点から X_i メートルの位置にあり、標高は P_i メートルです。2つの村 i, j の間の距離は |X_i - X_j| メートルで定義されます（標高の差は距離に影響しません）。

高橋君は、すべての村に電波を届けるために、いくつかの村に電波塔を設置することになりました。電波塔は、標高が K メートル以上の村（すなわち P_i \geq K を満たす村 i）にのみ設置できます。標高は電波塔の設置可否にのみ関係し、電波の届く範囲には影響しません。

電波塔を設置した村から距離が D メートル以下であるすべての村は、その電波塔の電波を受信できます（電波塔を設置した村自身も、距離 0 として受信できます）。距離が D メートルを超える村には電波は届きません。電波の届く最大距離 D はすべての電波塔で共通です。

すべての村は、少なくとも1つの電波塔から電波を受信できなければなりません。

高橋君は、この条件を満たしながら、設置する電波塔の数を最小化したいと考えています。条件を満たす電波塔の配置が存在する場合は、必要な電波塔の最小数を求めてください。条件を満たす配置が存在しない場合は -1 を出力してください。

条件を満たせない例としては、電波塔を設置可能な村がどこにも存在しない場合や、電波塔を設置可能な村が存在してもどの電波塔からも距離 D 以内に入らない村がある場合が挙げられます。

制約

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^9
1 \leq D \leq 10^9
0 \leq X_i \leq 10^9
1 \leq P_i \leq 10^9
X_i \neq X_j（i \neq j）
入力はすべて整数
村は位置 X_i の昇順に与えられるとは限らない

入力

N K D
X_1 P_1
X_2 P_2
\vdots
X_N P_N

1 行目には、村の数 N、電波塔を設置できる標高の下限 K、電波塔の電波が届く最大距離 D が、スペース区切りで与えられる。
2 行目から N + 1 行目では、各村の情報が与えられる。
1 + i 行目では、村 i の道路の起点からの位置 X_i と標高 P_i が、スペース区切りで与えられる。

出力

すべての村に電波を届けられるような電波塔の配置が存在する場合は、必要な電波塔の最小数を 1 行で出力してください。存在しない場合は -1 を出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

-1

入力例 3

出力例 3

Score : 400 pts

Problem Statement

Takahashi is an engineer responsible for developing the communication infrastructure of a certain region.

There are N villages in this region, placed at distinct positions along a straight road. Village i is located X_i meters from the starting point of the road and has an elevation of P_i meters. The distance between two villages i, j is defined as |X_i - X_j| meters (the difference in elevation does not affect the distance).

Takahashi needs to install radio towers in some of the villages in order to deliver radio signals to all villages. A radio tower can only be installed in a village whose elevation is at least K meters (that is, a village i satisfying P_i \geq K). Elevation only affects whether a radio tower can be installed or not, and does not affect the range of the radio signals.

All villages within a distance of D meters or less from a village where a radio tower is installed can receive the signal from that tower (the village where the tower is installed can also receive the signal, as the distance is 0). Villages at a distance exceeding D meters cannot receive the signal. The maximum signal range D is the same for all radio towers.

Every village must be able to receive a signal from at least one radio tower.

Takahashi wants to minimize the number of radio towers installed while satisfying this condition. If there exists a placement of radio towers that satisfies the condition, find the minimum number of radio towers needed. If no valid placement exists, output -1.

Examples of cases where the condition cannot be satisfied include: when there are no villages where a radio tower can be installed, or when there exists a village that cannot be within distance D of any village where a radio tower can be installed.

Constraints

1 \leq N \leq 2 \times 10^5
1 \leq K \leq 10^9
1 \leq D \leq 10^9
0 \leq X_i \leq 10^9
1 \leq P_i \leq 10^9
X_i \neq X_j (i \neq j)
All input values are integers
Villages are not necessarily given in ascending order of position X_i

Input

N K D
X_1 P_1
X_2 P_2
\vdots
X_N P_N

The first line contains the number of villages N, the minimum elevation K required to install a radio tower, and the maximum signal range D of a radio tower, separated by spaces.
From the 2nd line to the (N + 1)-th line, the information of each village is given.
The (1 + i)-th line contains the position X_i from the starting point of the road and the elevation P_i of village i, separated by spaces.

Output

If there exists a placement of radio towers that can deliver signals to all villages, output the minimum number of radio towers needed in one line. If no such placement exists, output -1.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

-1

Sample Input 3

Sample Output 3

E - Library Inventory Check

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君は大きな図書館の司書をしています。この図書館には N 個の書棚が一列に並んでおり、左から順に番号 1, 2, \ldots, N が付けられています。

書棚 i（1 \leq i \leq N）には A_i 冊の本が収められています。これらの本は現在修復作業中であり、書棚 i の本はすべて第 D_i 日目に修復が完了します。修復が完了した本は貸し出し可能となります。すなわち、書棚 i の本は第 D_i 日目以降（第 D_i 日目を含む）に貸し出すことができます。書棚 i の本が貸し出される際、利用者は本 1 冊につき V_i 円の利用料を図書館に納めます。

高橋君は Q 個の貸し出し計画を検討しています。各計画は互いに独立であり、ある計画で本が貸し出されても、他の計画には影響しません。

計画 j（1 \leq j \leq Q）では、連続する書棚の区間 [L_j, R_j]（1 \leq L_j \leq R_j \leq N）と日付 T_j が決まっています。この計画では、区間 [L_j, R_j] に含まれる書棚のうち、第 T_j 日目の時点で修復が完了しているもの（すなわち D_i \leq T_j を満たす書棚 i）について、その書棚の A_i 冊すべてが貸し出されます。修復が完了していない書棚の本は貸し出されません。

書棚 i の A_i 冊すべてが貸し出された場合、得られる利用料は A_i \times V_i 円です。

それぞれの計画について、貸し出しによって得られる利用料の合計額を求めてください。すなわち、計画 j で得られる利用料の合計額は、

\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i

です。

制約

1 \leq N
1 \leq Q
N + Q \leq 2 \times 10^5
1 \leq A_i \leq 10^4
1 \leq D_i \leq 10^5
1 \leq V_i \leq 10^4
1 \leq L_j \leq R_j \leq N
1 \leq T_j \leq 10^5
入力はすべて整数である
各計画について、答えは 2 \times 10^{13} 以下である

入力

N Q
A_1 D_1 V_1
A_2 D_2 V_2
\vdots
A_N D_N V_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q

1 行目には、書棚の数 N と貸し出し計画の数 Q がスペース区切りで与えられる。
続く N 行のうち i 行目には、書棚 i の本の冊数 A_i、修復完了日 D_i、本 1 冊あたりの利用料 V_i がスペース区切りで与えられる。
続く Q 行のうち j 行目には、計画 j の区間の左端 L_j、右端 R_j、日付 T_j がスペース区切りで与えられる。

出力

Q 行出力してください。j 行目には、計画 j で得られる利用料の合計額を整数で出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

入力例 4

30 20
10 15 100
25 3 40
7 22 500
100 1 20
13 18 70
6 9 1000
80 30 15
2 5 600
45 12 90
11 7 250
9 40 800
30 25 35
16 2 120
5 17 900
60 11 45
3 35 700
22 6 110
14 28 330
50 19 55
8 4 1000
19 23 75
4 14 650
70 8 25
12 31 400
33 10 60
1 100000 10000
90 13 30
18 21 200
27 16 85
40 24 95
1 30 10
1 30 100000
5 20 18
10 15 7
16 30 25
1 8 5
21 26 99999
26 26 100000
3 27 12
8 23 30
12 29 20
2 2 2
4 4 1
14 18 35
19 30 23
6 17 11
24 30 31
1 1 14
7 13 40
28 30 15

出力例 4

入力例 5

1 1
10000 100000 10000
1 1 99999

出力例 5

Score : 466 pts

Problem Statement

Takahashi works as a librarian at a large library. This library has N bookshelves arranged in a row, numbered 1, 2, \ldots, N from left to right.

Bookshelf i (1 \leq i \leq N) contains A_i books. These books are currently under restoration, and all books on bookshelf i will have their restoration completed on day D_i. Once restoration is complete, the books become available for lending. That is, books on bookshelf i can be lent out from day D_i onward (including day D_i). When books from bookshelf i are lent out, the user pays a fee of V_i yen per book to the library.

Takahashi is considering Q lending plans. Each plan is independent of the others; books being lent out in one plan do not affect other plans.

In plan j (1 \leq j \leq Q), a contiguous interval of bookshelves [L_j, R_j] (1 \leq L_j \leq R_j \leq N) and a date T_j are specified. In this plan, among the bookshelves in the interval [L_j, R_j], those whose restoration is complete by day T_j (i.e., bookshelves i satisfying D_i \leq T_j) will have all A_i books lent out. Books on bookshelves whose restoration is not yet complete will not be lent out.

When all A_i books on bookshelf i are lent out, the fee earned is A_i \times V_i yen.

For each plan, determine the total fee earned from the lending. That is, the total fee earned in plan j is:

\sum_{\substack{L_j \leq i \leq R_j \\ D_i \leq T_j}} A_i \times V_i

Constraints

1 \leq N
1 \leq Q
N + Q \leq 2 \times 10^5
1 \leq A_i \leq 10^4
1 \leq D_i \leq 10^5
1 \leq V_i \leq 10^4
1 \leq L_j \leq R_j \leq N
1 \leq T_j \leq 10^5
All inputs are integers
For each plan, the answer is at most 2 \times 10^{13}

Input

N Q
A_1 D_1 V_1
A_2 D_2 V_2
\vdots
A_N D_N V_N
L_1 R_1 T_1
L_2 R_2 T_2
\vdots
L_Q R_Q T_Q

The first line contains the number of bookshelves N and the number of lending plans Q, separated by a space.
In the following N lines, the i-th line contains the number of books A_i on bookshelf i, the restoration completion day D_i, and the fee per book V_i, separated by spaces.
In the following Q lines, the j-th line contains the left endpoint L_j, right endpoint R_j, and date T_j for plan j, separated by spaces.

Output

Output Q lines. On the j-th line, output the total fee earned in plan j as an integer.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Sample Input 4

30 20
10 15 100
25 3 40
7 22 500
100 1 20
13 18 70
6 9 1000
80 30 15
2 5 600
45 12 90
11 7 250
9 40 800
30 25 35
16 2 120
5 17 900
60 11 45
3 35 700
22 6 110
14 28 330
50 19 55
8 4 1000
19 23 75
4 14 650
70 8 25
12 31 400
33 10 60
1 100000 10000
90 13 30
18 21 200
27 16 85
40 24 95
1 30 10
1 30 100000
5 20 18
10 15 7
16 30 25
1 8 5
21 26 99999
26 26 100000
3 27 12
8 23 30
12 29 20
2 2 2
4 4 1
14 18 35
19 30 23
6 17 11
24 30 31
1 1 14
7 13 40
28 30 15

Sample Output 4

Sample Input 5

1 1
10000 100000 10000
1 1 99999