Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
整数 S,P が与えられます。 N+M=S,N \times M =P を満たすような正の整数の組 (N,M) はありますか?
制約
- 与えられる入力は全て整数
- 1 \leq S,P \leq 10^{12}
入力
入力は以下の形式で標準入力から与えられる。
S P
出力
N+M=S,N \times M =P を満たすような正の整数の組 (N,M) があるなら Yes
、そうでないなら No
を出力せよ。
入力例 1
3 2
出力例 1
Yes
- 例えば N=1,M=2 のとき、N+M=3,N \times M =2 となります。
入力例 2
1000000000000 1
出力例 2
No
- そのような (N,M) は存在しません。
Score : 300 points
Problem Statement
Given are integers S and P. Is there a pair of positive integers (N,M) such that N + M = S and N \times M = P?
Constraints
- All values in input are integers.
- 1 \leq S,P \leq 10^{12}
Input
Input is given from Standard Input in the following format:
S P
Output
If there is a pair of positive integers (N,M) such that N + M = S and N \times M = P, print Yes
; otherwise, print No
.
Sample Input 1
3 2
Sample Output 1
Yes
- For example, we have N+M=3 and N \times M =2 for N=1,M=2.
Sample Input 2
1000000000000 1
Sample Output 2
No
- There is no such pair (N,M).
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の英小文字のみからなる文字列 s が与えられます。
すぬけ君は s から fox
という部分文字列を 1 つ選んで取り除き、その前後の部分を連結する、という操作を何度でも行うことができます。
すぬけ君が操作を何度か行ったあと、s の長さは最小でいくつになりえますか?
制約
- 1 \leq N \leq 2 \times 10^{5}
- s は英小文字のみからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N s
出力
すぬけ君が操作を何度か行ったあとの s の長さとしてありうる値の最小値を出力せよ。
入力例 1
6 icefox
出力例 1
3
icefox
の末尾fox
を取り除くことで s をice
にすることができます。
入力例 2
7 firebox
出力例 2
7
fox
という部分文字列が存在しません。
入力例 3
48 ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo
出力例 3
27
Score : 400 points
Problem Statement
Given is a string S of length N consisting of lowercase English letters.
Snuke can do this operation any number of times: remove fox
occurring as a substring from s and concatenate the remaining parts of s.
What is the minimum possible length of s after some number of operations by Snuke?
Constraints
- 1 \leq N \leq 2 \times 10^{5}
- s is a string of length N consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N s
Print the minimum possible length of s after some number of operations by Snuke.
Sample Input 1
6 icefox
Sample Output 1
3
- By removing the
fox
at the end oficefox
, we can turn s intoice
.
Sample Input 2
7 firebox
Sample Output 2
7
fox
does not occur as a substring.
Sample Input 3
48 ffoxoxuvgjyzmehmopfohrupffoxoxfofofoxffoxoxejffo
Sample Output 3
27
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
1 から N の番号がついた N 個の頂点と 1 から M の番号がついた M 本の辺からなる連結な無向グラフが与えられます。 このグラフに多重辺は存在するかもしれませんが、自己ループはありません。
このグラフのそれぞれの辺には 1 以上 N 以下の整数で表されるラベルがついています。 辺 i はラベル c_i がついており、頂点 u_i,v_i を双方向につなぐ辺です。
すぬけ君はそれぞれの頂点に 1 以上 N 以下の整数を書き込んだのち(頂点に書き込まれた整数に重複があっても構いません)、以下の条件を満たす辺のみを残してそれ以外の辺を取り除くことにしました。
条件:辺の両端の頂点に書き込まれた整数を x,y として、x,y のいずれか一方のみが辺についたラベルと等しい
上記の条件を満たさない辺を取り除いたあとのグラフも連結のままであるような頂点への整数の書き込み方を よい書き込み方 と呼びます。よい書き込み方が存在するかどうかを判定し、存在するならばその一例を示してください。
制約
- 2 \leq N \leq 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq u_i,v_i,c_i \leq N
- 与えられるグラフは連結
- 与えられるグラフに自己ループはない
入力
入力は以下の形式で標準入力から与えられる。
N M u_1 v_1 c_1 \vdots u_M v_M c_M
出力
よい書き込み方が存在しないならば No
を出力せよ。
存在する場合、N 行出力せよ。i 行目には頂点 i に書き込む整数を出力せよ。
この書き込み方がよい書き込み方ならば正解となる。
入力例 1
3 4 1 2 1 2 3 2 3 1 3 1 3 1
出力例 1
1 2 1
- 頂点 1,2,3 にそれぞれ 1,2,1 を書き込みます。
- 辺 1 は頂点 1,2 をつないでおり、ラベルが 1 です。
- 頂点 1 に書き込まれた整数のみが辺についたラベルと等しいため辺 1 は取り除かれません。
- 辺 2 は頂点 2,3 をつないでおり、ラベルが 2 です。
- 頂点 2 に書き込まれた整数のみが辺についたラベルと等しいため辺 2 は取り除かれません。
- 辺 3 は頂点 1,3 をつないでおり、ラベルが 3 です。
- どちらの頂点に書き込まれた整数も辺についたラベルと異なるため辺 3 は取り除かれます。
- 辺 4 は頂点 1,3 をつないでおり、ラベルが 1 です。
- どちらの頂点に書き込まれた整数も辺についたラベルと等しいため辺 4 は取り除かれます。
- 辺 3,4 が取り除かれたあともグラフは連結なので、この書き込み方はよい書き込み方です。
Score : 500 points
Problem Statement
Given is an undirected connected graph with N vertices numbered 1 to N, and M edges numbered 1 to M. The given graph may contain multi-edges but not self loops.
Each edge has an integer label between 1 and N (inclusive). Edge i has a label c_i, and it connects Vertex u_i and v_i bidirectionally.
Snuke will write an integer between 1 and N (inclusive) on each vertex (multiple vertices may have the same integer written on them) and then keep only the edges satisfying the condition below, removing the other edges.
Condition: Let x and y be the integers written on the vertices that are the endpoints of the edge. Exactly one of x and y equals the label of the edge.
We call a way of writing integers on the vertices good if (and only if) the graph is still connected after removing the edges not satisfying the condition above. Determine whether a good way of writing integers exists, and present one such way if it exists.
Constraints
- 2 \leq N \leq 10^5
- N-1 \leq M \leq 2 \times 10^5
- 1 \leq u_i,v_i,c_i \leq N
- The given graph is connected and has no self-loops.
Input
Input is given from Standard Input in the following format:
N M u_1 v_1 c_1 \vdots u_M v_M c_M
Output
If there is no good way of writing integers, print No
.
Otherwise, print N lines. The i-th line should contain the integer written on Vertex i.
Any good way of writing integers will be accepted.
Sample Input 1
3 4 1 2 1 2 3 2 3 1 3 1 3 1
Sample Output 1
1 2 1
- We write 1, 2, and 1 on Vertex 1, 2, and 3, respectively.
- Edge 1 connects Vertex 1 and 2, and its label is 1.
- Only the integer written on Vertex 1 equals the label, so this edge will not get removed.
- Edge 2 connects Vertex 2 and 3, and its label is 2.
- Only the integer written on Vertex 2 equals the label, so this edge will not be removed.
- Edge 3 connects Vertex 1 and 3, and its label is 3.
- Both integers written on the vertices differ from the label, so this edge will be removed.
- Edge 4 connects Vertex 1 and 3, and its label is 1.
- Both integers written on the vertices equal the label, so this edge will be removed.
- After Edge 3 and 4 are removed, the graph will still be connected, so this is a good way of writing integers.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 N と 4 つの文字 c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}} が与えられます。
ここで、与えられる 4 つの文字はいずれも A
か B
であることが保証されます。
すぬけ君は文字列 s を持っています。
s ははじめ AB
です。
s の長さを |s| と書くことにします。 すぬけ君は以下の 4 種類の操作を任意の順序で 0 回以上行うことができます。
- 1 \leq i < |s|, s_{i} =
A
, s_{i+1} =A
なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{AA}} を挿入する。 - 1 \leq i < |s|,s_{i} =
A
, s_{i+1} =B
なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{AB}} を挿入する。 - 1 \leq i < |s|,s_{i} =
B
, s_{i+1} =A
なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{BA}} を挿入する。 - 1 \leq i < |s|,s_{i} =
B
, s_{i+1} =B
なる i を選んで、s の i 文字目と i+1 文字目の間に c_{\mathrm{BB}} を挿入する。
s の長さが N になるまで操作を行ったあとの s としてありうる文字列の個数を 10^9+7 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 1000
- c_{\mathrm{AA}},c_{\mathrm{AB}},c_{\mathrm{BA}},c_{\mathrm{BB}} は
A
かB
入力
入力は以下の形式で標準入力から与えられる。
N c_{\mathrm{AA}} c_{\mathrm{AB}} c_{\mathrm{BA}} c_{\mathrm{BB}}
出力
s の長さが N になるまで操作を行ったあとの s としてありうる文字列の個数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
4 A B B A
出力例 1
2
- s としてありうる文字列は
ABAB
とABBB
の 2 通りです。
入力例 2
1000 B B B B
出力例 2
1
- s としてありうる文字列は 1 通りです。
Score : 600 points
Problem Statement
Given are an integer N and four characters c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}}.
Here, it is guaranteed that each of those four characters is A
or B
.
Snuke has a string s, which is initially AB
.
Let |s| denote the length of s. Snuke can do the four kinds of operations below zero or more times in any order:
- Choose i such that 1 \leq i < |s|, s_{i} =
A
, s_{i+1} =A
and insert c_{\mathrm{AA}} between the i-th and (i+1)-th characters of s. - Choose i such that 1 \leq i < |s|, s_{i} =
A
, s_{i+1} =B
and insert c_{\mathrm{AB}} between the i-th and (i+1)-th characters of s. - Choose i such that 1 \leq i < |s|, s_{i} =
B
, s_{i+1} =A
and insert c_{\mathrm{BA}} between the i-th and (i+1)-th characters of s. - Choose i such that 1 \leq i < |s|, s_{i} =
B
, s_{i+1} =B
and insert c_{\mathrm{BB}} between the i-th and (i+1)-th characters of s.
Find the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.
Constraints
- 2 \leq N \leq 1000
- Each of c_{\mathrm{AA}}, c_{\mathrm{AB}}, c_{\mathrm{BA}}, and c_{\mathrm{BB}} is
A
orB
.
Input
Input is given from Standard Input in the following format:
N c_{\mathrm{AA}} c_{\mathrm{AB}} c_{\mathrm{BA}} c_{\mathrm{BB}}
Output
Print the number, modulo (10^9+7), of strings that can be s when Snuke has done the operations so that the length of s becomes N.
Sample Input 1
4 A B B A
Sample Output 1
2
- There are two strings that can be s when Snuke is done:
ABAB
andABBB
.
Sample Input 2
1000 B B B B
Sample Output 2
1
- There is just one string that can be s when Snuke is done.
Time Limit: 3 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
N 脚のイスが左から右に並んでいます。 左から i 番目のイスのIDは a_i です。ここで、a_i がすべて相異なることが保証されます。
すぬけ君は何脚かのイスに印をつけ、印をつけたイス以外を捨てることにしました。はじめ、どのイスにも印はついていません。 印のついたイスたちのIDが左から右に単調増加になっているような印のつけ方を よい印のつけ方 と呼びます。
すぬけ君は以下の手続きに従って印をつけることにしました。
- イス x に新たに印をつけても印のつけ方がよい印のつけ方のままであるとき、イス x を 良いイス とする。現在の良いイスの脚数を k とする
- k=0 なら印のついていないイスを取り除き手続きを終了する。そうでないなら、k 脚の良いイスから等確率で 1 つを選んで印をつけ手順 1 へ戻る
手続き終了時に残るイスの脚数の期待値が有理数になることが証明できます。その値を P/Q (既約分数)とします。また M=10^{9}+7 とします。このとき、0 以上 M-1 以下の整数 R がただ一つ存在して P \equiv Q \times R \pmod{M} となることが証明でき、その値は P \times Q^{-1} \pmod{M} と等しくなります。ここで、Q^{-1} はモジュラ逆数です。R を求めてください。
制約
- 与えられる入力は全て整数
- 1 \leq N \leq 2000
- 1 \leq a_i \leq N
- a_i はすべて相異なる
入力
入力は以下の形式で標準入力から与えられる。
N a_1 a_2 \cdots a_N
出力
R を出力せよ。
入力例 1
3 3 1 2
出力例 1
666666673
- はじめにイス 1(IDが 1 のイスです) に印がついたとき、最終的に残るイスはイス 1,2 の 2 脚です。
- はじめにイス 2 に印がついたとき、最終的に残るイスはイス 1,2 の 2 脚です。
- はじめにイス 3 に印がついたとき、最終的に残るイスはイス 3 の 1 脚です。
- イスは等確率で選ばれるので手続き終了時に残るイスの脚数の期待値は \frac{5}{3} となります。5 \equiv 3 \times 666666673 \pmod{M} より、R=666666673 です。
入力例 2
30 26 16 28 30 23 11 29 18 22 15 20 13 27 9 21 7 5 25 4 19 8 3 1 24 10 14 17 12 2 6
出力例 2
297703424
Score : 700 points
Problem Statement
There are N isu - chairs in Japanese - arranged from left to right. The i-th chair from the left has the ID number a_i. Here, it is guaranteed that a_i are distinct.
Snuke has decided to mark some of the chairs and throw away the rest. Initially, no chair is marked. We call a choice of marked chairs good when the IDs of the marked chairs are monotonically increasing from left to right.
Snuke has decided to do the following procedure to mark chairs:
- We say a chair x to be nice if (and only if) the choice of marked chairs is still good when x gets marked. Let k be the current number of nice chairs.
- If k=0, remove the unmarked chairs and terminate the procedure. Otherwise, choose one from the k nice chairs with equal probability, mark it, and go back to Step 1.
It can be proved that the expected value of the number of chairs that remain at the end of the procedure is a rational number. Let this value be P/Q, an irreducible fraction. Additionally, let M=10^{9}+7. Then, we can prove that there uniquely exists an integer R between 0 and M-1 (inclusive) such that P \equiv Q \times R \pmod{M}, and that value equals P \times Q^{-1} \pmod{M}, where Q^{-1} is the modular multiplicative inverse of Q. Find R.
Constraints
- All values in input are integers.
- 1 \leq N \leq 2000
- 1 \leq a_i \leq N
- a_i are distinct.
Input
Input is given from Standard Input in the following format:
N a_1 a_2 \cdots a_N
Output
Print R.
Sample Input 1
3 3 1 2
Sample Output 1
666666673
- If Chair 1 (the chair with the ID number 1) gets marked first, two chairs will remain at the end: Chair 1 and 2.
- If Chair 2 gets marked first, two chairs will remain at the end: Chair 1 and 2.
- If Chair 3 gets marked first, one chair will remain at the end: Chair 3.
- Since chairs are chosen with equal probability, the expected value of the number of chairs at the end is \frac{5}{3}. We have 5 \equiv 3 \times 666666673 \pmod{M}, so R=666666673.
Sample Input 2
30 26 16 28 30 23 11 29 18 22 15 20 13 27 9 21 7 5 25 4 19 8 3 1 24 10 14 17 12 2 6
Sample Output 2
297703424
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
1 から N の番号がついた N 個の頂点と、1 から N-1 の番号がついた N-1 本の辺からなる木が与えられます。 辺 i は頂点 a_i と頂点 b_i を双方向につなぐ長さ 1 の辺です。
すぬけ君はそれぞれの頂点を白か黒のどちらかで塗ります。 塗り方の 良さ は、白色の頂点同士の距離の最大値を X、黒色の頂点同士の距離の最大値を Y として \max(X,Y) です。 ここで、その色の頂点が存在しない場合の距離の最大値は 0 とすることにします。
頂点への色の塗り方は 2^N 通りあります。それぞれの塗り方について良さを計算し、その総和を 10^{9}+7 で割ったあまりを求めてください。
制約
- 与えられる入力は全て整数
- 2 \leq N \leq 2 \times 10^{5}
- 1 \leq a_i, b_i \leq N
- 与えられるグラフは木
入力
入力は以下の形式で標準入力から与えられる。
N a_1 b_1 \vdots a_{N-1} b_{N-1}
出力
それぞれの塗り方について良さを計算し、その総和を 10^{9}+7 で割ったあまりを出力せよ。
入力例 1
2 1 2
出力例 1
2
- 頂点 1,2 の両方を同じ色で塗ったときの良さは 1 で、異なる色で塗ったときの良さは 0 です。
- 塗り方の良さの総和は 2 となります。
入力例 2
6 1 2 2 3 3 4 4 5 3 6
出力例 2
224
入力例 3
35 25 4 33 7 11 26 32 4 12 7 31 27 19 6 10 22 17 12 28 24 28 1 24 15 30 24 24 11 23 18 14 15 4 29 33 24 15 34 11 3 4 35 5 34 34 2 16 19 7 18 19 31 22 8 13 26 20 6 20 9 4 33 4 8 29 19 15 21
出力例 3
298219707
- 10^{9}+7 で割ったあまりを求めるのを忘れずに。
Score : 900 points
Problem Statement
Given is a tree with N vertices numbered 1 to N, and N-1 edges numbered 1 to N-1. Edge i connects Vertex a_i and b_i bidirectionally and has a length of 1.
Snuke will paint each vertex white or black. The niceness of a way of painting the graph is \max(X, Y), where X is the maximum among the distances between white vertices, and Y is the maximum among the distances between black vertices. Here, if there is no vertex of one color, we consider the maximum among the distances between vertices of that color to be 0.
There are 2^N ways of painting the graph. Compute the sum of the nicenesses of all those ways, modulo (10^{9}+7).
Constraints
- 2 \leq N \leq 2 \times 10^{5}
- 1 \leq a_i, b_i \leq N
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N a_1 b_1 \vdots a_{N-1} b_{N-1}
Output
Print the sum of the nicenesses of the ways of painting the graph, modulo (10^{9}+7).
Sample Input 1
2 1 2
Sample Output 1
2
- If we paint Vertex 1 and 2 the same color, the niceness will be 1; if we paint them different colors, the niceness will be 0.
- The sum of those nicenesses is 2.
Sample Input 2
6 1 2 2 3 3 4 4 5 3 6
Sample Output 2
224
Sample Input 3
35 25 4 33 7 11 26 32 4 12 7 31 27 19 6 10 22 17 12 28 24 28 1 24 15 30 24 24 11 23 18 14 15 4 29 33 24 15 34 11 3 4 35 5 34 34 2 16 19 7 18 19 31 22 8 13 26 20 6 20 9 4 33 4 8 29 19 15 21
Sample Output 3
298219707
- Be sure to compute the sum modulo (10^{9}+7).