実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
整数からなる数列が N 個あります。
i \, (1 \leq i \leq N) 番目の数列は L_i 項からなり、i 番目の数列の第 j \, (1 \leq j \leq L_i) 項 は a_{i, j} です。
Q 個のクエリが与えられます。k \, (1 \leq k \leq Q) 番目のクエリでは、整数 s_k, t_k が与えられるので、s_k 番目の数列の第 t_k 項を求めてください。
制約
- 1 \leq N, Q \leq 2 \times 10^5
- L_i \geq 1 \, (1 \leq i \leq N)
- \sum_{i=1}^N L_i \leq 2 \times 10^5
- 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
- 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots
s_Q t_Q
出力
Q 行出力せよ。k \, (1 \leq k \leq Q) 行目には、k 番目のクエリに対する答えを出力せよ。
入力例 1
2 2 3 1 4 7 2 5 9 1 3 2 1
出力例 1
7 5
1 番目の数列は (1, 4, 7)、2 番目の数列は (5, 9) です。
それぞれのクエリに対する答えは次のようになります。
- 1 番目の数列の第 3 項は 7 です。
- 2 番目の数列の第 1 項は 5 です。
入力例 2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
出力例 2
128 1 26535 901
Score : 200 points
Problem Statement
There are N sequences of integers.
The i-th (1 \leq i \leq N) sequence has L_i terms; the j-th (1 \leq j \leq L_i) term of the i-th sequence is a_{i, j}.
You are given Q queries. For the k-th (1 \leq k \leq Q) query, given integers s_k and t_k, find the t_k-th term of the s_k-th sequence.
Constraints
- 1 \leq N, Q \leq 2 \times 10^5
- L_i \geq 1 \, (1 \leq i \leq N)
- \sum_{i=1}^N L_i \leq 2 \times 10^5
- 1 \leq a_{i, j} \leq 10^9 \, (1 \leq i \leq N, 1 \leq j \leq L_i)
- 1 \leq s_k \leq N, 1 \leq t_k \leq L_{s_k} \, (1 \leq k \leq Q)
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N Q
L_1 a_{1, 1} \ldots a_{1, L_1}
\vdots
L_N a_{N, 1} \ldots a_{N, L_N}
s_1 t_1
\vdots
s_Q t_Q
Output
Print Q lines. The k-th (1 \leq k \leq Q) line should contain the answer to the k-th query.
Sample Input 1
2 2 3 1 4 7 2 5 9 1 3 2 1
Sample Output 1
7 5
The 1-st sequence is (1, 4, 7) and the 2-nd is (5, 9).
The answer to each query is as follows:
- The 3-rd term of the 1-st sequence is 7.
- The 1-st term of the 2-nd sequence is 5.
Sample Input 2
3 4 4 128 741 239 901 2 1 1 3 314 159 26535 1 1 2 2 3 3 1 4
Sample Output 2
128 1 26535 901
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
選挙が行われています。
N 人が投票を行い、i\,(1 \leq i \leq N) 番目の人は S_i という名前の候補者に投票しました。
得票数が最大の候補者の名前を答えてください。なお、与えられる入力では得票数が最大の候補者は一意に定まります。
制約
- 1 \leq N \leq 100
- S_i は英小文字からなる長さ 1 以上 10 以下の文字列
- N は整数
- 得票数が最大の候補者は一意に定まる
入力
入力は以下の形式で標準入力から与えられる。
N S_1 S_2 \vdots S_N
出力
得票数が最大の候補者の名前を出力せよ。
入力例 1
5 snuke snuke takahashi takahashi takahashi
出力例 1
takahashi
takahashi は 3 票、snuke は 2 票獲得しました。よって takahashi を出力します。
入力例 2
5 takahashi takahashi aoki takahashi snuke
出力例 2
takahashi
入力例 3
1 a
出力例 3
a
Score : 200 points
Problem Statement
An election is taking place.
N people voted. The i-th person (1 \leq i \leq N) cast a vote to the candidate named S_i.
Find the name of the candidate who received the most votes. The given input guarantees that there is a unique candidate with the most votes.
Constraints
- 1 \leq N \leq 100
- S_i is a string of length between 1 and 10 (inclusive) consisting of lowercase English letters.
- N is an integer.
- There is a unique candidate with the most votes.
Input
Input is given from Standard Input in the following format:
N S_1 S_2 \vdots S_N
Output
Print the name of the candidate who received the most votes.
Sample Input 1
5 snuke snuke takahashi takahashi takahashi
Sample Output 1
takahashi
takahashi got 3 votes, and snuke got 2, so we print takahashi.
Sample Input 2
5 takahashi takahashi aoki takahashi snuke
Sample Output 2
takahashi
Sample Input 3
1 a
Sample Output 3
a
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
高橋君は N 日間の鉄道旅行を計画しています。
高橋君はそれぞれの日について、運賃の通常料金を払うか、1 日周遊パスを 1 枚使用するか選ぶことができます。
ここで、1\leq i\leq N について、i 日目の旅行にかかる運賃の通常料金は F_i 円です。
一方、1 日周遊パスは D 枚セットで P 円で発売されており、何セットでも購入することが可能ですが、D 枚単位でしか購入することができません。
また、購入したパスは 1 枚ずつ好きな日に使うことができ、旅行が終了した時点で余っていても構いません。
N 日間の旅行でかかる金額、すなわち 1 日周遊パスの購入にかかった代金と、1 日周遊パスを利用しなかった日における運賃の通常料金の合計金額の和としてあり得る最小値を求めてください。
制約
- 1\leq N\leq 2\times 10^5
- 1\leq D\leq 2\times 10^5
- 1\leq P\leq 10^9
- 1\leq F_i\leq 10^9
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N D P F_1 F_2 \ldots F_N
出力
N 日間の旅行でかかる金額としてあり得る最小値を出力せよ。
入力例 1
5 2 10 7 1 6 3 6
出力例 1
20
1 日周遊パスを 1 セットだけ購入し、1 日目と 3 日目に使用すると、合計金額は (10\times 1)+(0+1+0+3+6)=20 となり、このときかかる金額が最小となります。
よって、20 を出力します。
入力例 2
3 1 10 1 2 3
出力例 2
6
3 日間すべてにおいて運賃の通常料金を支払ったときに最小となります。
入力例 3
8 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
出力例 3
3000000000
1 日周遊パスを 3 セット購入し、8 日間すべてにおいて 1 日周遊パスを利用したときに最小となります。
答えが 32 bit 整数型に収まらないことがあることに注意してください。
Score : 300 points
Problem Statement
Takahashi is planning an N-day train trip.
For each day, he can pay the regular fare or use a one-day pass.
Here, for 1\leq i\leq N, the regular fare for the i-th day of the trip is F_i yen.
On the other hand, a batch of D one-day passes is sold for P yen. You can buy as many passes as you want, but only in units of D.
Each purchased pass can be used on any day, and it is fine to have some leftovers at the end of the trip.
Find the minimum possible total cost for the N-day trip, that is, the cost of purchasing one-day passes plus the total regular fare for the days not covered by one-day passes.
Constraints
- 1\leq N\leq 2\times 10^5
- 1\leq D\leq 2\times 10^5
- 1\leq P\leq 10^9
- 1\leq F_i\leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N D P F_1 F_2 \ldots F_N
Output
Print the minimum possible total cost for the N-day trip.
Sample Input 1
5 2 10 7 1 6 3 6
Sample Output 1
20
If he buys just one batch of one-day passes and uses them for the first and third days, the total cost will be (10\times 1)+(0+1+0+3+6)=20, which is the minimum cost needed.
Thus, print 20.
Sample Input 2
3 1 10 1 2 3
Sample Output 2
6
The minimum cost is achieved by paying the regular fare for all three days.
Sample Input 3
8 3 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000 1000000000
Sample Output 3
3000000000
The minimum cost is achieved by buying three batches of one-day passes and using them for all eight days.
Note that the answer may not fit into a 32-bit integer type.
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 300 点
問題文
長さ N の整数からなる数列 A=(A_1,\ldots,A_N),B=(B_1,\ldots,B_N) が与えられます。
以下の条件を全て満たす長さ N の数列 X=(X_1,\ldots,X_N) が存在するかを判定してください。
-
すべての i(1\leq i\leq N) について、X_i = A_i または X_i = B_i
-
すべての i(1\leq i\leq N-1) について、|X_i - X_{i+1}| \leq K
制約
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 \ldots A_N B_1 \ldots B_N
出力
条件を全て満たす X が存在するならば Yes と、存在しないならば No と出力せよ。
入力例 1
5 4 9 8 3 7 2 1 6 2 9 5
出力例 1
Yes
X=(9,6,3,7,5) が全ての条件を満たします。
入力例 2
4 90 1 1 1 100 1 2 3 100
出力例 2
No
条件を満たす X は存在しません。
入力例 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
出力例 3
Yes
Score : 300 points
Problem Statement
You are given two sequences, each of length N, consisting of integers: A=(A_1, \ldots, A_N) and B=(B_1, \ldots, B_N).
Determine whether there is a sequence of length N, X=(X_1, \ldots, X_N), satisfying all of the conditions below.
-
X_i = A_i or X_i = B_i, for every i(1\leq i\leq N).
-
|X_i - X_{i+1}| \leq K, for every i(1\leq i\leq N-1).
Constraints
- 1 \leq N \leq 2\times 10^5
- 0 \leq K \leq 10^9
- 1 \leq A_i,B_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K A_1 \ldots A_N B_1 \ldots B_N
Output
If there is an X that satisfies all of the conditions, print Yes; otherwise, print No.
Sample Input 1
5 4 9 8 3 7 2 1 6 2 9 5
Sample Output 1
Yes
X=(9,6,3,7,5) satisfies all conditions.
Sample Input 2
4 90 1 1 1 100 1 2 3 100
Sample Output 2
No
No X satisfies all conditions.
Sample Input 3
4 1000000000 1 1 1000000000 1000000000 1 1000000000 1 1000000000
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 400 点
問題文
空でない文字列 S が与えられます。S の各文字は (, ), ? のいずれかです。
S に含まれる ? の個数を x とすると、? を ( あるいは ) に置き換えて新しい文字列を作る方法は 2^x 通りありますが、このうち新しくできた文字列が括弧列となるような置き換え方の数を 998244353 で割った余りを求めてください。
ただし、括弧列とは以下のいずれかの条件を満たす文字列のことです。
- 空文字列
- ある括弧列 A が存在して、
(, A,)をこの順に連結した文字列 - ある空でない括弧列 A, B が存在して、A, B をこの順に連結した文字列
制約
- S は長さ 3000 以下の
(,),?からなる空でない文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを出力せよ。
入力例 1
(???(?
出力例 1
2
S を ()()() あるいは (())() に置き換えると括弧列となります。
他の置き換え方で新しくできた文字列が括弧列となることはないので、2 を出力します。
入力例 2
)))))
出力例 2
0
入力例 3
??????????????(????????(??????)?????????(?(??)
出力例 3
603032273
998244353 で割った余りを出力してください。
Score : 400 points
Problem Statement
You are given a non-empty string S consisting of (, ), and ?.
There are 2^x ways to obtain a new string by replacing each ? in S with ( and ), where x is the number of occurrences of ? in S. Among them, find the number, modulo 998244353, of ways that yield a parenthesis string.
A string is said to be a parenthesis string if one of the following conditions is satisfied.
- It is an empty string.
- It is a concatenation of
(, A, and), for some parenthesis string A. - It is a concatenation of A and B, for some non-empty parenthesis strings A and B.
Constraints
- S is a non-empty string of length at most 3000 consisting of
(,), and?.
Input
The input is given from Standard Input in the following format:
S
Output
Print the answer.
Sample Input 1
(???(?
Sample Output 1
2
Replacing S with ()()() or (())() yields a parenthesis string.
The other replacements do not yield a parenthesis string, so 2 should be printed.
Sample Input 2
)))))
Sample Output 2
0
Sample Input 3
??????????????(????????(??????)?????????(?(??)
Sample Output 3
603032273
Print the count modulo 998244353.