AtCoder Daily Training EASY 2025/06/25 18:00start

A - Weekly Records

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋君は N 週間の間、自分が歩いた歩数を記録しました。i 日目に歩いた歩数は A_i でした。

各週に高橋君が歩いた歩数の合計を求めてください。
より正確には、1 週目( 1 日目から 7 日目まで)の 7 日間の歩数の合計、2 週目( 8 日目から 14 日目まで)の 7 日間の歩数の合計、……をそれぞれ求めてください。

制約

1 \leq N \leq 10
0 \leq A_i \leq 10^5
入力は整数

入力

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

N
A_1 A_2 \ldots A_{7N}

出力

i 週目に歩いた歩数を B_i とする。B_1,B_2,\ldots,B_N をこの順に空白区切りで出力せよ。

入力例 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

出力例 1

28000 35000

高橋君は 1 週目に 1000+2000+3000+4000+5000+6000+7000=28000 歩あるき、2 週目に 2000+3000+4000+5000+6000+7000+8000=35000 歩あるきました。

入力例 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

出力例 2

314333 419427 335328

Score : 100 points

Problem Statement

Takahashi has recorded the number of steps he walked for N weeks. He walked A_i steps on the i-th day.

Find the total number of steps Takahashi walked each week.
More precisely, find the sum of the steps for the first week (the 1-st through 7-th day), the sum of the steps for the second week (the 8-th through 14-th day), and so on.

Constraints

1 \leq N \leq 10
0 \leq A_i \leq 10^5
All input values are integers.

Input

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

N
A_1 A_2 \ldots A_{7N}

Output

Let B_i be the number of steps walked for the i-th week. Print B_1,B_2,\ldots,B_N in this order, separated by spaces.

Sample Input 1

2
1000 2000 3000 4000 5000 6000 7000 2000 3000 4000 5000 6000 7000 8000

Sample Output 1

28000 35000

For the first week, he walked 1000+2000+3000+4000+5000+6000+7000=28000 steps, and for the second week, he walked 2000+3000+4000+5000+6000+7000+8000=35000 steps.

Sample Input 2

3
14159 26535 89793 23846 26433 83279 50288 41971 69399 37510 58209 74944 59230 78164 6286 20899 86280 34825 34211 70679 82148

Sample Output 2

314333 419427 335328

B - Leftrightarrow

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

<, =, > のみからなる文字列 S が与えられます。
S が 双方向矢印型 の文字列であるか判定してください。
ただし、文字列 S が双方向矢印型の文字列であるとは、ある正整数 k が存在して、
S が 1 個の < 、k 個の = 、1 個の > をこの順に連結した長さ (k+2) の文字列であることをいいます。

制約

S は <, =, > のみからなる長さ 3 以上 100 以下の文字列

入力

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

出力

S が 双方向矢印型 の文字列ならば Yes を、そうでないならば No を出力せよ。

入力例 1

<====>

出力例 1

Yes

<====> は、1 個の < 、4 個の = 、1 個の > をこの順に連結した文字列であり、双方向矢印型の文字列です。
よって、Yes を出力します。

入力例 2

==>

出力例 2

No

==> は双方向矢印型の文字列の条件をみたしていません。よって、No を出力します。

入力例 3

<>>

出力例 3

No

Scoring: 100 points

Problem Statement

You are given a string S consisting of <, =, and >.
Determine whether S is a bidirectional arrow string.
A string S is a bidirectional arrow string if and only if there is a positive integer k such that S is a concatenation of one <, k =s, and one >, in this order, with a length of (k+2).

Constraints

S is a string of length between 3 and 100, inclusive, consisting of <, =, and >.

Input

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

Output

If S is a bidirectional arrow string, print Yes; otherwise, print No.

Sample Input 1

<====>

Sample Output 1

Yes

<====> is a concatenation of one <, four =s, and one >, in this order, so it is a bidirectional arrow string.
Hence, print Yes.

Sample Input 2

==>

Sample Output 2

No

==> does not meet the condition for a bidirectional arrow string.
Hence, print No.

Sample Input 3

<>>

Sample Output 3

No

C - Light It Up

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

xy 平面上に N 人の人 1,2,\dots,N がおり、人 i は座標 (X_i,Y_i) にいます。
このうち、 K 人の人 A_1,A_2,\dots,A_K に同じ強さの明かりを持たせます。
座標 (x,y) にいる人が強さ R の明かりを持っている時、その明かりによって中心 (x,y) 、半径 R の円の内部全体(境界を含む)が照らされます。
すべての人が少なくとも 1 つの明かりによって照らされるために必要な明かりの強さの最小値を求めてください。

制約

入力は全て整数
1 \le K < N \le 1000
1 \le A_1 < A_2 < \dots < A_K \le N
|X_i|,|Y_i| \le 10^5
i \neq j ならば (X_i,Y_i) \neq (X_j,Y_j)

入力

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

N K
A_1 A_2 \dots A_K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

出力

答えを実数として出力せよ。
出力された解と想定解との絶対誤差または相対誤差が 10^{-5} 以下であるならば、出力は正しいと見なされる。

入力例 1

出力例 1

2.23606797749978969

この入力では人が 4 人おり、そのうち人 2,3 が明かりを持ちます。
R \ge \sqrt{5} \approx 2.236068 である時、すべての人が少なくとも 1 つの明かりによって照らされます。

入力例 2

2 1
2
-100000 -100000
100000 100000

出力例 2

282842.712474619009

入力例 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

出力例 3

130379.280458974768

Score : 200 points

Problem Statement

There are N people numbered 1, 2, \dots, N in the xy-plane. Person i is at the coordinates (X_i, Y_i).
K of these people, Persons A_1, A_2, \dots, A_K, will receive lights of the same strength.
When a person at coordinates (x, y) has a light of strength R, it lights up the interior of a circle of radius R centered at (x, y) (including the boundary).
Find the minimum strength of the lights needed for every person to be lit by at least one light.

Constraints

All values in input are integers.
1 \le K < N \le 1000
1 \le A_1 < A_2 < \dots < A_K \le N
|X_i|,|Y_i| \le 10^5
(X_i,Y_i) \neq (X_j,Y_j), if i \neq j.

Input

Input is given from Standard Input in the following format:

N K
A_1 A_2 \dots A_K
X_1 Y_1
X_2 Y_2
\vdots
X_N Y_N

Output

Print the answer as a real number.
Your output will be considered correct if its absolute or relative error from the judge's output is at most 10^{-5}.

Sample Input 1

Sample Output 1

2.23606797749978969

This input contains four people. Among them, Persons 2 and 3 will have lights.
Every person will be lit by at least one light if R \ge \sqrt{5} \approx 2.236068.

Sample Input 2

2 1
2
-100000 -100000
100000 100000

Sample Output 2

282842.712474619009

Sample Input 3

8 3
2 6 8
-17683 17993
93038 47074
58079 -57520
-41515 -89802
-72739 68805
24324 -73073
71049 72103
47863 19268

Sample Output 3

130379.280458974768

D - First Query Problem

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

整数 N と長さ N の数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。

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

1 k x : A _ k の値を x に変更する。
2 k : A _ k の値を出力する。

制約

1 \leq N \leq 10 ^ 5
1 \leq Q \leq 10 ^ 5
0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
どのクエリについても、1\leq k\leq N
1 番目の形式のクエリについて、0\leq x\leq 10 ^ 9
2 番目の形式のクエリが 1 つ以上存在する
入力はすべて整数

入力

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

N
A _ 1 A _ 2 \ldots A _ N
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

ただし、\operatorname{query} _ i は i 個目のクエリを表しており、次の形式のいずれかで与えられる。

1 k x

2 k

出力

2 番目の形式のクエリの回数を q 回として q 行出力せよ。 j\ (1\leq j\leq q) 行目には、2 番目の形式のクエリのうち j 個目のものに対する答えを出力せよ。

入力例 1

出力例 1

はじめ、A=(1,3,5) です。

1 つめのクエリにおいて、A=(1,3,5) です。A _ 2=3 なので、3 を出力します。
2 つめのクエリにおいて、A=(1,3,5) です。A _ 3=5 なので、5 を出力します。
3 つめのクエリでは、A _ 3 の値を 0 に変更し、A=(1,3,0) となります。
4 つめのクエリにおいて、A=(1,3,0) です。A _ 3=0 なので、0 を出力します。
5 つめのクエリでは、A _ 2 の値を 8 に変更し、A=(1,8,0) となります。
6 つめのクエリにおいて、A=(1,8,0) です。A _ 2=8 なので、8 を出力します。
7 つめのクエリにおいて、A=(1,8,0) です。A _ 1=1 なので、1 を出力します。

入力例 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

出力例 2

入力例 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

出力例 3

Score : 200 points

Problem Statement

You are given an integer N and a sequence A=(A _ 1,A _ 2,\ldots,A _ N) of length N.

Given Q queries, process them in the given order. Each query is of one of the following two kinds:

1 k x : set the value A _ k to x.
2 k : print the value A _ k.

Constraints

1 \leq N \leq 10 ^ 5
1 \leq Q \leq 10 ^ 5
0 \leq A _ i \leq 10 ^ 9\ (1\leq i\leq N)
1\leq k\leq N for all queries.
0\leq x\leq 10 ^ 9 for all queries of the first kind.
There is at least one query of the second kind.
All values in the input are integers.

Input

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

N
A _ 1 A _ 2 \ldots A _ N
Q
\operatorname{query} _ 1
\operatorname{query} _ 2
\vdots
\operatorname{query} _ Q

Here, \operatorname{query} _ i denotes the i-th query, given in one of the following formats:

1 k x

2 k

Output

Print q lines, where q is the number of queries of the second kind. The j-th (1\leq j\leq q) line should contain the response to the j-th such query.

Sample Input 1

Sample Output 1

Initially, A=(1,3,5).

For the 1-st query, A=(1,3,5), where A _ 2=3, so 3 should be printed.
For the 2-nd query, A=(1,3,5), where A _ 3=5, so 5 should be printed.
The 3-rd query sets the value A _ 3 to 0, making A=(1,3,0).
For the 4-th query, A=(1,3,0), where A _ 3=0, so 0 should be printed.
The 5-th query sets the value A _ 2 to 8, making A=(1,8,0).
For the 6-th query, A=(1,8,0), where A _ 2=8, so 8 should be printed.
For the 7-th query, A=(1,8,0), where A _ 1=1, so 1 should be printed.

Sample Input 2

5
22 2 16 7 30
10
1 4 0
1 5 0
2 2
2 3
2 4
2 5
1 4 100
1 5 100
2 3
2 4

Sample Output 2

Sample Input 3

7
478 369 466 343 541 42 165
20
2 1
1 7 729
1 6 61
1 6 838
1 3 319
1 4 317
2 4
1 1 673
1 3 176
1 5 250
1 1 468
2 6
1 7 478
1 5 595
2 6
1 6 599
1 6 505
2 3
2 5
2 1

Sample Output 3

E - Don’t be cycle

Time Limit: 2 sec / Memory Limit: 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