E - XX to XXX

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

配点 : 300 点

問題文

英小文字からなる 2 つの文字列 S, T が与えられます。 次の操作を好きな回数( 0 回でも良い)行うことで、S を T と一致させることができるかを判定してください。

S において同じ文字が 2 文字連続しているところの間に、その文字と同じ文字を 1 つ挿入する。 すなわち、下記の 3 つの手順からなる操作を行う。

  1. 現在の S の長さを N とし、S = S_1S_2\ldots S_N とする。
  2. 1 以上 N-1 以下の整数 i であって、S_i = S_{i+1} を満たすものを 1 つ選択する。(ただし、そのような i が存在しない場合は、何もせずに手順 3.をスキップして操作を終了する。)
  3. S の i 文字目と i+1 文字目の間に文字 S_i(= S_{i+1}) を 1 つ挿入する。その結果、S は長さ N+1 の文字列 S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N となる。

制約

  • S と T はそれぞれ英小文字からなる長さ 2 以上 2 \times 10^5 以下の文字列

入力

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

S
T

出力

S を T と一致させることができる場合は Yes を、そうでない場合は No を出力せよ。 ジャッジは英小文字と英大文字を厳密に区別することに注意せよ。


入力例 1

abbaac
abbbbaaac

出力例 1

Yes

下記の 3 回の操作によって、S = abbaac を T = abbbbaaac に一致させることができます。

  • まず、S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbaac となる。
  • 次に、再び S の 2 文字目と 3 文字目の間に b を挿入する。その結果、S = abbbbaac となる。
  • 最後に、S の 6 文字目と 7 文字目の間に a を挿入する。その結果、S = abbbbaaac となる。

よって、Yes を出力します。


入力例 2

xyzz
xyyzz

出力例 2

No

どのように操作を行っても、 S = xyzz を T = xyyzz に一致させることはできません。 よって、No を出力します。

Score : 300 points

Problem Statement

You are given two strings S and T. Determine whether it is possible to make S equal T by performing the following operation some number of times (possibly zero).

Between two consecutive equal characters in S, insert a character equal to these characters. That is, take the following three steps.

  1. Let N be the current length of S, and S = S_1S_2\ldots S_N.
  2. Choose an integer i between 1 and N-1 (inclusive) such that S_i = S_{i+1}. (If there is no such i, do nothing and terminate the operation now, skipping step 3.)
  3. Insert a single copy of the character S_i(= S_{i+1}) between the i-th and (i+1)-th characters of S. Now, S is a string of length N+1: S_1S_2\ldots S_i S_i S_{i+1} \ldots S_N.

Constraints

  • Each of S and T is a string of length between 2 and 2 \times 10^5 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

If it is possible to make S equal T, print Yes; otherwise, print No. Note that the judge is case-sensitive.


Sample Input 1

abbaac
abbbbaaac

Sample Output 1

Yes

You can make S = abbaac equal T = abbbbaaac by the following three operations.

  • First, insert b between the 2-nd and 3-rd characters of S. Now, S = abbbaac.
  • Next, insert b again between the 2-nd and 3-rd characters of S. Now, S = abbbbaac.
  • Lastly, insert a between the 6-th and 7-th characters of S. Now, S = abbbbaaac.

Thus, Yes should be printed.


Sample Input 2

xyzz
xyyzz

Sample Output 2

No

No sequence of operations makes S = xyzz equal T = xyyzz. Thus, No should be printed.

F - kasaka

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

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 S の先頭に a をいくつか( 0 個でも良い)つけ加えて回文にすることができるか判定してください。

ただし、長さ N の文字列 A=A_1A_2\ldots A_N が回文であるとは、すべての 1\leq i\leq N について A_i=A_{N+1-i} が成り立っていることをいいます。

制約

  • 1 \leq \lvert S \rvert \leq 10^6
  • S は英小文字のみからなる。

入力

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

S

出力

S の先頭に a をいくつかつけ加えて回文にすることができるならば Yes を、そうでないならば No を出力せよ。


入力例 1

kasaka

出力例 1

Yes

kasaka の先頭に a を 1 つ付け加えることによって、akasaka となり回文となるため Yes を出力します。


入力例 2

atcoder

出力例 2

No

atcoder の先頭に a をいくつ付け加えても回文となる事はありません。


入力例 3

php

出力例 3

Yes

php はそれ自体回文です。S の先頭に付け加える a は 0 個でも許されるため、Yes を出力します。

Score : 300 points

Problem Statement

Given is a string S consisting of lowercase English letters. Determine whether adding some number of a's (possibly zero) at the beginning of S can make it a palindrome.

Here, a string of length N, A=A_1A_2\ldots A_N, is said to be a palindrome when A_i=A_{N+1-i} for every 1\leq i\leq N.

Constraints

  • 1 \leq \lvert S \rvert \leq 10^6
  • S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S

Output

If adding some number of a's (possibly zero) at the beginning of S can make it a palindrome, print Yes; otherwise, print No.


Sample Input 1

kasaka

Sample Output 1

Yes

By adding one a at the beginning of kasaka, we have akasaka, which is a palindrome, so Yes should be printed.


Sample Input 2

atcoder

Sample Output 2

No

Adding any number of a's at the beginning of atcoder does not make it a palindrome.


Sample Input 3

php

Sample Output 3

Yes

php itself is a palindrome. Adding zero a's at the beginning of S is allowed, so Yes should be printed.

G - Pigeon Swap

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

配点 : 350 点

問題文

鳩 1, 鳩 2,\ldots, 鳩 N の N 羽の鳩と、巣 1, 巣 2,\ldots, 巣 N の N 個の巣があります。

はじめ、鳩 i (1\leq i\leq N) は巣 i にいます。

鳩たちに対して Q 回の操作を行います。

操作は次の 3 種類のうちのいずれかです。

  • 種類 1 : 整数 a,b (1\leq a\leq N,1\leq b\leq N) が与えられる。鳩 a を今いる巣から取り出し、巣 b へ移動する。
  • 種類 2 : 整数 a,b (1\leq a\lt b\leq N) が与えられる。巣 a にいる鳩をすべて巣 b へ移動し、巣 b にいる鳩をすべて巣 a へ移動する。これら 2 つの移動は一斉に行われる。
  • 種類 3 : 整数 a (1\leq a\leq N) が与えられる。鳩 a が今いる巣の番号を報告する。

Q 回の操作を順に行ったときの、種類 3 の各操作における報告の結果を出力してください。

制約

  • 1\leq N\leq10 ^ 6
  • 1\leq Q\leq3\times10 ^ 5
  • 入力される操作はすべて種類 1, 種類 2, 種類 3 のいずれかである。
  • 入力される操作は問題文中の制約を満たす。
  • 入力される操作のうちに種類 3 の操作が 1 つ以上含まれる。
  • 入力はすべて整数

入力

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

N Q
op _ 1
op _ 2
\vdots
op _ Q

ただし、i+1 行目の入力 op _ i は i 番目の操作を表しており、op _ i は次のいずれかの形式である。

i 番目の操作が種類 1 の操作のとき、i+1 行目は次の形式で与えられる。

1 a b

これは、与えられる整数を a と b として種類 1 の操作を行うことを表している。

i 番目の操作が種類 2 の操作のとき、i+1 行目は次の形式で与えられる。

2 a b

これは、与えられる整数を a と b として種類 2 の操作を行うことを表している。

i 番目の操作が種類 3 の操作のとき、i+1 行目は次の形式で与えられる。

3 a

これは、与えられる整数を a として種類 3 の操作を行うことを表している。

出力

与えられる種類 3 の操作の個数を q 個として、q 行にわたって出力せよ。

i 行目 (1\leq i\leq q) には、種類 3 の操作のうち i 番目の操作で報告される巣の番号を出力せよ。


入力例 1

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

出力例 1

4
5
2
5

与えられる操作で、鳩は以下の図のように移動します。

種類 3 の操作でそれぞれ報告すべき巣の番号は 4,5,2,5 なので、4 5 2 5 を 4 行にわたって出力してください。


入力例 2

1 2
1 1 1
3 1

出力例 2

1

種類 1 の操作で、鳩を取り出した巣にそのまま戻す場合もあります。


入力例 3

30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

出力例 3

3
15
7

Score : 350 points

Problem Statement

There are N pigeons labeled 1, 2, \ldots, N and N nests labeled 1, 2, \ldots, N.

Initially, pigeon i (1 \leq i \leq N) is in nest i.

You will perform Q operations on these pigeons.

There are three types of operations:

  • Type 1: You are given integers a and b (1 \leq a \leq N, 1 \leq b \leq N). Take pigeon a out of its current nest and move it to nest b.
  • Type 2: You are given integers a and b (1 \leq a < b \leq N). Move all pigeons in nest a to nest b, and move all pigeons in nest b to nest a. These two moves happen simultaneously.
  • Type 3: You are given an integer a (1 \leq a \leq N). Pigeon a reports the label of the nest it is currently in.

Print the result of each Type 3 operation in the order the operations are given.

Constraints

  • 1 \leq N \leq 10^6
  • 1 \leq Q \leq 3 \times 10^5
  • Every operation is of Type 1, 2, or 3.
  • All operations are valid according to the problem statement.
  • There is at least one Type 3 operation.
  • All input values are integers.

Input

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

N Q
op _ 1
op _ 2
\vdots
op _ Q

Here, op _ i on the line i+1 represents the i-th operation in one of the following formats.

If the i-th operation is of Type 1, op _ i is in the following format:

1 a b

This corresponds to a Type 1 operation with the given integers being a and b.

If the i-th operation is of Type 2, op _ i is in the following format:

2 a b

This corresponds to a Type 2 operation with the given integers being a and b.

If the i-th operation is of Type 3, op _ i is in the following format:

3 a

This corresponds to a Type 3 operation with the given integer being a.

Output

Let the number of Type 3 operations be q. Print q lines. The i-th line (1 \leq i \leq q) should contain the nest number reported in the i-th Type 3 operation.


Sample Input 1

6 8
1 2 4
1 3 6
3 2
2 4 5
3 2
1 4 2
3 4
3 2

Sample Output 1

4
5
2
5

In the operations given, the pigeons move as shown in the figure below:

The nest numbers to be reported for the Type 3 operations are 4,5,2,5. Print 4, 5, 2, 5 on separate lines.


Sample Input 2

1 2
1 1 1
3 1

Sample Output 2

1

The destination nest of a Type 1 operation may be the same as the nest the pigeon is currently in.


Sample Input 3

30 15
3 3
2 8 30
2 12 15
2 2 17
1 19 1
2 7 30
3 12
3 8
2 25 26
1 13 10
1 16 10
2 16 29
2 1 21
2 6 11
1 21 8

Sample Output 3

3
15
7
H - Min of Restricted Sum

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

配点 : 450 点

問題文

整数 N,M と長さ M の整数列 X=(X_1,X_2,\ldots,X_M),Y=(Y_1,Y_2,\ldots,Y_M),Z=(Z_1,Z_2,\ldots,Z_M) が与えられます。ここで、 X,Y の要素は全て 1 以上 N 以下であることが保証されます。

長さ N の非負整数列 A=(A_1,A_2,\ldots,A_N) であって、以下の条件を満たす整数列を 良い整数列 と呼びます。

  • 1\le i\le M を満たす全ての整数 i に対し、 A_{X_i} と A_{Y_i} の XOR が Z_i と一致する。

良い整数列 A=(A_1,A_2,\ldots,A_N) が存在するか判定し、存在するならば要素の総和 \displaystyle \sum_{i=1}^N A_i が最小になるような良い整数列を一つ求めてください。

XOR とは 非負整数 A,B の XOR A \oplus B は、以下のように定義されます。
  • A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
例えば、 3 \oplus 5 = 6 となります (二進表記すると: 011 \oplus 101=110)。

制約

  • 1\le N\le 2\times 10^5
  • 0\le M\le 10^5
  • 1\le X_i,Y_i\le N
  • 0\le Z_i\le 10^9
  • 入力される値は全て整数

入力

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

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

出力

良い整数列が存在しないならば -1 を出力せよ。

良い整数列が存在するならば要素の総和が最小になる良い整数列を一つ空白区切りで出力せよ。

なお、要素の総和が最小となる良い整数列が複数存在する場合は、どれを出力しても正答となる。


入力例 1

3 2
1 3 4
1 2 3

出力例 1

0 3 4

A=(0,3,4) は A_1 と A_2 の XOR が 3 、 A_1 と A_3 の XOR が 4 なので良い整数列です。

この他にも A=(1,2,5),(7,4,3) などが良い整数列ですが、良い整数列の中で総和が最小となるのは A=(0,3,4) です。


入力例 2

3 3
1 3 4
1 2 3
2 3 5

出力例 2

-1

良い整数列は存在しないので、 -1 を出力してください。


入力例 3

5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

出力例 3

0 2 9 6 0

Score : 450 points

Problem Statement

You are given integers N, M and three integer sequences of length M: X = (X_1, X_2, \ldots, X_M), Y = (Y_1, Y_2, \ldots, Y_M), and Z = (Z_1, Z_2, \ldots, Z_M). It is guaranteed that all elements of X and Y are between 1 and N, inclusive.

We call a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) a good sequence if and only if it satisfies the following condition:

  • For every integer i with 1 \le i \le M, the XOR of A_{X_i} and A_{Y_i} is Z_i.

Determine whether a good sequence A=(A_1,A_2,\ldots,A_N) exists, and if it exists, find one good sequence that minimizes the sum of its elements \displaystyle \sum_{i=1}^N A_i.

Notes on XOR For non-negative integers A and B, their XOR A \oplus B is defined as follows:
  • In the binary representation of A \oplus B, the digit in the place corresponding to 2^k \,(k \ge 0) is 1 if and only if exactly one of the digits in the same place of A and B is 1; otherwise, it is 0.
For example, 3 \oplus 5 = 6 (in binary: 011 \oplus 101 = 110).

Constraints

  • 1 \le N \le 2\times 10^5
  • 0 \le M \le 10^5
  • 1 \le X_i, Y_i \le N
  • 0 \le Z_i \le 10^9
  • All input values are integers.

Input

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

N M
X_1 Y_1 Z_1
X_2 Y_2 Z_2
\vdots
X_M Y_M Z_M

Output

If no good sequence exists, print -1.

If a good sequence exists, print one good sequence that minimizes the sum of its elements, separated by spaces.

If there are multiple good sequences with the same minimum sum, printing any of them is accepted.


Sample Input 1

3 2
1 3 4
1 2 3

Sample Output 1

0 3 4

A=(0,3,4) is a good sequence because A_1 \oplus A_2 = 3 and A_1 \oplus A_3 = 4.

Other good sequences include A=(1,2,5) and A=(7,4,3), but A=(0,3,4) has the smallest sum among all good sequences.


Sample Input 2

3 3
1 3 4
1 2 3
2 3 5

Sample Output 2

-1

No good sequence exists, so print -1.


Sample Input 3

5 8
4 2 4
2 3 11
3 4 15
4 5 6
3 2 11
3 3 0
3 1 9
3 4 15

Sample Output 3

0 2 9 6 0
I - Christmas Present 2

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

配点 : 550 点

問題文

xy 平面として表される町があり、サンタさんと、1 から N までの番号が付けられた N 人の子供が住んでいます。 サンタさんの家の座標は (S_X,S_Y) であり、子供 i\ (1\leq i\leq N) の家の座標は (X_i,Y_i) です。

サンタさんは、N 人の子供たちに番号順にプレゼントを 1 個ずつ配りたいです。 子供 i にプレゼントを配るためには、プレゼントを 1 個以上持った状態で子供 i の家に行く必要があります。 しかし、サンタさんは同時に K 個までしかプレゼントを持つことができず、プレゼントを補充するためには一旦自分の家に戻る必要があります(サンタさんの家には十分な数のプレゼントがあります)。

サンタさんが自分の家を出発し、N 人の子供たち全員にプレゼントを配って、自分の家まで戻ってくるために移動する距離の最小値を求めてください。

制約

  • 1\leq K\leq N \leq 2\times 10^5
  • -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
  • (S_X,S_Y)\neq (X_i,Y_i)
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • 入力は全て整数

入力

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

N K
S_X S_Y
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

サンタさんが移動する距離の最小値を出力せよ。 出力は、真の値との絶対誤差または相対誤差が 10^{−6} 以下のとき正解と判定される。


入力例 1

3 2
1 1
3 1
1 2
3 2

出力例 1

9.236067977499790

上図において、赤い丸はサンタさんの家、中に数字が書かれた丸はその番号の子供の家を表しています。

サンタさんが以下のように行動することを考えます。

  1. プレゼントを 2 個持ってサンタさんの家を出る。
  2. 子供 1 の家に行ってプレゼントを 1 個配る。
  3. サンタさんの家に戻ってプレゼントを 1 個補充する。
  4. 子供 2 の家に行ってプレゼントを 1 個配る。
  5. 子供 3 の家に行ってプレゼントを 1 個配る。
  6. サンタさんの家に戻る。

このとき、サンタさんが移動する距離は 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots となり、これが最小です。


入力例 2

2 1
0 1
-1 1
1 1

出力例 2

4.000000000000000

入力例 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

出力例 3

11347715738.116592407226562

Score : 550 points

Problem Statement

There is a town represented as an xy-plane, where Santa lives, along with N children numbered 1 to N. Santa's house is at coordinates (S_X,S_Y), and the house of child i\ (1\leq i\leq N) is at (X_i,Y_i).

Santa wants to deliver one present to each of the N children in numerical order. To deliver a present to child i, Santa must visit the house of child i with at least one present in hand. However, Santa can only carry up to K presents at a time, and he must return to his own house to replenish presents (there are enough presents at Santa's house).

Find the minimum distance Santa must travel to leave his house, deliver presents to all N children, and return to his house.

Constraints

  • 1\leq K\leq N \leq 2\times 10^5
  • -10^9\leq S_X,S_Y,X_i,Y_i \leq 10^9
  • (S_X,S_Y)\neq (X_i,Y_i)
  • (X_i,Y_i)\neq (X_j,Y_j)\ (i\neq j)
  • All input values are integers.

Input

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

N K
S_X S_Y
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the minimum distance Santa must travel. The output will be considered correct if the absolute or relative error from the true value is at most 10^{−6}.


Sample Input 1

3 2
1 1
3 1
1 2
3 2

Sample Output 1

9.236067977499790

In the figure above, the red circle represents Santa's house, and the circles with numbers represent the houses of the children with those numbers.

Consider Santa acting as follows:

  1. Leave his house with two presents.
  2. Go to child 1's house and deliver a present.
  3. Return to his house and replenish one present.
  4. Go to child 2's house and deliver a present.
  5. Go to child 3's house and deliver a present.
  6. Return to his house.

In this case, Santa travels the distance of 2+2+1+2+\sqrt{5}=7+\sqrt{5}=9.236\dots, which is the minimum.


Sample Input 2

2 1
0 1
-1 1
1 1

Sample Output 2

4.000000000000000

Sample Input 3

8 3
735867677 193944314
586260100 -192321079
95834122 802780784
418379342 -790013317
-445130206 189801569
-354684803 -49687658
-204491568 -840249197
853829789 470958158
-751917965 762048217

Sample Output 3

11347715738.116592407226562