AtCoder Daily Training EASY 2026/02/26 18:00start

A - Doors in the Center

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

以下の条件を全て満たす長さ N の文字列を求めてください。

各文字は - または = である
回文である
文字列中に = は 1 個または 2 個含まれる。 2 個含まれる場合、それらの = は隣接している

なお、そのような文字列はちょうど 1 つ存在します。

制約

1 \leq N \leq 100
N は整数である

入力

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

出力

答えを出力せよ。

入力例 1

出力例 1

-==-

入力例 2

出力例 2

---=---

Score : 100 points

Problem Statement

Find a length-N string that satisfies all of the following conditions:

Each character is - or =.
It is a palindrome.
It contains exactly one or exactly two =s. If it contains two =s, they are adjacent.

Such a string is unique.

Constraints

1 \leq N \leq 100
N is an integer.

Input

The 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

---=---

B - Conflict

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

N 個の商品があります。高橋君と青木君がどの商品を欲しがっているかを表す長さ N の文字列 T,A が与えられます。T,A の i\ (1\leq i\leq N) 文字目をそれぞれ T_i,A_i とします。

高橋君は T_i が o のとき i 番目の商品を欲しがっており、T_i が x のとき i 番目の商品を欲しがっていません。同様に、青木君は A_i が o のとき i 番目の商品を欲しがっており、A_i が x のとき i 番目の商品を欲しがっていません。

2 人ともが欲しがっている商品が存在するか判定してください。

制約

1\leq N\leq 100
N は整数
T,A は o および x からなる長さ N の文字列

入力

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

N
T
A

出力

2 人とも欲しがっている商品が存在するならば Yes を、存在しないならば No を出力せよ。

入力例 1

4
oxoo
xoox

出力例 1

Yes

3 つ目の商品は 2 人ともが欲しがっているため、Yes を出力します。

入力例 2

5
xxxxx
ooooo

出力例 2

No

2 人とも欲しがっている商品は存在しないため、No を出力します。

入力例 3

10
xoooxoxxxo
ooxooooxoo

出力例 3

Yes

Score : 100 points

Problem Statement

There are N items. You are given strings T and A of length N that represent which items Takahashi and Aoki want, respectively. Let T_i and A_i be the i-th (1\leq i\leq N) characters of T and A, respectively.

Takahashi wants the i-th item when T_i is o, and does not want the i-th item when T_i is x. Similarly, Aoki wants the i-th item when A_i is o, and does not want the i-th item when A_i is x.

Determine whether there exists an item that both of them want.

Constraints

1\leq N\leq 100
N is an integer.
T and A are strings of length N consisting of o and x.

Input

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

N
T
A

Output

If there exists an item that both of them want, output Yes; otherwise, output No.

Sample Input 1

4
oxoo
xoox

Sample Output 1

Yes

The third item is wanted by both of them, so output Yes.

Sample Input 2

5
xxxxx
ooooo

Sample Output 2

No

There is no item that both of them want, so output No.

Sample Input 3

10
xoooxoxxxo
ooxooooxoo

Sample Output 3

Yes

C - Explore

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君はゲームの中で洞窟を探索しています。

洞窟は N 個の部屋が一列に並んだ構造であり、入り口から順に部屋 1,2,\ldots,N と番号がついています。

最初、高橋君は部屋 1 におり、持ち時間 は T です。
各 1 \leq i \leq N-1 について、持ち時間を A_i 消費することで、部屋 i から部屋 i+1 へ移動することができます。これ以外に部屋を移動する方法はありません。また、持ち時間が 0 以下になるような移動は行うことができません。

洞窟内には M 個のボーナス部屋があります。i 番目のボーナス部屋は部屋 X_i であり、この部屋に到達すると持ち時間が Y_i 増加します。

高橋君は部屋 N にたどりつくことができますか？

制約

2 \leq N \leq 10^5
0 \leq M \leq N-2
1 \leq T \leq 10^9
1 \leq A_i \leq 10^9
1 < X_1 < \ldots < X_M < N
1 \leq Y_i \leq 10^9
入力に含まれる値は全て整数である

入力

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

N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

高橋君が部屋 N にたどりつくことができるなら Yes を、できないなら No を出力せよ。

入力例 1

4 1 10
5 7 5
2 10

出力例 1

Yes

高橋君は最初、部屋 1 にいて持ち時間は 10 です。
持ち時間を 5 消費して部屋 2 に移動します。持ち時間は 5 になります。その後、持ち時間が 10 増え 15 になります。
持ち時間を 7 消費して部屋 3 に移動します。持ち時間は 8 になります。
持ち時間を 5 消費して部屋 4 に移動します。持ち時間は 3 になります。

入力例 2

4 1 10
10 7 5
2 10

出力例 2

No

部屋 1 から部屋 2 へ移動することができません。

Score : 200 points

Problem Statement

Takahashi is exploring a cave in a video game.

The cave consists of N rooms arranged in a row. The rooms are numbered Room 1,2,\ldots,N from the entrance.

Takahashi is initially in Room 1, and the time limit is T.
For each 1 \leq i \leq N-1, he may consume a time of A_i to move from Room i to Room (i+1). There is no other way to move between rooms. He cannot make a move that makes the time limit 0 or less.

There are M bonus rooms in the cave. The i-th bonus room is Room X_i; when he arrives at the room, the time limit increases by Y_i.

Can Takahashi reach Room N?

Constraints

2 \leq N \leq 10^5
0 \leq M \leq N-2
1 \leq T \leq 10^9
1 \leq A_i \leq 10^9
1 < X_1 < \ldots < X_M < N
1 \leq Y_i \leq 10^9
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M T
A_1 A_2 \ldots A_{N-1}
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

If Takahashi can reach Room N, print Yes; otherwise, print No.

Sample Input 1

4 1 10
5 7 5
2 10

Sample Output 1

Yes

Takahashi is initially in Room 1, and the time limit is 10.
He consumes a time of 5 to move to Room 2. Now the time limit is 5. Then, the time limit increases by 10; it is now 15.
He consumes a time of 7 to move to Room 3. Now the time limit is 8.
He consumes a time of 5 to move to Room 4. Now the time limit is 3.

Sample Input 2

4 1 10
10 7 5
2 10

Sample Output 2

No

He cannot move from Room 1 to Room 2.

D - Hurdle Parsing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

いろはちゃんは長さ N ( N \ge 1 ) の正整数列 A=(A_1,A_2,\dots,A_N) を持っています。
いろはちゃんは A を使って、次のように文字列 S を生成しました。

S= | から始める。
i=1,2,\dots,N の順に、次の操作を行う。
- S の末尾に - を A_i 個追加する。
- その後、 S の末尾に | を 1 個追加する。

生成された文字列 S が与えられるので、正整数列 A を復元してください。

制約

S は問題文中の方法で生成された長さ 3 以上 100 以下の文字列
A は長さ 1 以上の正整数列

入力

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

出力

答えを以下の形式で、 1 行に空白区切りで出力せよ。

A_1 A_2 \dots A_N

入力例 1

|---|-|----|-|-----|

出力例 1

3 1 4 1 5

S= |---|-|----|-|-----| が生成されるような A は (3,1,4,1,5) です。

入力例 2

|----------|

出力例 2

入力例 3

|-|-|-|------|

出力例 3

1 1 1 6

Score : 200 points

Problem Statement

Iroha has a sequence of positive integers A = (A_1, A_2, \dots, A_N) of length N (N \ge 1).
She generated a string S using A as follows:

Start with S = |.
For i = 1, 2, \dots, N, perform the following operations in order:
- Append A_i copies of - to the end of S.
- Then, append one | to the end of S.

Given the generated string S, reconstruct the sequence A.

Constraints

S is a string of length between 3 and 100, inclusive, generated by the method in the problem statement.
A is a sequence of positive integers of length at least 1.

Input

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

Output

Print the answer in the following format, with elements separated by spaces in a single line:

A_1 A_2 \dots A_N

Sample Input 1

|---|-|----|-|-----|

Sample Output 1

3 1 4 1 5

S = |---|-|----|-|-----| is generated by A = (3, 1, 4, 1, 5).

Sample Input 2

|----------|

Sample Output 2

Sample Input 3

|-|-|-|------|

Sample Output 3

1 1 1 6

E - Just K

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

英小文字のみからなる N 個の文字列 S_1,S_2,\dots,S_N が与えられます。

S_1,S_2,\dots,S_N から文字列を好きな個数選ぶことを考えます。

このとき、「選んだ文字列の中でちょうど K 個の文字列に登場する英小文字」の種類数としてあり得る最大値を求めてください。

制約

1 \le N \le 15
1 \le K \le N
N,K は整数
S_i は英小文字からなる空でない文字列である。
1 \le i \le N を満たす整数 i に対し、S_i に同じ文字は 2 個以上含まれない。
i \neq j ならば S_i \neq S_j である。

入力

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

N K
S_1
S_2
\vdots
S_N

出力

答えを出力せよ。

入力例 1

4 2
abi
aef
bc
acg

出力例 1

S_1,S_3,S_4 を選んだ場合、a,b,c がちょうど 2 個の文字列に含まれます。

4 個以上の文字がちょうど 2 個の文字列に含まれるような選び方は存在しないため、答えは 3 です。

入力例 2

2 2
a
b

出力例 2

同じ文字列を複数回選ぶことはできません。

入力例 3

5 2
abpqxyz
az
pq
bc
cy

出力例 3

Score : 300 points

Problem Statement

You are given N strings S_1,S_2,\dots,S_N consisting of lowercase English alphabets.

Consider choosing some number of strings from S_1,S_2,\dots,S_N.

Find the maximum number of distinct alphabets that satisfy the following condition: "the alphabet is contained in exactly K of the chosen strings."

Constraints

1 \le N \le 15
1 \le K \le N
N and K are integers.
S_i is a non-empty string consisting of lowercase English alphabets.
For each integer i such that 1 \le i \le N, S_i does not contain two or more same alphabets.
If i \neq j, then S_i \neq S_j.

Input

Input is given from Standard Input in the following format:

N K
S_1
S_2
\vdots
S_N

Output

Print the answer.

Sample Input 1

4 2
abi
aef
bc
acg

Sample Output 1

When S_1,S_3, and S_4 are chosen, a,b, and c occur in exactly two of the strings.

There is no way to choose strings so that 4 or more alphabets occur in exactly 2 of the strings, so the answer is 3.

Sample Input 2

2 2
a
b

Sample Output 2

You cannot choose the same string more than once.

Sample Input 3

5 2
abpqxyz
az
pq
bc
cy