Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 233 点
問題文
高橋君は山頂を目指して登山道を歩いています。
登山道には 1 から N までの番号がついた N 個のチェックポイントがあり、チェックポイント i の気温は T_i 度です。
高橋君はチェックポイント 1 から出発し、2, 3, \dots, N の順にすべてのチェックポイントを通過して山頂（チェックポイント N）に到達します。
チェックポイント i（2 \le i \le N）において、直前のチェックポイントとの気温差の絶対値が基準値 K 以上であるとき、すなわち |T_i - T_{i-1}| \geq K であるとき、チェックポイント i で 急変 が起きるといいます。
チェックポイント 2, 3, \dots, N のうち、急変が起きるチェックポイントの個数を求めてください。
制約
- 2 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- -10^9 \leq T_i \leq 10^9
- 入力はすべて整数である
入力
N K T_1 T_2 \vdots T_N
- 1 行目には、チェックポイントの数 N と、急変の基準値 K がスペース区切りで与えられる。
- 続く N 行には、チェックポイントの気温が順に与えられる。このうち i 番目の行（1 \le i \le N）には、チェックポイント i の気温 T_i が与えられる。
出力
急変が起きるチェックポイントの個数を 1 行で出力してください。
入力例 1
5 3 10 12 15 14 20
出力例 1
2
入力例 2
4 10 5 8 3 12
出力例 2
0
入力例 3
10 5 0 -4 2 7 1 10 6 -1 4 4
出力例 3
6
入力例 4
20 100 0 50 -60 40 140 139 239 100 0 -100 -50 49 149 300 201 101 1 -98 -198 -97
出力例 4
13
入力例 5
2 1000000000 -1000000000 0
出力例 5
1
Score : 233 pts
Problem Statement
Takahashi is walking along a mountain trail aiming for the summit.
There are N checkpoints numbered from 1 to N along the trail, and the temperature at checkpoint i is T_i degrees.
Takahashi starts from checkpoint 1 and passes through all checkpoints in the order 2, 3, \dots, N to reach the summit (checkpoint N).
At checkpoint i (2 \le i \le N), if the absolute difference in temperature from the previous checkpoint is at least the threshold value K, that is, if |T_i - T_{i-1}| \geq K, we say a sudden change occurs at checkpoint i.
Among checkpoints 2, 3, \dots, N, find the number of checkpoints where a sudden change occurs.
Constraints
- 2 \leq N \leq 10^5
- 1 \leq K \leq 10^9
- -10^9 \leq T_i \leq 10^9
- All inputs are integers
Input
N K T_1 T_2 \vdots T_N
- The first line contains the number of checkpoints N and the threshold value for sudden changes K, separated by a space.
- The following N lines give the temperatures at the checkpoints in order. The i-th of these lines (1 \le i \le N) gives the temperature T_i at checkpoint i.
Output
Print the number of checkpoints where a sudden change occurs, in a single line.
Sample Input 1
5 3 10 12 15 14 20
Sample Output 1
2
Sample Input 2
4 10 5 8 3 12
Sample Output 2
0
Sample Input 3
10 5 0 -4 2 7 1 10 6 -1 4 4
Sample Output 3
6
Sample Input 4
20 100 0 50 -60 40 140 139 239 100 0 -100 -50 49 149 300 201 101 1 -98 -198 -97
Sample Output 4
13
Sample Input 5
2 1000000000 -1000000000 0
Sample Output 5
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君の住む街には、N 個の地点が一列に並んだ一本道があります。左から順に地点 1, 地点 2, \ldots, 地点 N と番号が付けられています。
隣り合う地点 i と地点 i + 1 (1 \leq i \leq N-1) の間の区間について、通行止めかどうかが整数 W_i によって表されます。W_i = 1 のとき、その区間は工事のため通行止めであり、通り抜けることができません。W_i = 0 のとき、その区間は自由に通行できます。
高橋君は M 枚の工事完了許可証を持っています。高橋君は移動を始める前に、通行止めの区間（W_i = 1 である区間）の中から最大 M 個まで区間を選び、選んだ各区間に許可証を 1 枚ずつ使用できます。許可証を使用された区間は通行止めが解除され、自由に通行できるようになります。同じ区間に 2 枚以上の許可証を使用することはできません。また、許可証の使用先はすべて移動開始前に決定し、移動中に追加で使用することはできません。
高橋君は地点 1 から出発します。通行止めでない区間（もともと W_i = 0 である区間、および許可証により通行止めが解除された区間）を通って、隣接する地点間を双方向に何度でも移動できます。
許可証を使用する区間を最適に選んだとき、高橋君が地点 1 から到達できる地点の数（地点 1 自身を含む）を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq N - 1
- W_i \in \{0, 1\} (1 \leq i \leq N-1)
- 入力はすべて整数である
入力
N M
W_1 W_2 \ldots W_{N-1}
- 1 行目には、地点の数を表す整数 N と、許可証の枚数を表す整数 M が、スペース区切りで与えられる。
- 2 行目には、隣接する地点間の通行止めの有無を表す N - 1 個の整数 W_1, W_2, \ldots, W_{N-1} が、スペース区切りで与えられる。N = 1 のとき区間は存在しないため、2 行目には何も出力されない（空行が与えられる）。
- W_i は地点 i と地点 i + 1 の間の区間が通行止めかどうかを表し、1 なら通行止め、0 なら通行可能であることを意味する。
出力
高橋君が許可証を最適に使用したとき、到達できる地点の数を 1 行で出力せよ。
入力例 1
7 2 0 1 0 1 1 0
出力例 1
5
入力例 2
10 0 0 0 1 0 0 0 1 0 0
出力例 2
3
入力例 3
15 3 1 0 0 1 0 1 0 0 1 1 0 0 1 0
出力例 3
9
Score : 300 pts
Problem Statement
In the town where Takahashi lives, there is a straight road with N points arranged in a line. They are numbered from left to right as point 1, point 2, \ldots, point N.
For each section between adjacent points i and i + 1 (1 \leq i \leq N-1), whether it is closed or not is represented by an integer W_i. When W_i = 1, the section is closed due to construction and cannot be passed through. When W_i = 0, the section can be freely traversed.
Takahashi has M construction completion permits. Before starting his journey, Takahashi can select up to M closed sections (sections where W_i = 1) and use one permit on each selected section. A section on which a permit is used has its closure lifted and becomes freely traversable. It is not possible to use two or more permits on the same section. Additionally, all permits must be assigned before the journey begins; no additional permits can be used during the journey.
Takahashi starts at point 1. He can travel between adjacent points any number of times in both directions through sections that are not closed (sections that originally have W_i = 0, as well as sections whose closure has been lifted by a permit).
When the sections to use permits on are chosen optimally, find the number of points that Takahashi can reach from point 1 (including point 1 itself).
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq M \leq N - 1
- W_i \in \{0, 1\} (1 \leq i \leq N-1)
- All input values are integers.
Input
N M
W_1 W_2 \ldots W_{N-1}
- The first line contains an integer N representing the number of points and an integer M representing the number of permits, separated by a space.
- The second line contains N - 1 integers W_1, W_2, \ldots, W_{N-1} representing whether each section between adjacent points is closed or not, separated by spaces. When N = 1, there are no sections, so the second line is empty (an empty line is given).
- W_i represents whether the section between point i and point i + 1 is closed: 1 means closed, and 0 means passable.
Output
Print in one line the number of points Takahashi can reach when he uses his permits optimally.
Sample Input 1
7 2 0 1 0 1 1 0
Sample Output 1
5
Sample Input 2
10 0 0 0 1 0 0 0 1 0 0
Sample Output 2
3
Sample Input 3
15 3 1 0 0 1 0 1 0 0 1 1 0 0 1 0
Sample Output 3
9
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 366 点
問題文
高橋君は N 個の貯金箱を管理しています。それぞれの貯金箱には 1 から N までの番号が付けられています。
各貯金箱 i（1 \leq i \leq N）には、初期状態で A_i 円が入っています。これから Q 回の操作が順番に行われます。各操作は以下の 2 種類のいずれかです：
- 種類 1（入金）：正の整数 L, R, X が与えられる。貯金箱 L, L+1, \ldots, R のそれぞれに X 円ずつ入金する。すなわち、これらの貯金箱の金額がそれぞれ X 円増加する。
- 種類 2（確認）：整数 P が与えられる。貯金箱 P の現在の金額を確認する。
高橋君のために、種類 2 の操作が行われるたびに、その時点で貯金箱 P に入っている金額を求めてください。
制約
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 種類 1 の操作において、1 \leq L \leq R \leq N
- 種類 1 の操作において、1 \leq X \leq 10^4
- 種類 2 の操作において、1 \leq P \leq N
- 種類 2 の操作は 1 回以上存在する
- 入力はすべて整数
- 種類 2 の操作における答え（出力する金額）は 10^{18} 以下であることが保証される
入力
入力は以下の形式で標準入力から与えられる。
N Q A_1 A_2 \ldots A_N query_1 query_2 \vdots query_Q
- 1 行目には、貯金箱の個数 N と操作の回数 Q が、スペース区切りで与えられる。
- 2 行目には、各貯金箱の初期金額 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
- 続く Q 行にわたって、各操作の情報 query_1, query_2, \ldots, query_Q が 1 行ずつ与えられる。各 query_i は先頭の整数が操作の種類を表し、以下のいずれかの形式である。
- 種類 1 の場合：
1L R X（貯金箱 L から R までのそれぞれに X 円入金する） - 種類 2 の場合：
2P（貯金箱 P の金額を確認する）
出力
種類 2 の操作が行われるたびに、その時点で貯金箱 P に入っている金額を 1 行に出力せよ。
入力例 1
5 4 10 20 30 40 50 2 3 1 2 4 5 2 3 2 1
出力例 1
30 35 10
入力例 2
8 7 100 200 300 400 500 600 700 800 1 1 5 10 1 3 8 20 2 3 2 6 1 1 8 100 2 1 2 8
出力例 2
330 620 210 920
入力例 3
10 10 0 1000000000 500 0 999999999 1 2 3 4 5 1 1 10 10000 2 2 1 5 5 3 2 5 1 1 1 1 2 1 1 3 7 100 2 4 2 10 2 7
出力例 3
1000010000 1000010002 10001 10100 10005 10102
Score : 366 pts
Problem Statement
Takahashi manages N piggy banks. Each piggy bank is numbered from 1 to N.
Each piggy bank i (1 \leq i \leq N) initially contains A_i yen. From now on, Q operations will be performed in order. Each operation is one of the following two types:
- Type 1 (deposit): Positive integers L, R, X are given. Deposit X yen into each of the piggy banks L, L+1, \ldots, R. That is, the amount in each of these piggy banks increases by X yen.
- Type 2 (check): An integer P is given. Check the current amount in piggy bank P.
For each Type 2 operation, determine the amount of money currently in piggy bank P.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- For Type 1 operations, 1 \leq L \leq R \leq N
- For Type 1 operations, 1 \leq X \leq 10^4
- For Type 2 operations, 1 \leq P \leq N
- There is at least one Type 2 operation
- All input values are integers
- It is guaranteed that the answer for each Type 2 operation (the amount to output) is at most 10^{18}
Input
Input is given from standard input in the following format.
N Q A_1 A_2 \ldots A_N query_1 query_2 \vdots query_Q
- The first line contains the number of piggy banks N and the number of operations Q, separated by a space.
- The second line contains the initial amounts A_1, A_2, \ldots, A_N in each piggy bank, separated by spaces.
- The following Q lines each contain the information for one operation query_1, query_2, \ldots, query_Q. The leading integer of each query_i indicates the type of operation, and the format is one of the following:
- Type 1:
1L R X (deposit X yen into each piggy bank from L to R) - Type 2:
2P (check the amount in piggy bank P)
Output
For each Type 2 operation, output the amount of money currently in piggy bank P on a single line.
Sample Input 1
5 4 10 20 30 40 50 2 3 1 2 4 5 2 3 2 1
Sample Output 1
30 35 10
Sample Input 2
8 7 100 200 300 400 500 600 700 800 1 1 5 10 1 3 8 20 2 3 2 6 1 1 8 100 2 1 2 8
Sample Output 2
330 620 210 920
Sample Input 3
10 10 0 1000000000 500 0 999999999 1 2 3 4 5 1 1 10 10000 2 2 1 5 5 3 2 5 1 1 1 1 2 1 1 3 7 100 2 4 2 10 2 7
Sample Output 3
1000010000 1000010002 10001 10100 10005 10102
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
高橋君は、N 人の子どもたちにケーキを配る係を任されました。子どもたちは左から順に子ども 1, 子ども 2, ..., 子ども N と番号が付けられており、一列に並んでいます。
現在、子ども i は A_i 個のケーキを持っています。高橋君は、すべての子どもが同じ数のケーキを持つように調整したいと考えています。
高橋君は以下の操作を何度でも行うことができます：
- 隣り合う2人の子ども（子ども j と子ども j+1、ただし 1 \leq j \leq N-1）を選び、どちらか一方から他方へケーキを 1 個移動させる。ただし、ケーキを 0 個しか持っていない子どもからケーキを移動させることはできない。
ケーキの総数は操作を通じて変わりません。新たにケーキを追加したり、ケーキを捨てたりすることはできません。
すべての子どもが持っているケーキの数を等しくするために必要な操作の最小回数を求めてください。ただし、ケーキの総数が N で割り切れず、目標を達成することが不可能な場合は -1 を出力してください。
制約
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- 入力はすべて整数
入力
N A_1 A_2 \cdots A_N
- 1 行目には、子どもの人数を表す整数 N が与えられる。
- 2 行目には、各子どもが持っているケーキの個数を表す N 個の整数 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
出力
すべての子どものケーキの個数を等しくするために必要な最小操作回数を 1 行で出力してください。目標を達成することが不可能な場合は -1 を出力してください。
入力例 1
3 1 2 3
出力例 1
2
入力例 2
3 1 2 4
出力例 2
-1
入力例 3
5 0 0 0 0 10
出力例 3
20
Score : 400 pts
Problem Statement
Takahashi has been assigned the task of distributing cakes to N children. The children are numbered child 1, child 2, ..., child N from left to right, and they are standing in a single line.
Currently, child i has A_i cakes. Takahashi wants to adjust the cakes so that all children have the same number of cakes.
Takahashi can perform the following operation any number of times:
- Choose two adjacent children (child j and child j+1, where 1 \leq j \leq N-1), and move 1 cake from one of them to the other. However, it is not possible to move a cake from a child who has 0 cakes.
The total number of cakes does not change through operations. It is not possible to add new cakes or discard cakes.
Find the minimum number of operations required to make the number of cakes held by all children equal. If the total number of cakes is not divisible by N and it is impossible to achieve the goal, output -1.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \leq A_i \leq 10^9
- All inputs are integers
Input
N A_1 A_2 \cdots A_N
- The first line contains an integer N representing the number of children.
- The second line contains N integers A_1, A_2, \ldots, A_N separated by spaces, representing the number of cakes each child has.
Output
Output in one line the minimum number of operations required to make the number of cakes equal for all children. If it is impossible to achieve the goal, output -1.
Sample Input 1
3 1 2 3
Sample Output 1
2
Sample Input 2
3 1 2 4
Sample Output 2
-1
Sample Input 3
5 0 0 0 0 10
Sample Output 3
20
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 466 点
問題文
高橋君は英小文字からなる長さ N の文字列 S で表される曲を持っています。
高橋君の音楽プレイヤーにはリピート再生機能があり、曲が終わると自動的に最初から再び再生されます。これにより、文字列 S を無限に繰り返し連結した文字列 S^{\infty} = SSS\ldots が流れ続けることになります。より正確には、S^{\infty} の第 k 文字目（k = 1, 2, 3, \ldots）は、S の第 ((k - 1) \bmod N) + 1 文字目です。ここで a \bmod b は a を b で割った余りであり、0 以上 b 未満の整数です。
青木君は高橋君に Q 個の質問をします。i 番目の質問では、2つの整数 L_i, R_i（1 \leq L_i \leq R_i）が与えられます。T_i を、S^{\infty} の第 L_i 文字目から第 R_i 文字目までの連続部分文字列とします。T_i の長さは R_i - L_i + 1 です。
各質問に対して、T_i が元の文字列 S の連続部分文字列として出現するかどうかを判定してください。すなわち、1 \leq p かつ p + (R_i - L_i + 1) - 1 \leq N を満たす整数 p が存在して、S の第 p 文字目から第 p + (R_i - L_i + 1) - 1 文字目までの連続部分文字列が T_i と一致するかどうかを判定してください。
なお、T_i の長さ R_i - L_i + 1 が N を超える場合、T_i は長さ N の文字列 S の連続部分文字列にはなりえないため、答えは必ず No です。
制約
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- S は長さ N の英小文字からなる文字列
- 1 \leq L_i \leq R_i \leq 10^{18}
- 入力で与えられる数値はすべて整数である
入力
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- 1 行目には、文字列の長さを表す整数 N と、質問の数を表す整数 Q が、スペース区切りで与えられる。
- 2 行目には、曲を表す長さ N の文字列 S が与えられる。
- 続く Q 行にわたって、各質問が与えられる。
- 2 + i 行目（1 \leq i \leq Q）には、i 番目の質問を表す整数 L_i と R_i がスペース区切りで与えられる。
出力
Q 行出力せよ。i 行目には、i 番目の質問に対して、T_i が S の連続部分文字列として出現するならば Yes を、そうでなければ No を出力せよ。
入力例 1
5 5 abcab 1 3 4 7 5 6 3 7 11 13
出力例 1
Yes No No No Yes
入力例 2
3 4 aab 1 4 4 6 2 4 1 3
出力例 2
No Yes No Yes
入力例 3
10 8 abracadabr 1 10 11 20 5 14 3 5 1 11 15 18 7 13 100 103
出力例 3
Yes Yes No Yes No Yes No No
入力例 4
20 10 abcdeabcdfabcdeabcdf 1 10 11 20 5 16 21 40 1 21 18 23 3 7 100000000000000000 1000000000000000000 35 39 6 10
出力例 4
Yes Yes Yes Yes No Yes Yes No Yes Yes
入力例 5
1 3 a 1 1 1000000000000000000 1000000000000000000 999999999999999999 1000000000000000000
出力例 5
Yes Yes No
Score : 466 pts
Problem Statement
Takahashi has a song represented by a string S of length N consisting of lowercase English letters.
Takahashi's music player has a repeat playback feature that automatically replays the song from the beginning when it ends. As a result, the string S infinitely concatenated with itself, S^{\infty} = SSS\ldots, plays continuously. More precisely, the k-th character of S^{\infty} (k = 1, 2, 3, \ldots) is the ((k - 1) \bmod N) + 1-th character of S. Here, a \bmod b is the remainder when a is divided by b, which is an integer at least 0 and less than b.
Aoki asks Takahashi Q questions. In the i-th question, two integers L_i and R_i (1 \leq L_i \leq R_i) are given. Let T_i be the contiguous substring of S^{\infty} from the L_i-th character to the R_i-th character. The length of T_i is R_i - L_i + 1.
For each question, determine whether T_i appears as a contiguous substring of the original string S. That is, determine whether there exists an integer p satisfying 1 \leq p and p + (R_i - L_i + 1) - 1 \leq N such that the contiguous substring of S from the p-th character to the p + (R_i - L_i + 1) - 1-th character matches T_i.
Note that if the length R_i - L_i + 1 of T_i exceeds N, then T_i cannot be a contiguous substring of the string S of length N, so the answer is always No.
Constraints
- 1 \leq N \leq 5 \times 10^5
- 1 \leq Q \leq 2 \times 10^5
- S is a string of length N consisting of lowercase English letters
- 1 \leq L_i \leq R_i \leq 10^{18}
- All numerical values given in the input are integers
Input
N Q S L_1 R_1 L_2 R_2 \vdots L_Q R_Q
- The first line contains an integer N representing the length of the string and an integer Q representing the number of questions, separated by a space.
- The second line contains the string S of length N representing the song.
- The following Q lines contain each question.
- The (2 + i)-th line (1 \leq i \leq Q) contains the integers L_i and R_i representing the i-th question, separated by a space.
Output
Output Q lines. On the i-th line, output Yes if T_i appears as a contiguous substring of S, and No otherwise.
Sample Input 1
5 5 abcab 1 3 4 7 5 6 3 7 11 13
Sample Output 1
Yes No No No Yes
Sample Input 2
3 4 aab 1 4 4 6 2 4 1 3
Sample Output 2
No Yes No Yes
Sample Input 3
10 8 abracadabr 1 10 11 20 5 14 3 5 1 11 15 18 7 13 100 103
Sample Output 3
Yes Yes No Yes No Yes No No
Sample Input 4
20 10 abcdeabcdfabcdeabcdf 1 10 11 20 5 16 21 40 1 21 18 23 3 7 100000000000000000 1000000000000000000 35 39 6 10
Sample Output 4
Yes Yes Yes Yes No Yes Yes No Yes Yes
Sample Input 5
1 3 a 1 1 1000000000000000000 1000000000000000000 999999999999999999 1000000000000000000
Sample Output 5
Yes Yes No