AtCoder Daily Training HARD 2024/04/03 20:00start

E - Min Max Pair

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

1 以上 N 以下の整数からなる長さ N の数列 a = (a_1, \dots, a_N) が与えられます。

以下の条件を全て満たす整数 i, j の組の総数を求めてください。

1 \leq i \lt j \leq N
\min(a_i, a_j) = i
\max(a_i, a_j) = j

制約

2 \leq N \leq 5 \times 10^5
1 \leq a_i \leq N \, (1 \leq i \leq N)
入力は全て整数

入力

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

N
a_1 \ldots a_N

出力

答えを出力せよ。

入力例 1

4
1 3 2 4

出力例 1

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

入力例 2

10
5 8 2 2 1 6 7 2 9 10

出力例 2

Score : 300 points

Problem Statement

You are given a sequence a = (a_1, \dots, a_N) of length N consisting of integers between 1 and N.

Find the number of pairs of integers i, j that satisfy all of the following conditions:

1 \leq i \lt j \leq N
\min(a_i, a_j) = i
\max(a_i, a_j) = j

Constraints

2 \leq N \leq 5 \times 10^5
1 \leq a_i \leq N \, (1 \leq i \leq N)
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
a_1 \ldots a_N

Output

Print the answer.

Sample Input 1

4
1 3 2 4

Sample Output 1

(i, j) = (1, 4), (2, 3) satisfy the conditions.

Sample Input 2

10
5 8 2 2 1 6 7 2 9 10

Sample Output 2

F - PC on the Table

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋君は部屋に PC を沢山置こうとしています。そこで最大何台の PC を部屋に置けるか調べるプログラムを書くことにしました。

H 個の長さ W の ., T からなる文字列 S_1,S_2,\ldots,S_H が与えられます。

高橋君は以下の操作を 0 回以上何回でも行うことができます。

1\leq i \leq H, 1 \leq j \leq W-1 を満たす整数であって、 S_i の j 番目の文字も j+1 番目の文字も T であるようなものを選ぶ。 S_i の j 番目の文字を P で置き換え、S_i の j+1 番目の文字を C で置き換える。

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を出力してください。

制約

1\leq H \leq 100
2\leq W \leq 100
H と W は整数である
S_i は ., T からなる長さ W の文字列

入力

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

H W 
S_1
S_2
\vdots
S_H

出力

高橋君が操作回数の最大化を目指すとき、操作終了後の S_1,S_2,\ldots,S_H としてあり得るものの一例を改行区切りで出力せよ。

解が複数存在する場合、どれを出力しても正答とみなされる。

入力例 1

2 3
TTT
T.T

出力例 1

PCT
T.T

可能な操作回数の最大値は 1 です。

例えば、 (i,j)=(1,1) として操作を行うと、S_1 が PCT に変化します。

入力例 2

3 5
TTT..
.TTT.
TTTTT

出力例 2

PCT..
.PCT.
PCTPC

Score : 300 points

Problem Statement

Planning to place many PCs in his room, Takahashi has decided to write a code that finds how many PCs he can place in his room.

You are given H strings S_1,S_2,\ldots,S_H, each of length W, consisting of . and T.

Takahashi may perform the following operation any number of times (possibly zero):

Choose integers satisfying 1\leq i \leq H and 1 \leq j \leq W-1 such that the j-th and (j+1)-th characters of S_i are both T. Replace the j-th character of S_i with P, and (j+1)-th with C.

He tries to maximize the number of times he performs the operation. Find possible resulting S_1,S_2,\ldots,S_H.

Constraints

1\leq H \leq 100
2\leq W \leq 100
H and W are integers.
S_i is a string of length W consisting of . and T.

Input

The input is given from Standard Input in the following format:

H W 
S_1
S_2
\vdots
S_H

Output

Print a sequence of strings, S_1,S_2,\ldots,S_H, separated by newlines, possibly resulting from maximizing the number of times he performs the operation.

If multiple solutions exist, print any of them.

Sample Input 1

2 3
TTT
T.T

Sample Output 1

PCT
T.T

He can perform the operation at most once.

For example, an operation with (i,j)=(1,1) makes S_1 PCT.

Sample Input 2

3 5
TTT..
.TTT.
TTTTT

Sample Output 2

PCT..
.PCT.
PCTPC

G - Union of Interval

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

実数 L,R に対して、L 以上 R 未満からなる実数の集合を [L,R) と表します。このような形で表される集合を右半開区間といいます。

N 個の右半開区間 [L_i,R_i) が与えられます。これらの和集合を S とします。S を最小の個数の右半開区間の和集合として表してください。

制約

1 \leq N \leq 2\times 10^5
1 \leq L_i \lt R_i \leq 2\times 10^5
入力に含まれる値は全て整数である

入力

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

N
L_1 R_1
\vdots
L_N R_N

出力

S が最小で k 個の右半開区間の和集合で表せるとする。そのような k 個の右半開区間 [X_i,Y_i) を X_i の昇順で以下のように k 行出力せよ。

X_1 Y_1
\vdots
X_k Y_k

入力例 1

出力例 1

10 30
40 50

3 つの右半開区間 [10,20),[20,30),[40,50) の和集合は 2 つの右半開区間 [10,30),[40,50) の和集合と等しくなります。

入力例 2

出力例 2

10 60

3 つの右半開区間 [10,40),[30,60),[20,50) の和集合は 1 つの右半開区間 [10,60) と等しくなります。

Score : 400 points

Problem Statement

For real numbers L and R, let us denote by [L,R) the set of real numbers greater than or equal to L and less than R. Such a set is called a right half-open interval.

You are given N right half-open intervals [L_i,R_i). Let S be their union. Represent S as a union of the minimum number of right half-open intervals.

Constraints

1 \leq N \leq 2\times 10^5
1 \leq L_i \lt R_i \leq 2\times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
L_1 R_1
\vdots
L_N R_N

Output

Let k be the minimum number of right half-open intervals needed to represent S as their union. Print k lines containing such k right half-open intervals [X_i,Y_i) in ascending order of X_i, as follows:

X_1 Y_1
\vdots
X_k Y_k

Sample Input 1

Sample Output 1

10 30
40 50

The union of the three right half-open intervals [10,20),[20,30),[40,50) equals the union of two right half-open intervals [10,30),[40,50).

Sample Input 2

Sample Output 2

10 60

The union of the three right half-open intervals [10,40),[30,60),[20,50) equals the union of one right half-open interval [10,60).

H - Packing Under Range Regulations

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

T 個のテストケースについて、以下の問題を解いてください。

1,2,\dots,10^9 の番号がついた 10^9 個の箱と、 1,2,\dots,N の番号がついた N 個のボールがあります。
それぞれの箱に入れることのできるボールの個数は多くとも 1 個です。
以下の条件を満たすように、 N 個のボールを全て箱に入れることができるか判定してください。

全ての 1 以上 N 以下の整数 i について、番号 i のボールが L_i 以上 R_i 以下の番号がついた箱に入っている。

制約

1 \le T \le 2 \times 10^5
1 \le N \le 2 \times 10^5
1 \le L_i \le R_i \le 10^9
1 つの入力に含まれるテストケースについて、それらの N の総和は 2 \times 10^5 を超えない。

入力

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

その後、 T 個のテストケースが続く。各テストケースは以下の形式で与えられる。

N
L_1 R_1
L_2 R_2
\dots
L_N R_N

出力

出力は T 行からなる。
i(1 \le i \le T) 行目には、 i 番目に入力されたテストケースについて、問題文中の条件を満たすように N 個のボールを全て箱に入れることができるなら Yes 、そうでないなら No と出力せよ。
なお、正誤判定器は英大文字と英小文字を区別せず、どちらも受理する。

入力例 1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

出力例 1

Yes
No

この入力には 2 つのテストケースが含まれます。

1 つ目のテストケースについて、以下のようにボールを箱に入れると、問題文中の条件を満たすように 3 個のボールを全て箱に入れることができるので、 Yes と出力します。
- ボール 1 を箱 1 に入れる。
- ボール 2 を箱 2 に入れる。
- ボール 3 を箱 3 に入れる。
2 つ目のテストケースについて、問題文中の条件を満たすように 5 個のボールを全て箱に入れることはできないので、 No と出力します。

Score : 500 points

Problem Statement

Solve the following problem for T test cases.

There are 10^9 boxes numbered 1,2,\dots,10^9 and N balls numbered 1,2,\dots,N.
Each box can contain at most one ball.
Determine whether it is possible to put all N balls in the boxes so that the following condition will be satisfied.

For each integer i from 1 through N, the ball numbered i is in a box numbered between L_i and R_i (inclusive).

Constraints

1 \le T \le 2 \times 10^5
1 \le N \le 2 \times 10^5
1 \le L_i \le R_i \le 10^9
The sum of N across the test cases in one input is at most 2 \times 10^5.

Input

Input is given from Standard Input. The first line is in the following format:

Then, T test cases follows, each of which is in the following format:

N
L_1 R_1
L_2 R_2
\dots
L_N R_N

Output

Your output should have T lines.
In the i-th (1 \le i \le T) line, print Yes if it is possible to put all N balls in the boxes so that the condition will be satisfied in the i-th test case in the input, and printNo otherwise.
The checker is case-insensitive; it will accept both uppercase and lowercase letters.

Sample Input 1

2
3
1 2
2 3
3 3
5
1 2
2 3
3 3
1 3
999999999 1000000000

Sample Output 1

Yes
No

This input contains two test cases.

In the 1-st test case, the following way to put the three balls would satisfy the condition, so we should print Yes.
- Put Ball 1 in Box 1.
- Put Ball 2 in Box 2.
- Put Ball 3 in Box 3.
In the 2-nd test case, there is no way to put the five balls to satisfy the condition, so we should print No.

I - Sensor Optimization Dilemma

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

キーエンスの工場長であるあなたは、ベルトコンベア上のいくつかの区間をセンサーによって監視したいと考えています。あなたが監視したい区間は全部で N 個あり、i 個目の区間の長さは D_i メートルです。

センサーには 2 種類の候補があり、それぞれのセンサーに関する情報は以下の通りです。

センサー j\ (1\leq j \leq 2) : 長さ L_j メートルの区間を監視できる。価格は 1 個あたり C_j であり、全体で最大 K_j 個まで使用することができる。

1 つの区間をいくつかの区間に分割して監視することもできます。また、センサーが監視する区間が重なっていたり、監視したい区間の長さより余分に監視していたりしても問題はありません。例えば、L_1=4,L_2=2 であるとき、センサー 1 を 1 つ使って長さ 3 メートルの区間を監視したり、センサー 1,2 を 1 つずつ使って長さ 5 メートルの区間を監視したりすることが可能です。

N 個の区画をすべて監視することが可能であるか判定し、可能ならば必要なセンサーの価格の総和の最小値を求めてください。

制約

1\leq N \leq 100
1\leq D_i,L_j \leq 10^5
1\leq C_j \leq 10^9
1\leq K_j \leq 10^3
入力は全て整数

入力

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

N
D_1 D_2 \dots D_N
L_1 C_1 K_1
L_2 C_2 K_2

出力

N 個の区画をすべて監視することが不可能ならば -1 を、可能ならば必要なセンサーの価格の総和の最小値を出力せよ。

入力例 1

出力例 1

以下のようにすることで、センサー 1 を 3 つ、センサー 2 を 4 つ使ってすべての区間を監視できます。

センサー 1 を 1 つ使って 1 個目の区間を監視する。
センサー 1,2 を 1 つずつ使って 2 個目の区間を監視する。
センサー 1 を 1 つ、センサー 2 を 3 つ使って 3 個目の区間を監視する。

このとき、必要なセンサーの価格の総和は 3\times 3 + 2\times 4 = 17 であり、これが最小です。

入力例 2

出力例 2

-1

入力例 3

2
4 8
3 1 100
4 10000 100

出力例 3

1 つも使わない種類のセンサーがあっても構いません。

Score : 500 points

Problem Statement

As the factory manager of Keyence, you want to monitor several sections on a conveyor belt. There are a total of N sections you want to monitor, and the length of the i-th section is D_i meters.

There are two types of sensors to choose from, and below is some information about each sensor.

Type-j sensor (1\leq j \leq 2): Can monitor a section of length L_j meters. The price is C_j per sensor, and you can use at most K_j sensors of this type in total.

You can divide one section into several sections for monitoring. It is fine if the sections monitored by the sensors overlap, or if they monitor more than the length of the section you want to monitor. For example, when L_1=4 and L_2=2, you can use one type-1 sensor to monitor a section of length 3 meters, or use one type-1 and one type-2 sensor to monitor a section of length 5 meters.

Determine whether it is possible to monitor all N sections, and if it is possible, find the minimum total cost of the necessary sensors.

Constraints

1\leq N \leq 100
1\leq D_i,L_j \leq 10^5
1\leq C_j \leq 10^9
1\leq K_j \leq 10^3
All input values are integers.

Input

The input is given from Standard Input in the following format:

N
D_1 D_2 \dots D_N
L_1 C_1 K_1
L_2 C_2 K_2

Output

If it is impossible to monitor all N sections, print -1. Otherwise, print the minimum total cost of the necessary sensors.

Sample Input 1

Sample Output 1

You can monitor all sections by using three type-1 sensors and four type-2 sensors as follows.

Use one type-1 sensor to monitor the first section.
Use one type-1 and one type-2 sensor to monitor the second section.
Use one type-1 and three type-2 sensors to monitor the third section.

In this case, the total cost of the necessary sensors is 3\times 3 + 2\times 4 = 17, which is the minimum.

Sample Input 2

Sample Output 2

-1

Sample Input 3

2
4 8
3 1 100
4 10000 100

Sample Output 3

It is fine if one type of sensor is not used at all.