AtCoder Beginner Contest 098

A - Add Sub Mul

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

2 つの整数 A, B が与えられます。 A+B, A-B, A \times B の中で最大の値を求めてください。

制約

-1000 \leq A,B \leq 1000
入力はすべて整数である

入力

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

A B

出力

A+B, A-B, A \times B の中で最大の値を出力せよ。

入力例 1

3 1

出力例 1

3+1=4, 3-1=2, 3 \times 1=3 なので、この中で最大の値である 4 が答えになります。

入力例 2

4 -2

出力例 2

4 - (-2) = 6 が最大の値になります。

入力例 3

0 0

出力例 3

Score : 100 points

Problem Statement

You are given two integers A and B. Find the largest value among A+B, A-B and A \times B.

Constraints

-1000 \leq A,B \leq 1000
All values in input are integers.

Input

Input is given from Standard Input in the following format:

A B

Output

Print the largest value among A+B, A-B and A \times B.

Sample Input 1

3 1

Sample Output 1

3+1=4, 3-1=2 and 3 \times 1=3. The largest among them is 4.

Sample Input 2

4 -2

Sample Output 2

The largest is 4 - (-2) = 6.

Sample Input 3

0 0

Sample Output 3

B - Cut and Count

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

英小文字からなる長さ N の文字列 S が与えられます。この文字列を一箇所で切断して、文字列 X と Y に分割します。このとき、「X と Y のどちらにも含まれている文字」の種類数を最大化したいです。文字列を切断する位置を適切に決めた際の「X と Y のどちらにも含まれている文字」の種類数の最大値を求めてください。

制約

2 \leq N \leq 100
|S| = N
S は英小文字からなる

入力

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

N
S

出力

「X と Y のどちらにも含まれている文字」の種類数の最大値を出力せよ。

入力例 1

6
aabbca

出力例 1

S を先頭から 3 文字目と 4 文字目の間で切って X = aab と Y = bca に分割すると、「X と Y のどちらにも含まれている文字」は a と b です。「X と Y のどちらにも含まれている文字」の種類数が 3 以上になることはないので、答えは 2 になります。

入力例 2

10
aaaaaaaaaa

出力例 2

どのように S を分割しても、「X と Y のどちらにも含まれている文字」は a のみです。

入力例 3

45
tgxgdqkyjzhyputjjtllptdfxocrylqfqjynmfbfucbir

出力例 3

Score : 200 points

Problem Statement

You are given a string S of length N consisting of lowercase English letters. We will cut this string at one position into two strings X and Y. Here, we would like to maximize the number of different letters contained in both X and Y. Find the largest possible number of different letters contained in both X and Y when we cut the string at the optimal position.

Constraints

2 \leq N \leq 100
|S| = N
S consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the largest possible number of different letters contained in both X and Y.

Sample Input 1

6
aabbca

Sample Output 1

If we cut the string between the third and fourth letters into X = aab and Y = bca, the letters contained in both X and Y are a and b. There will never be three or more different letters contained in both X and Y, so the answer is 2.

Sample Input 2

10
aaaaaaaaaa

Sample Output 2

However we divide S, only a will be contained in both X and Y.

Sample Input 3

45
tgxgdqkyjzhyputjjtllptdfxocrylqfqjynmfbfucbir

Sample Output 3

C - Attention

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

N 人の人が東西方向に一列に並んでいます。それぞれの人は、東または西を向いています。誰がどの方向を向いているかは長さ N の文字列 S によって与えられます。西から i 番目に並んでいる人は、S_i = E なら東を、S_i = W なら西を向いています。

あなたは、N 人のうち誰か 1 人をリーダーとして任命します。そして、リーダー以外の全員に、リーダーの方向を向くように命令します。このとき、リーダーはどちらの方向を向いていても構いません。

並んでいる人は、向く方向を変えるのを嫌っています。そのためあなたは、向く方向を変える人数が最小になるようにリーダーを選びたいです。向く方向を変える人数の最小値を求めてください。

制約

2 \leq N \leq 3 \times 10^5
|S| = N
S_i は E または W である

入力

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

N
S

出力

向く方向を変える人数の最小値を出力せよ。

入力例 1

5
WEEWW

出力例 1

西から 3 番目に並んでいる人をリーダーに任命するとします。すると、西から 1 番目に並んでいる人は東を向かなくてはならないので、向く方向を変える必要があります。ほかの人は向く方向を変える必要がないので、この場合、向く方向を変える人は 1 人になります。向く方向を変える人を 0 人にすることは出来ないので、答えは 1 になります。

入力例 2

12
WEWEWEEEWWWE

出力例 2

入力例 3

8
WWWWWEEE

出力例 3

Score : 300 points

Problem Statement

There are N people standing in a row from west to east. Each person is facing east or west. The directions of the people is given as a string S of length N. The i-th person from the west is facing east if S_i = E, and west if S_i = W.

You will appoint one of the N people as the leader, then command the rest of them to face in the direction of the leader. Here, we do not care which direction the leader is facing.

The people in the row hate to change their directions, so you would like to select the leader so that the number of people who have to change their directions is minimized. Find the minimum number of people who have to change their directions.

Constraints

2 \leq N \leq 3 \times 10^5
|S| = N
S_i is E or W.

Input

Input is given from Standard Input in the following format:

N
S

Output

Print the minimum number of people who have to change their directions.

Sample Input 1

5
WEEWW

Sample Output 1

Assume that we appoint the third person from the west as the leader. Then, the first person from the west needs to face east and has to turn around. The other people do not need to change their directions, so the number of people who have to change their directions is 1 in this case. It is not possible to have 0 people who have to change their directions, so the answer is 1.

Sample Input 2

12
WEWEWEEEWWWE

Sample Output 2

Sample Input 3

8
WWWWWEEE

Sample Output 3

D - Xor Sum 2

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

長さ N の整数列 A があります。

次の条件を満たす整数 l, r ( 1 \leq l \leq r \leq N ) の組の個数を求めてください。

A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r

xorの説明

整数 c_1, c_2, ..., c_m の xor は以下のように定義されます。

xor の値を X とおく。X を 2 進数表記したときの 2^k ( 0 \leq k, k は整数 ) の位の値は、c_1, c_2, ...c_m のうち、2 進数表記したときの 2^k の位の値が 1 となるものが奇数個ならば 1、偶数個ならば 0 となる。

例えば、3 と 5 の xor の値は、3 の 2 進数表記が 011、5 の 2 進数表記が 101 のため、2 進数表記が 110 の 6 となります。

制約

1 \leq N \leq 2 \times 10^5
0 \leq A_i < 2^{20}
入力はすべて整数である

入力

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

N
A_1 A_2 ... A_N

出力

条件を満たす整数 l, r ( 1 \leq l \leq r \leq N ) の組の個数を出力せよ。

入力例 1

4
2 5 4 6

出力例 1

明らかに、(l,r)=(1,1),(2,2),(3,3),(4,4) は条件を満たします。また、(l,r)=(1,2) の場合、A_1\ xor\ A_2 = A_1\ +\ A_2 = 7 となるので、これも条件を満たします。ほかに条件を満たす組はないので、答えは 5 になります。

入力例 2

9
0 0 0 0 0 0 0 0 0

出力例 2

入力例 3

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1

出力例 3

Score : 500 points

Problem Statement

There is an integer sequence A of length N.

Find the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the following condition:

A_l\ xor\ A_{l+1}\ xor\ ...\ xor\ A_r = A_l\ +\ A_{l+1}\ +\ ...\ +\ A_r

Here, xor denotes the bitwise exclusive OR.

Definition of XOR

The XOR of integers c_1, c_2, ..., c_m is defined as follows:

Let the XOR be X. In the binary representation of X, the digit in the 2^k's place (0 \leq k; k is an integer) is 1 if there are an odd number of integers among c_1, c_2, ...c_m whose binary representation has 1 in the 2^k's place, and 0 if that number is even.

For example, let us compute the XOR of 3 and 5. The binary representation of 3 is 011, and the binary representation of 5 is 101, thus the XOR has the binary representation 110, that is, the XOR is 6.

Constraints

1 \leq N \leq 2 \times 10^5
0 \leq A_i < 2^{20}
All values in input are integers.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the number of the pairs of integers l and r (1 \leq l \leq r \leq N) that satisfy the condition.

Sample Input 1

4
2 5 4 6

Sample Output 1

(l,r)=(1,1),(2,2),(3,3),(4,4) clearly satisfy the condition. (l,r)=(1,2) also satisfies the condition, since A_1\ xor\ A_2 = A_1\ +\ A_2 = 7. There are no other pairs that satisfy the condition, so the answer is 5.

Sample Input 2

9
0 0 0 0 0 0 0 0 0

Sample Output 2

Sample Input 3

19
885 8 1 128 83 32 256 206 639 16 4 128 689 32 8 64 885 969 1