Time Limit: 2 sec / Memory Limit: 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
5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5
出力例 1
3 0 2 0 1 1 1 0 1 0
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 ofR,L,U, andD, 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, andD. - 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
5 9 2 3 1 U 2 3 1 R 1 D 2 3 1 L 2 1 2 5
Sample Output 1
3 0 2 0 1 1 1 0 1 0
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.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するかどうか判定してください。
制約
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N X A_1 \ldots A_N
出力
1\leq i,j \leq N である組 (i,j) であって、A_i-A_j=X となるものが存在するとき Yes、存在しないとき No と出力せよ。
入力例 1
6 5 3 1 4 1 5 9
出力例 1
Yes
A_6-A_3=9-4=5 です。
入力例 2
6 -4 -2 -7 -1 -8 -2 -8
出力例 2
No
A_i-A_j=-4 となる組 (i,j) は存在しません。
入力例 3
2 0 141421356 17320508
出力例 3
Yes
A_1-A_1=0 です。
Score : 300 points
Problem Statement
You are given a sequence of N numbers: A=(A_1,\ldots,A_N).
Determine whether there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X.
Constraints
- 2 \leq N \leq 2\times 10^5
- -10^9 \leq A_i \leq 10^9
- -10^9 \leq X \leq 10^9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N X A_1 \ldots A_N
Output
Print Yes if there is a pair (i,j) with 1\leq i,j \leq N such that A_i-A_j=X, and No otherwise.
Sample Input 1
6 5 3 1 4 1 5 9
Sample Output 1
Yes
We have A_6-A_3=9-4=5.
Sample Input 2
6 -4 -2 -7 -1 -8 -2 -8
Sample Output 2
No
There is no pair (i,j) such that A_i-A_j=-4.
Sample Input 3
2 0 141421356 17320508
Sample Output 3
Yes
We have A_1-A_1=0.
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
2 次元平面上に N 個の相異なる点があり、1,2,\ldots ,N の番号がついています。点 i\,(1 \leq i \leq N) の座標は (x_i,y_i) です。
これらの点のうち 4 つを頂点とし、全ての辺が x 軸または y 軸に平行であるような長方形はいくつありますか？
制約
- 4 \leq N \leq 2000
- 0 \leq x_i, y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j) (i \neq j)
- 入力は全て整数である。
入力
入力は以下の形式で標準入力から与えられる。
N x_1 y_1 x_2 y_2 \vdots x_N y_N
出力
答えを出力せよ。
入力例 1
6 0 0 0 1 1 0 1 1 2 0 2 1
出力例 1
3
点 1 、点 2 、点 3 、点 4 を頂点とする長方形、
点 1 、点 2 、点 5 、点 6 を頂点とする長方形、
点 3 、点 4 、点 5 、点 6 を頂点とする長方形
の合計 3 つです。
入力例 2
4 0 1 1 2 2 3 3 4
出力例 2
0
入力例 3
7 0 1 1 0 2 0 2 1 2 2 3 0 3 2
出力例 3
1
Score : 400 points
Problem Statement
We have N distinct points on a two-dimensional plane, numbered 1,2,\ldots,N. Point i (1 \leq i \leq N) has the coordinates (x_i,y_i).
How many rectangles are there whose vertices are among the given points and whose edges are parallel to the x- or y-axis?
Constraints
- 4 \leq N \leq 2000
- 0 \leq x_i, y_i \leq 10^9
- (x_i,y_i) \neq (x_j,y_j) (i \neq j)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N x_1 y_1 x_2 y_2 \vdots x_N y_N
Output
Print the answer.
Sample Input 1
6 0 0 0 1 1 0 1 1 2 0 2 1
Sample Output 1
3
There are three such rectangles:
the rectangle whose vertices are Points 1, 2, 3, 4,
the rectangle whose vertices are Points 1, 2, 5, 6,
and the rectangle whose vertices are Points 3, 4, 5, 6.
Sample Input 2
4 0 1 1 2 2 3 3 4
Sample Output 2
0
Sample Input 3
7 0 1 1 0 2 0 2 1 2 2 3 0 3 2
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
高橋君は双六で遊んでいます。
この双六には 0 から N の番号がついた N+1 個のマスがあります。 高橋君はマス 0 からスタートし、マス N を目指します。
この双六では、1 から M までの M 種類の目が等確率で出るルーレットを使います。 高橋君はルーレットを回して出た目の数だけ進みます。もし、マス N を超えて進むことになる場合、マス N を超えた分だけ引き返します。
例えば、 N=4 で高橋君がマス 3 にいるとき、ルーレットを回して出た目が 4 の場合は、マス 4 を 3+4-4=3 マス超えてしまいます。そのため、 3 マスだけマス 4 から引き返し、マス 1 に移動します。
高橋君がマス N に到達するとゴールとなり、双六を終了します。
高橋君がルーレットを K 回まで回す時、ゴールできる確率を \text{mod } 998244353 で求めてください。
確率 \text{mod } 998244353 の定義
この問題で求める確率は必ず有理数になることが証明できます。 また、この問題の制約下では、求める確率を既約分数 \frac{y}{x} で表したときに x が 998244353 で割り切れないことが保証されます。
このとき xz \equiv y \pmod{998244353} を満たすような 0 以上 998244352 以下の整数 z が一意に定まります。この z を答えてください。
制約
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを出力せよ。
入力例 1
2 2 1
出力例 1
499122177
1 回ルーレットを回してゴールできるのは、ルーレットで 2 が出るときです。よってゴールできる確率は \frac{1}{2} です。
このとき、2\times 499122177 \equiv 1 \pmod{998244353} が成り立つので、答えとして 499122177 を出力してください。
入力例 2
10 5 6
出力例 2
184124175
入力例 3
100 1 99
出力例 3
0
Score : 500 points
Problem Statement
Takahashi is playing sugoroku, a board game.
The board has N+1 squares, numbered 0 to N. Takahashi starts at square 0 and goes for square N.
The game uses a roulette wheel with M numbers from 1 to M that appear with equal probability. Takahashi spins the wheel and moves by the number of squares indicated by the wheel. If this would send him beyond square N, he turns around at square N and goes back by the excessive number of squares.
For instance, assume that N=4 and Takahashi is at square 3. If the wheel shows 4, the excessive number of squares beyond square 4 is 3+4-4=3. Thus, he goes back by three squares from square 4 and arrives at square 1.
When Takahashi arrives at square N, he wins and the game ends.
Find the probability, modulo 998244353, that Takahashi wins when he may spin the wheel at most K times.
How to print a probability modulo 998244353
It can be proved that the sought probability is always a rational number. Additionally, under the Constraints of this problem, when the sought probability is represented as an irreducible fraction \frac{y}{x}, it is guaranteed that x is not divisible by 998244353.
Here, there is a unique integer z between 0 and 998244352 such that xz \equiv y \pmod{998244353}. Print this z.
Constraints
- M \leq N \leq 1000
- 1 \leq M \leq 10
- 1 \leq K \leq 1000
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 2 1
Sample Output 1
499122177
Takahashi wins in one spin if the wheel shows 2. Therefore, the probability of winning is \frac{1}{2}.
We have 2\times 499122177 \equiv 1 \pmod{998244353}, so the answer to be printed is 499122177.
Sample Input 2
10 5 6
Sample Output 2
184124175
Sample Input 3
100 1 99
Sample Output 3
0
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
N 頂点 M 辺の無向グラフ G_0 が与えられます。 G_0 の頂点および辺は、それぞれ頂点 1, 頂点 2, \ldots, 頂点 N および辺 1, 辺 2, \ldots, 辺 M と番号づけられており、 辺 i (1\leq i\leq M) は頂点 U_i と頂点 V_i を結んでいます。
高橋君はグラフ G と、駒 1, 駒 2, \ldots, 駒 N と番号づけられた N 個の駒を持っています。
最初、G=G_0 であり、さらに G の頂点 i (1\leq i\leq N) には駒 i が置かれています。
高橋君はこれから Q 回の操作を順に行います。 i 回目 (1\leq i\leq Q) の操作では 1 以上 M 以下の整数 X_i が与えられ、次の操作を行います。
G において駒 U_{X_i} と駒 V_{X_i} が異なる頂点に置かれており、 それらの間に（ G 上の）辺 e が存在するならばその辺を縮約したグラフ G' を作成する。 この際、自己ループができた場合は取り除き、多重辺が存在した場合は単純辺に置き換える。
その後、G において辺 e が結んでいた 2 頂点に置かれていた駒はすべて、G' の e の縮約によって新たに生成された頂点に置く。 G 上のその他の頂点に置かれていた駒については、G' の対応する頂点に置く。 最後に、このようにしてできた G' を新たな G とする。
駒 U_{X_i} と駒 V_{X_i} が同じ頂点に置かれていた場合、あるいは置かれている頂点の間が辺で結ばれていなかった場合は何も行わない。
i=1,2,\ldots, Q 回目の操作それぞれについて、i 回目の操作の後の G の辺の数を出力してください。
辺の縮約 とは
頂点 u と頂点 v を結ぶ辺の縮約とは、頂点 u,v を 1 つの頂点にまとめる操作です。 より正確には、G に対して辺の縮約を行なって得られるグラフとは G に対して次の操作を行って得られるものを指します。- G に新たに頂点 w を追加する。
- G 上の u,v 以外の各頂点 x について、u と x を結ぶ辺、あるいは v と x を結ぶ辺の少なくとも一方が存在するとき、かつその時に限り、w と x を結ぶ辺を加える。
- 頂点 u,v を削除し、頂点 u と v を結ぶ辺および頂点 u または v と他の頂点を結ぶ辺をすべて削除する。
制約
- 2\leq N\leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i<V_i\leq N
- i\neq j ならば (U_i,V_i)\neq (U_j,V_j)
- 1\leq Q\leq 3\times 10^5
- 1\leq X_i\leq M
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M Q X_1 X_2 \ldots X_Q
出力
Q 行出力せよ。 i 行目 (1\leq i\leq Q) には、i 回目の操作の後の G の辺の数を出力せよ。
入力例 1
7 7 1 2 1 3 2 3 1 4 1 5 2 5 6 7 5 1 2 3 1 5
出力例 1
4 3 3 3 2
最初、G は下図のようになっています。丸付き数字はその番号の駒を表します。
1 回目の操作では、駒 1 と駒 2 が置かれている頂点の間の辺（下図左）の縮約を行います。
操作後、G は下図右のようになり、特に辺の数は 4 です。
自己ループの削除および多重辺の単純辺への置換が行われていることに注意してください。
2 回目の操作では、駒 1 と駒 3 が置かれている頂点の間の辺の縮約を行います。
操作後、G は下図左のようになり、辺の数は 3 となります。
3 回目の操作では、駒 2 と駒 3 は同じ頂点に置かれているため、G はそのままであり、辺の数も 3 のままです。
4 回目の操作でも、駒 1 と駒 2 は同じ頂点に置かれているため、G はそのままであり、辺の数も 3 のままです。
5 回目の操作では、駒 1 と駒 5 が置かれている頂点の間の辺の縮約を行います。
操作後、G は下図右のようになり、辺の数は 2 となります。
よって、4,3,3,3,2 をこの順に改行区切りで出力します。
Score : 525 points
Problem Statement
You are given an undirected graph G_0 with N vertices and M edges. The vertices and edges of G_0 are numbered as vertices 1, 2, \ldots, N and edges 1, 2, \ldots, M, respectively, and edge i (1\leq i\leq M) connects vertices U_i and V_i.
Takahashi has a graph G and N pieces numbered as pieces 1, 2, \ldots, N.
Initially, G=G_0, and piece i (1\leq i\leq N) is placed on vertex i of G.
He will now perform Q operations in order. The i-th operation (1\leq i\leq Q) gives an integer X_i between 1 and M, inclusive, and performs the following operation:
In G, if pieces U_{X_i} and V_{X_i} are placed on different vertices and there exists an edge e (on G) between them, create a graph G' by contracting that edge. In this case, if self-loops are created, remove them, and if multi-edges exist, replace them with simple edges.
Then, all pieces that were placed on the two vertices connected by edge e in G are placed on the newly generated vertex by the contraction of e in G'. Pieces that were placed on other vertices in G are placed on the corresponding vertices in G'. Finally, set this resulting G' as the new G.
If pieces U_{X_i} and V_{X_i} are placed on the same vertex, or if the vertices they are placed on are not connected by an edge, do nothing.
For each of the operations i=1,2,\ldots, Q, output the number of edges in G after the i-th operation.
Edge Contraction
Edge contraction of an edge connecting vertices u and v is an operation that merges vertices u,v into one vertex. More precisely, a graph obtained by performing edge contraction on G refers to the result of performing the following operations on G:- Add a new vertex w to G.
- For each vertex x other than u,v in G, if and only if at least one of the edge connecting u and x or the edge connecting v and x exists, add an edge connecting w and x.
- Delete vertices u,v and remove all edges connecting vertices u and v, as well as all edges connecting vertex u or vertex v with other vertices.
Constraints
- 2\leq N\leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i<V_i\leq N
- (U_i,V_i)\neq (U_j,V_j) if i\neq j.
- 1\leq Q\leq 3\times 10^5
- 1\leq X_i\leq M
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M Q X_1 X_2 \ldots X_Q
Output
Output Q lines. On the i-th line (1\leq i\leq Q), output the number of edges in G after the i-th operation.
Sample Input 1
7 7 1 2 1 3 2 3 1 4 1 5 2 5 6 7 5 1 2 3 1 5
Sample Output 1
4 3 3 3 2
Initially, G is as shown in the figure below. The circled numbers represent pieces with those numbers.
In the 1st operation, we contract the edge between the vertices where pieces 1 and 2 are placed (left figure below).
After the operation, G becomes as shown in the right figure below, and in particular, the number of edges is 4.
Note that self-loops have been removed and multi-edges have been replaced with simple edges.
In the 2nd operation, we contract the edge between the vertices where pieces 1 and 3 are placed.
After the operation, G becomes as shown in the left figure below, and the number of edges becomes 3.
In the 3rd operation, since pieces 2 and 3 are placed on the same vertex, G remains unchanged, and the number of edges remains 3.
In the 4th operation as well, since pieces 1 and 2 are placed on the same vertex, G remains unchanged, and the number of edges remains 3.
In the 5th operation, we contract the edge between the vertices where pieces 1 and 5 are placed.
After the operation, G becomes as shown in the right figure below, and the number of edges becomes 2.
Thus, output 4,3,3,3,2 in this order, separated by newlines.