Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 100 点
問題文
数字のみからなる、長さがちょうど 9 の文字列 S が与えられます。
S には 0 から 9 までのうち、ちょうど 1 つの数字を除いた 9 種類の数字が一度ずつ登場します。
S に登場しない唯一の数字を出力してください。
制約
- S は数字のみからなる長さ 9 の文字列である。
- S の文字はすべて相異なる。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S に登場しない唯一の数字を出力せよ。
入力例 1
023456789
出力例 1
1
文字列 023456789 には 1 のみが登場していません。
よって、1 を出力します。
入力例 2
459230781
出力例 2
6
文字列 459230781 には 6 のみが登場していません。
よって、6 を出力します。
文字列に数字が現れる順番は昇順とは限らないので注意してください。
Score : 100 points
Problem Statement
You are given a string S of length exactly 9 consisting of digits.
One but all digits from 0 to 9 appear exactly once in S.
Print the only digit missing in S.
Constraints
- S is a string of length 9 consisting of digits.
- All characters in S are distinct.
Input
Input is given from Standard Input in the following format:
S
Output
Print the only digit missing in S.
Sample Input 1
023456789
Sample Output 1
1
The string 023456789 only lacks 1.
Thus, 1 should be printed.
Sample Input 2
459230781
Sample Output 2
6
The string 459230781 only lacks 6.
Thus, 6 should be printed.
Note that the digits in the string may not appear in increasing order.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 200 点
問題文
A 匹のスライムがいます。
すぬけくんが 1 回叫ぶたびに、スライムは K 倍に増殖します。
スライムが B 匹以上になるには、すぬけくんは最小で何回叫ぶ必要があるでしょうか？
制約
- 1 \leq A \leq B \leq 10^9
- 2 \leq K \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
A B K
出力
答えを出力せよ。
入力例 1
1 4 2
出力例 1
2
はじめ、スライムが 1 匹います。すぬけくんが 1 回叫ぶとスライムは 2 匹になり、 2 回叫ぶとスライムは 4 匹になります。4 匹以上になるためには、最小で 2 回叫ぶ必要があります。
入力例 2
7 7 10
出力例 2
0
はじめからスライムは 7 匹います。
入力例 3
31 415926 5
出力例 3
6
Score : 200 points
Problem Statement
There are A slimes.
Each time Snuke shouts, the slimes multiply by K times.
In order to have B or more slimes, at least how many times does Snuke need to shout?
Constraints
- 1 \leq A \leq B \leq 10^9
- 2 \leq K \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
A B K
Output
Print the answer.
Sample Input 1
1 4 2
Sample Output 1
2
We start with one slime. After Snuke's first shout, we have two slimes; after his second shout, we have four slimes. Thus, he needs to shout at least twice to have four or more slimes.
Sample Input 2
7 7 10
Sample Output 2
0
We have seven slimes already at the start.
Sample Input 3
31 415926 5
Sample Output 3
6
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N) であって、以下の条件を全て満たすものは何通りありますか？
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
ただし、答えは非常に大きくなることがあるので、答えを 998244353 で割った余りを求めてください。
制約
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M K
出力
答えを 998244353 で割った余りを出力せよ。
入力例 1
2 3 4
出力例 1
6
条件を満たす数列は以下の 6 つです。
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
入力例 2
31 41 592
出力例 2
798416518
答えを 998244353 で割った余りを出力してください。
Score : 300 points
Problem Statement
How many integer sequences of length N, A=(A_1, \ldots, A_N), satisfy all of the conditions below?
-
1\le A_i \le M (1 \le i \le N)
-
\displaystyle\sum _{i=1}^N A_i \leq K
Since the count can get enormous, find it modulo 998244353.
Constraints
- 1 \leq N, M \leq 50
- N \leq K \leq NM
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M K
Output
Print the answer.
Sample Input 1
2 3 4
Sample Output 1
6
The following six sequences satisfy the conditions.
- (1,1)
- (1,2)
- (1,3)
- (2,1)
- (2,2)
- (3,1)
Sample Input 2
31 41 592
Sample Output 2
798416518
Be sure to print the count modulo 998244353.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 400 点
問題文
長さ N の数列 A=(A_1,\ldots,A_N) が与えられます。
以下の形式で与えられる Q 個のクエリに答えてください。
- 整数 L,R,X が与えられる。 A_L, \ldots,A_R のうち、値が X に等しいものの個数を求めよ。
制約
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq N
- 1 \leq Q \leq 2\times 10^5
- 各クエリについて、 1\le L \leq R \leq N, 1 \leq X \leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \ldots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
ただし、\mathrm{Query}_i は i 個目のクエリを表す。
各クエリは以下の形式で与えられる。
L R X
出力
Q 行出力せよ。i 行目には、i 個目のクエリに対する答えを出力せよ。
入力例 1
5 3 1 4 1 5 4 1 5 1 2 4 3 1 5 2 1 3 3
出力例 1
2 0 0 1
1 個目のクエリでは、 (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) のうち値が 1 に等しいものの個数は 2 です。
2 個目のクエリでは、 (A_2,A_3,A_4) =(1,4,1) のうち値が 3 に等しいものの個数は 0 です。
Score : 400 points
Problem Statement
You are given a sequence of length N: A=(A_1,\ldots,A_N).
Answer Q queries given in the following format.
- You are given integers L, R, and X. Find the number of elements among A_L, \ldots, A_R whose values are equal to X.
Constraints
- 1 \leq N \leq 2\times 10^5
- 1 \leq A_i \leq N
- 1 \leq Q \leq 2\times 10^5
- 1\le L \leq R \leq N, 1 \leq X \leq N, for each query.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \ldots A_N
Q
\mathrm{Query}_1
\mathrm{Query}_2
\vdots
\mathrm{Query}_Q
Here, \mathrm{Query}_i represents the i-th query.
Each query is in the following format:
L R X
Output
Print Q lines, the i-th of which contains the answer to the i-th query.
Sample Input 1
5 3 1 4 1 5 4 1 5 1 2 4 3 1 5 2 1 3 3
Sample Output 1
2 0 0 1
In the first query, two of (A_1,A_2,A_3,A_4,A_5) =(3,1,4,1,5) have values equal to 1.
In the second query, zero of (A_2,A_3,A_4) =(1,4,1) have values equal to 3.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
座標平面上の N 個の点が与えられます。 1\leq i\leq N について、i 番目の点の座標は (X_i, Y_i) です。
座標平面上の直線であって、N 個の点のうち K 個以上の点を通るものの個数を求めてください。
ただし、そのようなものが無数に存在する場合は Infinity を出力してください。
制約
- 1 \leq K \leq N \leq 300
- \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
- i\neq j ならば X_i\neq X_j または Y_i\neq Y_j
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
出力
与えられた N 個の点のうち K 個以上の点を通る直線の数を出力せよ。ただし、そのようなものが無数に存在する場合は Infinity を出力せよ。
入力例 1
5 2 0 0 1 0 0 1 -1 0 0 -1
出力例 1
6
x=0, y=0, y=x\pm 1, y=-x\pm 1 の 6 本の直線が条件をみたします。
例えば、x=0 は、1, 3, 5 番目の 3 個の点を通ります。
よって、6 を出力します。
入力例 2
1 1 0 0
出力例 2
Infinity
原点を通る直線は無数に存在します。
よって、Infinity を出力します。
Score : 500 points
Problem Statement
You are given N points in the coordinate plane. For each 1\leq i\leq N, the i-th point is at the coordinates (X_i, Y_i).
Find the number of lines in the plane that pass K or more of the N points.
If there are infinitely many such lines, print Infinity.
Constraints
- 1 \leq K \leq N \leq 300
- \lvert X_i \rvert, \lvert Y_i \rvert \leq 10^9
- X_i\neq X_j or Y_i\neq Y_j, if i\neq j.
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K X_1 Y_1 X_2 Y_2 \vdots X_N Y_N
Output
Print the number of lines in the plane that pass K or more of the N points, or Infinity if there are infinitely many such lines.
Sample Input 1
5 2 0 0 1 0 0 1 -1 0 0 -1
Sample Output 1
6
The six lines x=0, y=0, y=x\pm 1, and y=-x\pm 1 satisfy the requirement.
For example, x=0 passes the first, third, and fifth points.
Thus, 6 should be printed.
Sample Input 2
1 1 0 0
Sample Output 2
Infinity
Infinitely many lines pass the origin.
Thus, Infinity should be printed.
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
2 以上の整数 N および素数 P が与えられます。
下図のような 2N 頂点 (3N-2) 辺のグラフ G を考えます。
より具体的には、頂点を順に頂点 1, 頂点 2, \ldots, 頂点 2N、 辺を順に辺 1, 辺 2, \ldots, 辺 (3N-2) とすると、各辺は次のように頂点を結んでいます。
- 1\leq i\leq N-1 について、辺 i は頂点 i と頂点 i+1 を結んでいる。
- 1\leq i\leq N-1 について、辺 (N-1+i) は頂点 N+i と頂点 N+i+1 を結んでいる。
- 1\leq i\leq N について、辺 (2N-2+i) は頂点 i と頂点 N+i を結んでいる。
i=1,2,\ldots ,N-1 について、次の問題を解いてください。
G の 3N-2 本の辺からちょうど i 本の辺を取り除く方法であって、辺を取り除いた後のグラフも連結であるようなものの個数を P で割ったあまりを求めよ。
制約
- 2 \leq N \leq 3000
- 9\times 10^8 \leq P \leq 10^9
- N は整数である。
- P は素数である。
入力
入力は以下の形式で標準入力から与えられる。
N P
出力
N-1 個の整数を空白区切りで出力せよ。 ただし、k 番目の整数は i=k に対する答えである。
入力例 1
3 998244353
出力例 1
7 15
N=3 の場合について、取り除いた後のグラフも連結となるように、ちょうど 1 本の辺を取り除く方法は次の 7 通りです。
取り除いた後のグラフも連結となるように、ちょうど 2 本の辺を取り除く方法は次の 15 通りです。
よって、これらを P=998244353 で割ったあまりである 7, 15 をこの順に出力します。
入力例 2
16 999999937
出力例 2
46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
P で割ったあまりを出力することに注意してください。
Score : 500 points
Problem Statement
You are given an integer N greater than or equal to 2 and a prime P.
Consider the graph G with 2N vertices and (3N-2) edges shown in the figure below.
More specifically, the edges connect the vertices as follows, where the vertices are labeled as Vertex 1, Vertex 2, \ldots, Vertex 2N, and the edges are labeled as Edge 1, Edge 2, \ldots, Edge (3N-2).
- For each 1\leq i\leq N-1, Edge i connects Vertex i and Vertex i+1.
- For each 1\leq i\leq N-1, Edge (N-1+i) connects Vertex N+i and Vertex N+i+1.
- For each 1\leq i\leq N, Edge (2N-2+i) connects Vertex i and Vertex N+i.
For each i=1,2,\ldots ,N-1, solve the following problem.
Find the number of ways, modulo P, to remove exactly i of the 3N-2 edges of G so that the resulting graph is still connected.
Constraints
- 2 \leq N \leq 3000
- 9\times 10^8 \leq P \leq 10^9
- N is an integer.
- P is a prime.
Input
Input is given from Standard Input in the following format:
N P
Output
Print N-1 integers, the i-th of which is the answer for i=k, separated by spaces.
Sample Input 1
3 998244353
Sample Output 1
7 15
In the case N=3, there are 7 ways, shown below, to remove exactly one edge so that the resulting graph is still connected.
There are 15 ways, shown below, to remove exactly two edges so that the resulting graph is still connected.
Thus, these numbers modulo P=998244353 should be printed: 7 and 15, in this order.
Sample Input 2
16 999999937
Sample Output 2
46 1016 14288 143044 1079816 6349672 29622112 110569766 330377828 784245480 453609503 38603306 44981526 314279703 408855776
Be sure to print the numbers modulo P.
Time Limit: 8 sec / Memory Limit: 2048 MB
配点 : 600 点
問題文
N 頂点からなる無向木が与えられます。
頂点を順に頂点 1, 頂点 2, \ldots, 頂点 N とすると、
1\leq i\leq N-1 について、i 番目の辺は頂点 U_i と頂点 V_i を結んでいます。
また、それぞれの頂点には正整数が割り当てられており、
具体的には頂点 i には A_i が割り当てられています。
相異なる 2 頂点 s, t 間のコスト C(s,t) が次のようにして定められます。
頂点 s と頂点 t を結ぶ単純パス上の頂点を順に p_1(=s), p_2, \ldots, p_k(=t) とする。 ここで、k はパス上の(端点含む)頂点数である。
このとき、C(s,t)=k\times \gcd (A_{p_1},A_{p_2},\ldots,A_{p_k}) で定める。
ただし、\gcd (X_1,X_2,\ldots, X_k) で X_1,X_2,\ldots, X_k の最大公約数を表す。
\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j) を 998244353 で割ったあまりを求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq A_i\leq 10^5
- 1\leq U_i<V_i\leq N
- 入力は全て整数である。
- 与えられるグラフは木である。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \cdots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
出力
\displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j) を 998244353 で割ったあまりを出力せよ。
入力例 1
4 24 30 28 7 1 2 1 3 3 4
出力例 1
47
頂点 1 と頂点 2 、頂点 1 と頂点 3 、頂点 3 と頂点 4 がそれぞれ直接辺で結ばれています。 よって、コストはそれぞれ次のように求められます。
- C(1,2)=2\times \gcd(24,30)=12
- C(1,3)=2\times \gcd(24,28)=8
- C(1,4)=3\times \gcd(24,28,7)=3
- C(2,3)=3\times \gcd(30,24,28)=6
- C(2,4)=4\times \gcd(30,24,28,7)=4
- C(3,4)=2\times \gcd(28,7)=14
求める値は \displaystyle\sum_{i=1}^{3}\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47 を 998244353 で割ったあまりの 47 となります。
入力例 2
10 180 168 120 144 192 200 198 160 156 150 1 2 2 3 2 4 2 5 5 6 4 7 7 8 7 9 9 10
出力例 2
1184
Score : 600 points
Problem Statement
You are given an undirected tree with N vertices.
Let us call the vertices Vertex 1, Vertex 2, \ldots, Vertex N. For each 1\leq i\leq N-1, the i-th edge connects Vertex U_i and Vertex V_i.
Additionally, each vertex is assigned a positive integer: Vertex i is assigned A_i.
The cost between two distinct vertices s and t, C(s,t), is defined as follows.
Let p_1(=s), p_2, \ldots, p_k(=t) be the vertices of the simple path connecting Vertex s and Vertex t, where k is the number of vertices in the path (including the endpoints).
Then, let C(s,t)=k\times \gcd (A_{p_1},A_{p_2},\ldots,A_{p_k}),
where \gcd (X_1,X_2,\ldots, X_k) denotes the greatest common divisor of X_1,X_2,\ldots, X_k.
Find \displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j), modulo 998244353.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq A_i\leq 10^5
- 1\leq U_i<V_i\leq N
- All values in input are integers.
- The given graph is a tree.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \cdots A_N
U_1 V_1
U_2 V_2
\vdots
U_{N-1} V_{N-1}
Output
Print \displaystyle\sum_{i=1}^{N-1}\sum_{j=i+1}^N C(i,j), modulo 998244353.
Sample Input 1
4 24 30 28 7 1 2 1 3 3 4
Sample Output 1
47
There are edges directly connecting Vertex 1 and 2, Vertex 1 and 3, and Vertex 3 and 4. Thus, the costs are computed as follows.
- C(1,2)=2\times \gcd(24,30)=12
- C(1,3)=2\times \gcd(24,28)=8
- C(1,4)=3\times \gcd(24,28,7)=3
- C(2,3)=3\times \gcd(30,24,28)=6
- C(2,4)=4\times \gcd(30,24,28,7)=4
- C(3,4)=2\times \gcd(28,7)=14
Thus, the sought value is \displaystyle\sum_{i=1}^{3}\sum_{j=i+1}^4 C(i,j)=(12+8+3)+(6+4)+14=47 modulo 998244353, which is 47.
Sample Input 2
10 180 168 120 144 192 200 198 160 156 150 1 2 2 3 2 4 2 5 5 6 4 7 7 8 7 9 9 10
Sample Output 2
1184
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
(1,\ldots,N) を並び替えて得られる長さ N の順列 P=(P_1,\ldots,P_N)、及び整数 K が与えられます。
以下の条件を全て満たす整数組 (L,R) の個数を求めてください。
-
1 \leq L \leq R \leq N
-
\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K
制約
- 1 \leq N \leq 1.4\times 10^5
- P は (1,\ldots,N) を並び替えて得られる順列
- 0 \leq K \leq 3
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K P_1 P_2 \ldots P_N
出力
答えを出力せよ。
入力例 1
4 1 1 4 2 3
出力例 1
9
条件を満たす組 (L,R) は以下の 9 個です。
- (1,1)
- (1,3)
- (1,4)
- (2,2)
- (2,3)
- (2,4)
- (3,3)
- (3,4)
- (4,4)
(L,R) = (1,2) は \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 、R-L+K=2-1+1 = 2 となるので、条件を満たしません。
入力例 2
2 0 2 1
出力例 2
3
入力例 3
10 3 3 7 10 1 9 5 4 8 6 2
出力例 3
37
Score : 600 points
Problem Statement
You are given a permutation P=(P_1,\ldots,P_N) of (1,\ldots,N), and an integer K.
Find the number of pairs of integers (L, R) that satisfy all of the following conditions:
-
1 \leq L \leq R \leq N
-
\mathrm{max}(P_L,\ldots,P_R) - \mathrm{min}(P_L,\ldots,P_R) \leq R - L + K
Constraints
- 1 \leq N \leq 1.4\times 10^5
- P is a permutation of (1,\ldots,N).
- 0 \leq K \leq 3
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K P_1 P_2 \ldots P_N
Output
Print the answer.
Sample Input 1
4 1 1 4 2 3
Sample Output 1
9
The following nine pairs (L, R) satisfy the conditions.
- (1,1)
- (1,3)
- (1,4)
- (2,2)
- (2,3)
- (2,4)
- (3,3)
- (3,4)
- (4,4)
For (L,R) = (1,2), we have \mathrm{max}(A_1,A_2) -\mathrm{min}(A_1,A_2) = 4-1 = 3 and R-L+K=2-1+1 = 2, not satisfying the condition.
Sample Input 2
2 0 2 1
Sample Output 2
3
Sample Input 3
10 3 3 7 10 1 9 5 4 8 6 2
Sample Output 3
37