AtCoder Daily Training EASY 2025/08/19 19:30start

A - Content Too Large

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

高橋くんは、N 個の品物と 1 つのカバンを持っています。

i 番目 (1\le i\le N) の品物の大きさは A _ i で、カバンの大きさは M です。

カバンに入れようとしている品物の大きさの合計が M 以下のとき、かつそのときに限り、それらの品物をすべて同時にカバンに入れることができます。

高橋くんが N 個の品物すべてを同時にカバンに入れることができるなら Yes 、そうでなければ No と出力してください。

制約

1\le N\le100
1\le M\le10000
1\le A _ i\le100\ (1\le i\le N)
入力はすべて整数

入力

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

N M
A _ 1 A _ 2 \ldots A _ N

出力

高橋くんがすべての品物を同時にカバンに入れられるなら Yes を、そうでなければ No を出力せよ。

入力例 1

5 15
3 1 4 1 5

出力例 1

Yes

5 つの品物の大きさの合計は 3+1+4+1+5=14 です。これは、カバンの大きさ 15 以下なので、高橋くんはすべての品物を同時にカバンに入れることができます。なので、Yes を出力してください。

入力例 2

5 5
3 1 4 1 5

出力例 2

No

5 つの品物の大きさの合計は 14 で、カバンの大きさ 5 より大きいため、高橋くんはすべての品物を同時にカバンに入れることができません。なので、No を出力してください。

入力例 3

1 10000
100

出力例 3

Yes

Score : 100 points

Problem Statement

Takahashi has N items and one bag.

The size of the i-th (1\le i\le N) item is A_i, and the size of the bag is M.

If and only if the total size of the items he is trying to put in the bag is at most M, he can put all those items in the bag simultaneously.

If he can put all N items in the bag simultaneously, print Yes; otherwise, print No.

Constraints

1\le N\le100
1\le M\le10000
1\le A_i\le100\ (1\le i\le N)
All input values are integers.

Input

The input is given from standard input in the following format:

N M
A_1 A_2 \ldots A_N

Output

If Takahashi can put all items in the bag simultaneously, print Yes; otherwise, print No.

Sample Input 1

5 15
3 1 4 1 5

Sample Output 1

Yes

The total size of the 5 items is 3+1+4+1+5=14. Since this is not greater than the bag size 15, Takahashi can put all items in the bag simultaneously. Thus, print Yes.

Sample Input 2

5 5
3 1 4 1 5

Sample Output 2

No

The total size of the 5 items is 14, which is greater than the bag size 5, so he cannot put all items in the bag simultaneously. Thus, print No.

Sample Input 3

1 10000
100

Sample Output 3

Yes

B - Edge Checker 2

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 100 点

問題文

下の画像で示す図において、a 番の点と b 番の点が線で直接結ばれているかを答えてください。

制約

1 \leq a \lt b \leq 15
a,b は整数

入力

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

a b

出力

a 番の点と b 番の点が線で直接結ばれているなら Yes、結ばれていないなら No を出力せよ。

入力例 1

1 2

出力例 1

Yes

問題文で示した図において、1 番の点と 2 番の点は線で直接結ばれています。よって、Yes を出力します。

入力例 2

2 8

出力例 2

No

問題文で示した図において、2 番の点と 8 番の点は線で直接結ばれていません。よって、No を出力します。

入力例 3

14 15

出力例 3

No

Score : 100 points

Problem Statement

Determine if there is a segment that directly connects the points numbered a and b in the figure below.

Constraints

1 \leq a \lt b \leq 15
a and b are integers.

Input

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

a b

Output

Print Yes if there is a segment that directly connects the points numbered a and b; print No otherwise.

Sample Input 1

1 2

Sample Output 1

Yes

In the figure in the Problem Statement, there is a segment that directly connects the points numbered 1 and 2, so Yes should be printed.

Sample Input 2

2 8

Sample Output 2

No

In the figure in the Problem Statement, there is no segment that directly connects the points numbered 2 and 8, so No should be printed.

Sample Input 3

14 15

Sample Output 3

No

C - chess960

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君は chess960 と呼ばれるゲームで遊んでいます。高橋君はランダムに決めた初期配置が chess960 の条件を満たすか確認するプログラムを書くことにしました。

長さ 8 の文字列 S が与えられます。S には K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれます。 S が以下の条件を全て満たしているか判定してください。

S において左から x,y\ (x < y) 文字目が B であるとする。このとき x と y の偶奇が異なる。
K は 2 つの R の間にある。より形式的には、S において左から x,y\ (x < y) 文字目が R であり、 z 文字目が K であるとする。このとき、 x< z < y が成り立つ。

制約

S は長さ 8 の文字列であり、K, Q がちょうど 1 文字ずつ、R, B, N がちょうど 2 文字ずつ含まれる。

入力

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

出力

S が条件を満たす場合 Yes を、そうでない場合 No を出力せよ。

入力例 1

RNBQKBNR

出力例 1

Yes

B は左から 3 番目、6 番目にあり、3 と 6 は偶奇が異なります。また、K は 2 つの R の間にあります。よって条件を満たします。

入力例 2

KRRBBNNQ

出力例 2

No

K は 2 つの R の間にありません。

入力例 3

BRKRBQNN

出力例 3

No

Score : 200 points

Problem Statement

Takahashi is playing a game called Chess960. He has decided to write a code that determines if a random initial state satisfies the conditions of Chess960.

You are given a string S of length eight. S has exactly one K and Q, and exactly two R's, B's , and N's. Determine if S satisfies all of the following conditions.

Suppose that the x-th and y-th (x < y) characters from the left of S are B; then, x and y have different parities.
K is between two R's. More formally, suppose that the x-th and y-th (x < y) characters from the left of S are R and the z-th is K; then x< z < y.

Constraints

S is a string of length 8 that contains exactly one K and Q, and exactly two R's, B's , and N's.

Input

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

Output

Print Yes if S satisfies the conditions; print No otherwise.

Sample Input 1

RNBQKBNR

Sample Output 1

Yes

The 3-rd and 6-th characters are B, and 3 and 6 have different parities. Also, K is between the two R's. Thus, the conditions are fulfilled.

Sample Input 2

KRRBBNNQ

Sample Output 2

No

K is not between the two R's.

Sample Input 3

BRKRBQNN

Sample Output 3

No

D - World Meeting

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 250 点

問題文

キーエンスには世界各地に N 個の拠点があり、1 から N までの番号が付けられています。拠点 i には W_i 人の社員が所属しており、世界標準時で 0 時のとき拠点 i は X_i 時です。

あなたはキーエンス全社で 1 時間の会議を開きたいです。各社員は、会議の開催時間帯が所属する拠点における 9:00-18:00 の時間帯に完全に含まれる場合にのみ会議に参加できます。なるべく多くの社員が参加できるように会議の開催時間帯を決めるとき、会議に参加できる社員の数の最大値を求めてください。

制約

1\leq N \leq 1000
1\leq W_i \leq 10^6
0\leq X_i < 24
入力は全て整数

入力

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

N
W_1 X_1
W_2 X_2
\vdots
W_N X_N

出力

会議に参加できる社員の数の最大値を出力せよ。

入力例 1

出力例 1

世界標準時で 14:00-15:00 の時間帯に会議を開催することを考えます。

拠点 1 における 14:00-15:00 の時間帯に会議が開催されるため、拠点 1 に所属する 5 人の社員は会議に参加できます。
拠点 2 における 17:00-18:00 の時間帯に会議が開催されるため、拠点 2 に所属する 3 人の社員は会議に参加できます。
拠点 3 における 8:00-9:00 の時間帯に会議が開催されるため、拠点 3 に所属する 2 人の社員は会議に参加できません。

よって、合計で 5+3=8 人の社員が会議に参加できます。これより多くの社員が参加できるような会議の開催時間帯はありません。

入力例 2

2
1 10
1000000 20

出力例 2

入力例 3

出力例 3

Score : 250 points

Problem Statement

Keyence has N bases worldwide, numbered 1 to N. Base i has W_i employees, and at 0 o'clock in Coordinated Universal Time (UTC), it is X_i o'clock at base i.

You want to hold a one-hour meeting across the entire company. Each employee can only participate in the meeting if the meeting time is completely within the 9:00-18:00 time slot at their base. Find the maximum number of employees who can participate when deciding the meeting time to allow as many employees as possible to participate.

Constraints

1\leq N \leq 1000
1\leq W_i \leq 10^6
0\leq X_i < 24
All input values are integers.

Input

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

N
W_1 X_1
W_2 X_2
\vdots
W_N X_N

Output

Print the maximum number of employees who can participate in the meeting.

Sample Input 1

Sample Output 1

Consider holding the meeting from 14:00 to 15:00 in UTC.

The meeting is held from 14:00 to 15:00 at base 1, so the 5 employees at base 1 can participate in the meeting.
The meeting is held from 17:00 to 18:00 at base 2, so the 3 employees at base 2 can participate in the meeting.
The meeting is held from 8:00 to 9:00 at base 3, so the 2 employees at base 3 cannot participate in the meeting.

Thus, a total of 5+3=8 employees can participate in the meeting. No meeting time allows more employees to participate.

Sample Input 2

2
1 10
1000000 20

Sample Output 2

Sample Input 3

Sample Output 3

E - Merge Sequences

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

長さ N の狭義単調増加列 A=(A _ 1,A _ 2,\ldots,A _ N) と、長さ M の狭義単調増加列 B=(B _ 1,B _ 2,\ldots,B _ M) が与えられます。ここで、すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j が成り立っています。

長さ N+M の狭義単調増加列 C=(C _ 1,C _ 2,\ldots,C _ {N+M}) を、次の操作を行った結果得られる列として定めます。

C を A と B を連結した列とする。厳密には、i=1,2,\ldots,N について C _ i=A _ i とし、i=N+1,N+2,\ldots,N+M について C _ i=B _ {i-N} とする。
C を昇順にソートする。

A _ 1,A _ 2,\ldots,A _ N と B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるか求めてください。より厳密には、まず i=1,2,\ldots,N について C _ k=A _ i を満たす k を順に求めたのち、j=1,2,\ldots,M について C _ k=B _ j を満たす k を順に求めてください。

制約

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
すべての i,j\ (1\leq i\leq N,1\leq j\leq M) について A _ i\neq B _ j
入力はすべて整数

入力

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

N M
A _ 1 A _ 2 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

出力

答えを 2 行で出力せよ。
1 行目には A _ 1,A _ 2,\ldots,A _ N がそれぞれ C では何番目にあるかを空白区切りで出力せよ。
2 行目には B _ 1,B _ 2,\ldots,B _ M がそれぞれ C では何番目にあるかを空白区切りで出力せよ。

入力例 1

4 3
3 14 15 92
6 53 58

出力例 1

1 3 4 7
2 5 6

C は (3,6,14,15,53,58,92) となります。 A=(3,14,15,92) の要素はそれぞれ 1,3,4,7 番目にあり、B=(6,53,58) の要素はそれぞれ 2,5,6 番目にあります。

入力例 2

4 4
1 2 3 4
100 200 300 400

出力例 2

1 2 3 4
5 6 7 8

入力例 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

出力例 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19

Score : 300 points

Problem Statement

You are given strictly increasing sequences of length N and M: A=(A _ 1,A _ 2,\ldots,A _ N) and B=(B _ 1,B _ 2,\ldots,B _ M). Here, A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).

Let C=(C _ 1,C _ 2,\ldots,C _ {N+M}) be a strictly increasing sequence of length N+M that results from the following procedure.

Let C be the concatenation of A and B. Formally, let C _ i=A _ i for i=1,2,\ldots,N, and C _ i=B _ {i-N} for i=N+1,N+2,\ldots,N+M.
Sort C in ascending order.

For each of A _ 1,A _ 2,\ldots,A _ N, B _ 1,B _ 2,\ldots,B _ M, find its position in C. More formally, for each i=1,2,\ldots,N, find k such that C _ k=A _ i, and for each j=1,2,\ldots,M, find k such that C _ k=B _ j.

Constraints

1\leq N,M\leq 10^5
1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq 10^9
1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\leq 10^9
A _ i\neq B _ j for every i and j (1\leq i\leq N,1\leq j\leq M).
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 \ldots A _ N
B _ 1 B _ 2 \ldots B _ M

Output

Print the answer in two lines.
The first line should contain the positions of A _ 1,A _ 2,\ldots,A _ N in C, with spaces in between.
The second line should contain the positions of B _ 1,B _ 2,\ldots,B _ M in C, with spaces in between.

Sample Input 1

4 3
3 14 15 92
6 53 58

Sample Output 1

1 3 4 7
2 5 6

C will be (3,6,14,15,53,58,92). Here, the 1-st, 3-rd, 4-th, 7-th elements are from A=(3,14,15,92), and the 2-nd, 5-th, 6-th elements are from B=(6,53,58).

Sample Input 2

4 4
1 2 3 4
100 200 300 400

Sample Output 2

1 2 3 4
5 6 7 8

Sample Input 3

8 12
3 4 10 15 17 18 22 30
5 7 11 13 14 16 19 21 23 24 27 28

Sample Output 3

1 2 5 9 11 12 15 20
3 4 6 7 8 10 13 14 16 17 18 19