C - Number Box

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 N が与えられます。

N 行 N 列のマス目があり、上から i 行目、左から j 列目のマスには数字 A_{i,j} が書かれています。

このマス目は上下および左右がつながっているものとします。つまり以下が全て成り立ちます。

  • (1,i) の上のマスは (N,i) であり、(N,i) の下のマスは (1,i) である。(1\le i\le N)
  • (i,1) の左のマスは (i,N) であり、(i,N) の右のマスは (i,1) である。(1\le i\le N)

高橋君は、上下左右および斜めの 8 方向のうちいずれかを初めに選びます。そして、好きなマスから決めた方向に 1 マス移動することを N-1 回繰り返します。

高橋君は N 個のマス上を移動することになりますが、高橋君が通ったマスに書かれている数字を左から通った順番に並べた整数としてあり得る最大のものを求めてください。

制約

  • 1 \le N \le 10
  • 1 \le A_{i,j} \le 9
  • 入力はすべて整数。

入力

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

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

出力

答えを出力せよ。


入力例 1

4
1161
1119
7111
1811

出力例 1

9786

高橋君が上から 2 行目、左から 4 列目のマスから出発し、右下に進むことで、通ったマスに書かれた数字を並べ 9786 を作ることができます。 9786 より大きい値を作ることはできないため、9786 が解です。


入力例 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

出力例 2

1111111111

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

Score : 200 points

Problem Statement

You are given a positive integer N.

We have a grid with N rows and N columns, where the square at the i-th row from the top and j-th column from the left has a digit A_{i,j} written on it.

Assume that the upper and lower edges of this grid are connected, as well as the left and right edges. In other words, all of the following holds.

  • (N,i) is just above (1,i), and (1,i) is just below (N,i). (1\le i\le N).
  • (i,N) is just to the left of (i,1), and (i,1) is just to the right of (i,N). (1\le i\le N).

Takahashi will first choose one of the following eight directions: up, down, left, right, and the four diagonal directions. Then, he will start on a square of his choice and repeat moving one square in the chosen direction N-1 times.

In this process, Takahashi visits N squares. Find the greatest possible value of the integer that is obtained by arranging the digits written on the squares visited by Takahashi from left to right in the order visited by him.

Constraints

  • 1 \le N \le 10
  • 1 \le A_{i,j} \le 9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_{1,1}A_{1,2}\dots A_{1,N}
A_{2,1}A_{2,2}\dots A_{2,N}
\vdots
A_{N,1}A_{N,2}\dots A_{N,N}

Output

Print the answer.


Sample Input 1

4
1161
1119
7111
1811

Sample Output 1

9786

If Takahashi starts on the square at the 2-nd row from the top and 4-th column from the left and goes down and to the right, the integer obtained by arranging the digits written on the visited squares will be 9786. It is impossible to make a value greater than 9786, so the answer is 9786.


Sample Input 2

10
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111
1111111111

Sample Output 2

1111111111

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

D - Everyone is Friends

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

1,2,\ldots,N の番号がついた N 人の人がいます。

M 回の舞踏会が行われました。 i (1\leq i \leq M) 回目の舞踏会には k_i 人が参加し、参加した人は人 x_{i,1},x_{i,2},\ldots,x_{i,k_i} でした。

どの二人も少なくとも 1 回同じ舞踏会に参加したか判定してください。

制約

  • 2\leq N \leq 100
  • 1\leq M \leq 100
  • 2\leq k_i \leq N
  • 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
  • 入力は全て整数

入力

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

N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}

出力

どの二人も少なくとも 1 回同じ舞踏会に参加した場合 Yes を、そうでない場合 No を出力せよ。


入力例 1

3 3
2 1 2
2 2 3
2 1 3

出力例 1

Yes

人 1 と人 2 は共に 1 回目の舞踏会に参加しています。

人 2 と人 3 は共に 2 回目の舞踏会に参加しています。

人 1 と人 3 は共に 3 回目の舞踏会に参加しています。

以上よりどの二人も少なくとも 1 回同じ舞踏会に参加したので、答えは Yes です。


入力例 2

4 2
3 1 2 4
3 2 3 4

出力例 2

No

人 1 と人 3 は 1 回も同じ舞踏会に参加していないので、答えは No です。

Score : 200 points

Problem Statement

There are N people numbered 1,2,\ldots,N.

M parties were held. k_i people attended the i-th (1\leq i \leq M) party, and they were People x_{i,1},x_{i,2},\ldots,x_{i,k_i}.

Determine if every two people attended the same party at least once.

Constraints

  • 2\leq N \leq 100
  • 1\leq M \leq 100
  • 2\leq k_i \leq N
  • 1\leq x_{i,1}<x_{i,2}<\ldots < x_{i,k_i}\leq N
  • All values in the input are integers.

Input

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

N M
k_1 x_{1,1} x_{1,2} \ldots x_{1,k_1}
\vdots
k_M x_{M,1} x_{M,2} \ldots x_{M,k_M}

Output

Print Yes if every two people attended the same party at least once; print No otherwise.


Sample Input 1

3 3
2 1 2
2 2 3
2 1 3

Sample Output 1

Yes

Both Person 1 and Person 2 attended the 1-st party.

Both Person 2 and Person 3 attended the 2-nd party.

Both Person 1 and Person 3 attended the 3-rd party.

Therefore, every two people attended the same party at least once, so the answer is Yes.


Sample Input 2

4 2
3 1 2 4
3 2 3 4

Sample Output 2

No

Person 1 and Person 3 did not attend the same party, so the answer is No.

E - XX to XXX

Time Limit: 2 sec / Memory Limit: 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 - Calendar Validator

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

10^{100} 行 7 列の行列 A があり、任意の整数対 (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7) についてその (i,j) 成分は (i-1) \times 7 + j です。

N 行 M 列の行列 B が与えられるので、B が A から一部の矩形領域を(向きを変えずに)切り出したものであるかを判定してください。

制約

  • 1 \leq N \leq 10^4
  • 1 \leq M \leq 7
  • 1 \leq B_{i,j} \leq 10^9
  • 入力はすべて整数

入力

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

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

出力

B が A から一部の矩形領域を切り出したものであれば Yes と、そうでないなら No と出力せよ。


入力例 1

2 3
1 2 3
8 9 10

出力例 1

Yes

与えられる B は、A の左上 2 行 3 列を切り出したものとなっています。


入力例 2

2 1
1
2

出力例 2

No

与えられる B を 90 度回転させると A の左上 1 行 2 列と一致しますが、問題文中に「向きを変えずに」とある通り回転による一致は認められていないため、答えは No となります。


入力例 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

出力例 3

Yes

Score : 300 points

Problem Statement

There is a 10^{100} \times 7 matrix A, where the (i,j)-th entry is (i-1) \times 7 + j for every pair of integers (i,j)\ (1 \leq i \leq 10^{100}, 1 \leq j \leq 7).

Given an N \times M matrix B, determine whether B is some (unrotated) rectangular part of A.

Constraints

  • 1 \leq N \leq 10^4
  • 1 \leq M \leq 7
  • 1 \leq B_{i,j} \leq 10^9
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
B_{1,1} B_{1,2} \ldots B_{1,M}
B_{2,1} B_{2,2} \ldots B_{2,M}
\hspace{1.6cm}\vdots
B_{N,1} B_{N,2} \ldots B_{N,M}

Output

If B is some rectangular part of A, print Yes; otherwise, print No.


Sample Input 1

2 3
1 2 3
8 9 10

Sample Output 1

Yes

The given matrix B is the top-left 2 \times 3 submatrix of A.


Sample Input 2

2 1
1
2

Sample Output 2

No

Although the given matrix B would match the top-left 1 \times 2 submatrix of A after rotating 90 degrees, the Problem Statement asks whether B is an unrotated part of A, so the answer is No.


Sample Input 3

10 4
1346 1347 1348 1349
1353 1354 1355 1356
1360 1361 1362 1363
1367 1368 1369 1370
1374 1375 1376 1377
1381 1382 1383 1384
1388 1389 1390 1391
1395 1396 1397 1398
1402 1403 1404 1405
1409 1410 1411 1412

Sample Output 3

Yes
G - Add One Edge

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

N_1+N_2 頂点 M 辺の無向グラフがあります。i=1,2,\ldots,M に対し、i 番目の辺は頂点 a_i と頂点 b_i を結びます。
また、以下を満たすことが保障されます。

  • 1 \leq u,v \leq N_1 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
  • N_1+1 \leq u,v \leq N_1+N_2 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
  • 頂点 1 と頂点 N_1+N_2 は非連結

次の操作をちょうど 1 回行います。

  • 1 \leq u \leq N_1 を満たす整数 u と N_1+1 \leq v \leq N_1+N_2 を満たす整数 v を選び、頂点 u と頂点 v を結ぶ辺を追加する

操作後のグラフにおいて、頂点 1 と頂点 N_1+N_2 は必ず連結であることが示せます。そこで、頂点 1 と頂点 N_1+N_2 を結ぶ経路の長さ(辺の本数)の最小値を d とします。

操作で追加する辺を適切に選んだ時にありえる d の最大値を求めてください。

連結とは? 無向グラフの頂点 u,v が連結であるとは、頂点 u と頂点 v を結ぶ経路が存在することをいいます。

制約

  • 1 \leq N_1,N_2 \leq 1.5 \times 10^5
  • 0 \leq M \leq 3 \times 10^5
  • 1 \leq a_i \leq b_i \leq N_1+N_2
  • i \neq j ならば (a_i,b_i) \neq (a_j,b_j)
  • 1 \leq u,v \leq N_1 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
  • N_1+1 \leq u,v \leq N_1+N_2 を満たす整数 u,v に対し、頂点 u と頂点 v は連結
  • 頂点 1 と頂点 N_1+N_2 は非連結
  • 入力はすべて整数

入力

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

N_1 N_2 M
a_1 b_1
\vdots
a_M b_M

出力

答えを出力せよ。


入力例 1

3 4 6
1 2
2 3
4 5
4 6
1 3
6 7

出力例 1

5

u=2,v=5 として操作することで d=5 と出来ます。これが最大値です。


入力例 2

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

出力例 2

4

Score : 400 points

Problem Statement

We have an undirected graph with (N_1+N_2) vertices and M edges. For i=1,2,\ldots,M, the i-th edge connects vertex a_i and vertex b_i.
The following properties are guaranteed:

  • Vertex u and vertex v are connected, for all integers u and v with 1 \leq u,v \leq N_1.
  • Vertex u and vertex v are connected, for all integers u and v with N_1+1 \leq u,v \leq N_1+N_2.
  • Vertex 1 and vertex (N_1+N_2) are disconnected.

Consider performing the following operation exactly once:

  • choose an integer u with 1 \leq u \leq N_1 and an integer v with N_1+1 \leq v \leq N_1+N_2, and add an edge connecting vertex u and vertex v.

We can show that vertex 1 and vertex (N_1+N_2) are always connected in the resulting graph; so let d be the minimum length (number of edges) of a path between vertex 1 and vertex (N_1+N_2).

Find the maximum possible d resulting from adding an appropriate edge to add.

Definition of "connected" Two vertices u and v of an undirected graph are said to be connected if and only if there is a path between vertex u and vertex v.

Constraints

  • 1 \leq N_1,N_2 \leq 1.5 \times 10^5
  • 0 \leq M \leq 3 \times 10^5
  • 1 \leq a_i \leq b_i \leq N_1+N_2
  • (a_i,b_i) \neq (a_j,b_j) if i \neq j.
  • Vertex u and vertex v are connected for all integers u and v such that 1 \leq u,v \leq N_1.
  • Vertex u and vertex v are connected for all integers u and v such that N_1+1 \leq u,v \leq N_1+N_2.
  • Vertex 1 and vertex (N_1+N_2) are disconnected.
  • All input values are integers.

Input

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

N_1 N_2 M
a_1 b_1
\vdots
a_M b_M

Output

Print the answer.


Sample Input 1

3 4 6
1 2
2 3
4 5
4 6
1 3
6 7

Sample Output 1

5

If we set u=2 and v=5, the operation yields d=5, which is the maximum possible.


Sample Input 2

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

Sample Output 2

4