実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
相異なる二つの文字列 S, T が与えられます。
S が T よりも辞書順で小さい場合は Yes を、大きい場合は No を出力してください。
辞書順とは？
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、相異なる文字列 S と文字列 T の大小を判定するアルゴリズムを以下に説明します。
以下では「 S の i 文字目の文字」を S_i のように表します。また、 S が T より辞書順で小さい場合は S \lt T 、大きい場合は S \gt T と表します。
- S と T のうち長さが短い方の文字列の長さを L とします。i=1,2,\dots,L に対して S_i と T_i が一致するか調べます。
- S_i \neq T_i である i が存在する場合、そのような i のうち最小のものを j とします。そして、S_j と T_j を比較して、 S_j がアルファベット順で T_j より小さい場合は S \lt T 、大きい場合は S \gt T と決定して、アルゴリズムを終了します。
- S_i \neq T_i である i が存在しない場合、 S と T の長さを比較して、S が T より短い場合は S \lt T 、長い場合は S \gt T と決定して、アルゴリズムを終了します。
なお、主要なプログラミング言語の多くでは、文字列の辞書順による比較は標準ライブラリに含まれる関数や演算子として実装されています。詳しくは各言語のリファレンスをご参照ください。
制約
- S, T は英小文字からなる長さ 1 以上 10 以下の相異なる文字列である。
入力
入力は以下の形式で標準入力から与えられる。
S T
出力
S が T より辞書順で小さい場合は Yes を、大きい場合は No を出力せよ。
入力例 1
abc atcoder
出力例 1
Yes
abc と atcoder は 1 文字目が同じで 2 文字目が異なります。 アルファベットの b は t よりもアルファベット順で先に来るので、 abc の方が atcoder よりも辞書順で小さいことがわかります。
入力例 2
arc agc
出力例 2
No
入力例 3
a aa
出力例 3
Yes
Score : 100 points
Problem Statement
You are given two different strings S and T.
If S is lexicographically smaller than T, print Yes; otherwise, print No.
What is the lexicographical order?
Simply speaking, the lexicographical order is the order in which words are listed in a dictionary. As a more formal definition, here is the algorithm to determine the lexicographical order between different strings S and T.
Below, let S_i denote the i-th character of S. Also, if S is lexicographically smaller than T, we will denote that fact as S \lt T; if S is lexicographically larger than T, we will denote that fact as S \gt T.
- Let L be the smaller of the lengths of S and T. For each i=1,2,\dots,L, we check whether S_i and T_i are the same.
- If there is an i such that S_i \neq T_i, let j be the smallest such i. Then, we compare S_j and T_j. If S_j comes earlier than T_j in alphabetical order, we determine that S \lt T and quit; if S_j comes later than T_j, we determine that S \gt T and quit.
- If there is no i such that S_i \neq T_i, we compare the lengths of S and T. If S is shorter than T, we determine that S \lt T and quit; if S is longer than T, we determine that S \gt T and quit.
Note that many major programming languages implement lexicographical comparison of strings as operators or functions in standard libraries. For more detail, see your language's reference.
Constraints
- S and T are different strings, each of which consists of lowercase English letters and has a length of between 1 and 10 (inclusive).
Input
Input is given from Standard Input in the following format:
S T
Output
If S is lexicographically smaller than T, print Yes; otherwise, print No.
Sample Input 1
abc atcoder
Sample Output 1
Yes
abc and atcoder begin with the same character, but their second characters are different. Since b comes earlier than t in alphabetical order, we can see that abc is lexicographically smaller than atcoder.
Sample Input 2
arc agc
Sample Output 2
No
Sample Input 3
a aa
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 100 点
問題文
水圧は水深のみに依存し、水深 x [m] の場所では \dfrac{x}{100} [MPa] になるものとします。
水深 D [m] の場所の水圧は何 [MPa] ですか？
制約
- 1 \leq D \leq 10000
- D は整数である。
入力
入力は以下の形式で標準入力から与えられる。
D
出力
答えを出力せよ。想定解答との絶対誤差または相対誤差が 10^{-3} 以下であれば正解として扱われる。
入力例 1
1000
出力例 1
10
水深 1000 [m] の場所の水圧は 10 [MPa] です。10.0 や 9.999999 などを出力しても正解となります。
入力例 2
50
出力例 2
0.5
入力例 3
3141
出力例 3
31.41
Score : 100 points
Problem Statement
Let us assume that water pressure depends only on depth and is \dfrac{x}{100} megapascal at a depth of x meters.
What is the water pressure in megapascals at a depth of D meters?
Constraints
- 1 \leq D \leq 10000
- D is an integer.
Input
Input is given from Standard Input in the following format:
D
Output
Print the answer. Your output will be considered correct when its absolute or relative error from our answer is at most 10^{-3}.
Sample Input 1
1000
Sample Output 1
10
The water pressure at a depth of 1000 meters is 10 megapascal. Outputs such as 10.0 and 9.999999 would also be accepted.
Sample Input 2
50
Sample Output 2
0.5
Sample Input 3
3141
Sample Output 3
31.41
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 250 点
問題文
英小文字と ? からなる文字列 T と、英小文字のみからなる文字列 U が与えられます。
T は、英小文字のみからなる文字列 S のちょうど 4 文字を ? で置き換えることで得られた文字列です。
S が U を連続部分文字列として含んでいた可能性があるかどうか判定してください。
制約
- T は長さ 4 以上 10 以下の英小文字と
?からなる文字列 - T にはちょうど 4 つの
?が含まれる - U は長さ 1 以上 |T| 以下の英小文字からなる文字列
入力
入力は以下の形式で標準入力から与えられる。
T U
出力
S が U を部分文字列として含んでいた可能性があるならば Yes を、そうでないならば No を出力せよ。
入力例 1
tak??a?h? nashi
出力例 1
Yes
例えば、S が takanashi である場合、これは nashi を連続部分文字列として含みます。
入力例 2
??e??e snuke
出力例 2
No
? がどのような文字であっても、S は snuke を連続部分文字列として含むことがありません。
入力例 3
???? aoki
出力例 3
Yes
Score : 250 points
Problem Statement
You are given a string T consisting of lowercase English letters and ?, and a string U consisting of lowercase English letters.
The string T is obtained by taking some lowercase-only string S and replacing exactly four of its characters with ?.
Determine whether it is possible that the original string S contained U as a contiguous substring.
Constraints
- T is a string of length between 4 and 10, inclusive, consisting of lowercase letters and
?. - T contains exactly four occurrences of
?. - U is a string of length between 1 and |T|, inclusive, consisting of lowercase letters.
Input
The input is given from Standard Input in the following format:
T U
Output
Print Yes if it is possible that the original string S contained U as a contiguous substring; otherwise, print No.
Sample Input 1
tak??a?h? nashi
Sample Output 1
Yes
For example, if S is takanashi, it contains nashi as a contiguous substring.
Sample Input 2
??e??e snuke
Sample Output 2
No
No matter what characters replace the ?s in T, S cannot contain snuke as a contiguous substring.
Sample Input 3
???? aoki
Sample Output 3
Yes
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 200 点
問題文
H 行 W 列のマス目があり、そのうち二つの異なるマスに駒が置かれています。
マス目の状態は H 個の長さ W の文字列 S_1, \dots, S_H で表されます。S_{i, j} = o ならば i 行目 j 列目のマスに駒が置かれていることを、S_{i, j} = - ならばそのマスには駒が置かれていないことを表します。なお、S_{i, j} は文字列 S_i の j 文字目を指します。
一方の駒をマス目の外側に出ないように上下左右の隣接するマスに動かすことを繰り返すとき、もう一方の駒と同じマスに移動させるためには最小で何回動かす必要がありますか？
制約
- 2 \leq H, W \leq 100
- H, W は整数
- S_i \, (1 \leq i \leq H) は
oおよび-のみからなる長さ W の文字列 - S_{i, j} =
oとなる整数 1 \leq i \leq H, 1 \leq j \leq W の組がちょうど二つ存在する
入力
入力は以下の形式で標準入力から与えられる。
H W S_1 \vdots S_H
出力
答えを出力せよ。
入力例 1
2 3 --o o--
出力例 1
3
1 行目 3 列目に置かれている駒を 下 \rightarrow 左 \rightarrow 左 と移動すると 3 回でもう一方の駒と同じマスに移動させることができます。2 回以下で移動させることはできないので、3 を出力します。
入力例 2
5 4 -o-- ---- ---- ---- -o--
出力例 2
4
Score : 200 points
Problem Statement
There is a grid with H horizontal rows and W vertical columns, in which two distinct squares have a piece.
The state of the squares is represented by H strings S_1, \dots, S_H of length W. S_{i, j} = o means that there is a piece in the square at the i-th row from the top and j-th column from the left; S_{i, j} = - means that the square does not have a piece. Here, S_{i, j} denotes the j-th character of the string S_i.
Consider repeatedly moving one of the pieces to one of the four adjacent squares. It is not allowed to move the piece outside the grid. How many moves are required at minimum for the piece to reach the square with the other piece?
Constraints
- 2 \leq H, W \leq 100
- H and W are integers.
- S_i \, (1 \leq i \leq H) is a string of length W consisting of
oand-. - There exist exactly two pairs of integers 1 \leq i \leq H, 1 \leq j \leq W such that S_{i, j} =
o.
Input
Input is given from Standard Input in the following format:
H W S_1 \vdots S_H
Output
Print the answer.
Sample Input 1
2 3 --o o--
Sample Output 1
3
The piece at the 1-st row from the top and 3-rd column from the left can reach the square with the other piece in 3 moves: down, left, left. Since it is impossible to do so in two or less moves, 3 should be printed.
Sample Input 2
5 4 -o-- ---- ---- ---- -o--
Sample Output 2
4
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 350 点
問題文
この問題は F 問題の簡易版です。
長さ N の整数列 A=(A_1,A_2,\ldots,A_N) が与えられます。
A を 1 か所で区切って 2 個の空でない連続する部分列に分割するとき、数列に含まれる数の種類数の和としてありえる最大値を求めてください。
より厳密には、1 \leq i \leq N-1 を満たす整数 i について (A_1,A_2,\ldots,A_i), (A_{i+1},A_{i+2},\ldots,A_N) のそれぞれに含まれる整数の種類数の和としてありえる最大値を求めてください。
制約
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 入力はすべて整数である
入力
入力は以下の形式で標準入力から与えられる。
N A_1 A_2 \ldots A_N
出力
答えを出力せよ。
入力例 1
5 3 1 4 1 5
出力例 1
5
- i=1 としたとき、(3) と (1,4,1,5) のそれぞれに含まれる整数の種類数は 1,3 で、これらの和は 4 です。
- i=2 としたとき、(3,1) と (4,1,5) のそれぞれに含まれる整数の種類数は 2,3 で、これらの和は 5 です。
- i=3 としたとき、(3,1,4) と (1,5) のそれぞれに含まれる整数の種類数は 3,2 で、これらの和は 5 です。
- i=4 としたとき、(3,1,4,1) と (5) のそれぞれに含まれる整数の種類数は 3,1 で、これらの和は 4 です。
よって、 i=2,3 のときに、最大値 5 を取ります。
入力例 2
10 2 5 6 5 2 1 7 9 7 2
出力例 2
8
Score : 350 points
Problem Statement
This problem is a simplified version of Problem F.
You are given an integer sequence of length N: A = (A_1, A_2, \ldots, A_N).
When splitting A at one position into two non-empty (contiguous) subarrays, find the maximum possible sum of the counts of distinct integers in those subarrays.
More formally, find the maximum sum of the following two values for an integer i such that 1 \leq i \leq N-1: the count of distinct integers in (A_1, A_2, \ldots, A_i), and the count of distinct integers in (A_{i+1}, A_{i+2}, \ldots, A_N).
Constraints
- 2 \leq N \leq 3 \times 10^5
- 1 \leq A_i \leq N (1 \leq i \leq N)
- 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 answer.
Sample Input 1
5 3 1 4 1 5
Sample Output 1
5
- For i=1, (3) contains 1 distinct integer, and (1,4,1,5) contains 3 distinct integers, for a total of 4.
- For i=2, (3,1) contains 2 distinct integers, and (4,1,5) contains 3 distinct integers, for a total of 5.
- For i=3, (3,1,4) contains 3 distinct integers, and (1,5) contains 2 distinct integers, for a total of 5.
- For i=4, (3,1,4,1) contains 3 distinct integers, and (5) contains 1 distinct integer, for a total of 4.
Therefore, the maximum sum is 5 for i=2,3.
Sample Input 2
10 2 5 6 5 2 1 7 9 7 2
Sample Output 2
8