AtCoder Weekday Contest 0196 Beta

A - Contents of the Wallet

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君の財布には N 枚のお金が入っています。財布の中身は長さ N の文字列 S で表され、 S の i 文字目が C なら i 枚目は硬貨、 B なら紙幣です。

高橋君の財布に硬貨と紙幣が両方とも 1 枚以上入っているなら Yes を、そうでないなら No を出力してください。

制約

1 \leq N \leq 100
S は C と B のみからなる長さ N の文字列

入力

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

N
S

1 行目には、お金の枚数 N が与えられる。
2 行目には、財布の中身を表す文字列 S が与えられる。

出力

硬貨と紙幣が両方あるなら Yes を、そうでないなら No を 1 行で出力せよ。

入力例 1

3
CCB

出力例 1

Yes

入力例 2

3
BBB

出力例 2

No

入力例 3

3
BCB

出力例 3

Yes

入力例 4

60
CBCCCCCCBBBBBBBBBBBBBBCBCCCCBBCBCBBBBBCCBBBBBCBBBCBBCBCCBBBB

出力例 4

Yes

入力例 5

7
CBBBCBB

出力例 5

Yes

Score : 200 pts

Problem Statement

Takahashi's wallet contains N pieces of money. The contents of the wallet are represented by a string S of length N: if the i-th character of S is C, the i-th piece is a coin; if it is B, the piece is a bill.

Print Yes if Takahashi's wallet contains at least one coin and at least one bill, and No otherwise.

Constraints

1 \leq N \leq 100
S is a string of length N consisting only of C and B.

Input

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

N
S

The first line contains the number of pieces of money N.
The second line contains the string S representing the contents of the wallet.

Output

Print Yes in one line if both coins and bills are present, and No otherwise.

Sample Input 1

3
CCB

Sample Output 1

Yes

Sample Input 2

3
BBB

Sample Output 2

No

Sample Input 3

3
BCB

Sample Output 3

Yes

Sample Input 4

60
CBCCCCCCBBBBBBBBBBBBBBCBCCCCBBCBCBBBBBCCBBBBBCBBBCBBCBCCBBBB

Sample Output 4

Yes

Sample Input 5

7
CBBBCBB

Sample Output 5

Yes

B - Treasure Map

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 233 点

問題文

高橋君は縦 H 行、横 W 列のマス目でできた宝物の地図を持っています。地図の様子は H 個の文字列 S_1, S_2, \ldots, S_H で表され、 S_i の j 文字目は上から i 行目、左から j 列目のマスの様子です。 T は宝物が埋まっていることを、 . は何もないことを表します。

各行について、その行に宝物が 1 つ以上あるかどうかを調べ、あるなら o 、ないなら x として、上の行から順に並べた長さ H の文字列を出力してください。

制約

1 \leq H \leq 10
1 \leq W \leq 10
S_i は T と . のみからなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H

1 行目には、地図の行数 H と列数 W がスペース区切りで与えられる。
2 行目から H 行にわたり、 1 + i 行目には上から i 行目の様子を表す文字列 S_i が与えられる。

出力

長さ H の文字列を 1 行で出力せよ。

入力例 1

2 2
T.
..

出力例 1

ox

入力例 2

3 3
...
.T.
...

出力例 2

xox

入力例 3

1 1
T

出力例 3

入力例 4

2 2
..
..

出力例 4

xx

入力例 5

3 3
T.T
...
T.T

出力例 5

oxo

Score : 233 pts

Problem Statement

Takahashi has a treasure map made of a grid with H rows and W columns. The map is described by H strings S_1, S_2, \ldots, S_H, where the j-th character of S_i represents the cell in the i-th row from the top and the j-th column from the left. T means a treasure is buried there, and . means there is nothing.

For each row, determine whether the row contains at least one treasure. Output a string of length H consisting of o (if it does) or x (if it does not), listed from the top row to the bottom row.

Constraints

1 \leq H \leq 10
1 \leq W \leq 10
S_i is a string of length W consisting only of T and .

Input

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

H W
S_1
S_2
\vdots
S_H

The first line contains the number of rows H and the number of columns W of the map, separated by a space.
The next H lines follow: the (1 + i)-th line contains the string S_i describing the i-th row from the top.

Output

Print a single line containing a string of length H.

Sample Input 1

2 2
T.
..

Sample Output 1

ox

Sample Input 2

3 3
...
.T.
...

Sample Output 2

xox

Sample Input 3

1 1
T

Sample Output 3

Sample Input 4

2 2
..
..

Sample Output 4

xx

Sample Input 5

3 3
T.T
...
T.T

Sample Output 5

oxo

C - Absolute Ace

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 333 点

問題文

高橋君はサッカーチームの監督です。チームには N 人の選手がおり、選手 i (1 \leq i \leq N) は攻撃力 A_i と守備力 B_i の 2 つのパラメータを持っています。

ある選手 k が絶対的エースであるとは、k 以外のすべての選手 j (1 \leq j \leq N, j \neq k) に対して、A_k > A_j かつ B_k > B_j が成り立つことを指します。

高橋君は、特別な強化トレーニングを繰り返し行うことができます。1 回のトレーニングでは、N 人の中から選手を 1 人選び、その選手の攻撃力と守備力のうちちょうど 1 つを選んで 1 だけ上昇させます。同じ選手を何度でも選ぶことができ、同じパラメータを何度でも上昇させることができます。また、異なる選手に対してそれぞれトレーニングを行うこともできます。ただし、パラメータを下げることはできません。トレーニングを 1 回も行わないことも許されます。

高橋君は、すべてのトレーニングが終了した後の状態において、絶対的エースである選手が少なくとも 1 人存在するようにしたいと考えています。絶対的エースとなる選手は N 人のうち誰であってもかまいません。この状態を達成するために必要なトレーニングの最小回数を求めてください。

制約

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
入力はすべて整数である。

入力

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

1 行目には、選手の人数を表す整数 N が与えられる。
続く N 行の i 行目 (1 \leq i \leq N) には、選手 i の攻撃力 A_i と守備力 B_i がスペース区切りで与えられる。

出力

絶対的エースである選手が少なくとも 1 人存在する状態を達成するために必要なトレーニングの最小回数を 1 行で出力せよ。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

出力例 3

Score : 333 pts

Problem Statement

Takahashi is the manager of a soccer team. The team has N players, and player i (1 \leq i \leq N) has two parameters: attack power A_i and defense power B_i.

A player k is called an absolute ace if, for every other player j (1 \leq j \leq N, j \neq k), both A_k > A_j and B_k > B_j hold.

Takahashi can repeatedly conduct special training sessions. In one training session, he selects one player from the N players, chooses exactly one of that player's attack power or defense power, and increases it by 1. The same player can be selected any number of times, and the same parameter can be increased any number of times. Training can also be performed on different players. However, parameters cannot be decreased. It is also allowed to perform no training sessions at all.

Takahashi wants to ensure that, after all training sessions are completed, there exists at least one player who is an absolute ace. The absolute ace can be any of the N players. Find the minimum number of training sessions required to achieve this.

Constraints

2 \leq N \leq 2 \times 10^5
1 \leq A_i \leq 10^9
1 \leq B_i \leq 10^9
All input values are integers.

Input

N
A_1 B_1
A_2 B_2
\vdots
A_N B_N

The first line contains an integer N representing the number of players.
The i-th of the following N lines (1 \leq i \leq N) contains the attack power A_i and defense power B_i of player i, separated by a space.

Output

Print in one line the minimum number of training sessions required to achieve a state where at least one player is an absolute ace.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

Sample Output 3

D - Painting the Fence

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は、横一列に並んだ N 枚の板からなるフェンスをペンキで塗ることにしました。

板には左から順に 1 から N までの番号が付けられています。

使用できるペンキの色は 1 から K までの K 種類あります。

高橋君は、それぞれの板をちょうど 1 つの色で塗ります。

板 i を色 j で塗るには、コストが C_{i, j} かかります。

また、見栄えを良くするため、隣り合う板を同じ色で塗ることはできません。すなわち、すべての 1 \leq i \leq N - 1 について、板 i と板 i + 1 は異なる色で塗る必要があります。

すべての板を条件を満たすように塗るとき、かかるコストの総和の最小値を求めてください。

制約

1 \leq N \leq 10^5
2 \leq K \leq 10^6
N \times K \leq 10^6
1 \leq C_{i, j} \leq 10^9
入力はすべて整数

入力

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

N K
C_{1, 1} C_{1, 2} \dots C_{1, K}
C_{2, 1} C_{2, 2} \dots C_{2, K}
\vdots
C_{N, 1} C_{N, 2} \dots C_{N, K}

出力

すべての板を条件を満たすように塗る際にかかるコストの総和の最小値を 1 行で出力してください。

入力例 1

出力例 1

入力例 2

出力例 2

入力例 3

8 4
12 45 67 23
89 34 11 56
78 90 21 43
15 63 82 99
44 12 77 35
68 29 51 14
93 84 37 62
19 73 48 85

出力例 3

入力例 4

12 4
837204918 294817263 948172635 182736452
718293041 492018273 618294031 384729102
529103847 819203948 203948172 638291047
192837465 748392018 382910475 920184736
482910374 192847563 839201746 573829104
628194038 394820174 182739405 748392019
918273645 538291047 284719203 401928374
284910385 619284730 847291038 193847562
394820174 728194039 501928374 819283746
182739405 492817364 738291048 394820175
618294037 839201745 294810385 501928374
748392018 193847562 482910375 628194039

出力例 4

3307291815

入力例 5

1 2
100 42

出力例 5

Score : 400 pts

Problem Statement

Takahashi has decided to paint a fence consisting of N boards arranged in a row from left to right.

The boards are numbered 1 through N from left to right.

There are K available colors of paint, numbered 1 through K.

Takahashi will paint each board with exactly one color.

Painting board i with color j costs C_{i, j}.

Furthermore, to make the fence look nice, no two adjacent boards can be painted with the same color. That is, for all 1 \leq i \leq N - 1, board i and board i + 1 must be painted with different colors.

Find the minimum total cost to paint all the boards such that the condition is satisfied.

Constraints

1 \leq N \leq 10^5
2 \leq K \leq 10^6
N \times K \leq 10^6
1 \leq C_{i, j} \leq 10^9
All input values are integers.

Input

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

N K
C_{1, 1} C_{1, 2} \dots C_{1, K}
C_{2, 1} C_{2, 2} \dots C_{2, K}
\vdots
C_{N, 1} C_{N, 2} \dots C_{N, K}

Output

Print the minimum total cost to paint all the boards satisfying the condition in a single line.

Sample Input 1

Sample Output 1

Sample Input 2

Sample Output 2

Sample Input 3

8 4
12 45 67 23
89 34 11 56
78 90 21 43
15 63 82 99
44 12 77 35
68 29 51 14
93 84 37 62
19 73 48 85

Sample Output 3

Sample Input 4

12 4
837204918 294817263 948172635 182736452
718293041 492018273 618294031 384729102
529103847 819203948 203948172 638291047
192837465 748392018 382910475 920184736
482910374 192847563 839201746 573829104
628194038 394820174 182739405 748392019
918273645 538291047 284719203 401928374
284910385 619284730 847291038 193847562
394820174 728194039 501928374 819283746
182739405 492817364 738291048 394820175
618294037 839201745 294810385 501928374
748392018 193847562 482910375 628194039

Sample Output 4

3307291815

Sample Input 5

1 2
100 42

Sample Output 5

E - Team Combinations

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 466 点

問題文

高橋君はプログラミング合宿の幹事を務めています。合宿の参加者はあらかじめ第 1 グループと第 2 グループの 2 つに分かれており、各グループにはそれぞれ N 人のメンバーがいます。

各メンバーには非負整数のスキル値が割り当てられています。第 1 グループのメンバーのスキル値は A_1, A_2, \ldots, A_N 、第 2 グループのメンバーのスキル値は B_1, B_2, \ldots, B_N です。異なるメンバーが同じスキル値を持つこともあります。

高橋君は、各グループからそれぞれメンバーの部分集合を 1 つずつ選びます（空集合、すなわち誰も選ばないことも許されます）。第 1 グループから選んだメンバーのスキル値の XOR（排他的論理和）を X 、第 2 グループから選んだメンバーのスキル値の XOR を Y とします。グループから誰も選ばなかった場合、そのグループの XOR は 0 とします。

青木君から、合宿の課題として非負整数の目標値 S が伝えられました。チーム編成が成功する条件は、X + Y = S を満たすことです。ここでの + は通常の整数の加算です。

第 1 グループからの部分集合の選び方と第 2 グループからの部分集合の選び方の組を 1 つの 選び方の組 とします。選ばれるメンバーの部分集合が少なくとも一方のグループで異なれば、結果として同じ X, Y の値になったとしても、それらは異なる選び方の組として別々に数えます。

X + Y = S を満たすような選び方の組の個数を求めてください。

制約

1 \leq N \leq 50
0 \leq S < 2^{21}
0 \leq A_i < 2^{20} (1 \leq i \leq N)
0 \leq B_i < 2^{20} (1 \leq i \leq N)
入力はすべて整数である
答えは 2^{63} 未満であることが保証される

入力

N S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

1 行目には、各グループのメンバー数を表す整数 N と、目標値を表す整数 S が、スペース区切りで与えられる。
2 行目には、第 1 グループの N 人のスキル値を表す整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
3 行目には、第 2 グループの N 人のスキル値を表す整数 B_1, B_2, \ldots, B_N が、スペース区切りで与えられる。

出力

条件 X + Y = S を満たす選び方の組の個数を 1 行で出力せよ。

入力例 1

2 3
1 2
0 3

出力例 1

入力例 2

2 7
1 2
8 16

出力例 2

入力例 3

10 12345
0 1 2 3 5 8 13 21 34 55
7 7 14 28 56 112 224 448 896 1792

出力例 3

入力例 4

40 1048576
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 262145 524289 1048575
524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 6 10 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152 98304 196608 393216 786432 1048574

出力例 4

1152920405095219200

入力例 5

1 2097150
1048575
1048575

出力例 5

Score : 466 pts

Problem Statement

Takahashi is organizing a programming camp. The participants of the camp are already divided into two groups, Group 1 and Group 2, each consisting of N members.

Each member has a non-negative integer skill value assigned. The skill values of the members in Group 1 are A_1, A_2, \ldots, A_N, and the skill values of the members in Group 2 are B_1, B_2, \ldots, B_N. Different members may have the same skill value.

Takahashi will choose a subset of members from each group (the empty set, i.e., choosing no one, is also allowed). Let X be the XOR (bitwise exclusive OR) of the skill values of the members chosen from Group 1, and Y be the XOR of the skill values of the members chosen from Group 2. If no one is chosen from a group, the XOR for that group is 0.

Aoki has given him a non-negative integer target value S as a task for the camp. The condition for successful team formation is that X + Y = S is satisfied. Here, + represents standard integer addition.

A pair consisting of a choice of a subset from Group 1 and a choice of a subset from Group 2 is called a combination of choices. If the chosen subset of members differs in at least one group, they are counted as different combinations of choices, even if they result in the same values of X and Y.

Find the number of combinations of choices that satisfy X + Y = S.

Constraints

1 \leq N \leq 50
0 \leq S < 2^{21}
0 \leq A_i < 2^{20} (1 \leq i \leq N)
0 \leq B_i < 2^{20} (1 \leq i \leq N)
All input values are integers.
The answer is guaranteed to be less than 2^{63}.

Input

N S
A_1 A_2 \ldots A_N
B_1 B_2 \ldots B_N

The first line contains an integer N, representing the number of members in each group, and an integer S, representing the target value, separated by a space.
The second line contains N integers A_1, A_2, \ldots, A_N, representing the skill values of the members of Group 1, separated by spaces.
The third line contains N integers B_1, B_2, \ldots, B_N, representing the skill values of the members of Group 2, separated by spaces.

Output

Print the number of combinations of choices that satisfy the condition X + Y = S in a single line.

Sample Input 1

2 3
1 2
0 3

Sample Output 1

Sample Input 2

2 7
1 2
8 16

Sample Output 2

Sample Input 3

10 12345
0 1 2 3 5 8 13 21 34 55
7 7 14 28 56 112 224 448 896 1792

Sample Output 3

Sample Input 4

40 1048576
1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288 3 5 9 17 33 65 129 257 513 1025 2049 4097 8193 16385 32769 65537 131073 262145 524289 1048575
524288 262144 131072 65536 32768 16384 8192 4096 2048 1024 512 256 128 64 32 16 8 4 2 1 6 10 12 24 48 96 192 384 768 1536 3072 6144 12288 24576 49152 98304 196608 393216 786432 1048574

Sample Output 4

1152920405095219200

Sample Input 5

1 2097150
1048575
1048575