AtCoder Daily Training MEDIUM 2024/05/15 20:00start

C - Roulette

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

配点 : 200 点

問題文

人 1 、人 2 、\ldots 、人 N の N 人の人がルーレットの賭けに参加しました。このルーレットの出目は、0 から 36 までの 37 個の整数のうちいずれかです。 i = 1, 2, \ldots, N について、人 i は 37 個の目のうち C_i 個の目 A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} に賭けました。

ルーレットが回され、出目は X でした。 X に賭けた人たちのうち、賭けた目の個数が最も少ない人たちの番号を昇順にすべて出力してください。

より形式的には、1 以上 N 以下の整数 i であって、下記の 2 つの条件をともに満たすものを昇順にすべて出力してください。

人 i は X に賭けている。
任意の j = 1, 2, \ldots, N について「人 j が X に賭けているならば、C_i \leq C_j 」が成り立つ。

出力するべき番号が 1 つも無い場合もあることに注意してください（入力例２を参照）。

制約

1 \leq N \leq 100
1 \leq C_i \leq 37
0 \leq A_{i, j} \leq 36
任意の i = 1, 2, \ldots, N について、A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} はすべて異なる。
0 \leq X \leq 36
入力はすべて整数

入力

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

N
C_1
A_{1, 1} A_{1, 2} \ldots A_{1, C_1}
C_2
A_{2, 1} A_{2, 2} \ldots A_{2, C_2}
\vdots
C_N
A_{N, 1} A_{N, 2} \ldots A_{N, C_N}
X

出力

出力するべき番号を昇順にすベて並べた列を、B_1, B_2, \ldots, B_K とする。下記の形式にしたがい、1 行目には出力するべき番号の個数 K を、 2 行目には B_1, B_2, \ldots, B_K を空白区切りで、それぞれ出力せよ。

K
B_1 B_2 \ldots B_K

入力例 1

出力例 1

2
1 4

ルーレットが回され、出目は 19 でした。 19 に賭けた人は人 1 、人 2 、人 4 の 3 人であり、それぞれが賭けた目の個数は 3, 4, 3 です。よって、19 に賭けた人のうち、賭けた目の個数が最も少ない人は人 1 と人 4 の 2 人です。

入力例 2

出力例 2

ルーレットが回され出目は 0 でしたが、0 に賭けた人は一人もいないため、出力するべき番号は 1 つもありません。

Score : 200 points

Problem Statement

N people, person 1, person 2, \ldots, person N, are playing roulette. The outcome of a spin is one of the 37 integers from 0 to 36. For each i = 1, 2, \ldots, N, person i has bet on C_i of the 37 possible outcomes: A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i}.

The wheel has been spun, and the outcome is X. Print the numbers of all people who have bet on X with the fewest bets, in ascending order.

More formally, print all integers i between 1 and N, inclusive, that satisfy both of the following conditions, in ascending order:

Person i has bet on X.
For each j = 1, 2, \ldots, N, if person j has bet on X, then C_i \leq C_j.

Note that there may be no number to print (see Sample Input 2).

Constraints

1 \leq N \leq 100
1 \leq C_i \leq 37
0 \leq A_{i, j} \leq 36
A_{i, 1}, A_{i, 2}, \ldots, A_{i, C_i} are all different for each i = 1, 2, \ldots, N.
0 \leq X \leq 36
All input values are integers.

Input

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

N
C_1
A_{1, 1} A_{1, 2} \ldots A_{1, C_1}
C_2
A_{2, 1} A_{2, 2} \ldots A_{2, C_2}
\vdots
C_N
A_{N, 1} A_{N, 2} \ldots A_{N, C_N}
X

Output

Let B_1, B_2, \ldots, B_K be the sequence of numbers to be printed in ascending order. Using the following format, print the count of numbers to be printed, K, on the first line, and B_1, B_2, \ldots, B_K separated by spaces on the second line:

K
B_1 B_2 \ldots B_K

Sample Input 1

Sample Output 1

2
1 4

The wheel has been spun, and the outcome is 19. The people who has bet on 19 are person 1, person 2, and person 4, and the number of their bets are 3, 4, and 3, respectively. Therefore, among the people who has bet on 19, the ones with the fewest bets are person 1 and person 4.

Sample Input 2

Sample Output 2

The wheel has been spun and the outcome is 0, but no one has bet on 0, so there is no number to print.

D - Election

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

配点 : 200 点

問題文

選挙が行われています。

N 人が投票を行い、i\,(1 \leq i \leq N) 番目の人は S_i という名前の候補者に投票しました。

得票数が最大の候補者の名前を答えてください。なお、与えられる入力では得票数が最大の候補者は一意に定まります。

制約

1 \leq N \leq 100
S_i は英小文字からなる長さ 1 以上 10 以下の文字列
N は整数
得票数が最大の候補者は一意に定まる

入力

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

N
S_1
S_2
\vdots
S_N

出力

得票数が最大の候補者の名前を出力せよ。

入力例 1

5
snuke
snuke
takahashi
takahashi
takahashi

出力例 1

takahashi

takahashi は 3 票、snuke は 2 票獲得しました。よって takahashi を出力します。

入力例 2

5
takahashi
takahashi
aoki
takahashi
snuke

出力例 2

takahashi

入力例 3

1
a

出力例 3

Score : 200 points

Problem Statement

An election is taking place.

N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.

Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.

Constraints

1 \leq N \leq 100
S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
N is an integer.
There is a unique candidate with the most votes.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2
\vdots
S_N

Output

Print the name of the candidate who received the most votes.

Sample Input 1

5
snuke
snuke
takahashi
takahashi
takahashi

Sample Output 1

takahashi

takahashi got 3 votes, and snuke got 2, so we print takahashi.

Sample Input 2

5
takahashi
takahashi
aoki
takahashi
snuke

Sample Output 2

takahashi

Sample Input 3

1
a

Sample Output 3

E - Merge Sequences

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

配点 : 300 点

問題文

長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。

長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。

C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
C を昇順にソートする。

A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。

制約

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
入力はすべて整数

入力

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

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

出力

答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。

入力例 1

4 3
3 14 15 92
6 53 58

出力例 1

1 3 4 7
2 5 6

C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。

入力例 2

4 4
1 2 3 4
100 200 300 400

出力例 2

1 2 3 4
5 6 7 8

入力例 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

出力例 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Score : 300 points

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
All values in the input are integers.

Input

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

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

Output

Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

F - Don’t be cycle

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

配点 : 300 点

問題文

N 頂点 M 辺の単純無向グラフが与えられます。頂点には 1 から N の番号がついており、i 番目の辺は頂点 A_i と頂点 B_i を結んでいます。このグラフから 0 本以上のいくつかの辺を削除してグラフが閉路を持たないようにするとき、削除する辺の本数の最小値を求めてください。

単純無向グラフとは

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

閉路とは

単純無向グラフが閉路を持つとは、i \neq j ならば v_i \neq v_j を満たす長さ 3 以上の頂点列 (v_0, v_1, \ldots, v_{n-1}) であって、各 0 \leq i < n に対し v_i と v_{i+1 \bmod n} の間に辺が存在するものがあることをいいます。

制約

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq A_i, B_i \leq N
与えられるグラフは単純
入力はすべて整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

答えを出力せよ。

入力例 1

出力例 1

頂点 1 と頂点 2 を結ぶ辺・頂点 4 と頂点 5 を結ぶ辺の 2 本を削除するなどの方法でグラフが閉路を持たないようにすることができます。
1 本以下の辺の削除でグラフが閉路を持たないようにすることはできないので、2 を出力します。

入力例 2

4 2
1 2
3 4

出力例 2

入力例 3

出力例 3

Score : 300 points

Problem Statement

You are given a simple undirected graph with N vertices and M edges. The vertices are numbered 1 to N, and the i-th edge connects vertex A_i and vertex B_i. Let us delete zero or more edges to remove cycles from the graph. Find the minimum number of edges that must be deleted for this purpose.

What is a simple undirected graph?

A simple undirected graph is a graph without self-loops or multi-edges whose edges have no direction.

What is a cycle?

A cycle in a simple undirected graph is a sequence of vertices (v_0, v_1, \ldots, v_{n-1}) of length at least 3 satisfying v_i \neq v_j if i \neq j such that for each 0 \leq i < n, there is an edge between v_i and v_{i+1 \bmod n}.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq M \leq 2 \times 10^5
1 \leq A_i, B_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
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answer.

Sample Input 1

Sample Output 1

One way to remove cycles from the graph is to delete the two edges between vertex 1 and vertex 2 and between vertex 4 and vertex 5.
There is no way to remove cycles from the graph by deleting one or fewer edges, so you should print 2.

Sample Input 2

4 2
1 2
3 4

Sample Output 2

Sample Input 3

Sample Output 3

G - Take ABC

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

配点 : 425 点

問題文

A , B , C の 3 種類の文字のみからなる文字列 S が与えられます。

S が連続な部分文字列として文字列 ABC を含む限り、下記の操作を繰り返します。

S に連続な部分文字列として含まれる文字列 ABC のうち、S の中で最も左にあるものを、S から削除する。

上記の手順を行った後の、最終的な S を出力してください。

制約

S は A , B , C のみからなる長さ 1 以上 2\times 10^5 以下の文字列

入力

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

出力

答えを出力せよ。

入力例 1

BAABCBCCABCAC

出力例 1

BCAC

与えられた文字列 S = BAABCBCCABCAC に対して、下記の通りに操作が行われます。

1 回目の操作で、S = BAABCBCCABCAC の 3 文字目から 5 文字目の ABC が削除され、その結果 S = BABCCABCAC となります。
2 回目の操作で、S = BABCCABCAC の 2 文字目から 4 文字目の ABC が削除され、その結果 S = BCABCAC となります。
3 回目の操作で、S = BCABCAC の 3 文字目から 5 文字目の ABC が削除され、その結果 S = BCAC となります。

よって、最終的な S は BCAC です。

入力例 2

ABCABC

出力例 2

この入力例では、最終的な S は空文字列です。

入力例 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

出力例 3

AAABBBCCC

Score : 425 points

Problem Statement

You are given a string S consisting of three different characters: A, B, and C.

As long as S contains the string ABC as a consecutive substring, repeat the following operation:

Remove the leftmost occurrence of the substring ABC from S.

Print the final string S after performing the above procedure.

Constraints

S is a string of length between 1 and 2 \times 10^5, inclusive, consisting of the characters A, B, and C.

Input

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

Output

Print the answer.

Sample Input 1

BAABCBCCABCAC

Sample Output 1

BCAC

For the given string S = BAABCBCCABCAC, the operations are performed as follows.

In the first operation, the ABC from the 3-rd to the 5-th character in S = BAABCBCCABCAC is removed, resulting in S = BABCCABCAC.
In the second operation, the ABC from the 2-nd to the 4-th character in S = BABCCABCAC is removed, resulting in S = BCABCAC.
In the third operation, the ABC from the 3-rd to the 5-th character in S = BCABCAC is removed, resulting in S = BCAC.

Therefore, the final S is BCAC.

Sample Input 2

ABCABC

Sample Output 2

In this example, the final S is an empty string.

Sample Input 3

AAABCABCABCAABCABCBBBAABCBCCCAAABCBCBCC

Sample Output 3

AAABBBCCC