実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
整数 A, B が与えられます。 A^B の値を出力してください。
制約
- 1 \leq A, B \leq 9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
A B
出力
答えを出力せよ。
入力例 1
4 3
出力例 1
64
4^3 = 64 であるので、64 を出力します。
入力例 2
5 5
出力例 2
3125
入力例 3
8 1
出力例 3
8
Score : 100 points
Problem Statement
Given integers A and B, print the value A^B.
Constraints
- 1 \leq A, B \leq 9
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
A B
Output
Print the answer.
Sample Input 1
4 3
Sample Output 1
64
4^3 = 64, so 64 should be printed.
Sample Input 2
5 5
Sample Output 2
3125
Sample Input 3
8 1
Sample Output 3
8
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
英大文字と英小文字からなる文字列 S が与えられます。S の英大文字のみを元の順序で連結して得られる文字列を出力してください。
制約
- S は英大文字と英小文字からなる文字列である
- S の長さは 1 以上 100 以下である
入力
入力は以下の形式で標準入力から与えられる。
S
出力
S の英大文字のみを元の順序で連結して得られる文字列を出力せよ。
入力例 1
AtCoderBeginnerContest
出力例 1
ACBC
S の英大文字のみを元の順序で連結して得られる文字列は ACBC です。よって、ACBC を出力します。
入力例 2
PaymentRequired
出力例 2
PR
入力例 3
program
出力例 3
S に英大文字が含まれないことがあることに注意してください。
Score : 100 points
Problem Statement
You are given a string S consisting of uppercase and lowercase English letters. Print the string obtained by concatenating only the uppercase letters of S in their original order.
Constraints
- S is a string of uppercase and lowercase English letters.
- The length of S is between 1 and 100, inclusive.
Input
The input is given from Standard Input in the following format:
S
Output
Print the string obtained by concatenating only the uppercase letters of S in their original order.
Sample Input 1
AtCoderBeginnerContest
Sample Output 1
ACBC
The string obtained by concatenating only the uppercase letters of S in their original order is ACBC. Hence, print ACBC.
Sample Input 2
PaymentRequired
Sample Output 2
PR
Sample Input 3
program
Sample Output 3
Note that S may contain no uppercase letters.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
高橋君は英小文字からなる文字列 S を持っています。
高橋君は文字列 S に対して、下記の操作をちょうど 1 回行います。
- まず、非負整数 K を選ぶ。
- その後、S の各文字を K 個後ろの英小文字に変更する。
ただし、
aの 1 個後ろの英小文字はbであり、bの 1 個後ろの英小文字はcであり、cの 1 個後ろの英小文字はdであり、- \cdots
yの 1 個後ろの英小文字はzであり、zの 1 個後ろの英小文字はaです。
例えば、b の 4 個後ろの英小文字は f であり、y の 3 個後ろの英小文字は b です。
文字列 T が与えられます。 高橋君が上記の操作によって S を T に一致させることができるかを判定してください。
制約
- S と T はそれぞれ英小文字からなる長さ 1 以上 10^5 以下の文字列
- S の長さと T の長さは等しい
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
高橋君が S を T に一致させることができる場合は Yes と出力し、
できない場合は No と出力せよ。
入力例 1
abc ijk
出力例 1
Yes
高橋君が K=8 を選ぶと、
aは 8 個後ろのiにbは 8 個後ろのjにcは 8 個後ろのkに
それぞれ変更され、S と T が一致します。
高橋君が S を T に一致させることができるため Yes と出力します。
入力例 2
z a
出力例 2
Yes
高橋君が K=1 を選ぶと S と T が一致します。
z の 1 個後ろの英小文字は a であることに注意してください。
入力例 3
ppq qqp
出力例 3
No
高橋君は非負整数 K をどのように選んでも S を T に一致させることができません。
よって、No と出力します。
入力例 4
atcoder atcoder
出力例 4
Yes
高橋君が K=0 を選ぶと S と T が一致します。
Score : 200 points
Problem Statement
Takahashi has a string S consisting of lowercase English letters.
On this string, he will do the operation below just once.
- First, choose a non-negative integer K.
- Then, shift each character of S to the right by K (see below).
Here,
ashifted to the right by 1 isb;bshifted to the right by 1 isc;cshifted to the right by 1 isd;- \cdots
yshifted to the right by 1 isz;zshifted to the right by 1 isa.
For example, b shifted to the right by 4 is f, and y shifted to the right by 3 is b.
You are given a string T. Determine whether Takahashi can make S equal T by the operation above.
Constraints
- Each of S and T is a string of length between 1 and 10^5 (inclusive) consisting of lowercase English letters.
- The lengths of S and T are equal.
Input
Input is given from Standard Input in the following format:
S T
Output
If Takahashi can make S equal T, print Yes; if not, print No.
Sample Input 1
abc ijk
Sample Output 1
Yes
When Takahashi chooses K=8,
ais shifted to the right by 8 and becomesi,bis shifted to the right by 8 and becomesj,cis shifted to the right by 8 and becomesk,
and now S and T are equal.
Therefore, he can make S equal T, so Yes should be printed.
Sample Input 2
z a
Sample Output 2
Yes
Choosing K=1 makes S and T equal.
Note that the letter on the right of z is a.
Sample Input 3
ppq qqp
Sample Output 3
No
There is no non-negative integer K that he can choose to make S equal T, so No should be printed.
Sample Input 4
atcoder atcoder
Sample Output 4
Yes
Choosing K=0 makes S and T equal.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
ある測定では、時刻 0,1,\dots,T におけるセンサーの測定値を以下の規則で記録します。
- 時刻 0 では、測定値を保存する。
- 時刻 1,2,\dots,T では、「現時刻の測定値」と「直前に保存された測定値」との差の絶対値が X 以上であるとき、またその時に限り値を保存する。
時刻 i=0,1,\dots,T におけるセンサーの測定値は A_i でした。
測定値が保存された時刻と保存された値とを、時刻の昇順に出力してください。
制約
- 1 \le T \le 100
- 1 \le X \le 100
- 0 \le A_i \le 100
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
T X A_0 A_1 \dots A_T
出力
測定値が k 回保存され、そのうち時刻の昇順に並べた時に i 回目の時刻が t_i 、測定値が a_i であったとき、以下の形式で出力せよ。
t_1 a_1 t_2 a_2 \vdots t_k a_k
入力例 1
6 10 30 35 40 21 30 12 31
出力例 1
0 30 2 40 3 21 6 31
測定は以下の流れで進行します。
- 時刻 0 の測定値は 30 であった。これを保存する。
- 時刻 1 の測定値は 35 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 未満であるため、保存しない。
- 時刻 2 の測定値は 40 であった。最後に保存された測定値は 30 であり、この値との差の絶対値が 10 以上であるため、保存する。
- 時刻 3 の測定値は 21 であった。最後に保存された測定値は 40 であり、この値との差の絶対値が 10 以上であるため、保存する。
- 時刻 4 の測定値は 30 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
- 時刻 5 の測定値は 12 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 未満であるため、保存しない。
- 時刻 6 の測定値は 31 であった。最後に保存された測定値は 21 であり、この値との差の絶対値が 10 以上であるため、保存する。
Score : 200 points
Problem Statement
In a certain measurement, the sensor readings at times 0,1,\dots,T are recorded according to the following rules.
- At time 0, the reading is saved.
- At times 1,2,\dots,T, the reading is saved if and only if the absolute difference between the current reading and the most recently saved reading is at least X.
The sensor reading at time i=0,1,\dots,T was A_i.
Output the times at which readings were saved and the saved values, in ascending order of time.
Constraints
- 1 \le T \le 100
- 1 \le X \le 100
- 0 \le A_i \le 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
T X A_0 A_1 \dots A_T
Output
If k readings were saved, and the i-th saved reading in ascending order of time was at time t_i with value a_i, output in the following format:
t_1 a_1 t_2 a_2 \vdots t_k a_k
Sample Input 1
6 10 30 35 40 21 30 12 31
Sample Output 1
0 30 2 40 3 21 6 31
The measurement proceeds as follows.
- The reading at time 0 is 30. Save it.
- The reading at time 1 is 35. The most recently saved reading is 30, and the absolute difference is less than 10, so it is not saved.
- The reading at time 2 is 40. The most recently saved reading is 30, and the absolute difference is at least 10, so it is saved.
- The reading at time 3 is 21. The most recently saved reading is 40, and the absolute difference is at least 10, so it is saved.
- The reading at time 4 is 30. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
- The reading at time 5 is 12. The most recently saved reading is 21, and the absolute difference is less than 10, so it is not saved.
- The reading at time 6 is 31. The most recently saved reading is 21, and the absolute difference is at least 10, so it is saved.
実行時間制限: 4 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
縦 N マス、横 N マスの N ^ 2 マスからなるマス目があります。 上から i 行目 (1\leq i\leq N) 、左から j 列目 (1\leq j\leq N) のマスをマス (i,j) と呼ぶことにします。
それぞれのマスは、空マスであるかコマが置かれているかのどちらかです。 マス目には合計で M 個のコマが置かれており、k 番目 (1\leq k\leq M) のコマはマス (a _ k,b _ k) に置かれています。
あなたは、すでに置かれているどのコマにも取られないように、いずれかの空マスに自分のコマを置きたいです。
マス (i,j) に置かれているコマは、次のどれかの条件を満たすコマを取ることができます。
- マス (i+2,j+1) に置かれている
- マス (i+1,j+2) に置かれている
- マス (i-1,j+2) に置かれている
- マス (i-2,j+1) に置かれている
- マス (i-2,j-1) に置かれている
- マス (i-1,j-2) に置かれている
- マス (i+1,j-2) に置かれている
- マス (i+2,j-1) に置かれている
ただし、存在しないマスについての条件は常に満たされないものとします。
たとえば、マス (4,4) に置かれているコマは、以下の図で青く示されたマスに置かれているコマを取ることができます。

あなたがコマを置くことができるマスがいくつあるか求めてください。
制約
- 1\leq N\leq10 ^ 9
- 1\leq M\leq2\times10 ^ 5
- 1\leq a _ k\leq N,1\leq b _ k\leq N\ (1\leq k\leq M)
- (a _ k,b _ k)\neq(a _ l,b _ l)\ (1\leq k\lt l\leq M)
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M a _ 1 b _ 1 a _ 2 b _ 2 \vdots a _ M b _ M
出力
すでに置かれているコマに取られずに自分のコマを置くことができる空マスの個数を出力せよ。
入力例 1
8 6 1 4 2 1 3 8 4 5 5 2 8 3
出力例 1
38
すでに置かれているコマは、以下の図で青く示されたマスに置かれたコマを取ることができます。

よって、あなたがすでに置かれているコマに取られないように自分のコマを置くことができるマスは残りの 38 マスです。
入力例 2
1000000000 1 1 1
出力例 2
999999999999999997
10 ^ {18} マスのうち、置くことができないマスはマス (1,1),(2,3),(3,2) の 3 マスのみです。
答えが 2 ^ {32} 以上になる場合があることに注意してください。
入力例 3
20 10 1 4 7 11 7 15 8 10 11 6 12 5 13 1 15 2 20 10 20 15
出力例 3
338
Score : 300 points
Problem Statement
There is a grid of N^2 squares with N rows and N columns. Let (i,j) denote the square at the i-th row from the top (1\leq i\leq N) and j-th column from the left (1\leq j\leq N).
Each square is either empty or has a piece placed on it. There are M pieces placed on the grid, and the k-th (1\leq k\leq M) piece is placed on square (a_k,b_k).
You want to place your piece on an empty square in such a way that it cannot be captured by any of the existing pieces.
A piece placed on square (i,j) can capture pieces that satisfy any of the following conditions:
- Placed on square (i+2,j+1)
- Placed on square (i+1,j+2)
- Placed on square (i-1,j+2)
- Placed on square (i-2,j+1)
- Placed on square (i-2,j-1)
- Placed on square (i-1,j-2)
- Placed on square (i+1,j-2)
- Placed on square (i+2,j-1)
Here, conditions involving non-existent squares are considered to never be satisfied.
For example, a piece placed on square (4,4) can capture pieces placed on the squares shown in blue in the following figure:

How many squares can you place your piece on?
Constraints
- 1\leq N\leq10^9
- 1\leq M\leq2\times10^5
- 1\leq a_k\leq N,1\leq b_k\leq N\ (1\leq k\leq M)
- (a_k,b_k)\neq(a_l,b_l)\ (1\leq k\lt l\leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M a_1 b_1 a_2 b_2 \vdots a_M b_M
Output
Print the number of empty squares where you can place your piece without it being captured by any existing pieces.
Sample Input 1
8 6 1 4 2 1 3 8 4 5 5 2 8 3
Sample Output 1
38
The existing pieces can capture pieces placed on the squares shown in blue in the following figure:

Therefore, you can place your piece on the remaining 38 squares.
Sample Input 2
1000000000 1 1 1
Sample Output 2
999999999999999997
Out of 10^{18} squares, only 3 squares cannot be used: squares (1,1), (2,3), and (3,2).
Note that the answer may be 2^{32} or greater.
Sample Input 3
20 10 1 4 7 11 7 15 8 10 11 6 12 5 13 1 15 2 20 10 20 15
Sample Output 3
338
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
空の列と、N 個のボールがあります。i 個目 (1\leq i\leq N) のボールの大きさは 2^{A_i} です。
これから N 回の操作を行います。
i 回目の操作では、i 個目のボールを列の一番右に付け加えた後、次の手順を繰り返します。
- 列にあるボールが 1 つ以下ならば操作を終了する。
- 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 異なる ならば操作を終了する。
- 列にあるボールのうち右から 1 番目のものと 2 番目のものの大きさが 等しい ならば、2 つのボールを取り除き、「取り除かれた 2 つのボールの大きさの和」の大きさのボール 1 つを列の一番右に付け加える。その後、1. に戻り、手順を繰り返す。
N 回の操作の後で、列にあるボールの数を求めてください。
制約
- 1\leq N \leq 2\times 10^5
- 0\leq A_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
N 回の操作の後で、列にあるボールの数を出力せよ。
入力例 1
7 2 1 1 3 5 3 3
出力例 1
3
操作は次のように行われます。
- 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^2 です。
- 2 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^2, 2^1 です。
- 3 回目の操作の後、列にあるボールは 1 つで、大きさは 2^3 です。これは次のようにして得ることができます。
- 3 回目の操作において 3 個目のボールを付け加えたとき、列にあるボールの大きさは順に 2^2,2^1,2^1 となります。
- 右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^1+2^1=2^2 のボールが追加されます。このとき、列にあるボールの大きさは 2^2, 2^2 となります。
- さらに、再び右から 1 番目のボールと 2 番目のボールの大きさが等しいため、これらのボールが取り除かれ、大きさが 2^2+2^2=2^3 のボールが追加され、列にあるボールの大きさは 2^3 となります。
- 4 回目の操作の後、列にあるボールは 1 つで、大きさは 2^4 です。
- 5 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^4, 2^5 です。
- 6 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^3 です。
- 7 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^4, 2^5, 2^4 です。
よって、最後に列にあるボールの数である 3 を出力します。
入力例 2
5 0 0 0 1 2
出力例 2
4
操作は次のように行われます。
- 1 回目の操作の後、列にあるボールは 1 つで、大きさは 2^0 です。
- 2 回目の操作の後、列にあるボールは 1 つで、大きさは 2^1 です。
- 3 回目の操作の後、列にあるボールは 2 つで、大きさは順に 2^1, 2^0 です。
- 4 回目の操作の後、列にあるボールは 3 つで、大きさは順に 2^1, 2^0, 2^1 です。
- 5 回目の操作の後、列にあるボールは 4 つで、大きさは順に 2^1, 2^0, 2^1, 2^2 です。
よって、最後に列にあるボールの数である 4 を出力します。
Score: 250 points
Problem Statement
You have an empty sequence and N balls. The size of the i-th ball (1 \leq i \leq N) is 2^{A_i}.
You will perform N operations.
In the i-th operation, you add the i-th ball to the right end of the sequence, and repeat the following steps:
- If the sequence has one or fewer balls, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have different sizes, end the operation.
- If the rightmost ball and the second rightmost ball in the sequence have the same size, remove these two balls and add a new ball to the right end of the sequence with a size equal to the sum of the sizes of the two removed balls. Then, go back to step 1 and repeat the process.
Determine the number of balls remaining in the sequence after the N operations.
Constraints
- 1 \leq N \leq 2 \times 10^5
- 0 \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 \ldots A_N
Output
Print the number of balls in the sequence after the N operations.
Sample Input 1
7 2 1 1 3 5 3 3
Sample Output 1
3
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size 2^2.
- After the second operation, the sequence has two balls, of sizes 2^2 and 2^1 in order.
- After the third operation, the sequence has one ball, of size 2^3. This is obtained as follows:
- When the third ball is added during the third operation, the sequence has balls of sizes 2^2, 2^1, 2^1 in order.
- The first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^1 + 2^1 = 2^2 is added. Now, the sequence has balls of sizes 2^2, 2^2.
- Again, the first and second balls from the right have the same size, so these balls are removed, and a ball of size 2^2 + 2^2 = 2^3 is added, leaving the sequence with a ball of size 2^3.
- After the fourth operation, the sequence has one ball, of size 2^4.
- After the fifth operation, the sequence has two balls, of sizes 2^4 and 2^5 in order.
- After the sixth operation, the sequence has three balls, of sizes 2^4, 2^5, 2^3 in order.
- After the seventh operation, the sequence has three balls, of sizes 2^4, 2^5, 2^4 in order.
Therefore, you should print 3, the final number of balls in the sequence.
Sample Input 2
5 0 0 0 1 2
Sample Output 2
4
The operations proceed as follows:
- After the first operation, the sequence has one ball, of size 2^0.
- After the second operation, the sequence has one ball, of size 2^1.
- After the third operation, the sequence has two balls, of sizes 2^1 and 2^0 in order.
- After the fourth operation, the sequence has three balls, of sizes 2^1, 2^0, 2^1 in order.
- After the fifth operation, the sequence has four balls, of sizes 2^1, 2^0, 2^1, 2^2 in order.
Therefore, you should print 4, the final number of balls in the sequence.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 450 点
問題文
縦横 10^9 マスのグリッドがあります。上から i + 1 行目、左から j + 1 列目 (0 \leq i, j \lt 10^9) にあるマスを (i, j) と呼びます。(通常と異なる index の割り当て方に注意してください。)
各マスは黒マスか白マスのいずれかです。マス (i, j) の色は文字 P[i \bmod N][j \bmod N] によって表されて、B ならばマス (i, j) は黒マス、W ならば白マスです。ここで a \bmod b は a を b で割った余りを意味します。
Q 個のクエリが与えられるので順に処理してください。
各クエリでは 4 つの整数 A, B, C, D が与えられるので、(A, B) を左上隅、(C, D) を右下隅とする長方形領域に含まれる黒マスの個数を求めてください。
制約
- 1 \leq N \leq 1000
- P[i][j] は
WまたはB - 1 \leq Q \leq 2 \times 10^5
- 0 \leq A \leq C \lt 10^9
- 0 \leq B \leq D \lt 10^9
- N, Q, A, B, C, D は全て整数
入力
入力は以下の形式で標準入力から与えられる。ここで \text{query}_i は i 番目に処理するクエリである。
N Q
P[0][0]P[0][1]\dots P[0][N-1]
P[1][0]P[1][1]\dots P[1][N-1]
\vdots
P[N-1][0]P[N-1][1]\dots P[N-1][N-1]
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
各クエリは以下の形式で与えられる。
A B C D
出力
問題文の指示に従ってクエリへの答えを改行区切りで出力せよ。
入力例 1
3 2 WWB BBW WBW 1 2 3 4 0 3 4 5
出力例 1
4 7
グリッドの左上部分を図示すると次の図のようになります。

1 番目のクエリについて、(1, 2) を左上隅、(3, 4) を右下隅とする長方形領域は図の赤い枠線に囲まれた部分で、領域に含まれる黒マスの個数は 4 個です。
2 番目のクエリについて、(0, 3) を左上隅、(4, 5) を右下隅とする長方形領域は図の青い枠線に囲まれた部分で、領域に含まれる黒マスの個数は 7 個です。
入力例 2
10 5 BBBWWWBBBW WWWWWBBBWB BBBWBBWBBB BBBWWBWWWW WWWWBWBWBW WBBWBWBBBB WWBBBWWBWB WBWBWWBBBB WBWBWBBWWW WWWBWWBWWB 5 21 21 93 35 35 70 43 55 72 61 84 36 33 46 95 0 0 999999999 999999999
出力例 2
621 167 44 344 500000000000000000
Score : 450 points
Problem Statement
There is a grid with 10^9 by 10^9 squares. Let (i, j) denote the square at the (i + 1)-th row from the top and the (j + 1)-th column from the left (0 \leq i, j \lt 10^9). (Note the unusual index assignment.)
Each square is black or white. The color of the square (i, j) is represented by a character P[i \bmod N][j \bmod N], where B means black, and W means white. Here, a \bmod b denotes the remainder when a is divided by b.
Answer Q queries.
Each query gives you four integers A, B, C, D and asks you to find the number of black squares contained in the rectangular area with (A, B) as the top-left corner and (C, D) as the bottom-right corner.
Constraints
- 1 \leq N \leq 1000
- P[i][j] is
WorB. - 1 \leq Q \leq 2 \times 10^5
- 0 \leq A \leq C \lt 10^9
- 0 \leq B \leq D \lt 10^9
- N, Q, A, B, C, D are all integers.
Input
The input is given from Standard Input in the following format. Here, \text{query}_i is the i-th query to be processed.
N Q
P[0][0]P[0][1]\dots P[0][N-1]
P[1][0]P[1][1]\dots P[1][N-1]
\vdots
P[N-1][0]P[N-1][1]\dots P[N-1][N-1]
\text{query}_1
\text{query}_2
\vdots
\text{query}_Q
Each query is given in the following format:
A B C D
Output
Follow the instructions in the problem statement and print the answers to the queries, separated by newlines.
Sample Input 1
3 2 WWB BBW WBW 1 2 3 4 0 3 4 5
Sample Output 1
4 7
The figure below illustrates the upper left part of the grid.

For the first query, the rectangular area with (1, 2) as the top-left corner and (3, 4) as the bottom-right corner, surrounded by the red frame in the figure, contains four black squares.
For the second query, the rectangular area with (0, 3) as the top-left corner and (4, 5) as the bottom-right corner, surrounded by the blue frame in the figure, contains seven black squares.
Sample Input 2
10 5 BBBWWWBBBW WWWWWBBBWB BBBWBBWBBB BBBWWBWWWW WWWWBWBWBW WBBWBWBBBB WWBBBWWBWB WBWBWWBBBB WBWBWBBWWW WWWBWWBWWB 5 21 21 93 35 35 70 43 55 72 61 84 36 33 46 95 0 0 999999999 999999999
Sample Output 2
621 167 44 344 500000000000000000
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
1 以上 N-1 以下の整数からなる長さ M の数列 A=(A_1,A_2,\dots,A_M) が与えられます。 i=1,2,\dots,M について、以下の質問に答えてください。
- 数列 B=(B_1,B_2,\dots,B_N) がある。最初、各 j について B_j=j である。今から、k=1,2,\dots,i-1,i+1,\dots,M の順に以下の操作を行う
(すなわち、i を除いた 1 以上 M 以下の整数 k について、昇順に以下の操作を行う)。
- B_{A_k} と B_{A_k+1} の値を入れ替える。
- 全ての操作が終了した段階で、B_j=1 を満たす j の値を S_i と定義する。S_i を求めよ。
制約
- 2 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- 1 \leq A_i \leq N-1\ (1\leq i \leq M)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 A_2 \dots A_M
出力
M 行出力せよ。 i\ (1\leq i \leq M) 行目には、S_i の値を整数として出力せよ。
入力例 1
5 4 1 2 3 2
出力例 1
1 3 2 4
i = 2 のとき、操作によって B は以下のように変化します。
- 最初、B = (1,2,3,4,5)
- k=1 として操作を行う。すなわち B_1 と B_2 の値を入れ替えて、B = (2,1,3,4,5)
- k=3 として操作を行う。すなわち B_3 と B_4 の値を入れ替えて、B = (2,1,4,3,5)
- k=4 として操作を行う。すなわち B_2 と B_3 の値を入れ替えて、B = (2,4,1,3,5)
全ての操作が終了した段階で B_3=1 であるため、S_2 = 3 です。
同様に、
- i=1 のとき:k=2,3,4 の順に操作を行うと B=(1,4,3,2,5) になるので、S_1=1
- i=3 のとき:k=1,2,4 の順に操作を行うと B=(2,1,3,4,5) になるので、S_3=2
- i=4 のとき:k=1,2,3 の順に操作を行うと B=(2,3,4,1,5) になるので、S_4=4
です。
入力例 2
3 3 2 2 2
出力例 2
1 1 1
入力例 3
10 10 1 1 1 9 4 4 2 1 3 3
出力例 3
2 2 2 3 3 3 1 3 4 4
Score : 500 points
Problem Statement
You are given a sequence of length M consisting of integers between 1 and N-1, inclusive: A=(A_1,A_2,\dots,A_M). Answer the following question for i=1, 2, \dots, M.
- There is a sequence B=(B_1,B_2,\dots,B_N). Initially, we have B_j=j for each j. Let us perform the following operation for k=1, 2, \dots, i-1, i+1, \dots, M in this order (in other words, for integers k between 1 and M except i in ascending order).
- Swap the values of B_{A_k} and B_{A_k+1}.
- After all the operations, let S_i be the value of j such that B_j=1. Find S_i.
Constraints
- 2 \leq N \leq 2\times 10^5
- 1 \leq M \leq 2\times 10^5
- 1 \leq A_i \leq N-1\ (1\leq i \leq M)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 A_2 \dots A_M
Output
Print M lines. The i-th line (1\leq i \leq M) should contain the value S_i as an integer.
Sample Input 1
5 4 1 2 3 2
Sample Output 1
1 3 2 4
For i = 2, the operations change B as follows.
- Initially, B = (1,2,3,4,5).
- Perform the operation for k=1. That is, swap the values of B_1 and B_2, making B = (2,1,3,4,5).
- Perform the operation for k=3. That is, swap the values of B_3 and B_4, making B = (2,1,4,3,5).
- Perform the operation for k=4. That is, swap the values of B_2 and B_3, making B = (2,4,1,3,5).
After all the operations, we have B_3=1, so S_2 = 3.
Similarly, we have the following.
- For i=1: performing the operation for k=2,3,4 in this order makes B=(1,4,3,2,5), so S_1=1.
- For i=3: performing the operation for k=1,2,4 in this order makes B=(2,1,3,4,5), so S_3=2.
- For i=4: performing the operation for k=1,2,3 in this order makes B=(2,3,4,1,5), so S_4=4.
Sample Input 2
3 3 2 2 2
Sample Output 2
1 1 1
Sample Input 3
10 10 1 1 1 9 4 4 2 1 3 3
Sample Output 3
2 2 2 3 3 3 1 3 4 4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 500 点
問題文
N 頂点 M 辺の有向グラフ G が与えられます。
G の頂点は頂点 1 、頂点 2 、\ldots 、頂点 N と番号付けられており、
i 番目 (1\leq i\leq M) の辺は頂点 U_i から頂点 V_i へ向かう辺です。
k=1,2,\ldots,N について以下の問題を解いてください。
高橋君の目標は、G から(0 個でも良い)いくつかの頂点、およびそれらの頂点を始点または終点として持つすべての辺を削除することで、次の条件をみたすようにすることです。
- 頂点 1 から 0 本以上のいくつかの辺を辿って到達可能な頂点が頂点 1,2,\ldots,k のみである。
高橋君が目標を達成することが可能か判定し、可能な場合は目標を達成するために高橋君が最低何個の頂点を削除する必要があるか求めてください。
制約
- 2\leq N\leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i,V_i\leq N
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
出力
N 行出力せよ。
i 行目 (1\leq i\leq N) には、k=i のときの問題の答えを出力せよ。
ここで、各問題に対する答えとして、高橋君が目標を達成することが不可能な場合は -1 を、そうでない場合は目標を達成するために削除する必要のある頂点の個数の最小値を出力せよ。
入力例 1
5 5 1 2 2 4 2 5 4 3 4 5
出力例 1
1 2 -1 1 0
- k=1 のとき、頂点 2 を削除することによって目標を達成できます。このとき、頂点 3,4,5 は削除せずとも頂点 1 から到達できないことに注意してください。1 つも頂点を削除せずに目標を達成することはできないため、1 を 1 行目に出力します。
- k=2 のとき、頂点 4,5 を削除することにより目標を達成できます。1 つ以下の頂点を削除することによって目標を達成することは不可能なので、2 を 2 行目に出力します。
- k=3 のとき、高橋君はどのように頂点を削除しても目標を達成できません。よって、-1 を 3 行目に出力します。
- k=4 のとき、頂点 5 を削除することによって目標を達成できます。1 つも頂点を削除せずに目標を達成することはできないため、1 を 4 行目に出力します。
- k=5 のとき、頂点を削除することなく目標を達成できます。よって、0 を 5 行目に出力します。
入力例 2
5 5 1 1 1 2 3 1 3 1 3 5
出力例 2
1 0 -1 -1 -1
G は連結とは限りません。また、G は多重辺や自己ループを持つこともあります。
Score : 500 points
Problem Statement
You are given a directed graph G with N vertices and M edges.
The vertices of G are numbered as vertex 1, vertex 2, \ldots, vertex N, and the i-th edge (1\leq i\leq M) goes from vertex U_i to vertex V_i.
Solve the following problem for k=1,2,\ldots,N.
Takahashi's goal is to delete some (possibly zero) vertices from G, along with all edges having those vertices as an endpoint, so that the following condition is satisfied.
- The only vertices reachable from vertex 1 by traversing zero or more edges are vertices 1,2,\ldots,k.
Determine whether he can achieve his goal, and if so, find the minimum number of vertices he needs to delete to achieve it.
Constraints
- 2\leq N\leq 3\times 10^5
- 1\leq M\leq 3\times 10^5
- 1\leq U_i,V_i\leq N
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M U_1 V_1 U_2 V_2 \vdots U_M V_M
Output
Output N lines.
The i-th line (1\leq i\leq N) should contain the answer to the problem for k=i.
Here, for each problem, output -1 if it is impossible for Takahashi to achieve his goal, and otherwise output the minimum number of vertices that need to be deleted to achieve his goal.
Sample Input 1
5 5 1 2 2 4 2 5 4 3 4 5
Sample Output 1
1 2 -1 1 0
- For k=1, the goal can be achieved by deleting vertex 2. Note that vertices 3,4,5 are already unreachable from vertex 1 without deleting them. The goal cannot be achieved without deleting at least one vertex, so output 1 on the first line.
- For k=2, the goal can be achieved by deleting vertices 4 and 5. It is impossible to achieve the goal by deleting one or fewer vertices, so output 2 on the second line.
- For k=3, Takahashi cannot achieve the goal no matter how he deletes vertices. Thus, output -1 on the third line.
- For k=4, the goal can be achieved by deleting vertex 5. The goal cannot be achieved without deleting at least one vertex, so output 1 on the fourth line.
- For k=5, the goal can be achieved without deleting any vertices. Thus, output 0 on the fifth line.
Sample Input 2
5 5 1 1 1 2 3 1 3 1 3 5
Sample Output 2
1 0 -1 -1 -1
G is not necessarily connected. Also, G may have multi-edges or self-loops.