AtCoder Daily Training MEDIUM 2024/06/20 20:30start

C - Practical Computing

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

以下のような N 個の整数列 A_0,\ldots,A_{N-1} を求めてください。

各 i (0\leq i \leq N-1) について、A_i の長さは i+1 である。
各 i,j (0\leq i \leq N-1, 0 \leq j \leq i) について、A_i の j+1 番目の値 a_{i,j} は次のように定められる。
- j=0 または j=i の時、a_{i,j}=1
- それ以外の時、a_{i,j} = a_{i-1,j-1} + a_{i-1,j}

制約

1 \leq N \leq 30
N は整数

入力

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

出力

N 行出力せよ。 i 行目には A_{i-1} の値を順に空白区切りで出力せよ。

入力例 1

出力例 1

1
1 1
1 2 1

入力例 2

出力例 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

Score : 200 points

Problem Statement

Find the N integer sequences A_0,\ldots,A_{N-1} defined as follows.

For each i (0\leq i \leq N-1), the length of A_i is i+1.
For each i and j (0\leq i \leq N-1, 0 \leq j \leq i), the (j+1)-th term of A_i, denoted by a_{i,j}, is defined as follows.
- a_{i,j}=1, if j=0 or j=i.
- a_{i,j} = a_{i-1,j-1} + a_{i-1,j}, otherwise.

Constraints

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

Input

Input is given from Standard Input in the following format:

Output

Print N lines. The i-th line should contain the terms of A_{i-1} separated by spaces.

Sample Input 1

Sample Output 1

1
1 1
1 2 1

Sample Input 2

Sample Output 2

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1

D - Star or Not

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

N 頂点 N-1 辺の木が与えられます。
頂点には 1,2,\ldots,N の番号がついており、i 本目の辺は頂点 a_i と頂点 b_i を結んでいます。

この木がスターであるか判定してください。

ただしスターとは、1 つの頂点から、他の全ての頂点に 1 本ずつ辺が出ている木のことです。

注記

「木」については、Wikipedia「木(数学)」を参照してください。

制約

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
与えられるグラフは木である

入力

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

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

出力

与えられたグラフがスターであるなら Yes と、スターでないなら No と出力せよ。

入力例 1

出力例 1

Yes

与えられたグラフはスターです。

入力例 2

出力例 2

No

与えられたグラフはスターではありません。

入力例 3

出力例 3

Yes

Score : 200 points

Problem Statement

You are given a tree with N vertices and N-1 edges.
The vertices are numbered 1,2,\ldots,N. The i-th edge connects Vertex a_i and Vertex b_i.

Determine whether this tree is a star.

Here, a star is a tree where there is a vertex directly connected to all other vertices.

Notes

For the definition of a tree, see Tree (graph theory) - Wikipedia.

Constraints

3 \leq N \leq 10^5
1 \leq a_i \lt b_i \leq N
The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
\vdots
a_{N-1} b_{N-1}

Output

If the given graph is a star, print Yes; otherwise, print No.

Sample Input 1

Sample Output 1

Yes

The given graph is a star.

Sample Input 2

Sample Output 2

No

The given graph is not a star.

Sample Input 3

Sample Output 3

Yes

E - Submask

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 300 点

問題文

非負整数 N が与えられるので、以下の条件を満たす非負整数 x を昇順に全て出力してください。

x を 2 進数として表記した時に 1 となる位の集合が、 N を 2 進数として表記した時に 1 となる位の集合の部分集合となる。
- すなわち、全ての非負整数 k について、「 x の 2^k の位が 1 ならば、 N の 2^k の位は 1 」が成り立つ。

制約

N は整数
0 \le N < 2^{60}
N を 2 進数として表記した時、 1 となる位は 15 個以下である

入力

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

出力

答えを 1 行に 1 つずつ、10 進法の整数として昇順に出力せよ。

入力例 1

出力例 1

N = 11_{(10)} を 2 進数で表記すると、 1011_{(2)} となります。
条件を満たす非負整数 x は以下の通りです。

0000_{(2)}=0_{(10)}
0001_{(2)}=1_{(10)}
0010_{(2)}=2_{(10)}
0011_{(2)}=3_{(10)}
1000_{(2)}=8_{(10)}
1001_{(2)}=9_{(10)}
1010_{(2)}=10_{(10)}
1011_{(2)}=11_{(10)}

入力例 2

出力例 2

入力例 3

576461302059761664

出力例 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

入力は 32bit 符号付き整数に収まらない可能性があります。

Score : 300 points

Problem Statement

You are given a non-negative integer N. Print all non-negative integers x that satisfy the following condition in ascending order.

The set of the digit positions containing 1 in the binary representation of x is a subset of the set of the digit positions containing 1 in the binary representation of N.
- That is, the following holds for every non-negative integer k: if the digit in the "2^ks" place of x is 1, the digit in the 2^ks place of N is 1.

Constraints

N is an integer.
0 \le N < 2^{60}
In the binary representation of N, at most 15 digit positions contain 1.

Input

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

Output

Print the answer as decimal integers in ascending order, each in its own line.

Sample Input 1

Sample Output 1

The binary representation of N = 11_{(10)} is 1011_{(2)}.
The non-negative integers x that satisfy the condition are:

0000_{(2)}=0_{(10)}
0001_{(2)}=1_{(10)}
0010_{(2)}=2_{(10)}
0011_{(2)}=3_{(10)}
1000_{(2)}=8_{(10)}
1001_{(2)}=9_{(10)}
1010_{(2)}=10_{(10)}
1011_{(2)}=11_{(10)}

Sample Input 2

Sample Output 2

Sample Input 3

576461302059761664

Sample Output 3

0
524288
549755813888
549756338176
576460752303423488
576460752303947776
576461302059237376
576461302059761664

The input may not fit into a 32-bit signed integer.

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

G - Flip and Adjust

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

両面に整数が書かれたカードが N 枚あり、i \, (1 \leq i \leq N) 枚目のカードの表には a_i が、裏には b_i が書かれています。

あなたは、それぞれのカードについて、表を上に向けて置くか裏を上に向けて置くかを自由に決めることができます。

上に向けられた面に書かれた整数の総和がちょうど S となるようにカードを置くことができるか判定し、可能ならそのようなカードの置き方の一例を求めてください。

制約

1 \leq N \leq 100
1 \leq S \leq 10000
1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
入力は全て整数

入力

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

N S
a_1 b_1
\vdots
a_N b_N

出力

まず、上に向けられた面に書かれた整数の総和がちょうど S となるようにカードを置くことができるならば Yes を、できなければ No を出力し、改行せよ。

さらに、そのようにカードを置くことができるならば、カードの置き方を表す H および T のみからなる長さ N の文字列を出力せよ。
この文字列の i \, (1 \leq i \leq N) 文字目は、i 枚目のカードを表を上に向けて置くなら H、裏を上に向けて置くなら T でなければならない。
条件を満たすカードの置き方が複数考えられる場合、どれを出力しても正解となる。

入力例 1

出力例 1

Yes
THH

例えば次のように置くことで、上に向けられた面に書かれた整数の総和がちょうど S (= 11) となります。

1 枚目は表、2 枚目は裏、3 枚目は裏を上に向けて置く。
1 枚目は裏、2 枚目は表、3 枚目は表を上に向けて置く。

よって、HTT や THH といった出力が正解となります。

入力例 2

出力例 2

No

上に向けられた面に書かれた整数の総和がちょうど S (= 25) となるようにカードを置くことはできません。

Score : 400 points

Problem Statement

There are N cards with an integer written on each side. Card i (1 \leq i \leq N) has an integer a_i written on the front and an integer b_i written on the back.

You may choose whether to place each card with its front or back side visible.

Determine if you can place the cards so that the sum of the visible integers exactly equals S. If possible, find a placement of the cards to realize it.

Constraints

1 \leq N \leq 100
1 \leq S \leq 10000
1 \leq a_i, b_i \leq 100 \, (1 \leq i \leq N)
All values in the input are integers.

Input

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

N S
a_1 b_1
\vdots
a_N b_N

Output

First, print Yes if you can make the sum of the visible integers exactly equal S, and No otherwise, followed by a newline.

Additionally, if such a placement is possible, print a string of length N consisting of H and T that represents the placement of the cards to realize it.
The i-th (1 \leq i \leq N) character should be H if the i-th card should be placed with its front side visible, and T with its back.
If there are multiple possible placements to realize the sum, printing any of them is accepted.

Sample Input 1

Sample Output 1

Yes
THH

For example, the following placements make the sum of the visible integers exactly equal S (= 11):

Place the 1-st card with its front side visible, 2-nd with its back, and 3-rd with its back.
Place the 1-st card with its back side visible, 2-nd with its front, and 3-rd with its front.

Therefore, outputs like HTT and THH are accepted.

Sample Input 2

Sample Output 2

No

You cannot place the cards so that the sum of the visible integers exactly equals S (= 25).