AtCoder Daily Training EASY 2026/08/07 18:00start

A - First ABC

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

A, B, C からなる文字列 S が与えられます。S は A, B, C を全て含むことが保証されます。

S を左から 1 文字ずつ見ていったときに、はじめて次の条件を満たした状態になるのは、左から何文字目まで見たときですか？

A, B, C が全て 1 回以上出現している。

制約

3 \leq N \leq 100
S は A, B, C からなる長さ N の文字列
S は A, B, C を全て含む

入力

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

N
S

出力

答えを出力せよ。

入力例 1

5
ACABB

出力例 1

左から 4 文字目までに A は 2 回, B は 1 回, C は 1 回出現していて、条件を満たします。
3 文字目以前では条件を満たさないので答えは 4 です。

入力例 2

4
CABC

出力例 2

左から 3 文字目までに A, B, C は 1 回ずつ出現していて、条件を満たします。

入力例 3

30
AABABBBABABBABABCABACAABCBACCA

出力例 3

Score : 100 points

Problem Statement

You are given a string S consisting of A, B, and C. S is guaranteed to contain all of A, B, and C.

If the characters of S are checked one by one from the left, how many characters will have been checked when the following condition is satisfied for the first time?

All of A, B, and C have appeared at least once.

Constraints

3 \leq N \leq 100
S is a string of length N consisting of A, B, and C.
S contains all of A, B, and C.

Input

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

N
S

Output

Print the answer.

Sample Input 1

5
ACABB

Sample Output 1

In the first four characters from the left, A, B, and C appear twice, once, and once, respectively, satisfying the condition.
The condition is not satisfied by checking three or fewer characters, so the answer is 4.

Sample Input 2

4
CABC

Sample Output 2

In the first three characters from the left, each of A, B, and C appears once, satisfying the condition.

Sample Input 3

30
AABABBBABABBABABCABACAABCBACCA

Sample Output 3

B - Intersection

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

数直線があり、高橋君はこれを赤色と青色で次のように塗りました。

X=L_1 から X=R_1 までをすべて赤色で塗る。
X=L_2 から X=R_2 までをすべて青色で塗る。

数直線のうち、赤色と青色の両方で塗られている部分の長さを求めてください。

制約

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
入力はすべて整数

入力

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

L_1 R_1 L_2 R_2

出力

両方の色で塗られている部分の長さを整数で出力せよ。

入力例 1

0 3 1 5

出力例 1

X=0 から X=3 までが赤く、 X=1 から X=5 までが青く塗られています。

よって、両方の色で塗られている部分は X=1 から X=3 までであり、その長さは 2 となります。

入力例 2

0 1 4 5

出力例 2

両方の色で塗られている部分はありません。

入力例 3

0 3 3 7

出力例 3

赤色と青色で塗られている部分が接している場合でも、両方の色で塗られている部分の長さは 0 となります。

Score : 100 points

Problem Statement

We have a number line. Takahashi painted some parts of this line, as follows:

First, he painted the part from X=L_1 to X=R_1 red.
Next, he painted the part from X=L_2 to X=R_2 blue.

Find the length of the part of the line painted both red and blue.

Constraints

0\leq L_1<R_1\leq 100
0\leq L_2<R_2\leq 100
All values in input are integers.

Input

Input is given from Standard Input in the following format:

L_1 R_1 L_2 R_2

Output

Print the length of the part of the line painted both red and blue, as an integer.

Sample Input 1

0 3 1 5

Sample Output 1

The part from X=0 to X=3 is painted red, and the part from X=1 to X=5 is painted blue.

Thus, the part from X=1 to X=3 is painted both red and blue, and its length is 2.

Sample Input 2

0 1 4 5

Sample Output 2

No part is painted both red and blue.

Sample Input 3

0 3 3 7

Sample Output 3

If the part painted red and the part painted blue are adjacent to each other, the length of the part painted both red and blue is 0.

C - Strictly Superior

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

AtCoder 商店には N 個の商品があります。 i\ (1\leq i\leq N) 番目の商品の価格は P _ i です。 i\ (1\leq i\leq N) 番目の商品は C _ i 個の機能をもち、i\ (1\leq i\leq N) 番目の商品の j\ (1\leq j\leq C _ i) 番目の機能は 1 以上 M 以下の整数 F _ {i,j} として表されます。

高橋くんは、AtCoder 商店の商品で一方が一方の上位互換であるものがないか気になりました。 i 番目の商品と j 番目の商品 (1\leq i,j\leq N) であって、次の条件をすべて満たすものがあるとき Yes と、ないとき No と出力してください。

P _ i\geq P _ j である。
j 番目の製品は i 番目の製品がもつ機能をすべてもつ。
P _ i\gt P _ j であるか、j 番目の製品は i 番目の製品にない機能を 1 つ以上もつ。

制約

2\leq N\leq100
1\leq M\leq100
1\leq P _ i\leq10^5\ (1\leq i\leq N)
1\leq C _ i\leq M\ (1\leq i\leq N)
1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
入力はすべて整数

入力

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

出力

答えを 1 行で出力せよ。

入力例 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

出力例 1

Yes

(i,j)=(4,3) とすると、条件を全て満たします。

他の組は条件を満たしません。例えば (i,j)=(4,5) とすると j 番目の商品は i 番目の商品の機能をすべてもっていますが、P _ i\lt P _ j なので上位互換ではありません。

入力例 2

出力例 2

No

まったく同じ価格と機能をもった商品がある場合もあります。

入力例 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

出力例 3

Yes

Score : 200 points

Problem Statement

AtCoder Shop has N products. The price of the i-th product (1\leq i\leq N) is P _ i. The i-th product (1\leq i\leq N) has C_i functions. The j-th function (1\leq j\leq C _ i) of the i-th product (1\leq i\leq N) is represented as an integer F _ {i,j} between 1 and M, inclusive.

Takahashi wonders whether there is a product that is strictly superior to another. If there are i and j (1\leq i,j\leq N) such that the i-th and j-th products satisfy all of the following conditions, print Yes; otherwise, print No.

P _ i\geq P _ j.
The j-th product has all functions of the i-th product.
P _ i\gt P _ j, or the j-th product has one or more functions that the i-th product lacks.

Constraints

2\leq N\leq100
1\leq M\leq100
1\leq P _ i\leq10^5\ (1\leq i\leq N)
1\leq C _ i\leq M\ (1\leq i\leq N)
1\leq F _ {i,1}\lt F _ {i,2}\lt\cdots\lt F _ {i,C _ i}\leq M\ (1\leq i\leq N)
All input values are integers.

Input

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

N M
P _ 1 C _ 1 F _ {1,1} F _ {1,2} \ldots F _ {1,C _ 1}
P _ 2 C _ 2 F _ {2,1} F _ {2,2} \ldots F _ {2,C _ 2}
\vdots
P _ N C _ N F _ {N,1} F _ {N,2} \ldots F _ {N,C _ N}

Output

Print the answer in a single line.

Sample Input 1

5 6
10000 2 1 3
15000 3 1 2 4
30000 3 1 3 5
35000 2 1 5
100000 6 1 2 3 4 5 6

Sample Output 1

Yes

(i,j)=(4,3) satisfies all of the conditions.

No other pair satisfies them. For instance, for (i,j)=(4,5), the j-th product has all functions of the i-th one, but P _ i\lt P _ j, so it is not strictly superior.

Sample Input 2

Sample Output 2

No

Multiple products may have the same price and functions.

Sample Input 3

20 10
72036 3 3 4 9
7716 4 1 2 3 6
54093 5 1 6 7 8 10
25517 7 3 4 5 6 7 9 10
96930 8 2 3 4 6 7 8 9 10
47774 6 2 4 5 6 7 9
36959 5 1 3 4 5 8
46622 7 1 2 3 5 6 8 10
34315 9 1 3 4 5 6 7 8 9 10
54129 7 1 3 4 6 7 8 9
4274 5 2 4 7 9 10
16578 5 2 3 6 7 9
61809 4 1 2 4 5
1659 5 3 5 6 9 10
59183 5 1 2 3 4 9
22186 4 3 5 6 8
98282 4 1 4 7 10
72865 8 1 2 3 4 6 8 9 10
33796 6 1 3 5 7 9 10
74670 4 1 2 6 8

Sample Output 3

Yes

D - Buy One Carton of Milk

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

スーパーマーケットで卵のパックが売られています。

卵 6 個入りのパックは S 円、卵 8 個入りのパックは M 円、卵 12 個入りのパックは L 円です。

どのパックも何パックでも購入できるとき、N 個以上の卵を買うために必要な最小の金額を求めてください。

制約

1 \leq N \leq 100
1 \leq S,M,L \leq 10^4
入力は全て整数である

入力

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

N S M L

出力

答えを出力せよ。

入力例 1

16 120 150 200

出力例 1

8 個入りのパックを 2 個買うのが最適です。

入力例 2

10 100 50 10

出力例 2

12 個入りのパックを 1 個買うのが最適です。

入力例 3

99 600 800 1200

出力例 3

8 個入りのパックと 12 個入りのパックを 5 個ずつ買うのが最適です。

Score : 200 points

Problem Statement

A supermarket sells egg packs.

A pack of 6 eggs costs S yen, a pack of 8 eggs costs M yen, and a pack of 12 eggs costs L yen.

When you can buy any number of each pack, find the minimum amount of money required to purchase at least N eggs.

Constraints

1 \leq N \leq 100
1 \leq S,M,L \leq 10^4
All input values are integers.

Input

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

N S M L

Output

Print the answer.

Sample Input 1

16 120 150 200

Sample Output 1

It is optimal to buy two 8-egg packs.

Sample Input 2

10 100 50 10

Sample Output 2

It is optimal to buy one 12-egg pack.

Sample Input 3

99 600 800 1200

Sample Output 3

It is optimal to buy five 8-egg packs and five 12-egg packs.

E - Domino

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

N 個のドミノが数直線上に一列に並んでいます。i 番目のドミノは座標 i の位置に立っており、高さは A_i です。

i 番目のドミノが右に倒れると、座標 i 以上 i+A_i 未満の範囲にあるドミノが全て右に倒れます。

1 番目のドミノを右に倒したとき、全部でいくつのドミノが倒れますか？

制約

1\leq N \leq 5\times 10^5
1\leq A_i \leq N
入力は全て整数

入力

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

N
A_1 A_2 \ldots A_N

出力

1 番目のドミノを右に倒したときに倒れるドミノの個数を出力せよ。

入力例 1

4
3 1 4 1

出力例 1

1 番目のドミノが右に倒れると、2,3 番目のドミノも右に倒れます。3 番目のドミノが右に倒れると、4 番目のドミノも倒れます。

入力例 2

9
1 4 1 4 2 1 3 5 6

出力例 2

1 番目のドミノを右に倒しても、他のドミノが倒れることはありません。

入力例 3

10
5 4 3 2 1 1 2 3 4 5

出力例 3

Score : 300 points

Problem Statement

There are N dominoes standing in a row on a number line. The i-th domino is standing at coordinate i and has height A_i.

When the i-th domino falls to the right, all dominoes in the range between coordinates i and i+A_i-1, inclusive, fall to the right.

How many dominoes will fall in total when the first domino falls to the right?

Constraints

1\leq N \leq 5\times 10^5
1\leq A_i \leq N
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

Output the number of dominoes that fall when the first domino falls to the right.

Sample Input 1

4
3 1 4 1

Sample Output 1

When the first domino falls to the right, the second and third dominoes also fall to the right. When the third domino falls to the right, the fourth domino also falls.

Sample Input 2

9
1 4 1 4 2 1 3 5 6

Sample Output 2

When the first domino falls to the right, no other dominoes will fall.

Sample Input 3

10
5 4 3 2 1 1 2 3 4 5