C - Daydream

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

英小文字からなる文字列 S が与えられます。 Tが空文字列である状態から始め、以下の操作を好きな回数繰り返すことで S = T とすることができるか判定してください。

  • T の末尾に dream dreamer erase eraser のいずれかを追加する。

制約

  • 1≦|S|≦10^5
  • S は英小文字からなる。

入力

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

S

出力

S = T とすることができる場合 YES を、そうでない場合 NO を出力せよ。

入力例 1

erasedream

出力例 1

YES

erase dream の順で T の末尾に追加することで S = T とすることができます。

入力例 2

dreameraser

出力例 2

YES

dream eraser の順で T の末尾に追加することで S = T とすることができます。

入力例 3

dreamerer

出力例 3

NO

Score : 300 points

Problem Statement

You are given a string S consisting of lowercase English letters. Another string T is initially empty. Determine whether it is possible to obtain S = T by performing the following operation an arbitrary number of times:

  • Append one of the following at the end of T: dream, dreamer, erase and eraser.

Constraints

  • 1≦|S|≦10^5
  • S consists of lowercase English letters.

Input

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

S

Output

If it is possible to obtain S = T, print YES. Otherwise, print NO.

Sample Input 1

erasedream

Sample Output 1

YES

Append erase and dream at the end of T in this order, to obtain S = T.

Sample Input 2

dreameraser

Sample Output 2

YES

Append dream and eraser at the end of T in this order, to obtain S = T.

Sample Input 3

dreamerer

Sample Output 3

NO
D - Connectivity

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

N 個の都市があり、K 本の道路と L 本の鉄道が都市の間に伸びています。 i 番目の道路は p_i 番目と q_i 番目の都市を双方向に結び、 i 番目の鉄道は r_i 番目と s_i 番目の都市を双方向に結びます。 異なる道路が同じ 2 つの都市を結ぶことはありません。同様に、異なる鉄道が同じ 2 つの都市を結ぶことはありません。

ある都市から別の都市に何本かの道路を通って到達できるとき、それらの都市は道路で連結しているとします。また、すべての都市はそれ自身と道路で連結しているとみなします。
鉄道についても同様に定めます。

全ての都市について、その都市と道路・鉄道のどちらでも連結している都市の数を求めてください。

制約

  • 2 ≦ N ≦ 2*10^5
  • 1 ≦ K, L≦ 10^5
  • 1 ≦ p_i, q_i, r_i, s_i ≦ N
  • p_i < q_i
  • r_i < s_i
  • i ≠ j のとき、(p_i, q_i) ≠ (p_j, q_j)
  • i ≠ j のとき、(r_i, s_i) ≠ (r_j, s_j)

入力

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

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

出力

N 個の整数を出力せよ。i 番目の数は i 番目の都市と道路・鉄道の両方で連結している都市の数である。

入力例 1

4 3 1
1 2
2 3
3 4
2 3

出力例 1

1 2 2 1

1, 2, 3, 4 番目の都市は全て互いに道路で連結しています。

鉄道で連結している都市は 2, 3 のみなので、答えは順に 1, 2, 2, 1 となります。

入力例 2

4 2 2
1 2
2 3
1 4
2 3

出力例 2

1 2 2 1

入力例 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

出力例 3

1 1 2 1 2 2 2

Score : 400 points

Problem Statement

There are N cities. There are also K roads and L railways, extending between the cities. The i-th road bidirectionally connects the p_i-th and q_i-th cities, and the i-th railway bidirectionally connects the r_i-th and s_i-th cities. No two roads connect the same pair of cities. Similarly, no two railways connect the same pair of cities.

We will say city A and B are connected by roads if city B is reachable from city A by traversing some number of roads. Here, any city is considered to be connected to itself by roads. We will also define connectivity by railways similarly.

For each city, find the number of the cities connected to that city by both roads and railways.

Constraints

  • 2 ≦ N ≦ 2*10^5
  • 1 ≦ K, L≦ 10^5
  • 1 ≦ p_i, q_i, r_i, s_i ≦ N
  • p_i < q_i
  • r_i < s_i
  • When i ≠ j, (p_i, q_i) ≠ (p_j, q_j)
  • When i ≠ j, (r_i, s_i) ≠ (r_j, s_j)

Input

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

N K L
p_1 q_1
:
p_K q_K
r_1 s_1
:
r_L s_L

Output

Print N integers. The i-th of them should represent the number of the cities connected to the i-th city by both roads and railways.

Sample Input 1

4 3 1
1 2
2 3
3 4
2 3

Sample Output 1

1 2 2 1

All the four cities are connected to each other by roads.

By railways, only the second and third cities are connected. Thus, the answers for the cities are 1, 2, 2 and 1, respectively.

Sample Input 2

4 2 2
1 2
2 3
1 4
2 3

Sample Output 2

1 2 2 1

Sample Input 3

7 4 4
1 2
2 3
2 5
6 7
3 5
4 5
3 4
6 7

Sample Output 3

1 1 2 1 2 2 2
E - Manhattan Compass

Time Limit: 3 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

xy 平面上に N 個の穴があります。i 番目の穴の位置は (x_i,y_i) です。

i 番目の穴と j 番目の穴のマンハッタン距離を d(i,j)(=|x_i-x_j|+|y_i-y_j|) と表します。

あなたはマンハッタンコンパスを持っています。 このコンパスは、常に 2 個の穴を指します。 コンパスが p, q 番目の穴を指している状態と、q, p 番目の穴を指している状態は区別しません。

また、d(p,q)=d(p,r) で、p 番目の穴と q 番目の穴を指しているとき、p 番目の穴と r 番目の穴を指すよう動かすことができます。

はじめ、コンパスは a 番目の穴と b 番目の穴を指しています。 コンパスが指すことのできる穴の組の数を求めてください。

制約

  • 2≦N≦10^5
  • 1≦x_i, y_i≦10^9
  • 1≦a < b≦N
  • i ≠ j のとき (x_i, y_i) ≠ (x_j, y_j)
  • x_i, y_i は整数である

入力

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

N a b
x_1 y_1
:
x_N y_N

出力

コンパスが指すことのできる穴の組の数を出力せよ。

入力例 1

5 1 2
1 1
4 3
6 1
5 5
4 8

出力例 1

4

はじめ、コンパスは 穴 1, 2 を指しています。
d(1,2) = d(1,3) なので、穴 1, 3を指すことができます。
d(1,3) = d(3,4) なので、穴 3, 4を指すことができます。
d(1,2) = d(2,5) なので、穴 2, 5を指すことができます。

他の穴の組でコンパスが指せるものはないため、答えは 4 となります。

入力例 2

6 2 3
1 3
5 3
3 5
8 4
4 7
2 5

出力例 2

4

入力例 3

8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8

出力例 3

7

Score : 900 points

Problem Statement

There are N pinholes on the xy-plane. The i-th pinhole is located at (x_i,y_i).

We will denote the Manhattan distance between the i-th and j-th pinholes as d(i,j)(=|x_i-x_j|+|y_i-y_j|).

You have a peculiar pair of compasses, called Manhattan Compass. This instrument always points at two of the pinholes. The two legs of the compass are indistinguishable, thus we do not distinguish the following two states: the state where the compass points at the p-th and q-th pinholes, and the state where it points at the q-th and p-th pinholes.

When the compass points at the p-th and q-th pinholes and d(p,q)=d(p,r), one of the legs can be moved so that the compass will point at the p-th and r-th pinholes.

Initially, the compass points at the a-th and b-th pinholes. Find the number of the pairs of pinholes that can be pointed by the compass.

Constraints

  • 2≦N≦10^5
  • 1≦x_i, y_i≦10^9
  • 1≦a < b≦N
  • When i ≠ j, (x_i, y_i) ≠ (x_j, y_j)
  • x_i and y_i are integers.

Input

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

N a b
x_1 y_1
:
x_N y_N

Output

Print the number of the pairs of pinholes that can be pointed by the compass.

Sample Input 1

5 1 2
1 1
4 3
6 1
5 5
4 8

Sample Output 1

4

Initially, the compass points at the first and second pinholes.

Since d(1,2) = d(1,3), the compass can be moved so that it will point at the first and third pinholes.

Since d(1,3) = d(3,4), the compass can also point at the third and fourth pinholes.

Since d(1,2) = d(2,5), the compass can also point at the second and fifth pinholes.

No other pairs of pinholes can be pointed by the compass, thus the answer is 4.

Sample Input 2

6 2 3
1 3
5 3
3 5
8 4
4 7
2 5

Sample Output 2

4

Sample Input 3

8 1 2
1 5
4 3
8 2
4 7
8 8
3 3
6 6
4 8

Sample Output 3

7
F - Shuffling

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 900 点

問題文

長さ N の 0、1 からなる文字列 S があります。あなたは、以下の操作を各 1≦i≦M に対し i の昇順に行います。

  • S のうち、左から l_i 文字目から r_i 文字目までの部分文字列を自由な順番で並び替える。

ただし、l_i は非減少です。

M 回の操作後の S としてありうるものの数を 1000000007(= 10^9+7) で割った余りを求めてください。

制約

  • 2≦N≦3000
  • 1≦M≦3000
  • S は0, 1 からなる。
  • S の長さは N と等しい。
  • 1≦l_i < r_i≦N
  • l_i ≦ l_{i+1}

入力

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

N M
S
l_1 r_1
:
l_M r_M

出力

M 回の操作後の S としてありうるものの数を 1000000007 で割った余りを出力してください。

入力例 1

5 2
01001
2 4
3 5

出力例 1

6

1回目の操作後の S としてありうるものは、 01001, 00101, 00011 の 3 つです。
2回目の操作後の S としてありうるものは、 01100, 01010, 01001, 00011, 00101, 00110 の 6 つです。

入力例 2

9 3
110111110
1 4
4 6
6 9

出力例 2

26

入力例 3

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

出力例 3

143

Score : 900 points

Problem Statement

There is a string S of length N consisting of characters 0 and 1. You will perform the following operation for each i = 1, 2, ..., m:

  • Arbitrarily permute the characters within the substring of S starting at the l_i-th character from the left and extending through the r_i-th character.

Here, the sequence l_i is non-decreasing.

How many values are possible for S after the M operations, modulo 1000000007(= 10^9+7)?

Constraints

  • 2≦N≦3000
  • 1≦M≦3000
  • S consists of characters 0 and 1.
  • The length of S equals N.
  • 1≦l_i < r_i≦N
  • l_i ≦ l_{i+1}

Input

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

N M
S
l_1 r_1
:
l_M r_M

Output

Print the number of the possible values for S after the M operations, modulo 1000000007.

Sample Input 1

5 2
01001
2 4
3 5

Sample Output 1

6

After the first operation, S can be one of the following three: 01001, 00101 and 00011.

After the second operation, S can be one of the following six: 01100, 01010, 01001, 00011, 00101 and 00110.

Sample Input 2

9 3
110111110
1 4
4 6
6 9

Sample Output 2

26

Sample Input 3

11 6
00101000110
2 4
2 3
4 7
5 6
6 10
10 11

Sample Output 3

143