Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 300 点
問題文
すぬけ君は、文字列の書かれた紙から文字をいくつか切り抜いて、並び替えて別の文字列を作るのが好きです。
明日になると、すぬけ君は文字列 S_1,...,S_n のうちどれか 1 つが書かれた紙がもらえます。 すぬけ君は文字列を作る事をとても楽しみにしているので、どんな文字列を作るか計画を立てることにしました。 ただし、すぬけ君はまだどの文字列が書かれた紙がもらえるかを知らないため、 どの文字列が書かれていた場合にも作れる文字列を考えることにしました。
S_1,...,S_n のどの文字列が書かれていても作れる文字列のうち、最長のものを求めてください。 最長のものが複数ある場合は、辞書順で最小のものを求めてください。
制約
- 1 \leq n \leq 50
- i = 1, ... , n に対して、 1 \leq |S_i| \leq 50
- i = 1, ... , n に対して、 S_i は小文字のアルファベット(
a
-z
)からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
n S_1 ... S_n
出力
条件を満たす最長の文字列のうち、辞書順で最小のものを出力せよ。 そのような文字列が空文字列である場合は、空行を出力せよ。
入力例 1
3 cbaa daacc acacac
出力例 1
aac
cbaa
, daacc
, acacac
のどの文字列からも aa
, aac
, aca
, caa
などが作れます。
そのうち最も長いものは aac
, aca
, caa
です。
この中で辞書順で最小のものは aac
なので、 aac
が答えになります。
入力例 2
3 a aa b
出力例 2
条件を満たす文字列は空文字列のみです。
Score : 300 points
Problem Statement
Snuke loves "paper cutting": he cuts out characters from a newspaper headline and rearranges them to form another string.
He will receive a headline which contains one of the strings S_1,...,S_n tomorrow. He is excited and already thinking of what string he will create. Since he does not know the string on the headline yet, he is interested in strings that can be created regardless of which string the headline contains.
Find the longest string that can be created regardless of which string among S_1,...,S_n the headline contains. If there are multiple such strings, find the lexicographically smallest one among them.
Constraints
- 1 \leq n \leq 50
- 1 \leq |S_i| \leq 50 for every i = 1, ..., n.
- S_i consists of lowercase English letters (
a
-z
) for every i = 1, ..., n.
Input
Input is given from Standard Input in the following format:
n S_1 ... S_n
Output
Print the lexicographically smallest string among the longest strings that satisfy the condition. If the answer is an empty string, print an empty line.
Sample Input 1
3 cbaa daacc acacac
Sample Output 1
aac
The strings that can be created from each of cbaa
, daacc
and acacac
, are aa
, aac
, aca
, caa
and so forth.
Among them, aac
, aca
and caa
are the longest, and the lexicographically smallest of these three is aac
.
Sample Input 2
3 a aa b
Sample Output 2
The answer is an empty string.
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
2 次元平面上に x 軸と平行な直線が m 本と y 軸と平行な直線が n 本引いてあります。 x 軸と平行な直線のうち下から i 番目は y = y_i で表せます。 y 軸と平行な直線のうち左から i 番目は x = x_i で表せます。
この中に存在しているすべての長方形についてその面積を求め、 合計を 10^9+7 で割ったあまりを出力してください。
つまり、1\leq i < j\leq n と 1\leq k < l\leq m を満たすすべての組 (i,j,k,l) について、 直線 x=x_i, x=x_j, y=y_k, y=y_l で囲まれる 長方形の面積を求め、合計を 10^9+7 で割ったあまりを出力してください。
制約
- 2 \leq n,m \leq 10^5
- -10^9 \leq x_1 < ... < x_n \leq 10^9
- -10^9 \leq y_1 < ... < y_m \leq 10^9
- x_i, y_i は整数である。
入力
入力は以下の形式で標準入力から与えられる。
n m x_1 x_2 ... x_n y_1 y_2 ... y_m
出力
長方形の面積の合計を 10^9+7 で割ったあまりを 1 行に出力せよ。
入力例 1
3 3 1 3 4 1 3 6
出力例 1
60
この入力を図にすると、以下のようになります。
長方形 A,B,...,I それぞれの面積を合計すると 60 になります。
入力例 2
6 5 -790013317 -192321079 95834122 418379342 586260100 802780784 -253230108 193944314 363756450 712662868 735867677
出力例 2
835067060
Score : 500 points
Problem Statement
On a two-dimensional plane, there are m lines drawn parallel to the x axis, and n lines drawn parallel to the y axis. Among the lines parallel to the x axis, the i-th from the bottom is represented by y = y_i. Similarly, among the lines parallel to the y axis, the i-th from the left is represented by x = x_i.
For every rectangle that is formed by these lines, find its area, and print the total area modulo 10^9+7.
That is, for every quadruple (i,j,k,l) satisfying 1\leq i < j\leq n and 1\leq k < l\leq m, find the area of the rectangle formed by the lines x=x_i, x=x_j, y=y_k and y=y_l, and print the sum of these areas modulo 10^9+7.
Constraints
- 2 \leq n,m \leq 10^5
- -10^9 \leq x_1 < ... < x_n \leq 10^9
- -10^9 \leq y_1 < ... < y_m \leq 10^9
- x_i and y_i are integers.
Input
Input is given from Standard Input in the following format:
n m x_1 x_2 ... x_n y_1 y_2 ... y_m
Output
Print the total area of the rectangles, modulo 10^9+7.
Sample Input 1
3 3 1 3 4 1 3 6
Sample Output 1
60
The following figure illustrates this input:
The total area of the nine rectangles A, B, ..., I shown in the following figure, is 60.
Sample Input 2
6 5 -790013317 -192321079 95834122 418379342 586260100 802780784 -253230108 193944314 363756450 712662868 735867677
Sample Output 2
835067060
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 600 点
問題文
A
, B
からなる文字列に対して、次の操作を考えます。
- 文字列中の 1 文字を選ぶ。それが
A
ならBB
で、B
ならAA
で置き換える。 AAA
かBBB
であるような部分文字列を選び、消す。
例えば、ABA
という文字列で 1 番目の操作を 1 文字目に対して行うと、 BBBA
となります。
また、BBBAAAA
に対して 2 番目の操作を 4 文字目から 6 文字目に対して行うと、 BBBA
となります。
これらの操作を何回でも好きな順で行うことができます。
文字列 S,T と q 個のクエリ a_i, b_i, c_i, d_i が与えられます。 各クエリに対して、 S の部分文字列 S_{a_i} S_{{a_i}+1} ... S_{b_i} を T の部分文字列 T_{c_i} T_{{c_i}+1} ... T_{d_i} にすることができるか判定してください。
制約
- 1 \leq |S|, |T| \leq 10^5
- S,T は文字
A
,B
からなる。 - 1 \leq q \leq 10^5
- 1 \leq a_i \leq b_i \leq |S|
- 1 \leq c_i \leq d_i \leq |T|
入力
入力は以下の形式で標準入力から与えられる。
S T q a_1 b_1 c_1 d_1 ... a_q b_q c_q d_q
出力
q 行出力せよ。
i 行目には、 i 番目のクエリに対する答えを出力せよ。
S_{a_i} S_{{a_i}+1} ... S_{b_i} を
T_{c_i} T_{{c_i}+1} ... T_{d_i} にすることができる場合は YES
を、
できない場合は NO
を出力せよ。
入力例 1
BBBAAAABA BBBBA 4 7 9 2 5 7 9 1 4 1 7 2 5 1 7 2 4
出力例 1
YES NO YES NO
1 つめのクエリでは、 ABA
という文字列を BBBA
にできるか聞かれています。
問題文中で例に挙げたように、1 番目の操作で可能です。
2 つめのクエリでは、 ABA
という文字列を BBBB
にできるか聞かれています。
4 つめのクエリでは、 BBBAAAA
という文字列を BBB
にできるか聞かれています。
どちらも不可能です。
3 つめのクエリでは、BBBAAAA
という文字列を BBBA
にできるか聞かれています。
問題文中で例に挙げたように、2 番目の操作で可能です。
入力例 2
AAAAABBBBAAABBBBAAAA BBBBAAABBBBBBAAAAABB 10 2 15 2 13 2 13 6 16 1 13 2 20 4 20 3 20 1 18 9 19 2 14 1 11 3 20 3 15 6 16 1 17 4 18 8 20 7 20 3 14
出力例 2
YES YES YES YES YES YES NO NO NO NO
Score : 600 points
Problem Statement
Let us consider the following operations on a string consisting of A
and B
:
- Select a character in a string. If it is
A
, replace it withBB
. If it isB
, replace withAA
. - Select a substring that is equal to either
AAA
orBBB
, and delete it from the string.
For example, if the first operation is performed on ABA
and the first character is selected, the string becomes BBBA
.
If the second operation is performed on BBBAAAA
and the fourth through sixth characters are selected, the string becomes BBBA
.
These operations can be performed any number of times, in any order.
You are given two string S and T, and q queries a_i, b_i, c_i, d_i. For each query, determine whether S_{a_i} S_{{a_i}+1} ... S_{b_i}, a substring of S, can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, a substring of T.
Constraints
- 1 \leq |S|, |T| \leq 10^5
- S and T consist of letters
A
andB
. - 1 \leq q \leq 10^5
- 1 \leq a_i \leq b_i \leq |S|
- 1 \leq c_i \leq d_i \leq |T|
Input
Input is given from Standard Input in the following format:
S T q a_1 b_1 c_1 d_1 ... a_q b_q c_q d_q
Output
Print q lines. The i-th line should contain the response to the i-th query. If S_{a_i} S_{{a_i}+1} ... S_{b_i} can be made into T_{c_i} T_{{c_i}+1} ... T_{d_i}, print YES
. Otherwise, print NO
.
Sample Input 1
BBBAAAABA BBBBA 4 7 9 2 5 7 9 1 4 1 7 2 5 1 7 2 4
Sample Output 1
YES NO YES NO
The first query asks whether the string ABA
can be made into BBBA
.
As explained in the problem statement, it can be done by the first operation.
The second query asks whether ABA
can be made into BBBB
, and the fourth query asks whether BBBAAAA
can be made into BBB
.
Neither is possible.
The third query asks whether the string BBBAAAA
can be made into BBBA
.
As explained in the problem statement, it can be done by the second operation.
Sample Input 2
AAAAABBBBAAABBBBAAAA BBBBAAABBBBBBAAAAABB 10 2 15 2 13 2 13 6 16 1 13 2 20 4 20 3 20 1 18 9 19 2 14 1 11 3 20 3 15 6 16 1 17 4 18 8 20 7 20 3 14
Sample Output 2
YES YES YES YES YES YES NO NO NO NO
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 1000 点
問題文
{{1, ... ,n}} からなる無限長の列 a_1, a_2, ... のうち、 次の条件を満たしているものは何通りあるでしょうか?
- 第 n 項から先はすべて同じ数である。つまり、n \leq i,j ならば a_i = a_j を満たす。
- どの正の整数 i に対しても、第 i 項の直後に並ぶ a_i 個の項はすべて同じ数である。つまり、 i < j < k\leq i+a_i ならば a_j = a_k を満たす。
答えを 10^9+7 で割ったあまりを求めてください。
制約
- 1 \leq n \leq 10^6
- n は整数
入力
入力は以下の形式で標準入力から与えられる。
n
出力
条件を満たす数列の数を 10^9+7 で割ったあまりを出力せよ。
入力例 1
2
出力例 1
4
以下の 4 通りがあります。
- 1, 1, 1, ...
- 1, 2, 2, ...
- 2, 1, 1, ...
- 2, 2, 2, ...
入力例 2
654321
出力例 2
968545283
Score : 1000 points
Problem Statement
How many infinite sequences a_1, a_2, ... consisting of {{1, ... ,n}} satisfy the following conditions?
- The n-th and subsequent elements are all equal. That is, if n \leq i,j, a_i = a_j.
- For every integer i, the a_i elements immediately following the i-th element are all equal. That is, if i < j < k\leq i+a_i, a_j = a_k.
Find the count modulo 10^9+7.
Constraints
- 1 \leq n \leq 10^6
Input
Input is given from Standard Input in the following format:
n
Output
Print how many sequences satisfy the conditions, modulo 10^9+7.
Sample Input 1
2
Sample Output 1
4
The four sequences that satisfy the conditions are:
- 1, 1, 1, ...
- 1, 2, 2, ...
- 2, 1, 1, ...
- 2, 2, 2, ...
Sample Input 2
654321
Sample Output 2
968545283