AtCoder Daily Training HARD 2024/02/27 19:30start

E - RANDOM

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。

S の列を並べ替えて T と等しくできるか判定してください。

但し、図形 X の列を並べ替えるとは、以下の操作を言います。

(1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
- 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。

制約

H,W は整数
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i,T_i は # と . からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

出力

S を T と等しくできるなら Yes 、そうでないなら No と出力せよ。

入力例 1

3 4
##.#
##..
#...
.###
..##
...#

出力例 1

Yes

例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。

入力例 2

3 3
#.#
.#.
#.#
##.
##.
.#.

出力例 2

No

この入力では、 S を T と等しくすることができません。

入力例 3

2 1
#
.
#
.

出力例 3

Yes

S=T である場合もあります。

入力例 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

出力例 4

Yes

Score : 300 points

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
- For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

H and W are integers.
1 \le H,W
1 \le H \times W \le 4 \times 10^5
S_i and T_i are strings of length W consisting of # and ..

Input

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

Output

If S can be made equal to T, print Yes; otherwise, print No.

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes

F - Peak

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

高橋くんは数直線上に N 個のプレゼントを置きました。そのうち i 個目のプレゼントは座標 A_i に置かれました。

あなたは数直線上の長さ M の半開区間 [x,x+M) を選び、そこに含まれるプレゼントを全て獲得します。
より詳しくは、以下の手順でプレゼントを獲得します。

まず、実数 x をひとつ選択する。
その後、プレゼントのうち置かれている座標が x \le A_i < x+M を満たすものを全て獲得する。

最大でいくつのプレゼントを獲得することができますか?

制約

入力は全て整数
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
0 \le A_i \le 10^9

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを整数として出力せよ。

入力例 1

8 6
2 3 5 7 11 13 17 19

出力例 1

例えば、半開区間 [1.5,7.5) を指定します。
このとき、座標 2,3,5,7 にある 4 つのプレゼントを全て獲得することができ、これが獲得可能な最大の個数です。

入力例 2

10 1
3 1 4 1 5 9 2 6 5 3

出力例 2

同一の座標に複数のプレゼントが置いてあることもあります。

入力例 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

出力例 3

Score : 300 points

Problem Statement

Takahashi has placed N gifts on a number line. The i-th gift is placed at coordinate A_i.

You will choose a half-open interval [x,x+M) of length M on the number line and acquire all the gifts included in it.
More specifically, you acquire gifts according to the following procedure.

First, choose one real number x.
Then, acquire all the gifts whose coordinates satisfy x \le A_i < x+M.

What is the maximum number of gifts you can acquire?

Constraints

All input values are integers.
1 \le N \le 3 \times 10^5
1 \le M \le 10^9
0 \le A_i \le 10^9

Input

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

N M
A_1 A_2 \dots A_N

Output

Print the answer as an integer.

Sample Input 1

8 6
2 3 5 7 11 13 17 19

Sample Output 1

For example, specify the half-open interval [1.5,7.5).
In this case, you can acquire the four gifts at coordinates 2,3,5,7, the maximum number of gifts that can be acquired.

Sample Input 2

10 1
3 1 4 1 5 9 2 6 5 3

Sample Output 2

There may be multiple gifts at the same coordinate.

Sample Input 3

10 998244353
100000007 0 1755647 998244353 495 1000000000 1755648 503 1755649 998244853

Sample Output 3

G - Iroha and Haiku (New ABC Edition)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

長さ N の数列 A=(A_0,\ldots,A_{N-1}) があります。
次の条件を全て満たす整数の組 (x,y,z,w) が存在するか判定してください。

0 \leq x < y < z < w \leq N
A_x + A_{x+1} + \ldots + A_{y-1} = P
A_y + A_{y+1} + \ldots + A_{z-1} = Q
A_z + A_{z+1} + \ldots + A_{w-1} = R

制約

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq P,Q,R \leq 10^{15}
入力に含まれる値は全て整数である

入力

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

N P Q R
A_0 A_1 \ldots A_{N-1}

出力

条件を満たす組が存在するなら Yes、存在しないなら No を出力せよ。

入力例 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

出力例 1

Yes

(x,y,z,w)=(1,3,6,8) が条件を満たします。

入力例 2

9 100 101 100
31 41 59 26 53 58 97 93 23

出力例 2

No

入力例 3

7 1 1 1
1 1 1 1 1 1 1

出力例 3

Yes

Score : 400 points

Problem Statement

There is a sequence A=(A_0,\ldots,A_{N-1}) of length N.
Determine if there exists a tuple of integers (x,y,z,w) that satisfies all of the following conditions:

0 \leq x < y < z < w \leq N
A_x + A_{x+1} + \ldots + A_{y-1} = P
A_y + A_{y+1} + \ldots + A_{z-1} = Q
A_z + A_{z+1} + \ldots + A_{w-1} = R

Constraints

3 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^9
1 \leq P,Q,R \leq 10^{15}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N P Q R
A_0 A_1 \ldots A_{N-1}

Output

If there exists a tuple that satisfies the conditions, print Yes; otherwise, print No.

Sample Input 1

10 5 7 5
1 3 2 2 2 3 1 4 3 2

Sample Output 1

Yes

(x,y,z,w)=(1,3,6,8) satisfies the conditions.

Sample Input 2

9 100 101 100
31 41 59 26 53 58 97 93 23

Sample Output 2

No

Sample Input 3

7 1 1 1
1 1 1 1 1 1 1

Sample Output 3

Yes

H - Addition and Multiplication 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

高橋君は整数 x を持っています。最初 x=0 です。

高橋君は以下の操作を好きな回数行えます。

整数 i\ (1\leq i \leq 9) を選ぶ。 C_i 円払い、x を 10x + i で置き換える。

高橋君の予算は N 円です。操作で支払うお金の総和が予算を超過しないように操作を行うとき、最終的に得られる x の最大値を求めてください。

制約

1 \leq N \leq 10^6
1 \leq C_i \leq N
入力は全て整数

入力

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

N
C_1 C_2 \ldots C_9

出力

答えを出力せよ。

入力例 1

5
5 4 3 3 2 5 3 5 3

出力例 1

例えば i = 9 とする操作、i=5 とする操作を順に行うことで、x は以下のように変化します。

0 \rightarrow 9 \rightarrow 95

操作により支払うお金の合計は C_9 + C_5 = 3 + 2 = 5 円であり、これは予算を超過しません。予算を超過しないような操作の方法によって 96 以上の整数を作ることが不可能であることが証明できるので、答えは 95 です。

入力例 2

20
1 1 1 1 1 1 1 1 1

出力例 2

99999999999999999999

答えが 64 bit整数型に収まらないこともあることに注意してください。

Score : 500 points

Problem Statement

Takahashi has an integer x. Initially, x=0.

Takahashi may do the following operation any number of times.

Choose an integer i\ (1\leq i \leq 9). Pay C_i yen (the currency in Japan) to replace x with 10x + i.

Takahashi has a budget of N yen. Find the maximum possible value of the final x resulting from operations without exceeding the budget.

Constraints

1 \leq N \leq 10^6
1 \leq C_i \leq N
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
C_1 C_2 \ldots C_9

Output

Print the answer.

Sample Input 1

5
5 4 3 3 2 5 3 5 3

Sample Output 1

For example, the operations where i = 9 and i=5 in this order change x as:

0 \rightarrow 9 \rightarrow 95.

The amount of money required for these operations is C_9 + C_5 = 3 + 2 = 5 yen, which does not exceed the budget. Since we can prove that we cannot make an integer greater than or equal to 96 without exceeding the budget, the answer is 95.

Sample Input 2

20
1 1 1 1 1 1 1 1 1

Sample Output 2

99999999999999999999

Note that the answer may not fit into a 64-bit integer type.

I - Vouchers

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 500 点

問題文

あなたは店で N 個の商品を買おうとしています。 i 個目の商品の定価は P_i 円です。

また、あなたは M 枚のクーポンを持っています。i 枚目のクーポンを使うと、定価が L_i 円以上の商品を一つ選び、その商品を定価より D_i 円低い価格で買うことができます。

ここで、一つのクーポンは一回までしか使えません。また、複数のクーポンを同じ商品に重ねて使うことはできません。

クーポンを使わなかった商品は定価で買うことになります。 N 個すべての商品を買うのに必要な最小の金額を求めてください。

制約

1\leq N,M\leq 2\times 10^5
1\leq P_i\leq 10^9
1\leq D_i \leq L_i \leq 10^9
入力される数値は全て整数

入力

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

N M
P_1 \ldots P_N
L_1 \ldots L_M
D_1 \ldots D_M

出力

答えを整数として出力せよ。

入力例 1

出力例 1

2 枚目のクーポンを 1 個目の商品に、 3 枚目のクーポンを 2 個目の商品に使うことを考えます。

このとき、1 個目の商品を 4-3=1 円、2 個目の商品を 3-1=2 円、3 個目の商品を 1 円で買うことになるので、 1+2+1=4 円で全ての商品を買うことができます。

入力例 2

10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2

出力例 2

Score : 500 points

Problem Statement

You are in a store to buy N items. The regular price of the i-th item is P_i yen (the currency in Japan).

You have M coupons. You can use the i-th coupon to buy an item whose regular price is at least L_i yen at a D_i-yen discount.

Here, each coupon can be used only once. Besides, multiple coupons cannot be used for the same item.

If no coupon is used for an item, you will buy it for a regular price. Find the minimum possible total amount of money required to buy all the N items.

Constraints

1\leq N,M\leq 2\times 10^5
1\leq P_i\leq 10^9
1\leq D_i \leq L_i \leq 10^9
All input values are integers.

Input

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

N M
P_1 \ldots P_N
L_1 \ldots L_M
D_1 \ldots D_M

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Consider using the 2-nd coupon for the 1-st item, and the 3-rd coupon for the 2-nd item.

Then, you buy the 1-st item for 4-3=1 yen, 2-nd item for 3-1=2 yen, and 3-rd item for 1 yen. Thus, you can buy all the items for 1+2+1=4 yen.

Sample Input 2

10 5
9 7 1 5 2 2 5 5 7 6
7 2 7 8 2
3 2 4 1 2