AtCoder Daily Training HARD 2025/08/27 18:00start

E - ~

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

整数列 A = (A_1, A_2, \ldots, A_{|A|}) に対し、A が チルダ型 とは以下の 4 つの条件をすべて満たすことであると定義します。

A の長さ |A| は 4 以上である
A_1 < A_2 である
A_{i - 1} < A_i > A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である　
A_{i - 1} > A_i < A_{i + 1} を満たす 2 \leq i < |A| なる整数 i はちょうど 1 個である

数列 (1, 2, \ldots, N) を並べ替えて得られる数列 P = (P_1, P_2, \ldots, P_N) が与えられます。P の連続部分列であってチルダ型である数列の個数を求めてください。

制約

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) は (1, 2, \ldots, N) を並べ替えて得られる数列
入力される値はすべて整数

入力

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

N
P_1 P_2 \ldots P_N

出力

答えを出力せよ。

入力例 1

6
1 3 6 4 2 5

出力例 1

数列 (1, 3, 6, 4, 2, 5) の連続部分列のうちチルダ型であるものは (3, 6, 4, 2, 5), (1, 3, 6, 4, 2, 5) の 2 つのみです。

入力例 2

6
1 2 3 4 5 6

出力例 2

入力例 3

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

出力例 3

Score : 350 points

Problem Statement

For an integer sequence A = (A_1, A_2, \ldots, A_{|A|}), we say that A is tilde-shaped if it satisfies all of the following four conditions:

The length |A| is at least 4.
A_1 < A_2.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} < A_i > A_{i+1}.
There exists exactly one integer i with 2 \leq i < |A| such that A_{i-1} > A_i < A_{i+1}.

You are given a permutation P = (P_1, P_2, \ldots, P_N) of (1, 2, \ldots, N). Find the number of (contiguous) subarrays of P that are tilde-shaped.

Constraints

4 \leq N \leq 3 \times 10^5
P = (P_1, P_2, \ldots, P_N) is a permutation of (1, 2, \ldots, N).
All input values are integers.

Input

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

N
P_1 P_2 \ldots P_N

Output

Output the answer.

Sample Input 1

6
1 3 6 4 2 5

Sample Output 1

Among the subarrays of (1, 3, 6, 4, 2, 5), exactly two are tilde-shaped: (3, 6, 4, 2, 5) and (1, 3, 6, 4, 2, 5).

Sample Input 2

6
1 2 3 4 5 6

Sample Output 2

Sample Input 3

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

Sample Output 3

F - Move It

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 250 点

問題文

1 から N の番号がついた N 個の箱と 1 から N の番号がついた N 個の荷物があります。荷物 i (1 \leq i \leq N) は箱 A_i の中にあり、重さは W_i です。

あなたは荷物を一つ選び、他の箱の中に移動させる操作を 0 回以上繰り返し行うことができます。1 回の操作で移動させる荷物の重さが w であるとき、w のコストがかかります。

全ての箱に荷物が 1 つずつ入っている状態にするためにかかるコストの総和の最小値を求めてください。

制約

1 \leq N \leq 10^{5}
1 \leq A_i \leq N (1 \leq i \leq N)
1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
入力はすべて整数

入力

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

N
A_1 A_2 \ldots A_N
W_1 W_2 \ldots W_N

出力

全ての箱に荷物が 1 つずつ入っている状態にするためにかかるコストの総和の最小値を出力せよ。

入力例 1

5
2 2 3 3 5
33 40 2 12 16

出力例 1

以下の 2 回の荷物の移動で、すべての箱に荷物が 1 つずつ入っている状態にすることができます。

荷物 1 を箱 2 から箱 1 に移す。このとき、コストは 33 である。
荷物 3 を箱 3 から箱 4 に移す。このとき、コストは 2 である。

この 2 回の荷物の移動は合計 35 のコストかかります。 35 未満のコストですべての箱に荷物が 1 つずつ入っている状態にすることはできないため、 35 を出力します。

入力例 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

出力例 2

Score : 250 points

Problem Statement

There are N boxes numbered 1 to N and N items numbered 1 to N. Item i (1 \leq i \leq N) is in box A_i and has a weight of W_i.

You can repeatedly perform the operation of choosing an item and moving it to another box zero or more times. If the weight of the item being moved is w, the cost of the operation is w.

Find the minimum total cost required to make each box contain exactly one item.

Constraints

1 \leq N \leq 10^{5}
1 \leq A_i \leq N (1 \leq i \leq N)
1 \leq W_i \leq 10^{4} (1 \leq i \leq N)
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N
W_1 W_2 \ldots W_N

Output

Print the minimum total cost required to make each box contain exactly one item.

Sample Input 1

5
2 2 3 3 5
33 40 2 12 16

Sample Output 1

With the following two moves, you can make each box contain exactly one item:

Move item 1 from box 2 to box 1. The cost is 33.
Move item 3 from box 3 to box 4. The cost is 2.

The total cost of these two moves is 35. It is impossible to make each box contain exactly one item with a cost less than 35, so print 35.

Sample Input 2

12
3 6 7 4 12 4 8 11 11 1 8 11
3925 9785 9752 3587 4013 1117 3937 7045 6437 6208 3391 6309

Sample Output 2

G - Writing a Numeral

実行時間制限: 3 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

文字列 S があり、初め S= 1 です。
以下の形式のクエリが Q 個与えられるので順に処理してください。

1 x : S の末尾に数字 x を追加する
2 : S の先頭の数字を削除する
3 : S を十進数表記の数とみなした値を 998244353 で割った余りを出力する

制約

1 \leq Q \leq 6 \times 10^5
1 番目の形式のクエリについて、x \in \{1,2,3,4,5,6,7,8,9\}
2 番目の形式のクエリは S が 2 文字以上の時にのみ与えられる
3 番目の形式のクエリが 1 個以上存在する

入力

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

Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

ただし \mathrm{query}_i は i 番目のクエリを表し、以下のいずれかの形式である。

1 x

出力

3 番目の形式のクエリの個数を q として、q 行出力せよ。i (1 \leq i \leq q) 行目には i 番目の 3 番目の形式のクエリに対する出力をせよ。

入力例 1

出力例 1

1
12

1 番目のクエリにおいて、S は 1 なので ( 1 を 998244353 で割った余りに等しい) 1 を出力します。
2 番目のクエリにおいて、S は 12 になります。
3 番目のクエリにおいて、S は 12 なので ( 12 を 998244353 で割った余りに等しい) 12 を出力します。

入力例 2

出力例 2

入力例 3

出力例 3

出力されるべき値は 998244353 で割った余りであることに注意してください。

Score : 400 points

Problem Statement

We have a string S. Initially, S= 1.
Process Q queries in the following formats in order.

1 x : Append a digit x at the end of S.
2 : Delete the digit at the beginning of S.
3 : Print the number represented by S in decimal, modulo 998244353.

Constraints

1 \leq Q \leq 6 \times 10^5
For each query in the first format, x \in \{1,2,3,4,5,6,7,8,9\}.
A query in the second format is given only if S has a length of 2 or greater.
There is at least one query in the third format.

Input

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

Q
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Here, \mathrm{query}_i denotes the i-th query, which is in one of the following formats:

1 x

Output

Print q lines, where q is the number of queries in the third format. The i-th line (1 \leq i \leq q) should correspond to the i-th query in the third format.

Sample Input 1

Sample Output 1

1
12

In the first query, S is 1, so you should print 1 modulo 998244353, that is, 1.
In the second query, S becomes 12.
In the third query, S is 12, so you should print 12 modulo 998244353, that is, 12.

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

Be sure to print numbers modulo 998244353.

H - Max/Min

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 475 点

問題文

長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。

\displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor を求めてください。

ただし、\lfloor x \rfloor は x 以下の最大の整数を表します。例えば、\lfloor 3.14 \rfloor=3、\lfloor 2 \rfloor=2 です。

制約

2 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
入力は全て整数である

入力

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

N
A_1 \ldots A_N

出力

答えを出力せよ。

入力例 1

3
3 1 4

出力例 1

求める値は

\left\lfloor\frac{\max(3,1)}{\min(3,1)}\right\rfloor + \left\lfloor\frac{\max(3,4)}{\min(3,4)}\right\rfloor + \left\lfloor\frac{\max(1,4)}{\min(1,4)}\right\rfloor\\ =\left\lfloor\frac{3}{1}\right\rfloor + \left\lfloor\frac{4}{3}\right\rfloor + \left\lfloor\frac{4}{1}\right\rfloor\\ =3+1+4\\ =8

となります。

入力例 2

6
2 7 1 8 2 8

出力例 2

入力例 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

出力例 3

Score : 475 points

Problem Statement

You are given a sequence A=(A_1,\ldots,A_N) of length N.

Find \displaystyle \sum_{i=1}^{N-1}\sum_{j=i+1}^{N}\left\lfloor\frac{\max(A_i,A_j)}{\min(A_i,A_j)}\right\rfloor.

Here, \lfloor x \rfloor represents the greatest integer not greater than x. For example, \lfloor 3.14 \rfloor=3 and \lfloor 2 \rfloor=2.

Constraints

2 \leq N \leq 2\times 10^5
1 \leq A_i \leq 10^6
All input values are integers.

Input

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

N
A_1 \ldots A_N

Output

Print the answer.

Sample Input 1

3
3 1 4

Sample Output 1

The sought value is

Sample Input 2

6
2 7 1 8 2 8

Sample Output 2

Sample Input 3

12
3 31 314 3141 31415 314159 2 27 271 2718 27182 271828

Sample Output 3

I - Erase and Rotate

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 500 点

問題文

1,2,\ldots,N がちょうど 1 回ずつ現れる数列 P = (p_1,p_2,\ldots,p_N) が与えられます。
あなたは以下の操作のうち 1 つを選んで行うことを 0 回以上 K 回以下繰り返せます。

P の項を 1 つ選び、削除する。
P の末尾の項を先頭に移動させる。

操作後の P として考えられるもののうち辞書順で最小のものを求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq K \leq N-1
1 \leq p_i \leq N
(p_1,p_2,\ldots,p_N) には 1,2,\ldots,N がちょうど 1 回ずつ現れる。
入力はすべて整数

入力

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

N K
p_1 p_2 \ldots p_N

出力

操作後の P として考えられるもののうち辞書順で最小のものを空白区切りで出力せよ。

入力例 1

5 3
4 5 2 3 1

出力例 1

1 2 3

以下のように操作をすると P は (1,2,3) になります。

先頭の項を削除する。これによって P は (5,2,3,1) になる。
末尾の項を先頭に移動させる。これによって P は (1,5,2,3) になる。
先頭から 2 番目の項を削除する。これによって P は (1,2,3) になる。

また、辞書順で (1,2,3) より小さい数列は操作後の P として考えられません。よってこれが答えです。

入力例 2

3 0
3 2 1

出力例 2

3 2 1

操作を 1 回も行えない場合があります。

入力例 3

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

出力例 3

1 3 4 7 2 8 11 9

Score : 500 points

Problem Statement

You are given a sequence P = (p_1,p_2,\ldots,p_N) that contains 1,2,\ldots,N exactly once each.
You may perform the following operations between 0 and K times in total in any order:

Choose one term of P and remove it.
Move the last term of P to the head.

Find the lexicographically smallest P that can be obtained as a result of the operations.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq K \leq N-1
1 \leq p_i \leq N
(p_1,p_2,\ldots,p_N) contains 1,2,\ldots,N exactly once each.
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
p_1 p_2 \ldots p_N

Output

Print the lexicographically smallest P that can be obtained as a result of the operations, separated by spaces.

Sample Input 1

5 3
4 5 2 3 1

Sample Output 1

1 2 3

The following operations make P equal (1,2,3).

Removing the first term makes P equal (5,2,3,1).
Moving the last term to the head makes P equal (1,5,2,3).
Removing the second term makes P equal (1,2,3).

There is no way to obtain P lexicographically smaller than (1,2,3), so this is the answer.

Sample Input 2

3 0
3 2 1

Sample Output 2

3 2 1

You may be unable to perform operations.

Sample Input 3

15 10
12 10 7 2 8 11 9 1 6 14 3 15 13 5 4

Sample Output 3

1 3 4 7 2 8 11 9