実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
高橋くんは、朝食にご飯、味噌汁、サラダを 1 皿ずつ食べます。
高橋くんの家のテーブルは細長いので、 3 皿を横一列に並べました。並べ方は文字列 S によって与えられ、左から i 番目の皿は S_i が R ならご飯、 S_i が M なら味噌汁、 S_i が S ならサラダです。
ご飯の皿が味噌汁の皿より左にあるかどうかを判定してください。
制約
- |S| = 3
- S には
RMSが 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, oneM, and oneS.
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.
実行時間制限: 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
TakahashiorAoki. (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
実行時間制限: 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
実行時間制限: 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
実行時間制限: 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