AtCoder Daily Training EASY 2024/11/19 19:30start

A - Legendary Players

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

AtCoder では、レーティング上位 10 人のハンドルネームには金色の冠が、上位 1 人のハンドルネームには白金色の冠が表示されます。

このコンテストが開始した時点で、アルゴリズム部門での上位 10 人に入っているプレイヤーのハンドルネームとレーティングは以下のようになっています。

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

上記のプレイヤーのハンドルネーム S が与えられるので、その人のレーティングを出力してください。

制約

S はアルゴリズム部門でレーティング上位 10 人に入っているプレイヤーのハンドルネームのいずれかと等しい。

入力

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

出力

対応するプレイヤーのレーティングを 1 行で出力せよ。

入力例 1

tourist

出力例 1

このコンテストが開始した時点において、 tourist さんのアルゴリズム部門のレーティングは 3858 です。

入力例 2

semiexp

出力例 2

このコンテストが開始した時点において、 semiexp さんのアルゴリズム部門のレーティングは 3481 です。

Score : 100 points

Problem Statement

In AtCoder, the top 10 rated players' usernames are displayed with a gold crown, and the top-rated player's username is displayed with a platinum crown.

At the start of this contest, the usernames and ratings of the top 10 rated players in the algorithm category are as follows:

tourist 3858
ksun48 3679
Benq 3658
Um_nik 3648
apiad 3638
Stonefeang 3630
ecnerwala 3613
mnbvmar 3555
newbiedmy 3516
semiexp 3481

You are given the username S of one of these players. Print that player's rating.

Constraints

S is equal to one of the usernames of the top 10 rated players in the algorithm category.

Input

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

Output

Print the rating of the corresponding player in one line.

Sample Input 1

tourist

Sample Output 1

At the start of this contest, the rating of tourist in the algorithm category is 3858.

Sample Input 2

semiexp

Sample Output 2

At the start of this contest, the rating of semiexp in the algorithm category is 3481.

B - Majority

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

ある提案に対し、N 人の人が賛成か反対かを表明しています。なお、N は奇数です。

i \, (i = 1, 2, \dots, N) 番目の人の意見は文字列 S_i で表され、S_i = For のとき賛成しており、S_i = Against のとき反対しています。

過半数の人がこの提案に賛成しているかどうかを判定してください。

制約

N は 1 以上 99 以下の奇数
全ての i = 1, 2, \dots, N に対し、S_i = For または S_i = Against

入力

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

N
S_1
S_2
\vdots
S_N

出力

N 人のうち過半数が提案に賛成しているならば Yes、そうでなければ No と出力せよ。

入力例 1

3
For
Against
For

出力例 1

Yes

提案に賛成している人数は 2 人であり、これは半数を超えているので Yes と出力します。

入力例 2

5
Against
Against
For
Against
For

出力例 2

No

提案に賛成している人数は 2 人であり、これは半数以下なので No と出力します。

入力例 3

1
For

出力例 3

Yes

Score : 100 points

Problem Statement

There are N people. Each of them agrees or disagrees with a proposal. Here, N is an odd number.

The i-th (i = 1, 2, \dots, N) person's opinion is represented by a string S_i: the person agrees if S_i = For and disagrees if S_i = Against.

Determine whether the majority agrees with the proposal.

Constraints

N is an odd number between 1 and 99, inclusive.
S_i = For or S_i = Against, for all i = 1, 2, \dots, N.

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print Yes if the majority of the N people agree with the proposal; print No otherwise.

Sample Input 1

3
For
Against
For

Sample Output 1

Yes

The proposal is supported by two people, which is the majority, so Yes should be printed.

Sample Input 2

5
Against
Against
For
Against
For

Sample Output 2

No

The proposal is supported by two people, which is not the majority, so No should be printed.

Sample Input 3

1
For

Sample Output 3

Yes

C - Adjacency Matrix

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。

G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。

i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。

ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。

制約

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
入力される値はすべて整数

入力

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

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

出力

N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。

入力例 1

出力例 1

頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。

同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。

入力例 2

2
0 0
0 0

出力例 2

G に辺が存在しないこともあります。

入力例 3

出力例 3

Score: 150 points

Problem Statement

There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.

You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.

For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.

Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.

Constraints

2 \leq N \leq 100
A_{i,j} \in \lbrace 0,1 \rbrace
A_{i,i} = 0
A_{i,j} = A_{j,i}
All input values are integers.

Input

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

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

Output

Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.

Sample Input 1

Sample Output 1

Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.

Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.

Sample Input 2

2
0 0
0 0

Sample Output 2

G may have no edges.

Sample Input 3

Sample Output 3

D - Append

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

空の数列 A があります。クエリが Q 個与えられるので、与えられた順に処理してください。
クエリは次の 2 種類のいずれかです。

1 x: A の末尾に x を追加する。
2 k: A の後ろから k 番目の値を求める。このクエリが与えられるとき、A の長さは k 以上であることが保証される。

制約

1 \leq Q \leq 100
1 種類目のクエリにおいて x は 1 \leq x \leq 10^9 を満たす整数
2 種類目のクエリにおいて k はその時点の数列 A の長さ以下の正の整数

入力

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

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

クエリは以下の 2 つのいずれかの形式である。

1 x

2 k

出力

2 種類目のクエリの個数を q として q 行出力せよ。
i 行目にはそのような i 回目のクエリに対する答えを出力せよ。

入力例 1

出力例 1

30
20

最初 A は空である。
1 番目のクエリにより A の末尾に 20 が追加され A=(20) となる。
2 番目のクエリにより A の末尾に 30 が追加され A=(20,30) となる。
3 番目のクエリの答えは A=(20,30) の後ろから 1 番目の値の 30 である。
4 番目のクエリにより A の末尾に 40 が追加され A=(20,30,40) となる。
5 番目のクエリの答えは A=(20,30,40) の後ろから 3 番目の値の 20 である。

Score: 200 points

Problem Statement

You have an empty sequence A. There are Q queries given, and you need to process them in the order they are given.
The queries are of the following two types:

1 x: Append x to the end of A.
2 k: Find the k-th value from the end of A. It is guaranteed that the length of A is at least k when this query is given.

Constraints

1 \leq Q \leq 100
In the first type of query, x is an integer satisfying 1 \leq x \leq 10^9.
In the second type of query, k is a positive integer not greater than the current length of sequence A.

Input

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

Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q

Each query is in one of the following two formats:

1 x

2 k

Output

Print q lines, where q is the number of queries of the second type.
The i-th line should contain the answer to the i-th such query.

Sample Input 1

Sample Output 1

30
20

Initially, A is empty.
The first query appends 20 to the end of A, making A=(20).
The second query appends 30 to the end of A, making A=(20,30).
The answer to the third query is 30, which is the 1-st value from the end of A=(20,30).
The fourth query appends 40 to the end of A, making A=(20,30,40).
The answer to the fifth query is 20, which is the 3-rd value from the end of A=(20,30,40).

E - Index × A(Continuous ver.)

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の整数列 A=(A_1,A_2,\dots,A_N) が与えられます。

長さ M の A の連続部分列 B=(B_1,B_2,\dots,B_M) に対する、\displaystyle \sum_{i=1}^{M} i \times B_i の最大値を求めてください。

注記

数列の連続部分列とは、数列の先頭から 0 個以上、末尾から 0 個以上の要素を削除して得られる列のことをいいます。

例えば (2, 3) や (1, 2, 3) は (1, 2, 3, 4) の連続部分列ですが、(1, 3) や (3,2,1) は (1, 2, 3, 4) の連続部分列ではありません。

制約

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
入力は全て整数。

入力

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

N M
A_1 A_2 \dots A_N

出力

答えを出力せよ。

入力例 1

4 2
5 4 -1 8

出力例 1

B=(A_3,A_4) とした場合、\displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15 となります。16 以上の値を達成することはできないため、解は 15 です。

B=(A_1,A_4) などを選ぶことができないことに注意してください。

入力例 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3

出力例 2

Score : 300 points

Problem Statement

You are given an integer sequence A=(A_1,A_2,\dots,A_N) of length N.

Find the maximum value of \displaystyle \sum_{i=1}^{M} i \times B_i for a contiguous subarray B=(B_1,B_2,\dots,B_M) of A of length M.

Notes

A contiguous subarray of a number sequence is a sequence that is obtained by removing 0 or more initial terms and 0 or more final terms from the original number sequence.

For example, (2, 3) and (1, 2, 3) are contiguous subarrays of (1, 2, 3, 4), but (1, 3) and (3,2,1) are not contiguous subarrays of (1, 2, 3, 4).

Constraints

1 \le M \le N \le 2 \times 10^5
- 2 \times 10^5 \le A_i \le 2 \times 10^5
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
A_1 A_2 \dots A_N

Output

Print the answer.

Sample Input 1

4 2
5 4 -1 8

Sample Output 1

When B=(A_3,A_4), we have \displaystyle \sum_{i=1}^{M} i \times B_i = 1 \times (-1) + 2 \times 8 = 15. Since it is impossible to achieve 16 or a larger value, the solution is 15.

Note that you are not allowed to choose, for instance, B=(A_1,A_4).

Sample Input 2

10 4
-3 1 -4 1 -5 9 -2 6 -5 3