Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
3 つの整数 A,B,C が与えられます。
三辺の長さがそれぞれ A,B,C であるような正三角形が存在するかどうか判定してください。
制約
- 入力は全て整数である。
- 1 \leq A,B,C \leq 100
入力
入力は以下の形式で標準入力から与えられる。
A B C
出力
三辺の長さが A,B,C であるような正三角形が存在するなら Yes
を、そうでなければ No
を出力せよ。
入力例 1
2 2 2
出力例 1
Yes
- 三辺の長さが 2,2,2 であるような正三角形は存在します。
入力例 2
3 4 5
出力例 2
No
- 三辺の長さが 3,4,5 であるような正三角形は存在しません。
Score : 100 points
Problem Statement
You are given three integers A, B and C.
Determine if there exists an equilateral triangle whose sides have lengths A, B and C.
Constraints
- All values in input are integers.
- 1 \leq A,B,C \leq 100
Input
Input is given from Standard Input in the following format:
A B C
Output
If there exists an equilateral triangle whose sides have lengths A, B and C, print Yes
; otherwise, print No
.
Sample Input 1
2 2 2
Sample Output 1
Yes
- There exists an equilateral triangle whose sides have lengths 2, 2 and 2.
Sample Input 2
3 4 5
Sample Output 2
No
- There is no equilateral triangle whose sides have lengths 3, 4 and 5.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
1 から N までの番号が割り当てられた N 人の人がいます。それぞれの人は赤い帽子か青い帽子のどちらかを被っています。
N 人の帽子の色を表す文字列 s が与えられます。人 i は、s_i が R
ならば赤い帽子を、B
ならば青い帽子を被っています。
赤い帽子を被っている人が青い帽子を被っている人より多いかどうかを判定してください。
制約
- 1 \leq N \leq 100
- |s| = N
- s_i は
R
あるいはB
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
赤い帽子を被っている人が青い帽子を被っている人より多いならば Yes
を、そうでなければ No
を出力せよ。
入力例 1
4 RRBR
出力例 1
Yes
- 赤い帽子を被っている人は 3 人、青い帽子を被っている人は 1 人です。
- 赤い帽子を被っている人の方が青い帽子を被っている人より多いので答えは
Yes
です。
入力例 2
4 BRBR
出力例 2
No
- 赤い帽子を被っている人は 2 人、青い帽子を被っている人は 2 人です。
- 赤い帽子を被っている人と青い帽子を被っている人が同数なので答えは
No
です。
Score : 200 points
Problem Statement
There are N people numbered 1 to N. Each person wears a red hat or a blue hat.
You are given a string s representing the colors of the people. Person i wears a red hat if s_i is R
, and a blue hat if s_i is B
.
Determine if there are more people wearing a red hat than people wearing a blue hat.
Constraints
- 1 \leq N \leq 100
- |s| = N
- s_i is
R
orB
.
Input
Input is given from Standard Input in the following format:
N s
Output
If there are more people wearing a red hat than there are people wearing a blue hat, print Yes
; otherwise, print No
.
Sample Input 1
4 RRBR
Sample Output 1
Yes
- There are three people wearing a red hat, and one person wearing a blue hat.
- Since there are more people wearing a red hat than people wearing a blue hat, the answer is
Yes
.
Sample Input 2
4 BRBR
Sample Output 2
No
- There are two people wearing a red hat, and two people wearing a blue hat.
- Since there are as many people wearing a red hat as people wearing a blue hat, the answer is
No
.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
左から右に向かって 1 から N の番号がついた N 個のマスがあります。 各マスには文字が書かれており、マス i には文字 s_i が書かれています。また、各マスにははじめ 1 体のゴーレムがいます。
すぬけ君は Q 回呪文を唱え、ゴーレムたちを移動させました。
i 番目の呪文は文字 t_i と d_i からなり、d_i は L
か R
のいずれかです。
すぬけ君がこの呪文を唱えると、t_i が書かれた全てのマスについて、そのマスにいる全てのゴーレムが隣接するマスに移動します。移動する方向は d_i が L
ならば左、R
ならば右です。
ただし、マス 1 から左に移動しようとしたゴーレムと、マス N から右に移動しようとしたゴーレムは消滅します。
Q 回の呪文詠唱後に消滅していないゴーレムの総数を求めてください。
制約
- 1 \leq N,Q \leq 2 \times 10^{5}
- |s| = N
- s_i,t_i は英大文字
- d_i は
L
またはR
入力
入力は以下の形式で標準入力から与えられる。
N Q s t_1 d_1 \vdots t_{Q} d_Q
出力
答えを出力せよ。
入力例 1
3 4 ABC A L B L B R A R
出力例 1
2
- はじめ、各マスに 1 体のゴーレムがいます。
- 1 番目の呪文では、マス 1 にいるゴーレムが左に移動しようとし、消滅します。
- 2 番目の呪文では、マス 2 にいるゴーレムが左に移動します。
- 3 番目の呪文では、移動するゴーレムはいません。
- 4 番目の呪文では、マス 1 にいるゴーレムが右に移動します。
- 4 回の呪文詠唱後、マス 2 に 1 体、マス 3 に 1 体のゴーレムがいるため、消滅していないゴーレムは 2 体です。
入力例 2
8 3 AABCBDBA A L B R A R
出力例 2
5
- 3 回の呪文詠唱後、マス 2 に 1 体、マス 4 に 2 体、マス 6 に 2 体のゴーレムがいるため、消滅していないゴーレムは 5 体です。
- 1 つの呪文で複数のゴーレムが移動しうることに注意してください。
入力例 3
10 15 SNCZWRCEWB B R R R E R W R Z L S R Q L W L B R C L A L N L E R Z L S L
出力例 3
3
Score : 500 points
Problem Statement
There are N squares numbered 1 to N from left to right. Each square has a character written on it, and Square i has a letter s_i. Besides, there is initially one golem on each square.
Snuke cast Q spells to move the golems.
The i-th spell consisted of two characters t_i and d_i, where d_i is L
or R
.
When Snuke cast this spell, for each square with the character t_i, all golems on that square moved to the square adjacent to the left if d_i is L
, and moved to the square adjacent to the right if d_i is R
.
However, when a golem tried to move left from Square 1 or move right from Square N, it disappeared.
Find the number of golems remaining after Snuke cast the Q spells.
Constraints
- 1 \leq N,Q \leq 2 \times 10^{5}
- |s| = N
- s_i and t_i are uppercase English letters.
- d_i is
L
orR
.
Input
Input is given from Standard Input in the following format:
N Q s t_1 d_1 \vdots t_{Q} d_Q
Output
Print the answer.
Sample Input 1
3 4 ABC A L B L B R A R
Sample Output 1
2
- Initially, there is one golem on each square.
- In the first spell, the golem on Square 1 tries to move left and disappears.
- In the second spell, the golem on Square 2 moves left.
- In the third spell, no golem moves.
- In the fourth spell, the golem on Square 1 moves right.
- After the four spells are cast, there is one golem on Square 2 and one golem on Square 3, for a total of two golems remaining.
Sample Input 2
8 3 AABCBDBA A L B R A R
Sample Output 2
5
- After the three spells are cast, there is one golem on Square 2, two golems on Square 4 and two golems on Square 6, for a total of five golems remaining.
- Note that a single spell may move multiple golems.
Sample Input 3
10 15 SNCZWRCEWB B R R R E R W R Z L S R Q L W L B R C L A L N L E R Z L S L
Sample Output 3
3
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
すぬけ君は黒板と N 個の整数からなる集合 S を持っています。 S の i 番目の要素は S_i です。
すぬけ君は黒板に整数 X を書いたのち、以下の操作を N 回行います。
- S から要素を 1 つ選んで取り除く。
- その後、現在黒板に書かれた数を x、S から取り除かれた整数を y として、黒板に書かれた数を x \bmod {y} に書き換える。
S から要素を取り除く順序は N! 通りありえます。 それぞれの場合について、N 回の操作後に黒板に書かれている数を求め、その総和を 10^{9}+7 で割ったあまりを求めてください。
制約
- 入力は全て整数である。
- 1 \leq N \leq 200
- 1 \leq S_i, X \leq 10^{5}
- S_i たちは相異なる。
入力
入力は以下の形式で標準入力から与えられる。
N X S_1 S_2 \ldots S_{N}
出力
答えを出力せよ。
入力例 1
2 19 3 7
出力例 1
3
- S から数を取り除く順序は 2 通りあります。
- 3,7 の順で取り除いたとき、黒板に書かれた数は 19 \rightarrow 1 \rightarrow 1 と変化します。
- 7,3 の順で取り除いたとき、黒板に書かれた数は 19 \rightarrow 5 \rightarrow 2 と変化します。
- これらの総和である 3 を出力してください。
入力例 2
5 82 22 11 6 5 13
出力例 2
288
入力例 3
10 100000 50000 50001 50002 50003 50004 50005 50006 50007 50008 50009
出力例 3
279669259
- 総和を 10^{9}+7 で割ったあまりを求めるのを忘れずに。
Score : 600 points
Problem Statement
Snuke has a blackboard and a set S consisting of N integers. The i-th element in S is S_i.
He wrote an integer X on the blackboard, then performed the following operation N times:
- Choose one element from S and remove it.
- Let x be the number written on the blackboard now, and y be the integer removed from S. Replace the number on the blackboard with x \bmod {y}.
There are N! possible orders in which the elements are removed from S. For each of them, find the number that would be written on the blackboard after the N operations, and compute the sum of all those N! numbers modulo 10^{9}+7.
Constraints
- All values in input are integers.
- 1 \leq N \leq 200
- 1 \leq S_i, X \leq 10^{5}
- S_i are pairwise distinct.
Input
Input is given from Standard Input in the following format:
N X S_1 S_2 \ldots S_{N}
Output
Print the answer.
Sample Input 1
2 19 3 7
Sample Output 1
3
- There are two possible orders in which we remove the numbers from S.
- If we remove 3 and 7 in this order, the number on the blackboard changes as follows: 19 \rightarrow 1 \rightarrow 1.
- If we remove 7 and 3 in this order, the number on the blackboard changes as follows: 19 \rightarrow 5 \rightarrow 2.
- The output should be the sum of these: 3.
Sample Input 2
5 82 22 11 6 5 13
Sample Output 2
288
Sample Input 3
10 100000 50000 50001 50002 50003 50004 50005 50006 50007 50008 50009
Sample Output 3
279669259
- Be sure to compute the sum modulo 10^{9}+7.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
今日のすぬけ君のおやつは B 個の黒いチョコレートと W 個の白いチョコレートです。
すぬけ君は以下の手続きをチョコレートがなくなるまで繰り返します。
- 黒か白を等確率で選び、選んだ色のチョコレートが存在するなら 1 つ食べる。
1 以上 B+W 以下の各整数 i について、すぬけ君が i 番目に食べたチョコレートの色が黒である確率を求めてください。 これらの確率は有理数となることが示せます。これらを注記で述べるように modulo 10^{9}+7 で出力してください。
注記
有理数を出力する際は、まずその有理数を分数 \frac{y}{x} として表してください。ここで、x, y は整数であり、x は 10^9 + 7 で割り切れてはなりません (この問題の制約下で、そのような表現は必ず可能です)。そして、xz \equiv y \pmod{10^9 + 7} を満たすような 0 以上 10^9 + 6 以下の唯一の整数 z を出力してください。
制約
- 入力は全て整数である。
- 1 \leq B,W \leq 10^{5}
入力
入力は以下の形式で標準入力から与えられる。
B W
出力
答えを B+W 行に出力せよ。i 行目ではすぬけ君が i 番目に食べたチョコレートの色が黒である確率を注記で述べるように modulo 10^{9}+7 で出力せよ。
入力例 1
2 1
出力例 1
500000004 750000006 750000006
- チョコレートを食べる順序としてありうるものは以下の 3 通りで、そのような食べ方が生じる確率はそれぞれ \frac{1}{2}, \frac{1}{4}, \frac{1}{4} です。
- 白、黒、黒
- 黒、白、黒
- 黒、黒、白
- よって、1 番目、2 番目、3 番目に食べたチョコレートが黒である確率はそれぞれ \frac{1}{2},\frac{3}{4},\frac{3}{4} です。
入力例 2
3 2
出力例 2
500000004 500000004 625000005 187500002 187500002
- それぞれ \frac{1}{2},\frac{1}{2},\frac{5}{8},\frac{11}{16},\frac{11}{16} です。
入力例 3
6 9
出力例 3
500000004 500000004 500000004 500000004 500000004 500000004 929687507 218750002 224609377 303710940 633300786 694091802 172485353 411682132 411682132
Score : 700 points
Problem Statement
Today, Snuke will eat B pieces of black chocolate and W pieces of white chocolate for an afternoon snack.
He will repeat the following procedure until there is no piece left:
- Choose black or white with equal probability, and eat a piece of that color if it exists.
For each integer i from 1 to B+W (inclusive), find the probability that the color of the i-th piece to be eaten is black. It can be shown that these probabilities are rational, and we ask you to print them modulo 10^9 + 7, as described in Notes.
Notes
When you print a rational number, first write it as a fraction \frac{y}{x}, where x, y are integers and x is not divisible by 10^9 + 7 (under the constraints of the problem, such representation is always possible). Then, you need to print the only integer z between 0 and 10^9 + 6, inclusive, that satisfies xz \equiv y \pmod{10^9 + 7}.
Constraints
- All values in input are integers.
- 1 \leq B,W \leq 10^{5}
Input
Input is given from Standard Input in the following format:
B W
Output
Print the answers in B+W lines. In the i-th line, print the probability that the color of the i-th piece to be eaten is black, modulo 10^{9}+7.
Sample Input 1
2 1
Sample Output 1
500000004 750000006 750000006
- There are three possible orders in which Snuke eats the pieces:
- white, black, black
- black, white, black
- black, black, white
- with probabilities \frac{1}{2}, \frac{1}{4}, \frac{1}{4}, respectively. Thus, the probabilities of eating a black piece first, second and third are \frac{1}{2},\frac{3}{4} and \frac{3}{4}, respectively.
Sample Input 2
3 2
Sample Output 2
500000004 500000004 625000005 187500002 187500002
- They are \frac{1}{2},\frac{1}{2},\frac{5}{8},\frac{11}{16} and \frac{11}{16}, respectively.
Sample Input 3
6 9
Sample Output 3
500000004 500000004 500000004 500000004 500000004 500000004 929687507 218750002 224609377 303710940 633300786 694091802 172485353 411682132 411682132
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 1200 点
問題文
AtCoder 共和国の首都タカハ市には,東西に伸びる道路が N 本,南北に伸びる道路が M 本あり,これ以外の道路はありません. 北から i 本目の東西方向の道路と,西から j 本目の南北方向の道路は,交差点 (i, j) で交わっています. 東西方向の道路同士,南北方向の道路同士が交わることはありません. また,同じ方向の隣り合う道路の間は距離 1 ずつ離れています.
それぞれの道路は一方通行で,片方の向きにのみ通行可能です.各道路の通行可能な方向は,長さ N の文字列 S,長さ M の文字列 T を用いて,次のようになっています:
- S の i 文字目が
W
のとき,北から i 本目の東西方向の道路は,西向きにのみ通行可能. - S の i 文字目が
E
のとき,北から i 本目の東西方向の道路は,東向きにのみ通行可能. - T の j 文字目が
N
のとき,西から j 本目の南北方向の道路は,北向きにのみ通行可能. - T の j 文字目が
S
のとき,西から j 本目の南北方向の道路は,南向きにのみ通行可能.
次のような形式の Q 個の質問に答えてください.
- i 番目の質問では,a_i, b_i, c_i, d_i が与えられる.このとき,交差点 (a_i, b_i) から (c_i, d_i) まで,道路のみを通行して移動するときの,最小の移動距離はいくらか?
制約
- 2 \leq N \leq 100000
- 2 \leq M \leq 100000
- 2 \leq Q \leq 200000
- |S| = N
- S は
W
,E
のみからなる - |T| = M
- T は
N
,S
のみからなる - 1 \leq a_i \leq N
- 1 \leq b_i \leq M
- 1 \leq c_i \leq N
- 1 \leq d_i \leq M
- (a_i, b_i) \neq (c_i, d_i)
入力
入力は以下の形式で標準入力から与えられる.
N M Q S T a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 : a_Q b_Q c_Q d_Q
出力
i 行目には,i 番目の質問に対する答えを出力せよ.ただし,交差点 (a_i, b_i) から (c_i, d_i) まで,道路のみを通行して移動することが不可能なときは,代わりに -1
を出力せよ.
入力例 1
4 5 4 EEWW NSNNS 4 1 1 4 1 3 1 2 4 2 3 2 3 3 3 5
出力例 1
6 11 5 4
各道路の通行可能な方向は下図の通りです(上向きを北とします):
4 個の質問それぞれについて,最小の移動距離を達成する経路の例は次の通りです:
入力例 2
3 3 2 EEE SSS 1 1 3 3 3 3 1 1
出力例 2
4 -1
移動が不可能な場合もあります.
入力例 3
9 7 10 EEEEEWEWW NSSSNSN 4 6 9 2 3 7 6 7 7 5 3 5 1 1 8 1 4 3 5 4 7 4 6 4 2 5 8 6 6 6 2 7 2 4 7 5 7 2 9 7
出力例 3
9 -1 4 9 2 3 7 7 6 -1
Score : 1200 points
Problem Statement
In Takaha-shi, the capital of Republic of AtCoder, there are N roads extending east and west, and M roads extending north and south. There are no other roads. The i-th east-west road from the north and the j-th north-south road from the west cross at the intersection (i, j). Two east-west roads do not cross, nor do two north-south roads. The distance between two adjacent roads in the same direction is 1.
Each road is one-way; one can only walk in one direction. The permitted direction for each road is described by a string S of length N and a string T of length M, as follows:
- If the i-th character in S is
W
, one can only walk westward along the i-th east-west road from the north; - If the i-th character in S is
E
, one can only walk eastward along the i-th east-west road from the north; - If the i-th character in T is
N
, one can only walk northward along the i-th north-south road from the west; - If the i-th character in T is
S
, one can only walk southward along the i-th south-west road from the west.
Process the following Q queries:
- In the i-th query, a_i, b_i, c_i and d_i are given. What is the minimum distance to travel to reach the intersection (c_i, d_i) from the intersection (a_i, b_i) by walking along the roads?
Constraints
- 2 \leq N \leq 100000
- 2 \leq M \leq 100000
- 2 \leq Q \leq 200000
- |S| = N
- S consists of
W
andE
. - |T| = M
- T consists of
N
andS
. - 1 \leq a_i \leq N
- 1 \leq b_i \leq M
- 1 \leq c_i \leq N
- 1 \leq d_i \leq M
- (a_i, b_i) \neq (c_i, d_i)
Input
Input is given from Standard Input in the following format:
N M Q S T a_1 b_1 c_1 d_1 a_2 b_2 c_2 d_2 : a_Q b_Q c_Q d_Q
Output
In the i-th line, print the response to the i-th query. If the intersection (c_i, d_i) cannot be reached from the intersection (a_i, b_i) by walking along the roads, print -1
instead.
Sample Input 1
4 5 4 EEWW NSNNS 4 1 1 4 1 3 1 2 4 2 3 2 3 3 3 5
Sample Output 1
6 11 5 4
The permitted direction for each road is shown in the following figure (north upward):
For each of the four queries, a route that achieves the minimum travel distance is as follows:
Sample Input 2
3 3 2 EEE SSS 1 1 3 3 3 3 1 1
Sample Output 2
4 -1
The travel may be impossible.
Sample Input 3
9 7 10 EEEEEWEWW NSSSNSN 4 6 9 2 3 7 6 7 7 5 3 5 1 1 8 1 4 3 5 4 7 4 6 4 2 5 8 6 6 6 2 7 2 4 7 5 7 2 9 7
Sample Output 3
9 -1 4 9 2 3 7 7 6 -1