A - A Healthy Breakfast

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

配点 : 100 点

問題文

高橋くんは、朝食にご飯、味噌汁、サラダを 1 皿ずつ食べます。

高橋くんの家のテーブルは細長いので、 3 皿を横一列に並べました。並べ方は文字列 S によって与えられ、左から i 番目の皿は S_i が R ならご飯、 S_i が M なら味噌汁、 S_i が S ならサラダです。

ご飯の皿が味噌汁の皿より左にあるかどうかを判定してください。

制約

  • |S| = 3
  • S には R M S が 1 文字ずつ含まれる

入力

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

S

出力

ご飯の皿が味噌汁の皿より左にあれば Yes 、そうでなければ No を出力してください。


入力例 1

RSM

出力例 1

Yes

ご飯の皿は左から 1 番目にあり、味噌汁の皿は左から 3 番目にあります。ご飯の皿の方が左にあるので、 Yes を出力します。


入力例 2

SMR

出力例 2

No

左から順に、サラダの皿、味噌汁の皿、ご飯の皿と並んでいます。

Score : 100 points

Problem Statement

Takahashi eats three plates for breakfast: rice, miso soup, and salad.

His table is long and narrow, so he arranged the three plates in a row. The arrangement is given by a string S, where the i-th plate from the left is rice if S_i is R, miso soup if S_i is M, and salad if S_i is S.

Determine whether the plate of rice is to the left of the plate of miso soup.

Constraints

  • |S| = 3
  • S contains one R, one M, and one S.

Input

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

S

Output

Print Yes if the plate of rice is to the left of the plate of miso soup, and No otherwise.


Sample Input 1

RSM

Sample Output 1

Yes

The plate of rice is at the 1st position from the left, and the plate of miso soup is at the 3rd position from the left. Since the plate of rice is to the left, print Yes.


Sample Input 2

SMR

Sample Output 2

No

The plates are arranged as salad, miso soup, and rice from left to right.

B - Count Takahashi

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

配点 : 100 点

問題文

文字列が N 個与えられます。

i 番目 (1\leq i\leq N) に与えられる文字列 S _ i は Takahashi か Aoki のどちらかと等しいです。

S _ i が Takahashi と等しい i がいくつあるか求めてください。

制約

  • 1\leq N\leq 100
  • N は整数
  • S _ i は Takahashi か Aoki のいずれか (1\leq i\leq N)

入力

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

N
S _ 1
S _ 2
\vdots
S _ N

出力

S _ i が Takahashi と等しい i の個数を整数として一行に出力せよ。


入力例 1

3
Aoki
Takahashi
Takahashi

出力例 1

2

S _ 2,S _ 3 の 2 つが Takahashi と等しく、S _ 1 はそうではありません。

よって、2 を出力してください。


入力例 2

2
Aoki
Aoki

出力例 2

0

Takahashi と等しい S _ i が存在しないこともあります。


入力例 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

出力例 3

7

Score : 100 points

Problem Statement

You are given N strings.

The i-th string S_i (1 \leq i \leq N) is either Takahashi or Aoki.

How many i are there such that S_i is equal to Takahashi?

Constraints

  • 1 \leq N \leq 100
  • N is an integer.
  • Each S_i is Takahashi or Aoki. (1 \leq i \leq N)

Input

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

N
S_1
S_2
\vdots
S_N

Output

Print the count of i such that S_i is equal to Takahashi as an integer in a single line.


Sample Input 1

3
Aoki
Takahashi
Takahashi

Sample Output 1

2

S_2 and S_3 are equal to Takahashi, while S_1 is not.

Therefore, print 2.


Sample Input 2

2
Aoki
Aoki

Sample Output 2

0

It is possible that no S_i is equal to Takahashi.


Sample Input 3

20
Aoki
Takahashi
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi
Aoki
Aoki
Aoki
Takahashi
Takahashi
Aoki
Takahashi
Aoki
Aoki
Aoki
Aoki
Takahashi

Sample Output 3

7
C - Cat

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

配点 : 200 点

問題文

長さ N の文字列 S が与えられます。

S に連続して含まれる na を全て nya に置き換えて得られる文字列を答えてください。

制約

  • N は 1 以上 1000 以下の整数
  • S は英小文字からなる長さ N の文字列

入力

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

N
S

出力

答えを出力せよ。


入力例 1

4
naan

出力例 1

nyaan

naan に連続して含まれる na を全て nya に置き換えて得られる文字列は nyaan です。


入力例 2

4
near

出力例 2

near

S に na が連続して含まれないこともあります。


入力例 3

8
national

出力例 3

nyationyal

Score : 200 points

Problem Statement

You are given a string S of length N.

Find the string obtained by replacing all contiguous occurrences of na in S with nya.

Constraints

  • N is an integer between 1 and 1000, inclusive.
  • S is a string of length N consisting of lowercase English letters.

Input

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

N
S

Output

Print the answer.


Sample Input 1

4
naan

Sample Output 1

nyaan

Replacing all contiguous occurrences of na in naan with nya results in the string nyaan.


Sample Input 2

4
near

Sample Output 2

near

S may not contain a contiguous na.


Sample Input 3

8
national

Sample Output 3

nyationyal
D - Traveling Takahashi Problem

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

配点 : 150 点

問題文

2 次元座標平面の原点に高橋くんがいます。

高橋くんが座標平面上の点 (a,b) から点 (c,d) に移動するには \sqrt{(a-c)^2+(b-d)^2} のコストがかかります。

高橋くんが原点からスタートし N 個の点 (X_1,Y_1),\ldots,(X_N,Y_N) へこの順に移動したのち原点に戻るときの、コストの総和を求めてください。

制約

  • 1 \leq N \leq 2\times 10^5
  • -10^9 \leq X_i,Y_i \leq 10^9
  • 入力は全て整数である

入力

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

N
X_1 Y_1
\vdots
X_N Y_N

出力

答えを出力せよ。
真の値との相対誤差または絶対誤差が 10^{-6} 以下であれば正解とみなされる。


入力例 1

2
1 2
-1 0

出力例 1

6.06449510224597979401

移動は次の 3 行程からなります。

  • (0,0) から (1,2) に移動する。\sqrt{(0-1)^2+(0-2)^2}=\sqrt{5}=2.236067977... のコストがかかる
  • (1,2) から (-1,0) に移動する。\sqrt{(1-(-1))^2+(2-0)^2}=\sqrt{8}=2.828427124... のコストがかかる
  • (-1,0) から (0,0) に移動する。\sqrt{(-1-0)^2+(0-0)^2}=\sqrt{1}=1 のコストがかかる

コストの総和は 6.064495102... となります。


入力例 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

出力例 2

384694.57587932075868509383

入力例 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

出力例 3

1414213.56237309504880168872

Score : 150 points

Problem Statement

Takahashi is at the origin on a two-dimensional coordinate plane.

The cost for him to move from point (a, b) to point (c, d) is \sqrt{(a - c)^2 + (b - d)^2}.

Find the total cost when he starts at the origin, visits N points (X_1, Y_1), \ldots, (X_N, Y_N) in this order, and then returns to the origin.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • -10^9 \leq X_i, Y_i \leq 10^9
  • All input values are integers.

Input

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

N
X_1 Y_1
\vdots
X_N Y_N

Output

Print the answer.
Your output will be considered correct if its absolute or relative error from the true value is at most 10^{-6}.


Sample Input 1

2
1 2
-1 0

Sample Output 1

6.06449510224597979401

The journey consists of the following three steps:

  • Move from (0, 0) to (1, 2). The cost is \sqrt{(0 - 1)^2 + (0 - 2)^2} = \sqrt{5} = 2.236067977....
  • Move from (1, 2) to (-1, 0). The cost is \sqrt{(1 - (-1))^2 + (2 - 0)^2} = \sqrt{8} = 2.828427124....
  • Move from (-1, 0) to (0, 0). The cost is \sqrt{(-1 - 0)^2 + (0 - 0)^2} = \sqrt{1} = 1.

The total cost is 6.064495102....


Sample Input 2

7
-14142 13562
-17320 50807
-22360 67977
24494 89742
-26457 51311
28284 27124
31622 77660

Sample Output 2

384694.57587932075868509383

Sample Input 3

5
-100000 100000
100000 -100000
-100000 100000
100000 -100000
-100000 100000

Sample Output 3

1414213.56237309504880168872
E - Peer Review

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

配点 : 300 点

問題文

N 人の研究者がおり、研究者には 1, 2, \ldots, N の番号が付けられています。

研究者の間には M 個の利害関係があり、i = 1, 2, \ldots, M に対して研究者 A_i と研究者 B_i は互いに利害関係にあります。

論文の査読者は、その論文の著者とは異なり、著者と利害関係にない相異なる 3 人の研究者である必要があります。

i = 1, 2, \ldots, N について以下の問題を解いてください。

  • 研究者 i が著者である論文の査読者の 3 人組として考えられるものは何通りあるか求めよ。

ただし、すべての論文は単著であるものとします。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • i \neq j のとき (A_i, B_i) \neq (A_j, B_j)
  • i \neq j のとき (A_i, B_i) \neq (B_j, A_j)
  • 入力される値はすべて整数

入力

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

出力

i = 1, 2, \ldots, N に対する答えをこの順に空白区切りで出力せよ。


入力例 1

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

出力例 1

0 1 0 4 4 10

以下、研究者の番号の集合により研究者の集合を表します。

  • 研究者 1 が著者である論文の査読者の 3 人組として考えられるものはありません。

  • 研究者 2 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 4, 5, 6 \rbrace の 1 通りです。

  • 研究者 3 が著者である論文の査読者の 3 人組として考えられるものはありません。

  • 研究者 4 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace の 4 通りです。

  • 研究者 5 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace の 4 通りです。

  • 研究者 6 が著者である論文の査読者の 3 人組として考えられるものは \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace の 10 通りです。


入力例 2

7 3
1 2
3 4
5 6

出力例 2

10 10 10 10 10 10 20

入力例 3

6 9
3 6
2 5
2 3
4 3
1 5
6 2
3 1
5 3
2 4

出力例 3

1 0 0 1 0 1

Score : 300 points

Problem Statement

There are N researchers, numbered 1, 2, \ldots, N.

There are M conflicts of interest among the researchers; for i = 1, 2, \ldots, M, researchers A_i and B_i have a conflict of interest with each other.

The reviewers of a paper must be three distinct researchers who are different from the author of the paper and have no conflict of interest with the author.

For i = 1, 2, \ldots, N, solve the following problem:

  • Find the number of possible triples of reviewers for a paper authored by researcher i.

Assume that all papers are single-authored.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 0 \leq M \leq 2 \times 10^5
  • 1 \leq A_i, B_i \leq N
  • A_i \neq B_i
  • (A_i, B_i) \neq (A_j, B_j) if i \neq j.
  • (A_i, B_i) \neq (B_j, A_j) if i \neq j.
  • All input values are integers.

Input

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

N M
A_1 B_1
A_2 B_2
\vdots
A_M B_M

Output

Print the answers for i = 1, 2, \ldots, N in this order, separated by spaces.


Sample Input 1

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

Sample Output 1

0 1 0 4 4 10

Below, we represent a set of researchers by the set of their numbers.

  • There are no possible triples of reviewers for a paper authored by researcher 1.

  • The possible triple of reviewers for a paper authored by researcher 2 is \lbrace 4, 5, 6 \rbrace, which is 1 triple.

  • There are no possible triples of reviewers for a paper authored by researcher 3.

  • The possible triples of reviewers for a paper authored by researcher 4 are \lbrace 2, 3, 5 \rbrace, \lbrace 2, 3, 6 \rbrace, \lbrace 2, 5, 6 \rbrace, \lbrace 3, 5, 6 \rbrace, which is 4 triples.

  • The possible triples of reviewers for a paper authored by researcher 5 are \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 6 \rbrace, \lbrace 1, 4, 6 \rbrace, \lbrace 2, 4, 6 \rbrace, which is 4 triples.

  • The possible triples of reviewers for a paper authored by researcher 6 are \lbrace 1, 2, 3 \rbrace, \lbrace 1, 2, 4 \rbrace, \lbrace 1, 2, 5 \rbrace, \lbrace 1, 3, 4 \rbrace, \lbrace 1, 3, 5 \rbrace, \lbrace 1, 4, 5 \rbrace, \lbrace 2, 3, 4 \rbrace, \lbrace 2, 3, 5 \rbrace, \lbrace 2, 4, 5 \rbrace, \lbrace 3, 4, 5 \rbrace, which is 10 triples.


Sample Input 2

7 3
1 2
3 4
5 6

Sample Output 2

10 10 10 10 10 10 20

Sample Input 3

6 9
3 6
2 5
2 3
4 3
1 5
6 2
3 1
5 3
2 4

Sample Output 3

1 0 0 1 0 1