AtCoder Daily Training EASY 2024/10/16 18:00start

A - Contest Result

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

配点 : 100 点

問題文

N 問の問題からなるコンテストが開催され、i\ (1\leq i\leq N) 問目の配点は A_i 点でした。

すぬけくんはこのコンテストに参加し、B_1,B_2,\ldots,B_M 問目の M 問を解きました。すぬけくんの総得点を求めてください。

ただし、総得点とは解いた問題の配点の総和を意味するものとします。

制約

1\leq M \leq N \leq 100
1\leq A_i \leq 100
1\leq B_1 < B_2 < \ldots < B_M \leq N
入力は全て整数

入力

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

N M
A_1 A_2 \dots A_N
B_1 B_2 \dots B_M

出力

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

入力例 1

3 2
10 20 30
1 3

出力例 1

すぬけくんは 1 問目と 3 問目を解きました。配点はそれぞれ 10 点と 30 点なので、総得点は 10+30=40 点です。

入力例 2

4 1
1 1 1 100
4

出力例 2

入力例 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

出力例 3

Score : 100 points

Problem Statement

There was a contest with N problems. The i-th (1\leq i\leq N) problem was worth A_i points.

Snuke took part in this contest and solved M problems: the B_1-th, B_2-th, \ldots, and B_M-th ones. Find his total score.

Here, the total score is defined as the sum of the points for the problems he solved.

Constraints

1\leq M \leq N \leq 100
1\leq A_i \leq 100
1\leq B_1 < B_2 < \ldots < B_M \leq N
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 \dots A_N
B_1 B_2 \dots B_M

Output

Print the answer as an integer.

Sample Input 1

3 2
10 20 30
1 3

Sample Output 1

Snuke solved the 1-st and 3-rd problems, which are worth 10 and 30 points, respectively. Thus, the total score is 10+30=40 points.

Sample Input 2

4 1
1 1 1 100
4

Sample Output 2

Sample Input 3

8 4
22 75 26 45 72 81 47 29
4 6 7 8

Sample Output 3

B - New Generation ABC

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

配点 : 100 点

問題文

AtCoder Beginner Contest は、今回で 214 回目の開催となりました。

今までの AtCoder Beginner Contest において、出題される問題数は次のように変化しました。

1 回目から 125 回目までは 4 問
126 回目から 211 回目までは 6 問
212 回目から 214 回目までは 8 問

N 回目の AtCoder Beginner Contest において出題された問題数を求めてください。

制約

1 \leq N \leq 214
入力は全て整数である。

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

Score : 100 points

Problem Statement

This is the 214-th AtCoder Beginner Contest (ABC).

The ABCs so far have had the following number of problems.

The 1-st through 125-th ABCs had 4 problems each.
The 126-th through 211-th ABCs had 6 problems each.
The 212-th through 214-th ABCs have 8 problems each.

Find the number of problems in the N-th ABC.

Constraints

1 \leq N \leq 214
All values in input are integers.

Input

Input is given from Standard Input in the following format:

Output

Print the answer.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

C - Cat

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

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

N は 1 以上 1000 以下の整数
S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。

入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。

入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。

入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

N is an integer between 1 and 1000, inclusive.
S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.

Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.

Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.

Sample Input 3

8
national

Sample Output 3

nyationyal

D - Distance Between Tokens

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

配点 : 200 点

問題文

H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。

マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。

一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？

制約

2 \leq H, W \leq 100
H, W は整数
S_i \, (1 \leq i \leq H) は o および - のみからなる長さ W の文字列
S_{i, j} = o となる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する

入力

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

H W
S_1
\vdots
S_H

出力

答えを出力せよ。

入力例 1

2 3
--o
o--

出力例 1

1 行目 3 列目に置かれている駒を下 \rightarrow 左 \rightarrow 左と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。

入力例 2

5 4
-o--
----
----
----
-o--

出力例 2

Score : 200 points

Problem Statement

There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.

The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.

Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?

Constraints

2 \leq H, W \leq 100
H and W are integers.
S_i \, (1 \leq i \leq H) is a string of length W consisting of o and -.
There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} = o.

Input

Input is given from Standard Input in the following format:

H W
S_1
\vdots
S_H

Output

Print the answer.

Sample Input 1

2 3
--o
o--

Sample Output 1

The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.

Sample Input 2

5 4
-o--
----
----
----
-o--

Sample Output 2

E - Attraction on Rainy Day

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

配点 : {400} 点

問題文

高橋君は AtCoder Land にある屋外アトラクションに K 回乗ろうとしています。このアトラクションの一回の所要時間は T です。

現在の時刻は 0 です。時刻 0 から N までの降水量が与えられます。時刻 i から時刻 i+1 までの降水量は P_i です (0\leq i\lt N)。アトラクションには時刻 0,1,…,N−T に乗ることができます。時刻 t にアトラクションに乗ると時刻 t+T にアトラクションから降りることができ、アトラクションに乗っている間に P_t+P_{t+1}+\dots+P_{t+T-1} だけ濡れます。

高橋君はアトラクションに乗っている間にできるだけ雨に濡れないようにしたいです。時刻 N までに K 回アトラクションに乗るとき、高橋君が濡れる量の総和の最小値を求めてください。ただし、乗り換えにかかる時間や待ち時間は 0 とし、アトラクションから降りた時刻に新たにアトラクションに乗ることができるものとします。

制約

1\leq N\leq 2\times 10^5
1\leq K\leq \min(N,100)
1\leq T\leq N/K
0\leq P_i\leq 10^{9}
入力は全て整数

入力

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

N K T
P_0 P_1 \ldots P_{N-1}

出力

答えを出力せよ。

入力例 1

8 3 2
3 5 10 4 1 7 3 9

出力例 1

次のようにアトラクションに 3 回乗ることで濡れる量を合計で 23 にすることができ、これが最小です。

アトラクションに時刻 0 に乗り、時刻 2 に降りる。この間に P_0+P_1=3+5=8 濡れる。
アトラクションに時刻 3 に乗り、時刻 5 に降りる。この間に P_3+P_4=4+1=5 濡れる。
アトラクションに時刻 5 に乗り、時刻 7 に降りる。この間に P_5+P_6=7+3=10 濡れる。

入力例 2

5 1 3
1000 1 10000 100 10

出力例 2

入力例 3

15 5 2
401054171 63773035 986525245 157986893 799814573 139201145 649233932 351289844 409065258 406122133 957285954 529460482 21179081 795984182 727882733

出力例 3

3522058414