AtCoder Daily Training EASY 2026/02/12 16:00start

A - Spoiler

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 150 点

問題文

英小文字と | のみからなる文字列 S が与えられます。S は | をちょうど 2 個含むことが保証されます。

2 つの | の間にある文字および | を S から削除した文字列を出力してください。

制約

S は英小文字および | のみからなる長さ 2 以上 100 以下の文字列
S は | をちょうど 2 個含む

入力

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

出力

答えを出力せよ。

入力例 1

atcoder|beginner|contest

出力例 1

atcodercontest

2 つの | に挟まれた文字を全て削除して出力してください。

入力例 2

|spoiler|

出力例 2

全ての文字が削除されることもあります。

入力例 3

||xyz

出力例 3

xyz

Score: 150 points

Problem Statement

You are given a string S consisting of lowercase English letters and |. S is guaranteed to contain exactly two |s.

Remove the characters between the two |s, including the |s themselves, and print the resulting string.

Constraints

S is a string of length between 2 and 100, inclusive, consisting of lowercase English letters and |.
S contains exactly two |s.

Input

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

Output

Print the answer.

Sample Input 1

atcoder|beginner|contest

Sample Output 1

atcodercontest

Remove all the characters between the two |s and print the result.

Sample Input 2

|spoiler|

Sample Output 2

It is possible that all characters are removed.

Sample Input 3

||xyz

Sample Output 3

xyz

B - 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

C - Happy Number

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

正整数 N が与えられるので、 N がハッピー数であるかを判定してください。

ハッピー数とは、以下の操作を有限回繰り返すことで 1 になる非負整数を指します。

自身を、十進法表記の各桁の数字の二乗和を取った整数に置き換える。
- 例えば、操作前に 2026 であれば、この操作を 1 度行うと自身が 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44 に置き換えられます。

具体的なハッピー数の例は入出力例の説明を参照してください。

制約

N は 1 以上 2026 以下の整数

入力

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

出力

N がハッピー数であるなら Yes 、ハッピー数でないなら No と出力せよ。

入力例 1

出力例 1

Yes

2026 はハッピー数です。

2026 の十進法表記の各桁は 2,0,2,6 であり、それらの二乗和を取ると 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44 となります。
44 の十進法表記の各桁は 4,4 であり、それらの二乗和を取ると 4^2+4^2 = 16+16 = 32 となります。
32 の十進法表記の各桁は 3,2 であり、それらの二乗和を取ると 3^2+2^2 = 9+4 = 13 となります。
13 の十進法表記の各桁は 1,3 であり、それらの二乗和を取ると 1^2+3^2 = 1+9 = 10 となります。
10 の十進法表記の各桁は 1,0 であり、それらの二乗和を取ると 1^2+0^2 = 1+0 = 1 となります。

自身を十進法表記の各桁の数字の二乗和を取った整数に置き換える操作を 5 回繰り返すことで 1 になったので、 2026 はハッピー数です。

入力例 2

出力例 2

No

439 はハッピー数ではありません。

操作を繰り返すことで 439 \rightarrow 106 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow \dotsb と変化し、ここから操作を何度繰り返しても 1 にならないことが証明できます。

入力例 3

出力例 3

Yes

440 はハッピー数です。

Score : 200 points

Problem Statement

You are given a positive integer N. Determine whether N is a happy number.

A happy number is a non-negative integer that becomes 1 after repeating the following operation a finite number of times:

Replace it with the integer obtained by taking the sum of the squares of the digits in its decimal representation.
- For example, performing this operation once on 2026 replaces it with 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44.

For examples of happy numbers, refer to the explanations of sample inputs and outputs.

Constraints

N is an integer between 1 and 2026, inclusive.

Input

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

Output

If N is a happy number, output Yes; otherwise, output No.

Sample Input 1

Sample Output 1

Yes

2026 is a happy number.

The digits of 2026 in decimal representation are 2,0,2,6, and taking the sum of their squares gives 2^2+0^2+2^2+6^2 = 4+0+4+36 = 44.
The digits of 44 in decimal representation are 4,4, and taking the sum of their squares gives 4^2+4^2 = 16+16 = 32.
The digits of 32 in decimal representation are 3,2, and taking the sum of their squares gives 3^2+2^2 = 9+4 = 13.
The digits of 13 in decimal representation are 1,3, and taking the sum of their squares gives 1^2+3^2 = 1+9 = 10.
The digits of 10 in decimal representation are 1,0, and taking the sum of their squares gives 1^2+0^2 = 1+0 = 1.

2026 is a happy number because it became 1 after repeating the operation of replacing itself with the integer obtained by taking the sum of the squares of the digits in its decimal representation five times.

Sample Input 2

Sample Output 2

No

439 is not a happy number.

Repeating the operation makes it 439 \rightarrow 106 \rightarrow 37 \rightarrow 58 \rightarrow 89 \rightarrow 145 \rightarrow 42 \rightarrow 20 \rightarrow 4 \rightarrow 16 \rightarrow 37 \rightarrow \dotsb, and it can be proved that no matter how many times the operation is repeated from here, it will not become 1.

Sample Input 3

Sample Output 3

Yes

440 is a happy number.

D - AtCoder Amusement Park

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 遊園地には K 人乗りのアトラクションがあります。現在、このアトラクションの待機列には N グループが並んでいます。

先頭から i 番目 (1\leq i\leq N) のグループは A _ i 人組です。すべての i (1\leq i\leq N) について、A _ i\leq K です。

高橋君はこのアトラクションのスタッフとして、並んでいるグループを次の手順に従って誘導します。

はじめ、アトラクションには誰も誘導されておらず、空席は K 個あります。

待機列に並んでいるグループがない場合、アトラクションをスタートさせ、誘導を終了する。
アトラクションの空席の数と待機列の先頭に並んでいるグループの人数を比較し、次のどちらかを行う。
- 待機列の先頭に並んでいるグループの人数よりアトラクションの空席の数のほうが少ない場合、アトラクションをスタートさせる。スタートしたのち、アトラクションの空席が K 個になる。
- そうでない場合、待機列の先頭に並んでいるグループを全員アトラクションへ誘導する。先頭のグループが待機列から取り出され、アトラクションの空席がグループの人数ぶんだけ減少する。
1 に戻る。

ただし、誘導を開始したあとに追加でグループが並ぶことはないとします。以上の条件のもとで、この手順が有限回で終了することが示せます。

高橋君が誘導を開始してから誘導を終了するまで、何回アトラクションをスタートさせるか求めてください。

制約

1\leq N\leq100
1\leq K\leq100
1\leq A _ i\leq K\ (1\leq i\leq N)
入力はすべて整数

入力

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

N K
A _ 1 A _ 2 \ldots A _ N

出力

答えを出力せよ。

入力例 1

7 6
2 5 1 4 1 2 3

出力例 1

はじめ、7 つのグループは以下のように並んでいます。

高橋君の誘導の様子の一部を以下の図に示します。

はじめ、先頭に並んでいるグループは 2 人のグループで、空席は 6 個です。よって、高橋君は先頭のグループをアトラクションに誘導し、空席は 4 個になります。
次に、先頭に並んでいるグループは 5 人のグループで、空席の個数 4 より多いため、アトラクションをスタートさせます。
空席が 6 個になったため、先頭のグループをアトラクションに誘導し、空席は 1 個になります。
次に先頭に並んでいるのは 1 人なので、アトラクションに誘導し、空席は 0 個になります。

すべての誘導が終了するまでに、高橋君は 4 回アトラクションをスタートさせることになります。よって、4 を出力してください。

入力例 2

7 10
1 10 1 10 1 10 1

出力例 2

入力例 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

出力例 3

Score: 200 points

Problem Statement

The AtCoder amusement park has an attraction that can accommodate K people. Now, there are N groups lined up in the queue for this attraction.

The i-th group from the front (1\leq i\leq N) consists of A_i people. For all i (1\leq i\leq N), it holds that A_i \leq K.

Takahashi, as a staff member of this attraction, will guide the groups in the queue according to the following procedure.

Initially, no one has been guided to the attraction, and there are K empty seats.

If there are no groups in the queue, start the attraction and end the guidance.
Compare the number of empty seats in the attraction with the number of people in the group at the front of the queue, and do one of the following:
- If the number of empty seats is less than the number of people in the group at the front, start the attraction. Then, the number of empty seats becomes K again.
- Otherwise, guide the entire group at the front of the queue to the attraction. The front group is removed from the queue, and the number of empty seats decreases by the number of people in the group.
Go back to step 1.

Here, no additional groups will line up after the guidance has started. Under these conditions, it can be shown that this procedure will end in a finite number of steps.

Determine how many times the attraction will be started throughout the guidance.

Constraints

1\leq N\leq 100
1\leq K\leq 100
1\leq A_i\leq K\ (1\leq i\leq N)
All input values are integers.

Input

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

N K
A_1 A_2 \ldots A_N

Output

Print the answer.

Sample Input 1

7 6
2 5 1 4 1 2 3

Sample Output 1

Initially, the seven groups are lined up as follows:

Part of Takahashi's guidance is shown in the following figure:

Initially, the group at the front has 2 people, and there are 6 empty seats. Thus, he guides the front group to the attraction, leaving 4 empty seats.
Next, the group at the front has 5 people, which is more than the 4 empty seats, so the attraction is started.
After the attraction is started, there are 6 empty seats again, so the front group is guided to the attraction, leaving 1 empty seat.
Next, the group at the front has 1 person, so they are guided to the attraction, leaving 0 empty seats.

In total, he starts the attraction four times before the guidance is completed. Therefore, print 4.

Sample Input 2

7 10
1 10 1 10 1 10 1

Sample Output 2

Sample Input 3

15 100
73 8 55 26 97 48 37 47 35 55 5 17 62 2 60

Sample Output 3

E - Bipartize

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

N 頂点 M 辺の単純な無向グラフがあります。グラフは頂点 1, 頂点 2,\ldots, 頂点 N からなり、i 番目 (1\le i\le M) の辺は頂点 u _ i と頂点 v _ i を結んでいます。

あなたは、次の操作を 0 回以上行います。

まだ削除されていない辺をひとつ選び、削除する。

あなたの目的はグラフを二部グラフにすることです。操作を行ったあとのグラフを二部グラフにするために、最低でも何回操作を行う必要があるか求めてください。

グラフが単純であるとは

グラフが単純であるとは、自己ループ（u _ i=v _ i となる辺）や多重辺（u _ i=u _ j かつ v _ i=v _ j となる辺のペア）が存在しないことをいいます。

二部グラフとは

二部グラフとは、頂点をそれぞれ黒か白のどちらか一色で塗り、次の条件を満たすことができるグラフのことをいいます。

どの辺についても、その辺が結んでいるふたつの頂点に塗られた色は異なる。

制約

2\le N\le10
1\le M\le\dfrac{N(N-1)}2
1\le u _ i\lt v _ i\le N\ (1\le i\le M)
与えられるグラフは単純
入力はすべて整数

入力

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

出力

操作を行ったあとのグラフを二部グラフにするために、行う必要がある操作の回数を出力せよ。

入力例 1

出力例 1

例えば、頂点 1 と頂点 3 を結ぶ辺、頂点 3 と頂点 5 を結ぶ辺の 2 つを削除することでグラフを二部グラフにすることができます。

操作を 1 回以下行うことでグラフを二部グラフにすることはできないため、2 を出力してください。

入力例 2

2 1
1 2

出力例 2

グラフははじめから二部グラフです。よって、行う必要がある操作の回数は 0 回です。

入力例 3

出力例 3

Score : 350 points

Problem Statement

There is a simple undirected graph with N vertices and M edges. The graph consists of vertex 1, vertex 2,\ldots, vertex N, and the i-th edge (1\le i\le M) connects vertices u _ i and v _ i.

You will perform the following operation zero or more times:

Choose one edge that has not been deleted yet, and delete it.

Your goal is to make the graph bipartite. Find the minimum number of operations needed to make the graph after the operations bipartite.

What it means for a graph to be simple?

A graph is simple if and only if it has no self-loops (edges where u _ i=v _ i) or multi-edges (pairs of edges where u _ i=u _ j and v _ i=v _ j).

What is a bipartite graph?

A bipartite graph is a graph where it is possible to color each vertex black or white satisfying the following condition:

For every edge, the two vertices connected by that edge have different colors.

Constraints

2\le N\le10
1\le M\le\dfrac{N(N-1)}2
1\le u _ i\lt v _ i\le N\ (1\le i\le M)
The given graph is simple.
All input values are integers.

Input

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

N M
u _ 1 v _ 1
u _ 2 v _ 2
\vdots
u _ M v _ M

Output

Print the number of operations that need to be performed to make the graph bipartite.

Sample Input 1

Sample Output 1

You can make the graph bipartite by deleting two edges: for example, the edge connecting vertices 1 and 3, and the edge connecting vertices 3 and 5.

It is impossible to make the graph bipartite by performing one or less operations, so print 2.

Sample Input 2

2 1
1 2

Sample Output 2

The graph is bipartite from the beginning. Thus, the number of operations that need to be performed is 0.

Sample Input 3