C - Piano 3

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

高橋君は、横一列に並んだ 100 個の鍵盤からなるピアノを持っています。 このピアノの左から i 個目の鍵盤のことを鍵盤 i と呼びます。

高橋君は今から N 回にわたってこのピアノの鍵盤を一つずつ押すことでとある曲を演奏します。 i 回目に押す鍵盤は鍵盤 A_i であり、それを押す手は S_i= L のとき左手、S_i= R のとき右手です。

演奏を始める前、高橋君は両手をそれぞれ好きな鍵盤の上に置くことができ、この時点での疲労度は 0 です。 演奏中、片方の手を鍵盤 x の上から鍵盤 y の上へと動かすと疲労度が |y-x| 増加します（逆に、手の移動以外で疲労度が増加することはありません）。 なお、ある手である鍵盤を押すためには、その手がその鍵盤の上に置かれている必要があります。

演奏が終了した時点での疲労度は最小でいくつになるか求めてください。

制約

  • 1\leq N \leq 100
  • 1\leq A_i \leq 100
  • N,A_i は整数
  • S_i は L または R

入力

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

出力

演奏が終了した時点での疲労度の最小値を出力せよ。

入力例 1

4
3 L
6 R
9 L
1 R

出力例 1

11

例えば以下のように演奏することができます。

  • 最初、左手を鍵盤 3 の上に、右手を鍵盤 6 の上に置いておく。
  • 左手で鍵盤 3 を押す。
  • 右手で鍵盤 6 を押す。
  • 左手を鍵盤 3 の上から鍵盤 9 の上へと動かす。疲労度が |9-3|=6 増加する。
  • 右手を鍵盤 6 の上から鍵盤 1 の上へと動かす。疲労度が |1-6|=5 増加する。
  • 左手で鍵盤 9 を押す。
  • 右手で鍵盤 1 を押す。

このとき、演奏が終了した時点での疲労度は 6+5=11 であり、これが最小です。

入力例 2

3
2 L
2 L
100 L

出力例 2

98

入力例 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

出力例 3

188

Score : 200 points

Problem Statement

Takahashi has a piano with 100 keys arranged in a row. The i-th key from the left is called key i.

He will play music by pressing N keys one by one. For the i-th press, he will press key A_i, using his left hand if S_i= L, and his right hand if S_i= R.

Before starting to play, he can place both of his hands on any keys he likes, and his fatigue level at this point is 0. During the performance, if he moves one hand from key x to key y, the fatigue level increases by |y-x| (conversely, the fatigue level does not increase for any reason other than moving hands). To press a certain key with a hand, that hand must be placed on that key.

Find the minimum possible fatigue level at the end of the performance.

Constraints

  • 1 \leq N \leq 100
  • 1 \leq A_i \leq 100
  • N and A_i are integers.
  • S_i is L or R.

Input

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

N
A_1 S_1
A_2 S_2
\vdots
A_N S_N

Output

Print the minimum fatigue level at the end of the performance.

Sample Input 1

4
3 L
6 R
9 L
1 R

Sample Output 1

11

For example, the performance can be done as follows:

  • Initially, place the left hand on key 3 and the right hand on key 6.
  • Press key 3 with the left hand.
  • Press key 6 with the right hand.
  • Move the left hand from key 3 to key 9. The fatigue level increases by |9-3| = 6.
  • Move the right hand from key 6 to key 1. The fatigue level increases by |1-6| = 5.
  • Press key 9 with the left hand.
  • Press key 1 with the right hand.

In this case, the fatigue level at the end of the performance is 6+5 = 11, which is the minimum possible.

Sample Input 2

3
2 L
2 L
100 L

Sample Output 2

98

Sample Input 3

8
22 L
75 L
26 R
45 R
72 R
81 R
47 L
29 R

Sample Output 3

188
D - Substring

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

英小文字からなる文字列 S が与えられます。S の空でない部分文字列は何種類ありますか？

ただし、部分文字列とは連続する部分列のことを指します。例えば、xxx は yxxxy の部分文字列ですが、xxyxx の部分文字列ではありません。

制約

  • S は英小文字からなる長さ 1 以上 100 以下の文字列

入力

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

S

出力

答えを出力せよ。

入力例 1

yay

出力例 1

5

S の空でない部分文字列は以下の 5 種類です。

  • a
  • y
  • ay
  • ya
  • yay

入力例 2

aababc

出力例 2

17

入力例 3

abracadabra

出力例 3

54

Score: 200 points

Problem Statement

You are given a string S consisting of lowercase English letters. How many different non-empty substrings does S have?

A substring is a contiguous subsequence. For example, xxx is a substring of yxxxy but not of xxyxx.

Constraints

  • S is a string of length between 1 and 100, inclusive, consisting of lowercase English letters.

Input

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

S

Output

Print the answer.

Sample Input 1

yay

Sample Output 1

5

S has the following five different non-empty substrings:

  • a
  • y
  • ay
  • ya
  • yay

Sample Input 2

aababc

Sample Output 2

17

Sample Input 3

abracadabra

Sample Output 3

54
E - Sum = 0

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 350 点

問題文

N 個の整数の組 (L_1,R_1),(L_2,R_2),\ldots,(L_N,R_N) が与えられます。

以下の条件を満たす長さ N の整数列 X=(X_1,X_2,\ldots,X_N) が存在するか判定し、存在するならば一つ出力してください。

  • 各 i=1,2,\ldots,N に対して L_i\leq X_i\leq R_i
  • \displaystyle \sum_{i=1}^N X_i=0

制約

  • 1\leq N\leq 2\times 10^5
  • -10^9\leq L_i\leq R_i\leq 10^9
  • 入力は全て整数

入力

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

出力

存在しない場合は No を出力せよ。存在する場合は条件を満たす整数列 X を以下の形式で出力せよ。

Yes
X_1 X_2 \ldots X_N

答えが複数存在する場合、どれを出力しても正解とみなされる。

入力例 1

3
3 5
-4 1
-2 3

出力例 1

Yes
4 -3 -1

数列 X=(4,-3,-1) は問題の条件をすべて満たします。ほかにも (3,-3,0) や (5,-4,-1) などが条件を満たします。

入力例 2

3
1 2
1 2
1 2

出力例 2

No

条件を満たす整数列 X は存在しません。

入力例 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

出力例 3

Yes
-66 -57 31 -6 89 9

Score : 350 points

Problem Statement

You are given N pairs of integers (L_1, R_1), (L_2, R_2), \ldots, (L_N, R_N).

Determine whether there exists a sequence of N integers X = (X_1, X_2, \ldots, X_N) that satisfies the following conditions, and print one such sequence if it exists.

  • L_i \leq X_i \leq R_i for each i = 1, 2, \ldots, N.
  • \displaystyle \sum_{i=1}^N X_i = 0.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq L_i \leq R_i \leq 10^9
  • All input values are integers.

Input

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

N
L_1 R_1
L_2 R_2
\vdots
L_N R_N

Output

If no solution exists, print No. Otherwise, print an integer sequence X that satisfies the conditions in the following format:

Yes
X_1 X_2 \ldots X_N

If multiple solutions exist, any of them will be considered correct.

Sample Input 1

3
3 5
-4 1
-2 3

Sample Output 1

Yes
4 -3 -1

The sequence X = (4, -3, -1) satisfies all the conditions. Other valid sequences include (3, -3, 0) and (5, -4, -1).

Sample Input 2

3
1 2
1 2
1 2

Sample Output 2

No

No sequence X satisfies the conditions.

Sample Input 3

6
-87 12
-60 -54
2 38
-76 6
87 96
-17 38

Sample Output 3

Yes
-66 -57 31 -6 89 9
F - Enumerate Sequences

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

以下の条件を満たす長さ N の整数列を辞書順で小さい方から順に全て出力して下さい。

  • i 番目の要素は 1 以上 R_i 以下
  • 総和が K の倍数
数列の辞書順とは？ 数列 A = (A_1, \ldots, A_{|A|}) が B = (B_1, \ldots, B_{|B|}) より辞書順で真に小さいとは、下記の 1. と 2. のどちらかが成り立つことを言います。
  1. |A|<|B| かつ (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}) である。
  2. ある整数 1\leq i\leq \min\{|A|,|B|\} が存在して、下記の 2 つがともに成り立つ。
    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
    • A_i < B_i

制約

  • 入力は全て整数
  • 1 \le N \le 8
  • 2 \le K \le 10
  • 1 \le R_i \le 5

入力

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

N K
R_1 R_2 \dots R_N

出力

出力すべき数列が X 個あり、そのうち i 個目が A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}) であったとき、答えを以下の形式で出力せよ。

A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}

入力例 1

3 2
2 1 3

出力例 1

1 1 2
2 1 1
2 1 3

出力すべき数列は 3 個で、辞書順で (1,1,2),(2,1,1),(2,1,3) です。

入力例 2

1 2
1

出力例 2



出力すべき数列が無い場合もあります。

この場合、出力は空で構いません。













入力例 3
5 5
2 3 2 3 2












出力例 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







Score : 300 points







Problem Statement
Print all integer sequences of length N that satisfy the following conditions, in ascending lexicographical order.


    

  • The i-th element is between 1 and R_i, inclusive.
    • 

  • The sum of all elements is a multiple of K.
    • 



 What is lexicographical order for sequences?
A sequence A = (A_1, \ldots, A_{|A|}) is lexicographically smaller than B = (B_1, \ldots, B_{|B|}) if either 1. or 2. below holds:

    

  1. |A|<|B| and (A_{1},\ldots,A_{|A|}) = (B_1,\ldots,B_{|A|}).
    2. 

  2. There exists an integer 1\leq i\leq \min\{|A|,|B|\} such that both of the following are true:

      

    • (A_{1},\ldots,A_{i-1}) = (B_1,\ldots,B_{i-1})
      • 

    • A_i < B_i
      • 

    















Constraints
    

  • All input values are integers.
    • 

  • 1 \le N \le 8
    • 

  • 2 \le K \le 10
    • 

  • 1 \le R_i \le 5
    • 
















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


N K
R_1 R_2 \dots R_N












Output
Print the answer in the following format, where X is the number of sequences to print, the i-th of which is A_i=(A_{i,1},A_{i,2},\dots,A_{i,N}):


A_{1,1} A_{1,2} \dots A_{1,N}
A_{2,1} A_{2,2} \dots A_{2,N}
\vdots
A_{X,1} A_{X,2} \dots A_{X,N}
















Sample Input 1
3 2
2 1 3












Sample Output 1
1 1 2
2 1 1
2 1 3



There are three sequences to be printed, which are (1,1,2),(2,1,1),(2,1,3) in lexicographical order.













Sample Input 2
1 2
1












Sample Output 2


There may be no sequences to print.

In this case, the output can be empty.













Sample Input 3
5 5
2 3 2 3 2












Sample Output 3
1 1 1 1 1
1 2 2 3 2
1 3 1 3 2
1 3 2 2 2
1 3 2 3 1
2 1 2 3 2
2 2 1 3 2
2 2 2 2 2
2 2 2 3 1
2 3 1 2 2
2 3 1 3 1
2 3 2 1 2
2 3 2 2 1







			


			
		

	
		

		

			G - Scope
			

			
実行時間制限: 2 sec / メモリ制限: 1024 MiB


			

				


配点 : 400 点







問題文
英小文字、(、) からなる文字列のうち、以下の手順によって空文字列になるものを良い文字列と呼びます:


    

  • まず、英小文字をすべて削除する。
    • 

  • 次に、連続する () が存在する限り、それを削除する。
    • 



例えば、((a)ba) は英小文字をすべて削除すると (()) となり、2 文字目と 3 文字目に連続する () を削除すると () となり、最終的に空文字列にすることができるので良い文字列です。  


良い文字列 S が与えられます。
S の i 文字目を S_i で表します。


各英小文字 a , b , \ldots , z に対して、その文字が書かれたボールが 1 つあります。
また、空の箱があります。


高橋君は i = 1,2, \ldots ,|S| に対してこの順に気を失わない限り操作を行います。


    

  • S_i が英小文字ならば、その英小文字が書かれたボールを箱に入れる。ただし、そのボールがすでに箱に入っている場合、高橋君は気を失う。
    • 

  • S_i が ( ならば、何もしない。  
    • 

  • S_i が ) ならば、i 未満の整数 j であって、S の j 番目から i 番目までの文字からなる文字列が良い文字列となる最大の整数 j を取る。（このような整数 j は必ず存在することが証明できる。）j 番目から i 番目までの操作で箱に入れたボールをすべて、箱から取り出す。
    • 



高橋君が気を失わずに一連の操作を完了させられるか判定してください。











制約
    

  • 1 \leq |S| \leq 3 \times 10^5
    • 

  • S は良い文字列
    • 
















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


S












出力
高橋君が気を失わずに一連の操作を完了させられる場合は Yes を、そうでない場合は No を出力せよ。















入力例 1
((a)ba)












出力例 1
Yes



i = 1 のとき、高橋君は何もしません。

i = 2 のとき、高橋君は何もしません。

i = 3 のとき、高橋君は a の書かれたボールを箱の中に入れます。

i = 4 のとき、4 未満の整数 j であって、S の j 番目から 4 番目までの文字からなる文字列が良い文字列となる最大の整数は 2 であるため、高橋君は a の書かれたボールを箱から取り出します。

i = 5 のとき、高橋君は b の書かれたボールを箱の中に入れます。

i = 6 のとき、高橋君は a の書かれたボールを箱の中に入れます。

i = 7 のとき、7 未満の整数 j であって、S の j 番目から 7 番目までの文字からなる文字列が良い文字列となる最大の整数は 1 であるため、高橋君は a の書かれたボールと b の書かれたボールを箱から取り出します。


したがってこの場合の答えは Yes となります。













入力例 2
(a(ba))












出力例 2
No



i = 1 のとき、高橋君は何もしません。

i = 2 のとき、高橋君は a の書かれたボールを箱の中に入れます。

i = 3 のとき、高橋君は何もしません。

i = 4 のとき、高橋君は b の書かれたボールを箱の中に入れます。

i = 5 のとき、a の書かれたボールはすでに箱に入っているため、高橋君は気を失い、これ以降の操作は行われません。


したがってこの場合の答えは No となります。













入力例 3
(((())))












出力例 3
Yes














入力例 4
abca












出力例 4
No







Score : 400 points







Problem Statement
A string consisting of lowercase English letters, (, and ) is said to be a good string if you can make it an empty string by the following procedure:


    

  • First, remove all lowercase English letters.
    • 

  • Then, repeatedly remove consecutive () while possible.
    • 



For example, ((a)ba) is a good string, because removing all lowercase English letters yields (()), from which we can remove consecutive () at the 2-nd and 3-rd characters to obtain (), which in turn ends up in an empty string.  


You are given a good string S.
We denote by S_i the i-th character of S.


For each lowercase English letter a, b, \ldots, and z, we have a ball with the letter written on it.
Additionally, we have an empty box.


For each i = 1,2, \ldots ,|S| in this order, Takahashi performs the following operation unless he faints.


    

  • If S_i is a lowercase English letter, put the ball with the letter written on it into the box.  If the ball is already in the box, he faints.  
    • 

  • If S_i is (, do nothing.  
    • 

  • If S_i is ), take the maximum integer j less than i such that the j-th through i-th characters of S form a good string.  (We can prove that such an integer j always exists.)  Take out from the box all the balls that he has put in the j-th through i-th operations.
    • 



Determine if Takahashi can complete the sequence of operations without fainting.











Constraints
    

  • 1 \leq |S| \leq 3 \times 10^5
    • 

  • S is a good string.
    • 
















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


S












Output
Print Yes if he can complete the sequence of operations without fainting; print No otherwise.















Sample Input 1
((a)ba)












Sample Output 1
Yes



For i = 1, he does nothing.

For i = 2, he does nothing.

For i = 3, he puts the ball with a written on it into the box.

For i = 4, j=2 is the maximum integer less than 4 such that the j-th through 4-th characters of S form a good string, so he takes out the ball with a written on it from the box.

For i = 5, he puts the ball with b written on it into the box.

For i = 6, he puts the ball with a written on it into the box.

For i = 7, j=1 is the maximum integer less than 7 such that the j-th through 7-th characters of S form a good string, so he takes out the ball with a written on it, and another with b, from the box.


Therefore, the answer to this case is Yes.













Sample Input 2
(a(ba))












Sample Output 2
No



For i = 1, he does nothing.

For i = 2, he puts the ball with a written on it into the box.

For i = 3, he does nothing.

For i = 4, he puts the ball with b written on it into the box.

For i = 5, the ball with a written on it is already in the box, so he faints, aborting the sequence of operations.


Therefore, the answer to this case is No.













Sample Input 3
(((())))












Sample Output 3
Yes














Sample Input 4
abca












Sample Output 4
No