Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
すぬけくんは,0 と 1 からなる長さ N の整数列 a=(a_1,a_2,\cdots,a_N) と,空の整数列 b を持っています. a の初期状態は入力で与えられ,a_i=S_i です.
すぬけくんは,以下の 3 種類の操作を好きな順番で好きな回数行えます.
-
a を右シフトする.つまり,a を (a_N,a_1,a_2,\cdots,a_{N-1}) で置き換える.
-
a を左シフトする.つまり,a を (a_2,a_3,\cdots,a_N,a_1) で置き換える.
-
b の末尾に現在の a_1 の値を追加する.
長さ M の整数列 T=(T_1,T_2,\cdots,T_M) が与えられます. b を T に一致させることができるか判定し,可能な場合は必要な操作回数の最小値を求めてください.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq S_i \leq 1
- 0 \leq T_i \leq 1
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N M S_1 S_2 \cdots S_N T_1 T_2 \cdots T_M
出力
b を T に一致させることが不可能な場合,-1
を出力せよ.
可能な場合は,必要な操作回数の最小値を出力せよ.
入力例 1
3 4 0 0 1 0 1 1 0
出力例 1
6
以下のように 6 回操作すればよいです.
-
b の末尾に現在の a_1 の値を追加する.b=(0) となる.
-
a を右シフトする.a=(1,0,0) となる.
-
b の末尾に現在の a_1 の値を追加する.b=(0,1) となる.
-
b の末尾に現在の a_1 の値を追加する.b=(0,1,1) となる.
-
a を右シフトする.a=(0,1,0) となる.
-
b の末尾に現在の a_1 の値を追加する.b=(0,1,1,0) となる.
入力例 2
1 1 0 1
出力例 2
-1
Score : 300 points
Problem Statement
Snuke has a sequence of N integers a=(a_1,a_2,\cdots,a_N) consisting of 0s and 1s, and an empty integer sequence b. The initial state a_i=S_i is given to you as input.
Snuke can do the following three operations any number of times in any order.
-
Shift a to the right. In other words, replace a with (a_N,a_1,a_2,\cdots,a_{N-1}).
-
Shift a to the left. In other words, replace a with (a_2,a_3,\cdots,a_N,a_1).
-
Append the current value of a_1 at the end of b.
You are also given a sequence of M integers T=(T_1,T_2,\cdots,T_M). Determine whether it is possible to make b equal to T. If it is possible, find the minimum number of operations needed to do so.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 0 \leq S_i \leq 1
- 0 \leq T_i \leq 1
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M S_1 S_2 \cdots S_N T_1 T_2 \cdots T_M
Output
If it is impossible to make b equal to T, print -1
.
If it is possible, print the minimum number of operations needed to do so.
Sample Input 1
3 4 0 0 1 0 1 1 0
Sample Output 1
6
The following sequence of six operations will do the job.
-
Append the current value of a_1 at the end of b, making b=(0).
-
Shift a to the right, making a=(1,0,0).
-
Append the current value of a_1 at the end of b, making b=(0,1).
-
Append the current value of a_1 at the end of b, making b=(0,1,1).
-
Shift a to the right, making a=(0,1,0).
-
Append the current value of a_1 at the end of b, making b=(0,1,1,0).
Sample Input 2
1 1 0 1
Sample Output 2
-1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 500 点
問題文
整数 N が与えられます. 以下の条件を満たす整数の組 (x,y) の個数を 998244353 で割った余りを求めてください.
-
1 \leq x,y \leq N
-
x^2-y は平方数である.(特に,0 も平方数とする.)
制約
- 1 \leq N \leq 10^{12}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N
出力
答えを出力せよ.
入力例 1
3
出力例 1
2
以下の 2 通りが考えられます.
-
x=1,y=1
-
x=2,y=3
入力例 2
10
出力例 2
8
入力例 3
10000000000
出力例 3
52583544
Score : 500 points
Problem Statement
You are given an integer N. Find the number of pairs of integers (x, y) that satisfy the following conditions, modulo 998244353.
-
1 \leq x,y \leq N.
-
x^2-y is a square number. (Assume 0 is also a square number.)
Constraints
- 1 \leq N \leq 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer.
Sample Input 1
3
Sample Output 1
2
We have the following two pairs.
-
x=1,y=1
-
x=2,y=3
Sample Input 2
10
Sample Output 2
8
Sample Input 3
10000000000
Sample Output 3
52583544
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
整数 N と,長さ K の単調増加な整数列 A=(A_1,A_2,\cdots,A_K) が与えられます. 次の条件を満たす (1,2,\cdots,N) の順列 P の中で,辞書順最小のものを求めてください.
- A は P の最長増加部分列(単調増加な部分列であって,長さが最大のもの)である. なお,P は複数の最長増加部分列を持つことがあるが,そのうちの一つが A に一致していればよい.
なお,問題の制約から,条件を満たす P が必ず存在することが証明できます.
制約
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_1 < A_2 < \cdots < A_K \leq N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N K A_1 A_2 \cdots A_K
出力
答えを出力せよ.
入力例 1
3 2 2 3
出力例 1
2 1 3
P の最長増加部分列が A に一致するのは,P=(2,1,3),(2,3,1) のときです. このうち,辞書順最小の (2,1,3) が答えになります.
入力例 2
5 1 4
出力例 2
5 4 3 2 1
Score : 600 points
Problem Statement
Given are an integer N and a monotonically increasing sequence of K integers A=(A_1,A_2,\cdots,A_K). Find the lexicographically smallest permutation P of (1,2,\cdots,N) that satisfies the following condition.
- A is a longest increasing subsequence of P (a monotonically increasing subsequence of P with the maximum possible length). It is fine if P has multiple longest increasing subsequences, one of which is A.
From the Constraints of this problem, we can prove that there always exists a P that satisfies the condition.
Constraints
- 1 \leq K \leq N \leq 2 \times 10^5
- 1 \leq A_1 < A_2 < \cdots < A_K \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 A_2 \cdots A_K
Output
Print the answer.
Sample Input 1
3 2 2 3
Sample Output 1
2 1 3
A is a longest increasing subsequence of P when P=(2,1,3),(2,3,1). The answer is the lexicographically smallest of the two, or (2,1,3).
Sample Input 2
5 1 4
Sample Output 2
5 4 3 2 1
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 700 点
問題文
長さ N の整数列 A_1,A_2,\cdots,A_N が与えられます.
A の非空な部分列 s であって,以下の条件を満たすものの個数を 998244353 で割った余りを求めてください.
- A から s を取り出す方法が一意である. つまり,s=(s_1,s_2,\cdots,s_k) とした時,A_{idx(i)}=s_i (1 \leq i \leq k)を満たす添字の列 1 \leq idx(1)<idx(2)<\cdots<idx(k) \leq N がちょうど一つ存在する.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N A_1 A_2 \cdots A_N
出力
答えを出力せよ.
入力例 1
3 1 2 1
出力例 1
5
以下の 5 つの部分列が条件を満たします.
- (1,1)
- (1,2)
- (1,2,1)
- (2)
- (2,1)
部分列 (1) は取り出す方法が 2 通りあるので条件を満たしません.
入力例 2
4 4 2 1 3
出力例 2
15
入力例 3
12 1 2 3 6 9 2 3 3 9 6 1 6
出力例 3
1178
Score : 700 points
Problem Statement
Given is a sequence of N integers A_1,A_2,\cdots,A_N.
Find the number of non-empty subsequences s of A satisfying the following condition, modulo 998244353.
- There is only one way to extract s from A. Formally, there uniquely exists a sequence of indices 1 \leq idx(1)<idx(2)<\cdots<idx(k) \leq N such that A_{idx(i)}=s_i (1 \leq i \leq k), where s=(s_1,s_2,\cdots,s_k).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq A_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 \cdots A_N
Output
Print the answer.
Sample Input 1
3 1 2 1
Sample Output 1
5
The following five subsequences satisfy the condition.
- (1,1)
- (1,2)
- (1,2,1)
- (2)
- (2,1)
The subsequence (1) does not satisfy the condition since there are two ways to extract it.
Sample Input 2
4 4 2 1 3
Sample Output 2
15
Sample Input 3
12 1 2 3 6 9 2 3 3 9 6 1 6
Sample Output 3
1178
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 800 点
問題文
1 から N までの番号のついた N 種類のお菓子があります. お菓子 i は A_i 個あります.
1 から M までの番号のついた M 人の子供がいます. この子供たちに,今からお菓子を配ります. ただし,お菓子を配る際には,次の条件を全て満たす必要があります.
-
子供 i は,どの種類のお菓子も B_i 個以下しかもらわない.
-
子供 i がもらうお菓子の個数の合計は C_i 以下である.
この条件のもとで,子どもたちに配るお菓子の個数の総和の最大値がいくらになるか求めてください.
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{12}
- 1 \leq B_i \leq 10^7
- 1 \leq C_i \leq 10^{12}
- 入力される値はすべて整数である
入力
入力は以下の形式で標準入力から与えられる.
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M C_1 C_2 \cdots C_M
出力
答えを出力せよ.
入力例 1
3 3 2 5 5 1 2 2 5 3 5
出力例 1
11
次のようにお菓子を配ればよいです.
-
子供 1 は,お菓子 1,2,3 をそれぞれ 1,1,1 個もらう.
-
子供 2 は,お菓子 1,2,3 をそれぞれ 0,2,1 個もらう.
-
子供 3 は,お菓子 1,2,3 をそれぞれ 1,2,2 個もらう.
入力例 2
10 6 3 54 62 64 25 89 1 47 77 4 1 17 10 29 95 17 32 40 90 27 50 9
出力例 2
211
Score : 800 points
Problem Statement
There are N kinds of snacks numbered 1 through N. We have A_i pieces of Snack i.
There are M children numbered 1 through M. We will distribute the pieces of snacks to these children. Here, all of the following conditions must be satisfied.
-
For every kind of snack, Child i gets at most B_i pieces of that kind.
-
Child i gets at most C_i pieces of snacks in total.
Find the maximum total number of pieces of snacks that can be distributed to the children under these conditions.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq M \leq 2 \times 10^5
- 1 \leq A_i \leq 10^{12}
- 1 \leq B_i \leq 10^7
- 1 \leq C_i \leq 10^{12}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N M A_1 A_2 \cdots A_N B_1 B_2 \cdots B_M C_1 C_2 \cdots C_M
Output
Print the answer.
Sample Input 1
3 3 2 5 5 1 2 2 5 3 5
Sample Output 1
11
The optimal distribution of snacks is as follows.
-
Child 1 gets 1, 1, 1 piece of Snacks 1, 2, 3, respectively.
-
Child 2 gets 0, 2, 1 piece(s) of Snacks 1, 2, 3, respectively.
-
Child 3 gets 1, 2, 2 piece(s) of Snacks 1, 2, 3, respectively.
Sample Input 2
10 6 3 54 62 64 25 89 1 47 77 4 1 17 10 29 95 17 32 40 90 27 50 9
Sample Output 2
211
Time Limit: 6 sec / Memory Limit: 1024 MB
配点 : 900 点
問題文
N 頂点からなる木が与えられます. 頂点には 1 から N までの番号がついており,i 番目の辺は頂点 A_i と頂点 B_i を結んでいます.
整数の組 (x,y) であって,以下の条件を満たすものが何通りあるかを求めてください.
-
0 \leq x \leq N
-
木からちょうど x 個の頂点を選び,その次数の和をちょうど y にすることができる.
制約
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i < B_i \leq N
- 入力されるグラフは木である.
入力
入力は以下の形式で標準入力から与えられる.
N A_1 B_1 A_2 B_2 \vdots A_{N-1} B_{N-1}
出力
答えを出力せよ.
入力例 1
3 1 2 2 3
出力例 1
6
条件を満たす (x,y) の組は以下の 6 通りです.
- x=0,y=0
- x=1,y=1
- x=1,y=2
- x=2,y=2
- x=2,y=3
- x=3,y=4
例えば,頂点 1 と頂点 2 を選ぶと次数の和が 3 になるため,x=2,y=3 は条件を満たします.
入力例 2
5 1 2 2 3 2 4 4 5
出力例 2
16
入力例 3
10 2 9 8 10 2 10 4 6 5 6 1 8 2 7 3 6 6 8
出力例 3
65
Score : 900 points
Problem Statement
Given is a tree with N vertices. The vertices are numbered 1 through N, and the i-th edge connects Vertex A_i and Vertex B_i.
Find the number of pairs of integers (x,y) that satisfy the following conditions.
-
0 \leq x \leq N.
-
There is a way to choose exactly x vertices from the tree so that the sum of their degrees equals y.
Constraints
- 2 \leq N \leq 2 \times 10^5
- 1 \leq A_i < B_i \leq N
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 B_1 A_2 B_2 \vdots A_{N-1} B_{N-1}
Output
Print the answer.
Sample Input 1
3 1 2 2 3
Sample Output 1
6
The following six pairs (x,y) satisfy the conditions.
- x=0,y=0
- x=1,y=1
- x=1,y=2
- x=2,y=2
- x=2,y=3
- x=3,y=4
x=2,y=3, for example, satisfies the condition because choosing Vertex 1 and Vertex 2 achieves the total degree of 3.
Sample Input 2
5 1 2 2 3 2 4 4 5
Sample Output 2
16
Sample Input 3
10 2 9 8 10 2 10 4 6 5 6 1 8 2 7 3 6 6 8
Sample Output 3
65