キーエンスプログラミングコンテスト2023夏（AtCoder Beginner Contest 315）

A - tcdr

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

配点 : 100 点

問題文

英小文字からなる文字列 S が与えられます。
S から a, e, i, o, u をすべて取り除いて得られる文字列を出力してください。
なお、S は a, e, i, o, u 以外の文字を一つ以上含みます。

制約

S は英小文字からなる長さ 1 以上 100 以下の文字列
S は a, e, i, o, u 以外の文字を一つ以上含む

入力

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

出力

答えを出力せよ。

入力例 1

atcoder

出力例 1

tcdr

S = atcoder のとき、1, 4, 6 文字目を取り除いて tcdr を得ます。

入力例 2

xyz

出力例 2

xyz

入力例 3

aaaabbbbcccc

出力例 3

bbbbcccc

Score : 100 points

Problem Statement

You are given a string S consisting of lowercase English letters.
Remove all occurrences of a, e, i, o, u from S and print the resulting string.
S contains at least one character other than a, e, i, o, u.

Constraints

S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.
S contains at least one character other than a, e, i, o, u.

Input

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

Output

Print the answer.

Sample Input 1

atcoder

Sample Output 1

tcdr

For S = atcoder, remove the 1-st, 4-th, and 6-th characters to get tcdr.

Sample Input 2

xyz

Sample Output 2

xyz

Sample Input 3

aaaabbbbcccc

Sample Output 3

bbbbcccc

B - The Middle Day

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

配点 : 200 点

問題文

AtCoder 国の暦では、一年は 1,2,\dots,M 番目の月の M か月からなり、そのうち i 番目の月は 1,2,\dots,D_i 番目の日の D_i 日からなります。
さらに、 AtCoder 国の一年の日数は奇数、即ち D_1+D_2+\dots+D_M は奇数です。
一年の真ん中の日は何番目の月の何番目の日か求めてください。
言い換えると、 1 番目の月の 1 番目の日を 1 日目としたときの (D_1+D_2+\dots+D_M+1)/2 日目が何番目の月の何番目の日かを求めてください。

制約

入力は全て整数
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M は奇数

入力

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

M
D_1 D_2 \dots D_M

出力

答えが a 番目の月の b 番目の日であるとき、以下の形式で出力せよ。

a b

入力例 1

12
31 28 31 30 31 30 31 31 30 31 30 31

出力例 1

7 2

この入力では、 1 年は 31+28+31+30+31+30+31+31+30+31+30+31=365 日からなります。
真ん中の日は (365+1)/2 = 183 日目であり、これを求めることを考えます。

1,2,3,4,5,6 番目の月に含まれる日数の合計は 181 日です。
7 番目の月の 1 番目の日は 182 日目です。
7 番目の月の 2 番目の日は 183 日目です。

以上から、答えが 7 番目の月の 2 番目の日であることが分かります。

入力例 2

1
1

出力例 2

1 1

入力例 3

6
3 1 4 1 5 9

出力例 3

5 3

Score : 200 points

Problem Statement

In the calendar of AtCoderLand, a year consists of M months: month 1, month 2, \dots, month M. The i-th month consists of D_i days: day 1, day 2, \dots, day D_i.
Furthermore, the number of days in a year is odd, that is, D_1+D_2+\dots+D_M is odd.
Find what day of what month is the middle day of the year.
In other words, let day 1 of month 1 be the first day, and find a and b such that the ((D_1+D_2+\dots+D_M+1)/2)-th day is day b of month a.

Constraints

All input values are integers.
1 \le M \le 100
1 \le D_i \le 100
D_1 + D_2 + \dots + D_M is odd.

Input

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

M
D_1 D_2 \dots D_M

Output

Let the answer be day b of month a, and print it in the following format:

a b

Sample Input 1

12
31 28 31 30 31 30 31 31 30 31 30 31

Sample Output 1

7 2

In this input, a year consists of 31+28+31+30+31+30+31+31+30+31+30+31=365 days.
Let us find the middle day, which is the ((365+1)/2 = 183)-th day.

Months 1,2,3,4,5,6 contain a total of 181 days.
Day 1 of month 7 is the 182-th day.
Day 2 of month 7 is the 183-th day.

Thus, the answer is day 2 of month 7.

Sample Input 2

1
1

Sample Output 2

1 1

Sample Input 3

6
3 1 4 1 5 9

Sample Output 3

5 3

C - Flavors

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

配点 : 300 点

問題文

N カップのアイスクリームがあります。
i カップ目の味は F_i 、美味しさは S_i ( S_i は偶数 ) です。

あなたは、 N 個のカップの中から 2 つを選んで食べることにしました。
このときの満足度は次のように定義されます。

食べたアイスクリームの美味しさを s,t ( 但し、 s \ge t ) とする。
- 2 つのカップの味が異なるなら、満足度は \displaystyle s+t である。
- そうでないなら、満足度は \displaystyle s + \frac{t}{2} である。

満足度として達成可能な最大値を求めてください。

制約

入力は全て整数
2 \le N \le 3 \times 10^5
1 \le F_i \le N
2 \le S_i \le 10^9
S_i は偶数

入力

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

N
F_1 S_1
F_2 S_2
\vdots
F_N S_N

出力

答えを整数として出力せよ。

入力例 1

出力例 1

2 カップ目と 4 カップ目のアイスを食べることを考えます。

2 カップ目の味は 2 、美味しさは 10 です。
4 カップ目の味は 3 、美味しさは 6 です。
両者の味は異なるので、満足度は 10+6=16 です。

以上より、満足度 16 を達成できます。
満足度を 16 より大きくすることはできません。

入力例 2

出力例 2

1 カップ目と 4 カップ目のアイスを食べることを考えます。

1 カップ目の味は 4 、美味しさは 10 です。
4 カップ目の味は 4 、美味しさは 12 です。
両者の味は同じなので、満足度は 12+\frac{10}{2}=17 です。

以上より、満足度 17 を達成できます。
満足度を 17 より大きくすることはできません。

Score : 300 points

Problem Statement

We have N cups of ice cream.
The flavor and deliciousness of the i-th cup are F_i and S_i, respectively (S_i is an even number).

You will choose and eat two of the N cups.
Your satisfaction here is defined as follows.

Let s and t (s \ge t) be the deliciousness of the eaten cups.
- If the two cups have different flavors, your satisfaction is \displaystyle s+t.
- Otherwise, your satisfaction is \displaystyle s + \frac{t}{2}.

Find the maximum achievable satisfaction.

Constraints

All input values are integers.
2 \le N \le 3 \times 10^5
1 \le F_i \le N
2 \le S_i \le 10^9
S_i is even.

Input

Input is given from Standard Input in the following format:

N
F_1 S_1
F_2 S_2
\vdots
F_N S_N

Output

Print the answer as an integer.

Sample Input 1

Sample Output 1

Consider eating the second and fourth cups.

The second cup has a flavor of 2 and deliciousness of 10.
The fourth cup has a flavor of 3 and deliciousness of 6.
Since they have different flavors, your satisfaction is 10+6=16.

Thus, you can achieve the satisfaction of 16.
You cannot achieve a satisfaction greater than 16.

Sample Input 2

Sample Output 2

Consider eating the first and fourth cups.

The first cup has a flavor of 4 and deliciousness of 10.
The fourth cup has a flavor of 4 and deliciousness of 12.
Since they have the same flavor, your satisfaction is 12+\frac{10}{2}=17.

Thus, you can achieve the satisfaction of 17.
You cannot achieve a satisfaction greater than 17.

D - Magical Cookies

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

配点 : 400 点

問題文

H \times W 枚のクッキーが H 行 W 列に並んでいます。
上から i 行目・左から j 列目のクッキーの色は英小文字 c_{i,j} で表されます。

これから、以下の手続きを行います。

1. 各行に対して次の操作を行う : その行に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

2. 各列に対して次の操作を行う : その列に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

3. 印のついたクッキーがあればそれらをすべて取り除いて 1. に戻り、なければ手続きを終了する。

手続きを終了した時点で残っているクッキーの枚数を求めてください。

制約

2 \leq H, W \leq 2000
c_{i,j} は英小文字である

入力

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

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

出力

答えを出力せよ。

入力例 1

4 3
aaa
aaa
abc
abd

出力例 1

以下で示す順で手続きを行います。

1. により、1, 2 行目のクッキーに印をつける。
2. により、1 列目のクッキーに印をつける。
3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
.bc
.bd

1. により、何もしない。
2. により、2 列目のクッキーに印をつける。
3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
..c
..d

1. により、何もしない。
2. により、何もしない。
3. により、印がついているクッキーが存在しないので手続きを終了する。

最終的に残っているクッキーの枚数は 2 枚です。

入力例 2

2 5
aaaaa
abcde

出力例 2

入力例 3

3 3
ooo
ooo
ooo

出力例 3

Score : 400 points

Problem Statement

There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.

2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.

3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

Constraints

2 \leq H, W \leq 2000
c_{i,j} is a lowercase English letter.

Input

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

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

Output

Print the answer.

Sample Input 1

4 3
aaa
aaa
abc
abd

Sample Output 1

The procedure is performed as follows.

1. Mark the cookies in the first and second rows.
2. Mark the cookies in the first column.
3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
.bc
.bd

1. Do nothing.
2. Mark the cookies in the second column.
3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
..c
..d

1. Do nothing.
2. Do nothing.
3. No cookies are marked, so terminate the procedure.

The final number of cookies remaining is 2.

Sample Input 2

2 5
aaaaa
abcde

Sample Output 2

Sample Input 3

3 3
ooo
ooo
ooo

Sample Output 3

E - Prerequisites

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

配点 : 425 点

問題文

1 から N までの番号がついた N 冊の本があります。
本 i には C_i 冊の前提となる本があり、そのうち j 冊目は本 P_{i,j} で、本 i を読む前にこの C_i 冊をすべて読む必要があります。
ただし、適切な順序を選ぶことですべての本を読むことができます。

あなたは本 1 を読むために必要な最小の数の本を読もうとしています。
本 1 以外に読まなければならない本の番号を読むべき順に出力してください。ただし、この条件下で読むべき本の集合は一意に定まります。
条件を満たす読む順番が複数考えられる場合は、そのいずれを出力しても構いません。

制約

2 \leq N \leq 2 \times 10^5
0 \leq C_i < N
\sum_{i=1}^{N} C_i \leq 2 \times 10^5
C_1 \geq 1
1 \leq P_{i,j} \leq N
1 \leq j < k \leq C_i のとき P_{i,j} \neq P_{i,k}
すべての本を読むことが可能である

入力

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

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

出力

本 1 を読むために読む必要のある最小の数の本を読むとき、それらの番号を読むべき順に空白区切りで出力せよ。

入力例 1

出力例 1

5 3 4 2

本 1 を読むために本 2,3,4、本 2 を読むために本 3,5、本 4 を読むために本 5 を読む必要があります。本 3,5,6 を読むために他の本を読む必要はありません。

このとき、例えば本 5,3,4,2 の順に読むことで本 1 を読むことができます。3 冊以下の本を読んだ状態で本 1 が読めるようになることはないため、これは答えの一つです。他にも本 3,5,4,2 の順などで読むことでも 4 冊の本を読んだ状態で本 1 を読むことができるようになります。

入力例 2

出力例 2

6 5 4 3 2

入力例 3

出力例 3

Score : 425 points

Problem Statement

We have N books numbered 1 to N.
Book i assumes that you have read C_i books, the j-th of which is book P_{i,j}: you must read all these C_i books before reading book i.
Here, you can read all the books in some order.

You are trying to read the minimum number of books required to read book 1.
Print the numbers of the books you must read excluding book 1 in the order they should be read. Under this condition, the set of books to read is uniquely determined.
If there are multiple reading orders that satisfy the condition, you may print any of them.

Constraints

2 \leq N \leq 2 \times 10^5
0 \leq C_i < N
\sum_{i=1}^{N} C_i \leq 2 \times 10^5
C_1 \geq 1
1 \leq P_{i,j} \leq N
P_{i,j} \neq P_{i,k} for 1 \leq j < k \leq C_i.
It is possible to read all the books.

Input

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

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

Output

Print the numbers of the books you must read to read book 1 in the order they should be read, with spaces in between.

Sample Input 1

Sample Output 1

5 3 4 2

To read book 1, you must read books 2,3,4; to read book 2, you must read books 3,5; to read book 4, you must read book 5. To read books 3,5,6, you do not have to read any other books.

For example, if you read books 5,3,4,2 in this order, you can read book 1. This is a correct answer, because you will never be able to read book 1 with three or fewer books read. As another example, reading books 3,5,4,2 in this order also allows you to read book 1 with 4 books read.

Sample Input 2

Sample Output 2

6 5 4 3 2

Sample Input 3

Sample Output 3

F - Shortcuts

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

配点 : 500 点

問題文

座標平面上でチェックポイント 1,2,\dots,N をこの順に通るレースが行われます。
チェックポイント i の座標は (X_i,Y_i) であり、すべてのチェックポイントの座標は異なります。

チェックポイント 1,N 以外のチェックポイントは、通過を省略することもできます。
ただし、通らなかったチェックポイントの個数を C として、以下の通りペナルティが課せられます。

C>0 なら \displaystyle 2^{C−1}
C=0 なら 0

チェックポイント 1 からチェックポイント N までの総移動距離（ユークリッド距離）とペナルティの和を s とします。
このとき、 s として達成可能な最小の値を求めてください。

制約

入力は全て整数
2 \le N \le 10^4
0 \le X_i,Y_i \le 10^4
i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)

入力

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを出力せよ。出力は、真の値との絶対誤差または相対誤差が 10^{−5} 以下のとき正解と判定される。

入力例 1

出力例 1

5.82842712474619009753

チェックポイント 1,2,5,6 を通過し、 3,4 の通過を省略することを考えます。

チェックポイント 1 \rightarrow 2 に移動する。 2 点間の距離は \sqrt{2} である。
チェックポイント 2 \rightarrow 5 に移動する。 2 点間の距離は 1 である。
チェックポイント 5 \rightarrow 6 に移動する。 2 点間の距離は \sqrt{2} である。
通らなかったチェックポイントは 2 つであり、このとき科せられるペナルティは 2 である。

以上のようにして、 s = 3 + 2\sqrt{2} \approx 5.828427 を達成できます。
s をこの値より小さくすることはできません。

入力例 2

出力例 2

24.63441361516795872523

入力例 3

出力例 3

110.61238353245736230207

Score : 500 points

Problem Statement

There is a race through checkpoints 1,2,\dots,N in this order on a coordinate plane.
The coordinates of checkpoint i are (X_i,Y_i), and all checkpoints have different coordinates.

Checkpoints other than checkpoints 1 and N can be skipped.
However, let C be the number of checkpoints skipped, and the following penalty will be imposed:

\displaystyle 2^{C−1} if C>0, and
0 if C=0.

Let s be the total distance traveled (Euclidean distance) from checkpoint 1 to checkpoint N plus the penalty.
Find the minimum achievable value as s.

Constraints

All input values are integers.
2 \le N \le 10^4
0 \le X_i,Y_i \le 10^4
(X_i,Y_i) \neq (X_j,Y_j) if i \neq j.

Input

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

N
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the answer. Your output is considered correct if the absolute or relative error from the true value is at most 10^{-5}.

Sample Input 1

Sample Output 1

5.82842712474619009753

Consider passing through checkpoints 1,2,5,6 and skip checkpoints 3,4.

Move from checkpoint 1 to 2. The distance between them is \sqrt{2}.
Move from checkpoint 2 to 5. The distance between them is 1.
Move from checkpoint 5 to 6. The distance between them is \sqrt{2}.
Two checkpoints are skipped, so the penalty of 2 is imposed.

In this way, you can achieve s = 3 + 2\sqrt{2} \approx 5.828427.
You cannot make s smaller than this value.

Sample Input 2

Sample Output 2

24.63441361516795872523

Sample Input 3

Sample Output 3

110.61238353245736230207

G - Ai + Bj + Ck = X (1 <= i, j, k <= N)

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

配点 : 550 点

問題文

整数 N,A,B,C,X が与えられるので、以下の条件を全て満たす整数組 (i,j,k) の数を求めてください。

1 \le i,j,k \le N
Ai+Bj+Ck=X

制約

入力は全て整数
1 \le N \le 10^6
1 \le A,B,C \le 10^9
1 \le X \le 3 \times 10^{15}

入力

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

N A B C X

出力

答えを整数として出力せよ。

入力例 1

5 3 1 5 15

出力例 1

条件を満たす整数組は以下の 3 つです。

(1,2,2) : 3 \times 1 + 1 \times 2 + 5 \times 2 = 15
(2,4,1) : 3 \times 2 + 1 \times 4 + 5 \times 1 = 15
(3,1,1) : 3 \times 3 + 1 \times 1 + 5 \times 1 = 15

入力例 2

1 1 1 1 1

出力例 2

入力例 3

100000 31415 92653 58979 1000000000

出力例 3

Score : 550 points

Problem Statement

You are given integers N,A,B,C,X. Find the number of triples of integers (i,j,k) that satisfy all of the following conditions.

1 \le i,j,k \le N
Ai+Bj+Ck=X

Constraints

All input values are integers.
1 \le N \le 10^6
1 \le A,B,C \le 10^9
1 \le X \le 3 \times 10^{15}

Input

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

N A B C X

Output

Print the answer as an integer.

Sample Input 1

5 3 1 5 15

Sample Output 1

The following three triples satisfy the conditions.

(1,2,2) : 3 \times 1 + 1 \times 2 + 5 \times 2 = 15
(2,4,1) : 3 \times 2 + 1 \times 4 + 5 \times 1 = 15
(3,1,1) : 3 \times 3 + 1 \times 1 + 5 \times 1 = 15

Sample Input 2

1 1 1 1 1

Sample Output 2

Sample Input 3

100000 31415 92653 58979 1000000000

Sample Output 3

Ex - Typical Convolution Problem

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

配点 : 650 点

問題文

数列 (A_1, A_2, \ldots , A_N) が与えられます。数列 (F_0, F_1, \ldots , F_N) を以下の式により定義します。

F_0 = 1
F_n = A_n\displaystyle\sum_{i+j<n}F_iF_j (1 \leq n \leq N)

F_1, \ldots , F_N を 998244353 で割った余りを求めてください。

制約

1 \leq N \leq 2 \times 10^5
0 \leq A_i < 998244353
入力される値はすべて整数

入力

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

N
A_1 A_2 \ldots A_N

出力

F_1, \ldots , F_N を 998244353 で割った余りをこの順に空白区切りで出力せよ。

入力例 1

5
1 2 3 4 5

出力例 1

1 6 48 496 6240

F_1 = A_1F_0F_0 = 1 です。 F_2 = A_2(F_0F_0+F_0F_1+F_1F_0) = 6 です。同様にして、F_3 = 48, F_4 = 496, F_5 = 6240 がわかります。

入力例 2

3
12345 678901 2345678

出力例 2

12345 790834943 85679169

Score : 650 points

Problem Statement

You are given a sequence (A_1, A_2, \ldots , A_N). Let us define a sequence (F_0, F_1, \ldots , F_N) by the following formulae.

F_0 = 1
F_n = A_n\displaystyle\sum_{i+j<n}F_iF_j (1 \leq n \leq N)

Find F_1, \ldots , F_N modulo 998244353.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq A_i < 998244353
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_N

Output

Print F_1, \ldots , F_N modulo 998244353 in this order, with spaces in between.

Sample Input 1

5
1 2 3 4 5

Sample Output 1

1 6 48 496 6240

F_1 = A_1F_0F_0 = 1. F_2 = A_2(F_0F_0+F_0F_1+F_1F_0) = 6. Similarly, we find F_3 = 48, F_4 = 496, F_5 = 6240.

Sample Input 2

3
12345 678901 2345678

Sample Output 2

12345 790834943 85679169