Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
正整数 N,K 及び長さ N の数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A に含まれる要素のうち、K の倍数であるもののみを全て取り出し、それらを K で割って出力してください。
制約
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A には K の倍数が 1 個以上含まれる
- 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \ldots A_N
出力
A に含まれる要素のうち、K の倍数であるもの全てを K で割った値を、空白区切りで昇順に出力せよ。
入力例 1
5 2 2 5 6 7 10
出力例 1
1 3 5
A に含まれる要素のうち、2 の倍数は 2,6,10 です。それらを 2 で割って得られる 1,3,5 を空白区切りで昇順に出力してください。
入力例 2
3 1 3 4 7
出力例 2
3 4 7
入力例 3
5 10 50 51 54 60 65
出力例 3
5 6
Score: 100 points
Problem Statement
You are given positive integers N and K, and a sequence of length N, A=(A_1,A_2,\ldots,A_N).
Extract all elements of A that are multiples of K, divide them by K, and print the quotients.
Constraints
- 1\leq N,K\leq 100
- 1\leq A_1 < A_2 < \ldots < A_N \leq 100
- A has at least one multiple of K.
- All given numbers are integers.
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \ldots A_N
Output
Divide all elements of A that are multiples of K and print the quotients in ascending order with spaces in between.
Sample Input 1
5 2 2 5 6 7 10
Sample Output 1
1 3 5
The multiples of 2 among the elements in A are 2, 6, and 10. Divide them by 2 to get 1, 3, and 5, and print them in ascending order with spaces in between.
Sample Input 2
3 1 3 4 7
Sample Output 2
3 4 7
Sample Input 3
5 10 50 51 54 60 65
Sample Output 3
5 6
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 100 点
問題文
1 から N までの番号が付けられた N 人の人がいます。 それぞれの人にはプログラミング力という整数値が定まっており、人 i のプログラミング力は P_i です。 人 1 が最強になるためには、あといくつプログラミング力を上げる必要がありますか? すなわち、すべての i \neq 1 に対して P_1 + x > P_i を満たすような最小の非負整数 x は何ですか?
制約
- 1\leq N \leq 100
- 1\leq P_i \leq 100
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N
出力
答えを整数として出力せよ。
入力例 1
4 5 15 2 10
出力例 1
11
人 1 が最強になるためには、プログラミング力を 16 以上にする必要があります。 よって、答えは 16-5=11 です。
入力例 2
4 15 5 2 10
出力例 2
0
人 1 は既に最強なので、これ以上プログラミング力を上げる必要はありません。
入力例 3
3 100 100 100
出力例 3
1
Score : 100 points
Problem Statement
There are N people numbered 1 through N. Each person has a integer score called programming ability; person i's programming ability is P_i points. How many more points does person 1 need, so that person 1 becomes the strongest? In other words, what is the minimum non-negative integer x such that P_1 + x > P_i for all i \neq 1?
Constraints
- 1\leq N \leq 100
- 1\leq P_i \leq 100
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N
Output
Print the answer as an integer.
Sample Input 1
4 5 15 2 10
Sample Output 1
11
Person 1 becomes the strongest when their programming skill is 16 points or more, so the answer is 16-5=11.
Sample Input 2
4 15 5 2 10
Sample Output 2
0
Person 1 is already the strongest, so no more programming skill is needed.
Sample Input 3
3 100 100 100
Sample Output 3
1
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
AtCoder社のオフィスは H 行 W 列のマス目で表されます。上から i 行目、左から j 列目のマスを (i, j) と表します。
各マスの状態は文字 S_{i,j} で表され、 S_{i,j} が # のときそのマスは机、. のときそのマスは床です。床のマスは 2 つ以上存在することが保証されます。
あなたは床のマスから異なる 2 マスを選び、加湿器を設置します。
加湿器が設置されたとき、あるマス (i,j) は加湿器があるマス (i',j') からのマンハッタン距離が D 以下であるとき、またその時に限り加湿されます。 なお、マス (i,j) からマス (i',j') までのマンハッタン距離は |i-i'|+|j-j'| で表されます。 ここで、加湿器が置かれた床のマスは必ず加湿されていることに注意してください。
加湿される 床のマス の個数として考えられる最大値を求めてください。
制約
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D は整数
- S_{i,j} は
#または.である (1 \leq i \leq H, 1 \leq j \leq W) - 床のマスは 2 つ以上存在する
入力
入力は以下の形式で標準入力から与えられる。
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
出力
答えを出力せよ。
入力例 1
2 5 1 .###. .#.##
出力例 1
3
マス (1,1) とマス (1,5) に加湿器を置いた時:
- マス (1,1) の加湿器によってマス (1,1),(2,1) の 2 マスが加湿されます。
- マス (1,5) の加湿器によってマス (1,5) の 1 マスが加湿されます。
よって、合計 3 マス加湿されています。また、4 マス以上加湿するような加湿器の置き方は存在しないため、答えは 3 です。
入力例 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
出力例 2
15
マス (2,4) とマス (5,3) に加湿器を置いた時、15 個の床のマスが加湿されます。
入力例 3
4 4 2 .... .##. .##. ....
出力例 3
10
Score : 250 points
Problem Statement
The AtCoder company office can be represented as a grid of H rows and W columns. Let (i, j) denote the cell at the i-th row from the top and j-th column from the left.
The state of each cell is represented by a character S_{i,j}. If S_{i,j} is #, that cell contains a desk; if S_{i,j} is ., that cell is a floor. It is guaranteed that there are at least two floor cells.
You will choose two distinct floor cells and place a humidifier on each.
After placing the humidifiers, a cell (i,j) is humidified if and only if it is within a Manhattan distance D from at least one of the humidifier cells (i',j'). The Manhattan distance between (i,j) and (i',j') is defined as |i - i'| + |j - j'|. Note that any floor cell on which a humidifier is placed is always humidified.
Find the maximum possible number of humidified floor cells.
Constraints
- 1 \leq H \leq 10
- 1 \leq W \leq 10
- 2 \leq H \times W
- 0 \leq D \leq H+W-2
- H,W,D are integers.
- S_{i,j} is
#or.. (1 \leq i \leq H, 1 \leq j \leq W) - There are at least two floor cells.
Input
The input is given from Standard Input in the following format:
H W D
S_{1,1}S_{1,2}\cdotsS_{1,W}
S_{2,1}S_{2,2}\cdotsS_{2,W}
\vdots
S_{H,1}S_{H,2}\cdotsS_{H,W}
Output
Print the answer.
Sample Input 1
2 5 1 .###. .#.##
Sample Output 1
3
When placing humidifiers on (1,1) and (1,5):
- From the humidifier on (1,1), two cells (1,1) and (2,1) are humidified.
- From the humidifier on (1,5), one cell (1,5) is humidified.
In total, three cells are humidified. No configuration can humidify four or more floor cells, so the answer is 3.
Sample Input 2
5 5 2 .#.#. ..... .#.#. #.#.# .....
Sample Output 2
15
When placing humidifiers on (2,4) and (5,3), 15 floor cells are humidified.
Sample Input 3
4 4 2 .... .##. .##. ....
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 150 点
問題文
N 頂点の単純無向グラフ G があり、グラフの頂点には 1,2,\ldots, N の番号が付けられています。
G の隣接行列 (A_{i,j}) が与えられます。すなわち、G は A_{i,j} = 1 であるとき、またそのときに限り頂点 i と頂点 j を結ぶ辺を持ちます。
i = 1, 2, \ldots, N について、頂点 i と直接結ばれている頂点の番号を昇順に出力してください。
ただし、頂点 i と頂点 j が直接結ばれているとは、頂点 i と頂点 j を結ぶ辺が存在することをいいます。
制約
- 2 \leq N \leq 100
- A_{i,j} \in \lbrace 0,1 \rbrace
- A_{i,i} = 0
- A_{i,j} = A_{j,i}
- 入力される値はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
出力
N 行出力せよ。 i 行目には頂点 i と直接結ばれている頂点の番号を昇順に空白区切りで出力せよ。
入力例 1
4 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0
出力例 1
2 3 1 4 1 2
頂点 1 と直接結ばれている頂点は頂点 2, 3 です。したがって、1 行目には 2, 3 をこの順で出力します。
同様に、2 行目には 1, 4 をこの順に、3 行目には 1 を、4 行目には 2 を出力します。
入力例 2
2 0 0 0 0
出力例 2
G に辺が存在しないこともあります。
入力例 3
5 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0
出力例 3
2 4 5 1 4 5 1 2 5 1 3 4
Score: 150 points
Problem Statement
There is a simple undirected graph G with N vertices labeled with numbers 1, 2, \ldots, N.
You are given the adjacency matrix (A_{i,j}) of G. That is, G has an edge connecting vertices i and j if and only if A_{i,j} = 1.
For each i = 1, 2, \ldots, N, print the numbers of the vertices directly connected to vertex i in ascending order.
Here, vertices i and j are said to be directly connected if and only if there is an edge connecting vertices i and j.
Constraints
- 2 \leq N \leq 100
- A_{i,j} \in \lbrace 0,1 \rbrace
- A_{i,i} = 0
- A_{i,j} = A_{j,i}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N
A_{1,1} A_{1,2} \ldots A_{1,N}
A_{2,1} A_{2,2} \ldots A_{2,N}
\vdots
A_{N,1} A_{N,2} \ldots A_{N,N}
Output
Print N lines. The i-th line should contain the numbers of the vertices directly connected to vertex i in ascending order, separated by a space.
Sample Input 1
4 0 1 1 0 1 0 0 1 1 0 0 0 0 1 0 0
Sample Output 1
2 3 1 4 1 2
Vertex 1 is directly connected to vertices 2 and 3. Thus, the first line should contain 2 and 3 in this order.
Similarly, the second line should contain 1 and 4 in this order, the third line should contain 1, and the fourth line should contain 2.
Sample Input 2
2 0 0 0 0
Sample Output 2
G may have no edges.
Sample Input 3
5 0 1 0 1 1 1 0 0 1 0 0 0 0 0 1 1 1 0 0 1 1 0 1 1 0
Sample Output 3
2 4 5 1 4 5 1 2 5 1 3 4
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
1 から N まで番号がつけられた N 個のマスが一列に並んでいます。最初、 M 個のマスに石が入っており、マス X_i には A_i 個 (1 \leq i \leq M) の石が入っています。
あなたは以下の操作を好きな回数( 0 回でもよい)行うことができます。
- マス i (1 \leq i \leq N-1) に石があるとき、マス i から石を 1 つマス i+1 に移動させる。
N 個のマスすべてに石がちょうど 1 個ずつ入っている状態にするために必要な操作回数の最小値を求めてください。ただし、不可能な場合は -1 を出力してください。
制約
- 2 \leq N \leq 2 \times 10^{9}
- 1 \leq M \leq 2 \times 10^{5}
- M \leq N
- 1 \leq X_i \leq N (1 \leq i \leq M)
- X_i \neq X_j (1 \leq i < j \leq M)
- 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M X_1 X_2 \ldots X_M A_1 A_2 \ldots A_M
出力
答えを出力せよ。
入力例 1
5 2 1 4 3 2
出力例 1
4
以下の 4 回の操作で、5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることができます。
- マス 1 の石を 1 つマス 2 に移動させる。
- マス 2 の石を 1 つマス 3 に移動させる。
- マス 4 の石を 1 つマス 5 に移動させる。
- マス 1 の石を 1 つマス 2 に移動させる。
また、3 回以下の操作では 5 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、4 を出力します。
入力例 2
10 3 1 4 8 4 2 4
出力例 2
-1
どのように操作を行っても 10 個のマスすべてに石がちょうど 1 個ずつ入っている状態にすることはできません。よって、-1 を出力します。
Score : 300 points
Problem Statement
There are N cells numbered from 1 to N in a row. Initially, M cells contain stones, and cell X_i contains A_i stones (1 \leq i \leq M).
You can perform the following operation any number of times (possibly zero):
- If cell i (1 \leq i \leq N-1) contains a stone, move one stone from cell i to cell i+1.
Find the minimum number of operations required to reach a state where each of the N cells contains exactly one stone. If it is impossible, print -1.
Constraints
- 2 \leq N \leq 2 \times 10^{9}
- 1 \leq M \leq 2 \times 10^{5}
- M \leq N
- 1 \leq X_i \leq N (1 \leq i \leq M)
- X_i \neq X_j (1 \leq i < j \leq M)
- 1 \leq A_i \leq 2 \times 10^{9} (1 \leq i \leq M)
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 X_2 \ldots X_M A_1 A_2 \ldots A_M
Output
Print the answer.
Sample Input 1
5 2 1 4 3 2
Sample Output 1
4
You can reach a state where each of the five cells contains exactly one stone with four operations as follows:
- Move one stone from cell 1 to cell 2.
- Move one stone from cell 2 to cell 3.
- Move one stone from cell 4 to cell 5.
- Move one stone from cell 1 to cell 2.
It is impossible to achieve the goal in three or fewer operations. Therefore, print 4.
Sample Input 2
10 3 1 4 8 4 2 4
Sample Output 2
-1
No matter how you perform the operations, you cannot reach a state where all ten cells contain exactly one stone. Therefore, print -1.
Time Limit: 3 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
文字列 T が次の条件を満たすとき、T を良い括弧列と呼びます。
-
次の操作を 0 回以上繰り返すことで T を空文字列にすることができる。
- T に(連続な)部分文字列として含まれる
()を選び、これを取り除く。
- T に(連続な)部分文字列として含まれる
例えば () や (()()), および空文字列は良い括弧列ですが、)()( や ))) は良い括弧列ではありません。
文字列 S があります。S ははじめ空文字列です。
以下で説明されるクエリを与えられる順に Q 個処理してください。そして、各クエリの直後に S が良い括弧列であるかを判定してください。
クエリは次の 2 種類です。
1 c: 文字 c が与えられる。c は(または)である。c を S の末尾に追加する。2: S の末尾の文字を削除する。この時、S は空文字列でないことが保証される。
制約
- 1 \leq Q \leq 8 \times 10^5
- 1 種類目のクエリの c は
(または) - 2 種類目のクエリを与えられた時点で S は空でないことが保証される
- Q は整数
入力
入力は以下の形式で標準入力から与えられる。ここで \mathrm{query}_i は i 番目のクエリを意味する。
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
各クエリは以下の 2 種類のいずれかの形式で与えられる。
1 c
2
出力
Q 行出力せよ。i 行目には、i 番目のクエリを処理した直後の文字列 S が良い括弧列である場合は Yes を、そうでない場合は No を出力せよ。
入力例 1
8 1 ( 2 1 ( 1 ) 2 1 ( 1 ) 1 )
出力例 1
No Yes No Yes No No No Yes
1 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
2 番目のクエリを処理した直後の S は空文字列で、これは良い括弧列です。
3 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
4 番目のクエリを処理した直後の S は () で、これは良い括弧列です。
5 番目のクエリを処理した直後の S は ( で、これは良い括弧列ではありません。
6 番目のクエリを処理した直後の S は (( で、これは良い括弧列ではありません。
7 番目のクエリを処理した直後の S は (() で、これは良い括弧列ではありません。
8 番目のクエリを処理した直後の S は (()) で、これは良い括弧列です。
Score : 300 points
Problem Statement
A string T is called a good bracket sequence if and only if it satisfies the following condition:
-
T can be made into an empty string by repeating the following operation zero or more times:
- Choose
()contained in T as a (contiguous) substring and remove it.
- Choose
For example, (), (()()), and the empty string are good bracket sequences, but )()( and ))) are not good bracket sequences.
There is a string S. Initially, S is an empty string.
Process Q queries in the order they are given. After each query, determine whether S is a good bracket sequence.
There are two types of queries:
1 c: A character c is given. c is either(or). Append c to the end of S.2: Remove the last character of S. It is guaranteed that S is not an empty string at this time.
Constraints
- 1 \leq Q \leq 8 \times 10^5
- c in queries of the first type is
(or). - It is guaranteed that S is not empty when a query of the second type is given.
- Q is an integer.
Input
The input is given from Standard Input in the following format, where \mathrm{query}_i denotes the i-th query.
Q
\mathrm{query}_1
\mathrm{query}_2
\vdots
\mathrm{query}_Q
Each query is given in one of the following two formats:
1 c
2
Output
Output Q lines. The i-th line should contain Yes if the string S immediately after processing the i-th query is a good bracket sequence, and No otherwise.
Sample Input 1
8 1 ( 2 1 ( 1 ) 2 1 ( 1 ) 1 )
Sample Output 1
No Yes No Yes No No No Yes
S immediately after processing the 1st query is (, which is not a good bracket sequence.
S immediately after processing the 2nd query is an empty string, which is a good bracket sequence.
S immediately after processing the 3rd query is (, which is not a good bracket sequence.
S immediately after processing the 4th query is (), which is a good bracket sequence.
S immediately after processing the 5th query is (, which is not a good bracket sequence.
S immediately after processing the 6th query is ((, which is not a good bracket sequence.
S immediately after processing the 7th query is ((), which is not a good bracket sequence.
S immediately after processing the 8th query is (()), which is a good bracket sequence.
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
N \times N のマス目が与えられます。このうち上から i 行目、左から j 列目のマスを (i,j) と書きます。
各マスの状態を表す N 個の長さ N の文字列 S_1,S_2,\dots,S_N が以下の形式で与えられます。
- S_i の j 文字目が
oであるとき、 (i,j) にはoが書かれている。 - S_i の j 文字目が
xであるとき、 (i,j) にはxが書かれている。
以下の条件を全て満たすマスの三つ組の個数を求めてください。
- 組に含まれる 3 マスは相異なる。
- 3 マス全てに
oが書かれている。 - マスのうち、丁度 2 つが同じ行にある。
- マスのうち、丁度 2 つが同じ列にある。
但し、ふたつの三つ組は、丁度一方に含まれるマスが存在する場合のみ区別します。
制約
- N は 2 以上 2000 以下の整数
- S_i は長さ N の
oとxからなる文字列
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
答えを整数として出力せよ。
入力例 1
3 ooo oxx xxo
出力例 1
4
以下の 4 つの三つ組が条件を満たします。
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
入力例 2
4 oxxx xoxx xxox xxxo
出力例 2
0
入力例 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
出力例 3
2960
Score : 400 points
Problem Statement
You are given an N \times N grid. Let (i,j) denote the cell in the i-th row from the top and the j-th column from the left.
The states of the cells are given by N strings of length N, S_1, S_2, \dots, S_N, in the following format:
- If the j-th character of S_i is
o, there is anowritten in cell (i,j). - If the j-th character of S_i is
x, there is anxwritten in cell (i,j).
Find the number of triples of cells that satisfy all of the following conditions:
- The three cells in the triple are distinct.
- All three cells have an
owritten in them. - Exactly two of the cells are in the same row.
- Exactly two of the cells are in the same column.
Here, two triples are considered different if and only if some cell is contained in exactly one of the triples.
Constraints
- N is an integer between 2 and 2000, inclusive.
- S_i is a string of length N consisting of
oandx.
Input
The input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the answer as an integer.
Sample Input 1
3 ooo oxx xxo
Sample Output 1
4
The following four triples satisfy the conditions:
- (1,1),(1,2),(2,1)
- (1,1),(1,3),(2,1)
- (1,1),(1,3),(3,3)
- (1,2),(1,3),(3,3)
Sample Input 2
4 oxxx xoxx xxox xxxo
Sample Output 2
0
Sample Input 3
15 xooxxooooxxxoox oxxoxoxxxoxoxxo oxxoxoxxxoxoxxx ooooxooooxxoxxx oxxoxoxxxoxoxxx oxxoxoxxxoxoxxo oxxoxooooxxxoox xxxxxxxxxxxxxxx xooxxxooxxxooox oxxoxoxxoxoxxxo xxxoxxxxoxoxxoo xooxxxooxxoxoxo xxxoxxxxoxooxxo oxxoxoxxoxoxxxo xooxxxooxxxooox
Sample Output 3
2960
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 500 点
問題文
マス 1 からマス N の N 個のマスがあります。はじめ、あなたはマス 1 にいます。
また、マス 1 からマス N-1 にはそれぞれサイコロが置いてあります。マス i のサイコロは 0 以上 A_i 以下の整数を等確率にランダムで出します。(サイコロを振る操作は毎回独立です。)
あなたは、マス N に到達するまで、現在いるマスに置かれているサイコロを振り、出た目の数だけ進むことを繰り返します。厳密に言うと、マス X にいるときにサイコロで Y が出た場合はマス X+Y に移動します。
サイコロを振る回数の期待値 \bmod\ 998244353 を求めてください。
注記
求める期待値は必ず有理数となることが証明できます。またこの問題の制約下では、その値を互いに素な 2 つの整数 P, Q を用いて \frac{P}{Q} と表したとき、R \times Q \equiv P\pmod{998244353} かつ 0 \leq R \lt 998244353 を満たす整数 R がただ一つ存在することが証明できます。この R を求めてください。
制約
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N-i(1 \le i \le N-1)
- 入力は全て整数。
入力
入力は以下の形式で標準入力から与えられる。
N
A_1 A_2 \dots A_{N-1}
出力
答えを出力せよ。
入力例 1
3 1 1
出力例 1
4
求める期待値は 4 であるため、4 を出力します。
マス N に到達するまでの流れとしては、以下のようなものが考えられます。
- マス 1 で 1 を出し、マス 2 に移動する。
- マス 2 で 0 を出し、移動しない。
- マス 2 で 1 を出し、マス 3 に移動する。
このようになる確率は \frac{1}{8} です。
入力例 2
5 3 1 2 1
出力例 2
332748122
Score : 500 points
Problem Statement
There are N squares called Square 1 though Square N. You start on Square 1.
Each of the squares from Square 1 through Square N-1 has a die on it. The die on Square i is labeled with the integers from 0 through A_i, each occurring with equal probability. (Die rolls are independent of each other.)
Until you reach Square N, you will repeat rolling a die on the square you are on. Here, if the die on Square x rolls the integer y, you go to Square x+y.
Find the expected value, modulo 998244353, of the number of times you roll a die.
Notes
It can be proved that the sought expected value is always a rational number. Additionally, if that value is represented \frac{P}{Q} using two coprime integers P and Q, there is a unique integer R such that R \times Q \equiv P\pmod{998244353} and 0 \leq R \lt 998244353. Find this R.
Constraints
- 2 \le N \le 2 \times 10^5
- 1 \le A_i \le N-i(1 \le i \le N-1)
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N
A_1 A_2 \dots A_{N-1}
Output
Print the answer.
Sample Input 1
3 1 1
Sample Output 1
4
The sought expected value is 4, so 4 should be printed.
Here is one possible scenario until reaching Square N:
- Roll 1 on Square 1, and go to Square 2.
- Roll 0 on Square 2, and stay there.
- Roll 1 on Square 2, and go to Square 3.
This scenario occurs with probability \frac{1}{8}.
Sample Input 2
5 3 1 2 1
Sample Output 2
332748122
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 525 点
問題文
長さ k の数列 a=(a_1,a_2,\dots,a_k) が 門松的 であることを、以下のようにして定めます。
- 2 \le i \le k-1 かつ a_{i-1} < a_i かつ a_i > a_{i+1} を満たす整数 i の個数を x とする。
- 2 \le i \le k-1 かつ a_{i-1} > a_i かつ a_i < a_{i+1} を満たす整数 i の個数を y とする。
- x > y であるとき、またそのときに限り、数列 a を 門松的 であると言います。
(1,2,\dots,N) の順列 P が与えられます。
P の (連続でなくともよい) 部分列であって、門松的であるものの個数を 998244353 で割った余りを求めてください。
制約
- 入力は全て整数
- 1 \le N \le 3 \times 10^5
- P は (1,2,\dots,N) の順列
入力
入力は以下の形式で標準入力から与えられる。
N P_1 P_2 \dots P_N
出力
答えを出力せよ。
入力例 1
4 1 3 4 2
出力例 1
4
P の部分列のうち、門松的であるものは以下の 4 つです。
- (1,3,4,2)
- (1,3,2)
- (1,4,2)
- (3,4,2)
入力例 2
1 1
出力例 2
0
入力例 3
20 11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3
出力例 3
431610
例えば、部分列 a=(10,13,12,5,7,9,20,3) は門松的です。
- i=2,7 に対して a_{i-1} < a_i かつ a_i > a_{i+1} が成り立つので、 x=2 です。
- i=4 に対して a_{i-1} > a_i かつ a_i < a_{i+1} が成り立つので、 y=1 です。
- x > y であるので、部分列 a は門松的です。
Score : 525 points
Problem Statement
A sequence a=(a_1,a_2,\dots,a_k) of length k is defined to be kadomatsu-like as follows:
- Let x be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} < a_i, and a_i > a_{i+1}.
- Let y be the number of integers i that satisfy 2 \le i \le k-1, a_{i-1} > a_i, and a_i < a_{i+1}.
- The sequence a is called kadomatsu-like if and only if x > y.
You are given a permutation P of (1,2,\dots,N).
Find the number, modulo 998244353, of (not necessarily contiguous) subsequences of P that are kadomatsu-like.
Constraints
- All input values are integers.
- 1 \le N \le 3 \times 10^5
- P is a permutation of (1,2,\dots,N).
Input
The input is given from Standard Input in the following format:
N P_1 P_2 \dots P_N
Output
Output the answer.
Sample Input 1
4 1 3 4 2
Sample Output 1
4
Among the subsequences of P, the following four are kadomatsu-like:
- (1,3,4,2)
- (1,3,2)
- (1,4,2)
- (3,4,2)
Sample Input 2
1 1
Sample Output 2
0
Sample Input 3
20 11 10 18 13 12 16 5 19 7 6 17 4 9 1 14 2 20 15 8 3
Sample Output 3
431610
For example, the subsequence a=(10,13,12,5,7,9,20,3) is kadomatsu-like.
- We have a_{i-1} < a_i and a_i > a_{i+1} for i=2,7, so x=2.
- We have a_{i-1} > a_i and a_i < a_{i+1} for i=4, so y=1.
- Since x > y, the subsequence a is kadomatsu-like.