Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
正整数 N,K が与えられます。長さ N+1 の数列 A=(A_0,A_1,\ldots,A_N) の各要素の値を、以下の方法で定義します。
- 0\leq i<K のとき、 A_i=1
- K\leq i のとき、 A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1}
A_N を 10^9 で割ったあまりを求めてください。
制約
- 1\leq N, K\leq 10^{6}
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K
出力
答えを出力せよ。
入力例 1
4 2
出力例 1
5
A_0=A_1=1 であり、A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5 となります。
入力例 2
10 20
出力例 2
1
入力例 3
1000000 500000
出力例 3
420890625
A_N を 10^9 で割ったあまりを出力することに注意してください。
Score : 300 points
Problem Statement
You are given positive integers N and K. Define a sequence A = (A_0, A_1, \ldots, A_N) of length N+1 as follows:
- A_i = 1 for 0 \le i < K;
- A_i=A_{i-K}+A_{i-K+1}+\ldots+A_{i-1} for K \le i.
Find A_N modulo 10^9.
Constraints
- 1 \le N, K \le 10^{6}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N K
Output
Print the answer.
Sample Input 1
4 2
Sample Output 1
5
We have A_0 = A_1 = 1, and A_2=A_0+A_1=2,A_3=A_1+A_2=3,A_4=A_2+A_3=5.
Sample Input 2
10 20
Sample Output 2
1
Sample Input 3
1000000 500000
Sample Output 3
420890625
Remember to print A_N modulo 10^9.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
長さ N の正整数列 A=(A_1,A_2,\dots,A_N) が与えられます。
1\leq l\leq r\leq N を満たす整数の組 (l,r) であって、数列 (A_l,A_{l+1},\dots,A_r) が等差数列であるようなものが何通りあるか求めてください。
なお、数列 (x_1,x_2,\dots,x_{|x|}) が等差数列であるとは、ある d が存在して x_{i+1}-x_i=d\ (1\leq i < |x|) であることをいいます。 特に、長さ 1 の数列は常に等差数列です。
制約
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \dots A_N
出力
答えを出力せよ。
入力例 1
4 3 6 9 3
出力例 1
8
条件を満たす整数の組 (l,r) は (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3) の 8 通りです。
実際、(l,r)=(1,3) のとき (A_l,\dots,A_r)=(3,6,9) は等差数列なので条件を満たしますが、 (l,r)=(2,4) のとき (A_l,\dots,A_r)=(6,9,3) は等差数列ではないので条件を満たしません。
入力例 2
5 1 1 1 1 1
出力例 2
15
すべての整数の組 (l,r)\ (1\leq l\leq r\leq 5) が条件を満たします。
入力例 3
8 87 42 64 86 72 58 44 30
出力例 3
22
Score : 300 points
Problem Statement
You are given a sequence of N positive integers A=(A_1,A_2,\dots,A_N).
Find the number of pairs of integers (l,r) satisfying 1\leq l\leq r\leq N such that the subsequence (A_l,A_{l+1},\dots,A_r) forms an arithmetic progression.
A sequence (x_1,x_2,\dots,x_{|x|}) is an arithmetic progression if and only if there exists a d such that x_{i+1}-x_i=d\ (1\leq i < |x|). In particular, a sequence of length 1 is always an arithmetic progression.
Constraints
- 1\leq N \leq 2\times 10^5
- 1\leq A_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N A_1 A_2 \dots A_N
Output
Print the answer.
Sample Input 1
4 3 6 9 3
Sample Output 1
8
There are eight pairs of integers (l,r) satisfying the condition: (1,1),(2,2),(3,3),(4,4),(1,2),(2,3),(3,4),(1,3).
Indeed, when (l,r)=(1,3), (A_l,\dots,A_r)=(3,6,9) is an arithmetic progression, so it satisfies the condition. However, when (l,r)=(2,4), (A_l,\dots,A_r)=(6,9,3) is not an arithmetic progression, so it does not satisfy the condition.
Sample Input 2
5 1 1 1 1 1
Sample Output 2
15
All pairs of integers (l,r)\ (1\leq l\leq r\leq 5) satisfy the condition.
Sample Input 3
8 87 42 64 86 72 58 44 30
Sample Output 3
22
Time Limit: 4 sec / Memory Limit: 1024 MiB
配点 : 450 点
問題文
整数 N と A, B, C からなる長さ N の文字列 R,C が与えられるので、以下の問題を解いてください。
N \times N のマス目があり、最初全てのマスは空きマスです。
各マスに A, B, C のうち高々 1 文字を書き込みます。( 空きマスのままにすることも許されます )
以下の条件を全て満たすことが可能であるか判定し、可能であれば書き込み方を 1 つ出力して下さい。
- 各行 / 各列 に
A,B,Cがちょうど 1 個ずつ含まれる - i 行目に書かれた文字の中で最も左にある文字は R の i 文字目と一致する
- i 列目に書かれた文字の中で最も上にある文字は C の i 文字目と一致する
制約
- N は 3 以上 5 以下の整数
- R,C は
A,B,Cからなる長さ N の文字列
入力
入力は以下の形式で標準入力から与えられる。
N R C
出力
問題文中の条件を満たす書き込み方が存在しない場合、 No と 1 行に出力してください。
そうでない場合、以下の形式に従い書き込み方を出力してください。
Yes A_1 A_2 \vdots A_N
まず、 1 行目に Yes と出力してください。
続く N 行のうちの i 行目に、長さ N の文字列である A_i を出力してください。
- A_i の j 文字目が
.であるとき、上から i 行目、左から j 列目のマスは空きマスであることを示します。 - A_i の j 文字目が
Aであるとき、上から i 行目、左から j 列目のマスにAが書き込まれたことを示します。 - A_i の j 文字目が
Bであるとき、上から i 行目、左から j 列目のマスにBが書き込まれたことを示します。 - A_i の j 文字目が
Cであるとき、上から i 行目、左から j 列目のマスにCが書き込まれたことを示します。
正しい書き込み方が複数存在する場合、どれを出力しても構いません。
入力例 1
5 ABCBC ACAAB
出力例 1
Yes AC..B .BA.C C.BA. BA.C. ..CBA
出力例のマス目は以下の条件を全て満たすため、正解として扱われます。
- 全ての行に
A,B,Cがちょうど 1 個ずつ含まれる - 全ての列に
A,B,Cがちょうど 1 個ずつ含まれる - 各行に書かれた最も左の文字は上から順に
A,B,C,B,Cである - 各列に書かれた最も上の文字は左から順に
A,C,A,A,Bである
入力例 2
3 AAA BBB
出力例 2
No
この入力では、条件を満たす書き込み方は存在しません。
Score : 450 points
Problem Statement
You are given an integer N and strings R and C of length N consisting of A, B, and C. Solve the following problem.
There is a N \times N grid. All cells are initially empty.
You can write at most one character from A, B, and C in each cell. (You can also leave the cell empty.)
Determine if it is possible to satisfy all of the following conditions, and if it is possible, print one way to do so.
- Each row and each column contain exactly one
A, oneB, and oneC. - The leftmost character written in the i-th row matches the i-th character of R.
- The topmost character written in the i-th column matches the i-th character of C.
Constraints
- N is an integer between 3 and 5, inclusive.
- R and C are strings of length N consisting of
A,B, andC.
Input
The input is given from Standard Input in the following format:
N R C
Output
If there is no way to fill the grid to satisfy the conditions in the problem statement, print No in one line.
Otherwise, print one such way to fill the grid in the following format:
Yes A_1 A_2 \vdots A_N
The first line should contain Yes.
The i-th of the subsequent N lines should contain a string A_i of length N.
- If the j-th character of A_i is
., it indicates that the cell in the i-th row from the top and the j-th column from the left is empty. - If the j-th character of A_i is
A, it indicates thatAis written in the cell in the i-th row from the top and the j-th column from the left. - If the j-th character of A_i is
B, it indicates thatBis written in the cell in the i-th row from the top and the j-th column from the left. - If the j-th character of A_i is
C, it indicates thatCis written in the cell in the i-th row from the top and the j-th column from the left.
If there are multiple correct ways to fill the grid, you may print any of them.
Sample Input 1
5 ABCBC ACAAB
Sample Output 1
Yes AC..B .BA.C C.BA. BA.C. ..CBA
The grid in the output example satisfies all the following conditions, so it will be treated as correct.
- Each row contains exactly one
A, oneB, and oneC. - Each column contains exactly one
A, oneB, and oneC. - The leftmost characters written in the rows are
A,B,C,B,Cfrom top to bottom. - The topmost characters written in the columns are
A,C,A,A,Bfrom left to right.
Sample Input 2
3 AAA BBB
Sample Output 2
No
For this input, there is no way to fill the grid to satisfy the conditions.
Time Limit: 6 sec / Memory Limit: 1024 MiB
配点 : 475 点
問題文
長さ N の数列 A=(A_1,A_2,\dots,A_N) があり、最初全ての項が 0 です。
入力で与えられる整数 K を用いて関数 f(A) を以下のように定義します。
- A を降順に (広義単調減少となるように) ソートしたものを B とする。
- このとき、 f(A)=B_1 + B_2 + \dots + B_K とする。
この数列に合計 Q 回の更新を行うことを考えます。
数列 A に対し以下の更新を i=1,2,\dots,Q の順に行い、各更新ごとにその時点での f(A) の値を出力してください。
- A_{X_i} を Y_i に変更する。
制約
- 入力は全て整数
- 1 \le K \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le X_i \le N
- 0 \le Y_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
出力
全体で Q 行出力せよ。そのうち i 行目には i 回目の更新を終えた時点での f(A) の値を整数として出力せよ。
入力例 1
4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0
出力例 1
5 6 8 8 15 13 13 11 1 0
この入力では N=4,K=2 です。 Q=10 回の更新を行います。
- 1 回目の更新を受けて A=(5,0,0,0) となります。このとき f(A)=5 です。
- 2 回目の更新を受けて A=(5,1,0,0) となります。このとき f(A)=6 です。
- 3 回目の更新を受けて A=(5,1,3,0) となります。このとき f(A)=8 です。
- 4 回目の更新を受けて A=(5,1,3,2) となります。このとき f(A)=8 です。
- 5 回目の更新を受けて A=(5,10,3,2) となります。このとき f(A)=15 です。
- 6 回目の更新を受けて A=(0,10,3,2) となります。このとき f(A)=13 です。
- 7 回目の更新を受けて A=(0,10,3,0) となります。このとき f(A)=13 です。
- 8 回目の更新を受けて A=(0,10,1,0) となります。このとき f(A)=11 です。
- 9 回目の更新を受けて A=(0,0,1,0) となります。このとき f(A)=1 です。
- 10 回目の更新を受けて A=(0,0,0,0) となります。このとき f(A)=0 です。
Score : 475 points
Problem Statement
We have a sequence A=(A_1,A_2,\dots,A_N) of length N. Initially, all the terms are 0.
Using an integer K given in the input, we define a function f(A) as follows:
- Let B be the sequence obtained by sorting A in descending order (so that it becomes monotonically non-increasing).
- Then, let f(A)=B_1 + B_2 + \dots + B_K.
We consider applying Q updates on this sequence.
Apply the following operation on the sequence A for i=1,2,\dots,Q in this order, and print the value f(A) at that point after each update.
- Change A_{X_i} to Y_i.
Constraints
- All input values are integers.
- 1 \le K \le N \le 5 \times 10^5
- 1 \le Q \le 5 \times 10^5
- 1 \le X_i \le N
- 0 \le Y_i \le 10^9
Input
The input is given from Standard Input in the following format:
N K Q X_1 Y_1 X_2 Y_2 \vdots X_Q Y_Q
Output
Print Q lines in total. The i-th line should contain the value f(A) as an integer when the i-th update has ended.
Sample Input 1
4 2 10 1 5 2 1 3 3 4 2 2 10 1 0 4 0 3 1 2 0 3 0
Sample Output 1
5 6 8 8 15 13 13 11 1 0
In this input, N=4 and K=2. Q=10 updates are applied.
- The 1-st update makes A=(5, 0,0,0). Now, f(A)=5.
- The 2-nd update makes A=(5, 1,0,0). Now, f(A)=6.
- The 3-rd update makes A=(5, 1,3,0). Now, f(A)=8.
- The 4-th update makes A=(5, 1,3,2). Now, f(A)=8.
- The 5-th update makes A=(5,10,3,2). Now, f(A)=15.
- The 6-th update makes A=(0,10,3,2). Now, f(A)=13.
- The 7-th update makes A=(0,10,3,0). Now, f(A)=13.
- The 8-th update makes A=(0,10,1,0). Now, f(A)=11.
- The 9-th update makes A=(0, 0,1,0). Now, f(A)=1.
- The 10-th update makes A=(0, 0,0,0). Now, f(A)=0.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
長さ N の正整数列 A=(A_1,A_2,\ldots,A_N), B=(B_1,B_2,\ldots,B_N) が与えられます。
Q 個のクエリが与えられるので順に処理してください。i 番目のクエリは以下で説明されます。
- 正整数 l_i,r_i,L_i,R_i が与えられる。数列 (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) を並び替えることで (B_{L_i},B_{L_i+1},\ldots,B_{R_i}) に一致させることができるならば
Yesを、できないならばNoを出力せよ。
制約
- 1\leq N,Q\leq 2\times 10^5
- 1\leq A_i,B_i\leq N
- 1\leq l_i \leq r_i\leq N
- 1\leq L_i \leq R_i\leq N
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N l_1 r_1 L_1 R_1 l_2 r_2 L_2 R_2 \vdots l_Q r_Q L_Q R_Q
出力
Q 行出力せよ。i 行目には i 番目のクエリの答えを出力せよ。
入力例 1
5 4 1 2 3 2 4 2 3 1 4 2 1 3 1 3 1 2 3 5 1 4 2 5 1 5 1 5
出力例 1
Yes No No Yes
- 1 番目のクエリについて、(1,2,3) を並び替えることで (2,3,1) に一致させることができます。よって
Yesを出力します。 - 2 番目のクエリについて、(1,2) をどのように並び替えても (1,4,2) に一致させることができません。よって
Noを出力します。 - 3 番目のクエリについて、(1,2,3,2) をどのように並び替えても (3,1,4,2) に一致させることができません。よって
Noを出力します。 - 4 番目のクエリについて、(1,2,3,2,4) を並び替えることで (2,3,1,4,2) に一致させることができます。よって
Yesを出力します。
入力例 2
4 4 4 4 4 4 4 4 4 4 1 2 2 3 3 3 1 1 1 3 1 4 1 4 2 3
出力例 2
Yes Yes No No
Score : 500 points
Problem Statement
You are given sequences of positive integers of length N: A=(A_1,A_2,\ldots,A_N) and B=(B_1,B_2,\ldots,B_N).
You are given Q queries to process in order. The i-th query is explained below.
- You are given positive integers l_i,r_i,L_i,R_i. Print
Yesif it is possible to rearrange the subsequence (A_{l_i},A_{l_i+1},\ldots,A_{r_i}) to match the subsequence (B_{L_i},B_{L_i+1},\ldots,B_{R_i}), andNootherwise.
Constraints
- 1\leq N,Q\leq 2\times 10^5
- 1\leq A_i,B_i\leq N
- 1\leq l_i \leq r_i\leq N
- 1\leq L_i \leq R_i\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N Q A_1 A_2 \ldots A_N B_1 B_2 \ldots B_N l_1 r_1 L_1 R_1 l_2 r_2 L_2 R_2 \vdots l_Q r_Q L_Q R_Q
Output
Print Q lines. The i-th line should contain the answer to the i-th query.
Sample Input 1
5 4 1 2 3 2 4 2 3 1 4 2 1 3 1 3 1 2 3 5 1 4 2 5 1 5 1 5
Sample Output 1
Yes No No Yes
- For the 1st query, it is possible to rearrange (1,2,3) to match (2,3,1). Hence, we print
Yes. - For the 2nd query, it is impossible to rearrange (1,2) in any way to match (1,4,2). Hence, we print
No. - For the 3rd query, it is impossible to rearrange (1,2,3,2) in any way to match (3,1,4,2). Hence, we print
No. - For the 4th query, it is possible to rearrange (1,2,3,2,4) to match (2,3,1,4,2). Hence, we print
Yes.
Sample Input 2
4 4 4 4 4 4 4 4 4 4 1 2 2 3 3 3 1 1 1 3 1 4 1 4 2 3
Sample Output 2
Yes Yes No No