AtCoder Daily Training MEDIUM 2024/10/17 20:30start

C - Prefix?

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

英小文字のみからなる 2 つの文字列 S, T が与えられます。 S が T の接頭辞かどうかを判定してください。

接頭辞とは

長さ N の文字列 T_1T_2\ldots T_N の接頭辞とは、 0 \leq i \leq N を満たすある整数 i によって、T の先頭 i 文字目までの文字列 T_1T_2\ldots T_i として表される文字列です。例えば、T = abc のとき、T の接頭辞は、空文字列、a 、ab 、abc の 4 つです。

制約

S と T はそれぞれ英小文字のみからなる長さが 1 以上 100 以下の文字列

入力

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

S
T

出力

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

入力例 1

atco
atcoder

出力例 1

Yes

atco は atcoder の接頭辞です。よって、Yes を出力します。

入力例 2

code
atcoder

出力例 2

No

code は atcoder の接頭辞ではありません。よって、No を出力します。

入力例 3

abc
abc

出力例 3

Yes

文字列全体もその文字列の接頭辞であることに注意してください。

入力例 4

aaaa
aa

出力例 4

No

Score : 200 points

Problem Statement

You are given two strings S and T consisting of lowercase English letters. Determine if S is a prefix of T.

What is a prefix?

A prefix of a string T_1T_2\ldots T_N of length N is a string expressed as the first i characters of T, T_1T_2\ldots T_i, where i is an integer such that 0 \leq i \leq N. For example, when T = abc, there are four prefixes of T: an empty string, a, ab, and abc.

Constraints

S and T are strings of lengths between 1 and 100 (inclusive) consisting of lowercase English letters.

Input

Input is given from Standard Input in the following format:

S
T

Output

Print Yes if S is a prefix of T; print No otherwise. Note that the judge is case-sensitive.

Sample Input 1

atco
atcoder

Sample Output 1

Yes

atco is a prefix of atcoder. Thus, Yes should be printed.

Sample Input 2

code
atcoder

Sample Output 2

No

code is not a prefix of atcoder. Thus, No should be printed.

Sample Input 3

abc
abc

Sample Output 3

Yes

Note that a string is also a prefix of itself.

Sample Input 4

aaaa
aa

Sample Output 4

No

D - Pentagon

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下の図で表される正五角形 P があります。

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しいか判定してください。

制約

S_1,S_2,T_1,T_2 は A, B, C, D, E のいずれかの文字
S_1 \neq S_2
T_1 \neq T_2

入力

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

S_1S_2
T_1T_2

出力

P の点 S_1 と点 S_2 を結ぶ線分と、点 T_1 と点 T_2 を結ぶ線分の長さが等しい場合 Yes を、等しくない場合 No を出力せよ。

入力例 1

AC
EC

出力例 1

Yes

P の点 A と点 C を結ぶ線分と、P の点 E と点 C を結ぶ線分の長さは等しいです。

入力例 2

DA
EA

出力例 2

No

P の点 D と点 A を結ぶ線分と、P の点 E と点 A を結ぶ線分の長さは等しくありません。

入力例 3

BD
BD

出力例 3

Yes

Score : 200 points

Problem Statement

A regular pentagon P is shown in the figure below.

Determine whether the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2.

Constraints

Each of S_1, S_2, T_1, and T_2 is one of the characters A, B, C, D, and E.
S_1 \neq S_2
T_1 \neq T_2

Input

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

S_1S_2
T_1T_2

Output

If the length of the line segment connecting points S_1 and S_2 of P equals the length of the line segment connecting points T_1 and T_2, print Yes; otherwise, print No.

Sample Input 1

AC
EC

Sample Output 1

Yes

The length of the line segment connecting point A and point C of P equals the length of the line segment connecting point E and point C.

Sample Input 2

DA
EA

Sample Output 2

No

The length of the line segment connecting point D and point A of P does not equal the length of the line segment connecting point E and point A.

Sample Input 3

BD
BD

Sample Output 3

Yes

E - T-shirts

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

AtCoder 社はロゴ入りの T シャツを販売しています。

高橋君の N 日間の予定が 0, 1, 2 のみからなる長さ N の文字列 S で与えられます。
具体的には、1\leq i\leq N をみたす整数 i について、

S の i 文字目が 0 のとき、i 日目に何の予定も入っていません。
S の i 文字目が 1 のとき、i 日目に高橋君は食事に行く予定があります。
S の i 文字目が 2 のとき、i 日目に高橋君は競技プログラミングのイベントに行く予定が入っています。

高橋君は無地の T シャツを M 枚持っており、1 日目の直前の時点ですべて洗濯済みの状態となっています。
これに加えて、次の条件をみたすように行動できるように、高橋君は AtCoder のロゴ入りの T シャツを何枚か購入する事にしました。

食事に行く日には、無地の T シャツ 1 枚またはロゴ入りの T シャツ 1 枚を着用する。
競技プログラミングのイベントに行く日にはロゴ入りの T シャツ 1 枚を着用する。
何の予定もない日には T シャツを着用しない。加えて、その時点で着用済みの T シャツを全て洗濯する。洗濯した T シャツは翌日から着用できる。
一度着用した T シャツは次に洗濯するまで着用できない。

N 日間のうち予定が入っている日すべてについて、条件をみたす T シャツを着用できるようにするために、高橋君は最低何枚のTシャツを購入する必要があるか求めてください。新しく T シャツを購入する必要がないならば 0 を出力してください。
ただし、購入した T シャツも 1 日目の直前の時点ですべて洗濯済みの状態で存在するものとします。

制約

1\leq M\leq N\leq 1000
S は 0, 1, 2 のみからなる長さ N の文字列
N,M は整数

入力

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

N M
S

出力

問題文の条件をみたすように行動するために高橋君が購入する必要のある T シャツの枚数の最小値を出力せよ。
新しく購入する必要がないならば 0 を出力せよ。

入力例 1

6 1
112022

出力例 1

高橋君がロゴ入りの T シャツを 2 枚購入したとき、次のようにして高橋君は T シャツを着用することができます。

1 日目、高橋君はロゴ入りの T シャツを着用して食事に行きます。
2 日目、高橋君は無地の T シャツを着用して食事に行きます。
3 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
4 日目、高橋君は予定がないため、着用した T シャツをすべて洗濯します。これにより、1,2,3 日目に着用した T シャツを再び着用することが可能になります。
5 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。
6 日目、高橋君はロゴ入りの T シャツを着用して競技プログラミングのイベントに行きます。

高橋君がロゴ入りの T シャツを 1 枚以下しか購入しなかった場合には、どのようにしても条件をみたすように T シャツを着用することができません。
よって、2 を出力します。

入力例 2

3 1
222

出力例 2

入力例 3

2 1
01

出力例 3

高橋君は新しく T シャツを購入する必要はありません。

Score : 300 points

Problem Statement

AtCoder Inc. sells T-shirts with its logo.

You are given Takahashi's schedule for N days as a string S of length N consisting of 0, 1, and 2.
Specifically, for an integer i satisfying 1\leq i\leq N,

if the i-th character of S is 0, he has no plan scheduled for the i-th day;
if the i-th character of S is 1, he plans to go out for a meal on the i-th day;
if the i-th character of S is 2, he plans to attend a competitive programming event on the i-th day.

Takahashi has M plain T-shirts, all washed and ready to wear just before the first day.
In addition, to be able to satisfy the following conditions, he will buy several AtCoder logo T-shirts.

On days he goes out for a meal, he will wear a plain or logo T-shirt.
On days he attends a competitive programming event, he will wear a logo T-shirt.
On days with no plans, he will not wear any T-shirts. Also, he will wash all T-shirts worn at that point. He can wear them again from the next day onwards.
Once he wears a T-shirt, he cannot wear it again until he washes it.

Determine the minimum number of T-shirts he needs to buy to be able to wear appropriate T-shirts on all scheduled days during the N days. If he does not need to buy new T-shirts, print 0.
Assume that the purchased T-shirts are also washed and ready to use just before the first day.

Constraints

1\leq M\leq N\leq 1000
S is a string of length N consisting of 0, 1, and 2.
N and M are integers.

Input

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

N M
S

Output

Print the minimum number of T-shirts Takahashi needs to buy to be able to satisfy the conditions in the problem statement.
If he does not need to buy new T-shirts, print 0.

Sample Input 1

6 1
112022

Sample Output 1

If Takahashi buys two logo T-shirts, he can wear T-shirts as follows:

On the first day, he wears a logo T-shirt to go out for a meal.
On the second day, he wears a plain T-shirt to go out for a meal.
On the third day, he wears a logo T-shirt to attend a competitive programming event.
On the fourth day, he has no plans, so he washes all the worn T-shirts. This allows him to reuse the T-shirts worn on the first, second, and third days.
On the fifth day, he wears a logo T-shirt to attend a competitive programming event.
On the sixth day, he wears a logo T-shirt to attend a competitive programming event.

If he buys one or fewer logo T-shirts, he cannot use T-shirts to meet the conditions no matter what. Hence, print 2.

Sample Input 2

3 1
222

Sample Output 2

Sample Input 3

2 1
01

Sample Output 3

He does not need to buy new T-shirts.

F - Count Connected Components

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

頂点に 1 から N の番号が、辺に 1 から M の番号がついた N 頂点 M 辺の単純無向グラフが与えられます。辺 i は頂点 u_i と頂点 v_i を結んでいます。
グラフに含まれる連結成分の個数を求めてください。

注釈

単純無向グラフ とは、単純で辺に向きの無いグラフのことをいいます。
グラフが単純であるとは、グラフが自己ループや多重辺を含まないことをいいます。

あるグラフの 部分グラフ とは、元のグラフのいくつかの頂点といくつかの辺を選んでできるグラフのことをいいます。
グラフが連結であるとは、グラフに含まれるすべての頂点同士が辺を経由して互いに行き来できることをいいます。
連結成分 とは、連結な部分グラフのうち、そのグラフを含んだより大きい連結な部分グラフが存在しないものをいいます。

制約

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
入力で与えられるグラフは単純
入力される値はすべて整数

入力

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

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

出力

答えを出力せよ。

入力例 1

出力例 1

与えられるグラフに含まれる連結成分は次の 2 個です。

頂点 1, 2, 3 および辺 1, 2 からなる部分グラフ
頂点 4, 5 および辺 3 からなる部分グラフ

入力例 2

5 0

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices numbered 1 to N and M edges numbered 1 to M. Edge i connects vertex u_i and vertex v_i.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Constraints

1 \leq N \leq 100
0 \leq M \leq \frac{N(N - 1)}{2}
1 \leq u_i, v_i \leq N
The given graph is simple.
All values in the input 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

Output

Print the answer.

Sample Input 1

Sample Output 1

The given graph contains the following two connected components:

a subgraph formed from vertices 1, 2, 3, and edges 1, 2;
a subgraph formed from vertices 4, 5, and edge 3.

Sample Input 2

5 0

Sample Output 2

Sample Input 3

Sample Output 3

G - K-th Nearest

Time Limit: 3 sec / Memory Limit: 1024 MiB

配点 : 425 点

問題文

数直線上に N+Q 個の点 A_1,\dots,A_N,B_1,\dots,B_Q があり、点 A_i の座標は a_i、点 B_j の座標は b_j です。

j=1,2,\dots,Q それぞれについて、以下の問題に答えてください。

点 A_1,A_2,\dots,A_N のうち点 B_j との距離が k_j 番目に近い点を X としたとき、点 X と点 B_j との距離を求めよ。より厳密には、点 A_i と点 B_j との距離を d_i として、(d_1,d_2,\dots,d_N) を昇順に並び替えてできる列を (d_1',d_2',\dots,d_N') としたとき、d_{k_j}' を求めよ。

制約

1\leq N,Q \leq 10^5
-10^8\leq a_i,b_j \leq 10^8
1\leq k_j\leq N
入力は全て整数

入力

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

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

出力

Q 行出力せよ。 l\ (1\leq l \leq Q) 行目には、j=l としたときの問題に対する答えを整数として出力せよ。

入力例 1

出力例 1

7
3
13

1 番目のクエリについて説明します。

点 A_1,A_2,A_3,A_4 と点 B_1 との距離は順に 1,1,7,8 なので、点 B_1 との距離が 3 番目に近いのは点 A_3 です。よって、点 A_3 と点 B_1 との距離である 7 を出力します。

入力例 2

出力例 2

0
0

同じ座標に複数の点がある可能性もあります。

入力例 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

出力例 3

Score : 425 points

Problem Statement

There are N+Q points A_1,\dots,A_N,B_1,\dots,B_Q on a number line, where point A_i has a coordinate a_i and point B_j has a coordinate b_j.

For each j=1,2,\dots,Q, answer the following question:

Let X be the point among A_1,A_2,\dots,A_N that is the k_j-th closest to point B_j. Find the distance between points X and B_j. More formally, let d_i be the distance between points A_i and B_j. Sort (d_1,d_2,\dots,d_N) in ascending order to get the sequence (d_1',d_2',\dots,d_N'). Find d_{k_j}'.

Constraints

1 \leq N, Q \leq 10^5
-10^8 \leq a_i, b_j \leq 10^8
1 \leq k_j \leq N
All input values are integers.

Input

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

N Q
a_1 a_2 \dots a_N
b_1 k_1
b_2 k_2
\vdots
b_Q k_Q

Output

Print Q lines. The l-th line (1 \leq l \leq Q) should contain the answer to the question for j=l as an integer.

Sample Input 1

Sample Output 1

7
3
13

Let us explain the first query.

The distances from points A_1, A_2, A_3, A_4 to point B_1 are 1, 1, 7, 8, respectively, so the 3rd closest to point B_1 is point A_3. Therefore, print the distance between point A_3 and point B_1, which is 7.

Sample Input 2

Sample Output 2

0
0

There may be multiple points with the same coordinates.

Sample Input 3

10 5
-84 -60 -41 -100 8 -8 -52 -62 -61 -76
-52 5
14 4
-2 6
46 2
26 7

Sample Output 3