Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
直線上に 7 個の点 A, B, C, D, E, F, G がこの順に並んでいます。(下の図も参考にしてください)
隣り合う点の距離は次の通りです。
- 点 A と点 B の距離は 3
- 点 B と点 C の距離は 1
- 点 C と点 D の距離は 4
- 点 D と点 E の距離は 1
- 点 E と点 F の距離は 5
- 点 F と点 G の距離は 9

2 つの英大文字 p, q が与えられます。p, q は A,B,C,D,E,F,G のいずれかで、 p \neq q が成り立ちます。
点 p と点 q の間の距離を答えてください。
制約
- p, q は
A,B,C,D,E,F,Gのいずれか - p \neq q
入力
入力は以下の形式で標準入力から与えられる。
p q
出力
点 p と点 q の間の距離を出力せよ。
入力例 1
A C
出力例 1
4
点 A と点 C の距離は 3 + 1 = 4 です。
入力例 2
G B
出力例 2
20
点 G と点 B の距離は 9 + 5 + 1 + 4 + 1 = 20 です。
入力例 3
C F
出力例 3
10
Score : 200 points
Problem Statement
There are 7 points A, B, C, D, E, F, and G on a straight line, in this order. (See also the figure below.)
The distances between adjacent points are as follows.
- Between A and B: 3
- Between B and C: 1
- Between C and D: 4
- Between D and E: 1
- Between E and F: 5
- Between F and G: 9

You are given two uppercase English letters p and q. Each of p and q is A, B, C, D, E, F, or G, and it holds that p \neq q.
Find the distance between the points p and q.
Constraints
- Each of p and q is
A,B,C,D,E,F, orG. - p \neq q
Input
The input is given from Standard Input in the following format:
p q
Output
Print the distance between the points p and q.
Sample Input 1
A C
Sample Output 1
4
The distance between the points A and C is 3 + 1 = 4.
Sample Input 2
G B
Sample Output 2
20
The distance between the points G and B is 9 + 5 + 1 + 4 + 1 = 20.
Sample Input 3
C F
Sample Output 3
10
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
空でない文字列に対し、先頭の文字を末尾に移動する操作を左シフト、末尾の文字を先頭に移動する操作を右シフトと呼びます。
例えば、abcde に対して左シフトを 1 回行うと bcdea となり、右シフトを 2 回行うと deabc となります。
英小文字からなる空でない文字列 S が与えられます。S に対し左シフトと右シフトをそれぞれ好きな回数(0 回でもよい)行って得られる文字列のうち、辞書順で最小のものと最大のものを求めてください。
辞書順とは?
辞書順とは簡単に説明すると「単語が辞書に載っている順番」を意味します。より厳密な説明として、英小文字からなる相異なる文字列 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 は英小文字からなる。
- S の長さは 1 以上 1000 以下である。
入力
入力は以下の形式で標準入力から与えられる。
S
出力
2 行にわたって出力せよ。S に対し左シフトと右シフトをそれぞれ好きな回数(0 回でもよい)行って得られる文字列のうち、辞書順で最小のものと最大のものをそれぞれ S_{\min}, S_{\max} とおいたとき、1 行目には S_{\min} を、2 行目には S_{\max} を出力せよ。
入力例 1
aaba
出力例 1
aaab baaa
操作によって、aaab , aaba , abaa , baaa の 4 通りの文字列を得ることができます。
これらのうち辞書順で最小、最大のものはそれぞれ aaab , baaa です。
入力例 2
z
出力例 2
z z
どのように操作を行っても、得られる文字列は z のみです。
入力例 3
abracadabra
出力例 3
aabracadabr racadabraab
Score : 200 points
Problem Statement
On a non-empty string, a left shift moves the first character to the end of the string, and a right shift moves the last character to the beginning of the string.
For example, a left shift on abcde results in bcdea, and two right shifts on abcde result in deabc.
You are given a non-empty S consisting of lowercase English letters. Among the strings that can be obtained by performing zero or more left shifts and zero or more right shifts on S, find the lexicographically smallest string and the lexicographically largest string.
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.
Constraints
- S consists of lowercase English letters.
- The length of S is between 1 and 1000 (inclusive).
Input
Input is given from Standard Input in the following format:
S
Output
Print two lines. The first line should contain S_{\min}, and the second line should contain S_{\max}. Here, S_{\min} and S_{\max} are respectively the lexicographically smallest and largest strings obtained by performing zero or more left shifts and zero or more right shifts on S.
Sample Input 1
aaba
Sample Output 1
aaab baaa
By performing shifts, we can obtain four strings: aaab, aaba, abaa, baaa. The lexicographically smallest and largest among them are aaab and baaa, respectively.
Sample Input 2
z
Sample Output 2
z z
Any sequence of operations results in z.
Sample Input 3
abracadabra
Sample Output 3
aabracadabr racadabraab
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 250 点
問題文
長さ N の数列 A が与えられます。
A のうち丁度 K 要素を自由に選んで消し、残った要素を順序を保って連結した数列を B とします。
( B の最大値 ) - ( B の最小値 ) としてありうる最小値を求めてください。
制約
- 入力は全て整数
- 1 \le K < N \le 2 \times 10^5
- 1 \le A_i \le 10^9
入力
入力は以下の形式で標準入力から与えられる。
N K A_1 A_2 \dots A_N
出力
答えを整数として出力せよ。
入力例 1
5 2 3 1 5 4 9
出力例 1
2
A=(3,1,5,4,9) から丁度 2 要素を自由に選んで消すことを考えます。
- 例えば 2 要素目の 1 、 5 要素目の 9 を消すと、消した後の数列 B=(3,5,4) となります。
- このとき B の最大値は 5 、最小値は 3 なので ( B の最大値 ) - ( B の最小値 ) =2 となり、これは達成可能な最小値です。
入力例 2
6 5 1 1 1 1 1 1
出力例 2
0
入力例 3
8 3 31 43 26 6 18 36 22 13
出力例 3
18
Score : 250 points
Problem Statement
You are given a sequence A of length N.
Freely choose exactly K elements from A and remove them, then concatenate the remaining elements in their original order to form a new sequence B.
Find the minimum possible value of this: the maximum value of B minus the minimum value of B.
Constraints
- All inputs are integers.
- 1 \le K < N \le 2 \times 10^5
- 1 \le A_i \le 10^9
Input
The input is given from Standard Input in the following format:
N K A_1 A_2 \dots A_N
Output
Print the answer as an integer.
Sample Input 1
5 2 3 1 5 4 9
Sample Output 1
2
Consider removing exactly two elements from A=(3,1,5,4,9).
- For example, if you remove the 2nd element 1 and the 5th element 9, the resulting sequence is B=(3,5,4).
- In this case, the maximum value of B is 5 and the minimum value is 3, so (maximum value of B) - (minimum value of B) =2, which is the minimum possible value.
Sample Input 2
6 5 1 1 1 1 1 1
Sample Output 2
0
Sample Input 3
8 3 31 43 26 6 18 36 22 13
Sample Output 3
18
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 300 点
問題文
高橋君は黒いマスと透明なマスからなるシート A,B を 1 枚ずつと、透明なマスのみからなる無限に広がるシート C を持っています。
また、高橋君には黒いマスと透明なマスからなる、理想とするシート X が存在します。
シート A,B,X の大きさはそれぞれ縦 H_A マス \times 横 W_A マス、縦 H_B マス \times 横 W_B マス、縦 H_X マス \times 横 W_X マスです。
シート A の各マスは . と # からなる長さ W_A の文字列 H_A 個 A_1,A_2,\ldots,A_{H_A} によって表され、
A_i (1\leq i\leq H_A) の j 文字目 (1\leq j\leq W_A) が、
. のときシート A の上から i 行目かつ左から j 列目のマスは透明なマスであり、
# のとき黒いマスです。
シート B,X の各マスも、同様に長さ W_B の文字列 H_B 個 B_1,B_2,\ldots,B_{H_B} および長さ W_X の文字列 H_X 個 X_1,X_2,\ldots,X_{H_X} によって表されます。
高橋君の目標は、次の手順で、シート A,B,C から、A,B に存在する すべての黒いマスを使って シート X を作り出すことです。
- シート A,B をマス目に沿ってシート C に貼り付ける。この時、シート A,B はそれぞれ好きな場所に平行移動させて貼って良いが、シートを切り分けたり、回転させたりしてはいけない。
- シート C からマス目に沿って H_X\times W_X マスの領域を切り出す。ここで、切り出されたシートの各マスは、シート A または B の黒いマスが貼り付けられていれば黒いマスに、そうでなければ透明なマスとなる。
このとき、貼り付ける位置と切り出す領域をうまくとることで高橋君は目標を達成できるか、すなわち次の条件をともにみたすことにできるか判定してください。
- 切り出されたシートはシート A,B の 黒いマスをすべて 含む。切り出されたシートの上でシート A,B の黒いマスどうしが重なって存在していても構わない。
- 切り出されたシートは、回転させたり裏返したりすることなくシート X と一致する。
制約
- 1\leq H_A,W_A,H_B,W_B,H_X,W_X\leq 10
- H_A,W_A,H_B,W_B,H_X,W_X は整数
- A_i は
.と#のみからなる長さ W_A の文字列 - B_i は
.と#のみからなる長さ W_B の文字列 - X_i は
.と#のみからなる長さ W_X の文字列 - シート A,B,X はそれぞれ少なくとも 1 つ以上の黒いマスを含む。
入力
入力は以下の形式で標準入力から与えられる。
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
出力
高橋君が問題文中の目標を達成できるならば Yes を、できないならば No を出力せよ。
入力例 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
出力例 1
Yes
まず、シート A をシート C に貼り付けると下図のようになります。
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
さらに、シート B をシート A と左上を合わせて貼ってみると下図のようになります。
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
ここで、上で具体的に図示されている範囲のうち、上から 1 行目かつ左から 2 列目のマスを左上として 5\times 3 マスを切り出すと下図のようになります。
... #.# .#. .#. ...
これはシート A,B のすべての黒いマスを含んでおり、また、シート X と一致しているため条件を満たしています。
よって、Yes を出力します。
入力例 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
出力例 2
No
シート A や B を回転させて貼ってはいけないことに注意してください。
入力例 3
1 1 # 1 2 ## 1 1 #
出力例 3
No
どのように貼ったり切り出したりしても、シート B の黒いマスをすべて含むように切り出すことはできないため、1 つめの条件をみたすことができません。
よって、No を出力します。
入力例 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
出力例 4
Yes
Score : 300 points
Problem Statement
Takahashi has two sheets A and B, each composed of black squares and transparent squares, and an infinitely large sheet C composed of transparent squares.
There is also an ideal sheet X for Takahashi composed of black squares and transparent squares.
The sizes of sheets A, B, and X are H_A rows \times W_A columns, H_B rows \times W_B columns, and H_X rows \times W_X columns, respectively.
The squares of sheet A are represented by H_A strings of length W_A, A_1, A_2, \ldots, A_{H_A} consisting of . and #.
If the j-th character (1\leq j\leq W_A) of A_i (1\leq i\leq H_A) is ., the square at the i-th row from the top and j-th column from the left is transparent; if it is #, that square is black.
Similarly, the squares of sheets B and X are represented by H_B strings of length W_B, B_1, B_2, \ldots, B_{H_B}, and H_X strings of length W_X, X_1, X_2, \ldots, X_{H_X}, respectively.
Takahashi's goal is to create sheet X using all black squares in sheets A and B by following the steps below with sheets A, B, and C.
- Paste sheets A and B onto sheet C along the grid. Each sheet can be pasted anywhere by translating it, but it cannot be cut or rotated.
- Cut out an H_X\times W_X area from sheet C along the grid. Here, a square of the cut-out sheet will be black if a black square of sheet A or B is pasted there, and transparent otherwise.
Determine whether Takahashi can achieve his goal by appropriately choosing the positions where the sheets are pasted and the area to cut out, that is, whether he can satisfy both of the following conditions.
- The cut-out sheet includes all black squares of sheets A and B. The black squares of sheets A and B may overlap on the cut-out sheet.
- The cut-out sheet coincides sheet X without rotating or flipping.
Constraints
- 1\leq H_A, W_A, H_B, W_B, H_X, W_X\leq 10
- H_A, W_A, H_B, W_B, H_X, W_X are integers.
- A_i is a string of length W_A consisting of
.and#. - B_i is a string of length W_B consisting of
.and#. - X_i is a string of length W_X consisting of
.and#. - Sheets A, B, and X each contain at least one black square.
Input
The input is given from Standard Input in the following format:
H_A W_A
A_1
A_2
\vdots
A_{H_A}
H_B W_B
B_1
B_2
\vdots
B_{H_B}
H_X W_X
X_1
X_2
\vdots
X_{H_X}
Output
If Takahashi can achieve the goal described in the problem statement, print Yes; otherwise, print No.
Sample Input 1
3 5 #.#.. ..... .#... 2 2 #. .# 5 3 ... #.# .#. .#. ...
Sample Output 1
Yes
First, paste sheet A onto sheet C, as shown in the figure below.
\vdots
.......
.#.#...
\cdots.......\cdots
..#....
.......
\vdots
Next, paste sheet B so that its top-left corner aligns with that of sheet A, as shown in the figure below.
\vdots
.......
.#.#...
\cdots..#....\cdots
..#....
.......
\vdots
Now, cut out a 5\times 3 area with the square in the first row and second column of the range illustrated above as the top-left corner, as shown in the figure below.
... #.# .#. .#. ...
This includes all black squares of sheets A and B and matches sheet X, satisfying the conditions.
Therefore, print Yes.
Sample Input 2
2 2 #. .# 2 2 #. .# 2 2 ## ##
Sample Output 2
No
Note that sheets A and B may not be rotated or flipped when pasting them.
Sample Input 3
1 1 # 1 2 ## 1 1 #
Sample Output 3
No
No matter how you paste or cut, you cannot cut out a sheet that includes all black squares of sheet B, so you cannot satisfy the first condition.
Therefore, print No.
Sample Input 4
3 3 ### ... ... 3 3 #.. #.. #.. 3 3 ..# ..# ###
Sample Output 4
Yes
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
無限に続く階段があります。 一番下は 0 段目で、1 段のぼるごとに 1 段目、2 段目と続きます。
0 段目に階段登りロボットがいます。 階段登りロボットは、一回の動作で A _ 1,A _ 2,\ldots,A _ N 段ぶん階段をのぼることができます。 つまり、階段登りロボットが i 段目にいるとき、一回動作をした後は i+A _ 1 段目、i+A _ 2 段目、⋯、i+A _ N 段目のいずれかにいることができます。 それ以外の段数を一回の動作でのぼることはできません。 階段登りロボットは階段を下ることもできません。
階段の B _ 1,B _ 2,\ldots,B _ M 段目にはモチが設置されています。 モチが設置されている段へのぼるとロボットは動けなくなり、他の段に移動することができなくなります。
階段登りロボットは階段のちょうど X 段目にのぼりたいです。 階段登りロボットが階段のちょうど X 段目にのぼることが可能か判定してください。
制約
- 1\leq N\leq10
- 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
- 1\leq M\leq10^5
- 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
- 入力はすべて整数
入力
入力は以下の形式で標準入力から与えられる。
N A _ 1 A _ 2 \ldots A _ N M B _ 1 B _ 2 \ldots B _ M X
出力
階段登りロボットが階段のちょうど X 段目にのぼることができるとき Yes を、そうでないとき No を 1 行に出力せよ。
入力例 1
3 3 4 5 4 4 5 6 8 15
出力例 1
Yes
例えば、次のようにして 15 段目に到達することができます。
- 階段を 3 段のぼる。ロボットは 3 段目に移動する。
- 階段を 4 段のぼる。ロボットは 7 段目に移動する。
- 階段を 5 段のぼる。ロボットは 12 段目に移動する。
- 階段を 3 段のぼる。ロボットは 15 段目に移動する。
入力例 2
4 2 3 4 5 4 3 4 5 6 8
出力例 2
No
どのように移動しても階段登りロボットが階段のちょうど 8 段目にいることはできません。
入力例 3
4 2 5 7 8 5 2 9 10 11 19 20
出力例 3
Yes
Score : 400 points
Problem Statement
There is a staircase with infinite steps. The foot of the stairs is the 0-th step, the next step is the 1-st step, the next is the 2-nd, and so on.
There is a stair-climbing robot on the 0-th step. The robot can climb up A _ 1,A _ 2,\ldots, or A _ N steps at a time. In other words, when the robot is on the i-th step, it can step onto one of the (i+A _ 1)-th step, (i+A _ 2)-th step, \ldots, and (i+A _ N)-th step, but not onto the others in a single step. The robot cannot descend the stairs, either.
There are traps on the B _ 1-th, B _ 2-th, \ldots, and B _ M-th steps. Once the robot steps onto a step with a trap, it cannot move anymore.
The robot wants to step onto the X-th step. Determine whether it is possible to do so.
Constraints
- 1\leq N\leq10
- 1\leq A _ 1\lt A _ 2\lt\cdots\lt A _ N\leq10^5
- 1\leq M\leq10^5
- 1\leq B _ 1\lt B _ 2\lt\cdots\lt B _ M\lt X\leq10^5
- All values in the input are integers.
Input
The input is given from Standard Input in the following format:
N A _ 1 A _ 2 \ldots A _ N M B _ 1 B _ 2 \ldots B _ M X
Output
In a single line, print Yes if the robot can step onto the X-th step, and No otherwise.
Sample Input 1
3 3 4 5 4 4 5 6 8 15
Sample Output 1
Yes
For example, the robot can reach the 15-th step as follows.
- Climb up 3 steps. The robot is now on the 3-rd step.
- Climb up 4 steps. The robot is now on the 7-th step.
- Climb up 5 steps. The robot is now on the 12-th step.
- Climb up 3 steps. The robot is now on the 15-th step.
Sample Input 2
4 2 3 4 5 4 3 4 5 6 8
Sample Output 2
No
No matter how the robot moves, it cannot step onto the 8-th step.
Sample Input 3
4 2 5 7 8 5 2 9 10 11 19 20
Sample Output 3
Yes