AtCoder Daily Training HARD 2024/03/26 17:30start

E - Four Variables

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

配点 : 300 点

問題文

正整数 N が与えられます。
正整数の組 (A,B,C,D) であって、AB + CD = N を満たすものの個数を求めてください。

なお、本問の制約の下、答えが 9 \times 10^{18} 以下であることが証明できます。

制約

2 \leq N \leq 2 \times 10^5
N は整数

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

(A,B,C,D) として以下の 8 個が考えられます。

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)

入力例 2

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a positive integer N.
Find the number of quadruples of positive integers (A,B,C,D) such that AB + CD = N.

Under the constraints of this problem, it can be proved that the answer is at most 9 \times 10^{18}.

Constraints

2 \leq N \leq 2 \times 10^5
N is an integer.

Input

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

Output

Print the answer.

Sample Input 1

Sample Output 1

Here are the eight desired quadruples.

(A,B,C,D)=(1,1,1,3)
(A,B,C,D)=(1,1,3,1)
(A,B,C,D)=(1,2,1,2)
(A,B,C,D)=(1,2,2,1)
(A,B,C,D)=(1,3,1,1)
(A,B,C,D)=(2,1,1,2)
(A,B,C,D)=(2,1,2,1)
(A,B,C,D)=(3,1,1,1)

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

F - Loong Tracking

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

配点 : 300 点

問題文

高橋君は座標平面上で龍を操作するゲームを作成しました。

龍は 1 から N までの番号がついた N 個のパーツからなり、パーツ 1 を頭と呼びます。

最初パーツ i は座標 (i,0) にあります。以下のクエリを Q 個処理してください。

1 C: 頭を方向 C に 1 移動させる。ここで、C は R, L, U, D のいずれかであり、それぞれ x 軸正方向、x 軸負方向、y 軸正方向、y 軸負方向を意味する。頭以外の全てのパーツは前のパーツに追従するように動く。すなわち、パーツ i\ \ (2\leq i \leq N) は移動前にパーツ i-1 があった座標に移動する。
2 p: パーツ p のある座標を求める。

制約

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
1 種類目のクエリにおいて、C は R, L, U, D のいずれか
2 種類目のクエリにおいて、1\leq p \leq N
入力に含まれる数値は全て整数

入力

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

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

各クエリは以下の 2 種類のいずれかの形式である。

1 C

2 p

出力

2 種類目のクエリの回数を q として q 行出力せよ。
i 行目には、i 番目のそのようなクエリに対する答えの座標を (x,y) としたとき、x,y を空白区切りで出力せよ。

入力例 1

出力例 1

2 種類目のクエリを処理する各タイミングにおいて、パーツの位置は次のようになっています。

複数のパーツが同じ座標に存在しうることに注意してください。

Score : 300 points

Problem Statement

Takahashi has created a game where the player controls a dragon on a coordinate plane.

The dragon consists of N parts numbered 1 to N, with part 1 being called the head.

Initially, part i is located at the coordinates (i,0). Process Q queries as follows.

1 C: Move the head by 1 in direction C. Here, C is one of R, L, U, and D, which represent the positive x-direction, negative x-direction, positive y-direction, and negative y-direction, respectively. Each part other than the head moves to follow the part in front of it. That is, part i (2\leq i \leq N) moves to the coordinates where part i-1 was before the move.
2 p: Find the coordinates of part p.

Constraints

2 \leq N \leq 10^6
1 \leq Q \leq 2\times 10^5
For the first type of query, C is one of R, L, U, and D.
For the second type of query, 1\leq p \leq N.
All numerical input values are integers.

Input

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

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

Each query is in one of the following two formats:

1 C

2 p

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain x and y separated by a space, where (x,y) are the answer to the i-th such query.

Sample Input 1

Sample Output 1

At each time when processing the second type of query, the parts are at the following positions:

Note that multiple parts may exist at the same coordinates.

G - Project Planning

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

配点 : 400 点

問題文

キーエンスには N 個の部署があり、i\,(1 \leq i \leq N) 番目の部署には A_i 人の社員が所属しています。異なる部署に同じ社員が所属していることはありません。

キーエンスは、部署をまたいだ全社横断プロジェクトを計画しています。1 つのプロジェクトは K 個の相異なる部署から 1 人ずつ選出して作り、ちょうど K 人から構成されるようにします。

プロジェクトは最大でいくつ作れますか？ただし、1 人が複数のプロジェクトに参加することはできません。

制約

1 \leq K \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^{12}
入力は全て整数

入力

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

N K
A_1 A_2 \ldots A_N

出力

プロジェクトの個数の最大値を出力せよ。

入力例 1

3 3
2 3 4

出力例 1

3 個の部署それぞれから 1 人ずつ選出したプロジェクトを 2 つ作ることができます。

入力例 2

4 2
1 1 3 4

出力例 2

入力例 3

4 3
1 1 3 4

出力例 3

Score : 400 points

Problem Statement

KEYENCE has N departments, where A_i employees belong to the i-th department (1 \leq i \leq N). No employee belongs to multiple departments.

The company is planning cross-departmental projects. Each project will be composed of exactly K employees chosen from K distinct departments.

At most how many projects can be made? No employee can participate in multiple projects.

Constraints

1 \leq K \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^{12}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \ldots A_N

Output

Print the maximum possible number of projects.

Sample Input 1

3 3
2 3 4

Sample Output 1

There can be two projects, each composed of three employees from distinct departments.

Sample Input 2

4 2
1 1 3 4

Sample Output 2

Sample Input 3

4 3
1 1 3 4

Sample Output 3

H - Alternating String

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

配点 : 450 点

問題文

0 と 1 のみからなる文字列であって、文字列中のどの連続する 2 文字も異なるようなものを 良い文字列 とよびます。
0 と 1 のみからなる長さ N の文字列 S が与えられます。 Q 個のクエリが与えられるので、順に処理してください。
クエリは次の 2 種類です。

1 L R : S の L 文字目から R 文字目までの 0 と 1 を反転させる。すなわち、L\leq i\leq R をみたす整数 i について、S の i 文字目が 0 ならば 1 に、1 ならば 0 に変更する。
2 L R : S の L 文字目から R 文字目までを（順番を変えずに）抜き出した長さ (R-L+1) の文字列を S' とする。S' が良い文字列ならば Yes を、そうでないならば No を出力する。

制約

1\leq N, Q\leq 5\times 10^5
S は 0 と 1 のみからなる長さ N の文字列
1,2 種類目のクエリについて、1\leq L\leq R\leq N
2 種類目のクエリが少なくとも 1 つ存在する。
N, Q, L, R は整数

入力

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

N Q
S
query_1
query_2
\vdots
query_Q

各クエリ query_i (1\leq i\leq Q) は、

1 L R

または、

2 L R

の形で与えられる。

出力

2 種類目のクエリの数を K 個として、K 行出力せよ。
i 行目には i 個目の 2 種類目のクエリに対する出力を出力せよ。

入力例 1

出力例 1

Yes
No
Yes
No

最初、S=10100 です。このとき、クエリを与えられた順に処理すると以下のようになります。

1 番目のクエリについて、S の 1 文字目から 3 文字目までを抜き出した文字列は S'=101 です。これは良い文字列なので Yes を出力します。
2 番目のクエリについて、S の 1 文字目から 5 文字目までを抜き出した文字列は S'=10100 です。これは良い文字列でないので No を出力します。
3 番目のクエリについて、S の 1 文字目から 4 文字目までの 0 と 1 を反転させます。文字列 S は S=01010 となります。
4 番目のクエリについて、S の 1 文字目から 5 文字目までを抜き出した文字列は S'=01010 です。これは良い文字列なので Yes を出力します。
5 番目のクエリについて、S の 3 文字目の 0 と 1 を反転させます。文字列 S は S=01110 となります。
6 番目のクエリについて、S の 2 文字目から 4 文字目までを抜き出した文字列は S'=111 です。これは良い文字列でないので No を出力します。

入力例 2

出力例 2

Yes

0 または 1 の 1 文字からなる文字列は良い文字列の条件をみたすことに注意してください。

Score: 450 points

Problem Statement

A string consisting of 0 and 1 is called a good string if two consecutive characters in the string are always different.
You are given a string S of length N consisting of 0 and 1. Q queries will be given and must be processed in order.
There are two types of queries:

1 L R: Flip each of the L-th to R-th characters of S. That is, for each integer i satisfying L\leq i\leq R, change the i-th character of S to 0 if it is 1, and vice versa.
2 L R: Let S' be the string of length (R-L+1) obtained by extracting the L-th to R-th characters of S (without changing the order). Print Yes if S' is a good string and No otherwise.

Constraints

1\leq N, Q\leq 5\times 10^5
S is a string of length N consisting of 0 and 1.
1\leq L\leq R\leq N for queries of types 1 and 2.
There is at least one query of type 2.
N, Q, L, and R are integers.

Input

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

N Q
S
query_1
query_2
\vdots
query_Q

Each query query_i (1\leq i\leq Q) is given in the form:

1 L R

or:

2 L R

Output

Let K be the number of queries of type 2. Print K lines.
The i-th line should contain the response to the i-th query of type 2.

Sample Input 1

Sample Output 1

Yes
No
Yes
No

Initially, S=10100. When processing the queries in the order they are given, the following occurs:

For the first query, the string obtained by extracting the 1-st to 3-rd characters of S is S'=101. This is a good string, so print Yes.
For the second query, the string obtained by extracting the 1-st to 5-th characters of S is S'=10100. This is not a good string, so print No.
For the third query, flip each of the 1-st to 4-th characters of S. The string S becomes S=01010.
For the fourth query, the string obtained by extracting the 1-st to 5-th character of S is S'=01010. This is a good string, so print Yes.
For the fifth query, flip the 3-rd character of S. The string S becomes S=01110.
For the sixth query, the string obtained by extracting the 2-nd to 4-th character of S is S'=111. This is not a good string, so print No.

Sample Input 2

Sample Output 2

Yes

Note that a string of a single character 0 or 1 satisfies the condition of being a good string.

I - Teleporter Takahashi

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

配点 : 500 点

問題文

xy 平面上に高橋くんがいます。はじめ、高橋くんは点 (s _ x,s _ y) にいます。高橋くんは、点 (t _ x,t _ y) に移動したいです。

xy 平面上に、長方形 R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace があります。次の操作を考えます。

長方形 R に含まれる格子点 (x,y) をひとつ選ぶ。点 (x,y) を中心に高橋くんはいまいる位置と対称な位置に瞬間移動する。

上の操作を 0 回以上 10^6 回以下繰り返して、高橋くんが点 (t _ x,t _ y) にいるようにできるか判定してください。できる場合、高橋くんが点 (t _ x,t _ y) に移動することができるような操作の列を 1 つ構成してください。

制約

0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
0\leq a\leq b\leq2\times10^5
0\leq c\leq d\leq2\times10^5
入力はすべて整数

入力

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

s _ x s _ y
t _ x t _ y
a b c d

出力

1 行目には、操作を 0 回以上 10^6 回以下繰り返して高橋くんが点 (t _ x,t _ y) に到達できるなら Yes 、そうでなければ No と出力せよ。 1 行目で Yes と出力したとき、かつそのときに限り、あなたが構成した操作列の長さを d としてさらに d 行出力せよ（d は 0\leq d\leq10^6 を満たさなければならない）。 1+i 行目 (1\leq i\leq d) には、i 回目の操作で選んだ点 (x, y)\in R の座標をこの順に空白区切りで出力せよ。

入力例 1

1 2
7 8
7 9 0 3

出力例 1

例えば、次のようにして (1,2) から (7,8) へ移動することができます。

点 (7,0) を選ぶ。高橋くんは (13,-2) に移動する。
点 (9,3) を選ぶ。高橋くんは (5,8) に移動する。
点 (7,1) を選ぶ。高橋くんは (9,-6) に移動する。
点 (8,1) を選ぶ。高橋くんは (7,8) に移動する。

条件を満たす操作の列であれば何を出力しても正答となるので、例えば

と出力しても正答となります。

入力例 2

0 0
8 4
5 5 0 0

出力例 2

No

どのように操作しても点 (8,4) に移動することはできません。

入力例 3

1 4
1 4
100 200 300 400

出力例 3

Yes

高橋くんがはじめから目的地にいる場合もあります。

入力例 4

22 2
16 7
14 30 11 14

出力例 4

No

Score : 500 points

Problem Statement

Takahashi is on an xy-plane. Initially, he is at point (s _ x,s _ y), and he wants to reach point (t _ x,t _ y).

On the xy-plane is a rectangle R\coloneqq\lbrace(x,y)\mid a-0.5\leq x\leq b+0.5,c-0.5\leq y\leq d+0.5\rbrace. Consider the following operation:

Choose a lattice point (x,y) contained in the rectangle R. Takahashi teleports to the point symmetric to his current position with respect to point (x,y).

Determine if he can reach point (t _ x,t _ y) after repeating the operation above between 0 and 10^6 times, inclusive. If it is possible, construct a sequence of operations that leads him to point (t _ x,t _ y).

Constraints

0\leq s _ x,s _ y,t _ x,t _ y\leq2\times10^5
0\leq a\leq b\leq2\times10^5
0\leq c\leq d\leq2\times10^5
All values in the input are integers.

Input

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

s _ x s _ y
t _ x t _ y
a b c d

Output

In the first line, print Yes if Takahashi can reach point (t _ x,t _ y) after repeating the operation between 0 and 10^6 times, inclusive, and No otherwise. If and only if you print Yes in the first line, print d more lines, where d is the length of the sequence of operations you have constructed (d must satisfy 0\leq d\leq10^6). The (1+i)-th line (1\leq i\leq d) should contain the space-separated coordinates of the point (x, y)\in R, in this order, that is chosen in the i-th operation.

Sample Input 1

1 2
7 8
7 9 0 3

Sample Output 1

For example, the following choices lead him from (1,2) to (7,8).

Choose (7,0). Takahashi moves to (13,-2).
Choose (9,3). Takahashi moves to (5,8).
Choose (7,1). Takahashi moves to (9,-6).
Choose (8,1). Takahashi moves to (7,8).

Any output that satisfies the conditions is accepted; for example, printing

is also accepted.

Sample Input 2

0 0
8 4
5 5 0 0

Sample Output 2

No

No sequence of operations leads him to point (8,4).

Sample Input 3

1 4
1 4
100 200 300 400

Sample Output 3

Yes

Takahashi may already be at the destination in the beginning.

Sample Input 4

22 2
16 7
14 30 11 14

Sample Output 4

No