Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 200 点
問題文
正整数 N が与えられるので、 2^k \le N となる最大の整数 k を求めてください。
制約
- N は 1 \le N \le 10^{18} を満たす整数である
入力
入力は以下の形式で標準入力から与えられる。
N
出力
答えを整数として出力せよ。
入力例 1
6
出力例 1
2
- k=2 は 2^2=4 \le 6 を満たします。
- k \ge 3 である全ての整数 k について 2^k > 6 となります。
以上より、答えは k=2 となります。
入力例 2
1
出力例 2
0
2^0=1 であることに注意してください。
入力例 3
1000000000000000000
出力例 3
59
入力が 32 bit 整数に収まらない場合があります。
Score : 200 points
Problem Statement
Given a positive integer N, find the maximum integer k such that 2^k \le N.
Constraints
- N is an integer satisfying 1 \le N \le 10^{18}.
Input
Input is given from Standard Input in the following format:
N
Output
Print the answer as an integer.
Sample Input 1
6
Sample Output 1
2
- k=2 satisfies 2^2=4 \le 6.
- For every integer k such that k \ge 3, 2^k > 6 holds.
Therefore, the answer is k=2.
Sample Input 2
1
Sample Output 2
0
Note that 2^0=1.
Sample Input 3
1000000000000000000
Sample Output 3
59
The input value may not fit into a 32-bit integer.
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
配点 : 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
配点 : 300 点
問題文
りんご市場に N 人の売り手と M 人の買い手がいます。
i 番目の売り手は、A_i 円以上でならりんごを売ってもよいと考えています。
i 番目の買い手は、B_i 円以下でならりんごを買ってもよいと考えています。
次の条件を満たすような最小の整数 X を求めてください。
条件：りんごを X 円で売ってもよいと考える売り手の人数が、りんごを X 円で買ってもよいと考える買い手の人数以上である。
制約
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- 入力は全て整数である
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 \ldots A_N B_1 \ldots B_M
出力
答えを出力せよ。
入力例 1
3 4 110 90 120 100 80 120 10000
出力例 1
110
りんごを 110 円で売ってもよいと考える売り手は 1,2 番目の 2 人であり、りんごを 110 円で買ってもよいと考える買い手は 3,4 番目の 2 人であるため、110 は条件を満たします。
110 未満の整数が条件を満たすことはないため、これが答えです。
入力例 2
5 2 100000 100000 100000 100000 100000 100 200
出力例 2
201
入力例 3
3 2 100 100 100 80 120
出力例 3
100
Score : 300 points
Problem Statement
There are N sellers and M buyers in an apple market.
The i-th seller may sell an apple for A_i yen or more (yen is the currency in Japan).
The i-th buyer may buy an apple for B_i yen or less.
Find the minimum integer X that satisfies the following condition.
Condition: The number of people who may sell an apple for X yen is greater than or equal to the number of people who may buy an apple for X yen.
Constraints
- 1 \leq N,M \leq 2\times 10^5
- 1\leq A_i,B_i \leq 10^9
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 \ldots A_N B_1 \ldots B_M
Output
Print the answer.
Sample Input 1
3 4 110 90 120 100 80 120 10000
Sample Output 1
110
Two sellers, the 1-st and 2-nd, may sell an apple for 110 yen; two buyers, the 3-rd and 4-th, may buy an apple for 110 yen. Thus, 110 satisfies the condition.
Since an integer less than 110 does not satisfy the condition, this is the answer.
Sample Input 2
5 2 100000 100000 100000 100000 100000 100 200
Sample Output 2
201
Sample Input 3
3 2 100 100 100 80 120
Sample Output 3
100
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
atcoder の並べ替えである文字列 S が与えられます。
この文字列 S に対して以下の操作を 0 回以上行います。
- S 中の隣接する 2 文字を選び、入れ替える。
S を atcoder にするために必要な最小の操作回数を求めてください。
制約
- S は
atcoderの並べ替えである文字列
入力
入力は以下の形式で標準入力から与えられる。
S
出力
答えを整数として出力せよ。
入力例 1
catredo
出力例 1
8
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
という流れで操作を行うと、 8 回で S を atcoder にすることができ、これが達成可能な最小の操作回数です。
入力例 2
atcoder
出力例 2
0
この場合、文字列 S は元から atcoder です。
入力例 3
redocta
出力例 3
21
Score : 400 points
Problem Statement
You are given a string S that is a permutation of atcoder.
On this string S, you will perform the following operation 0 or more times:
- Choose two adjacent characters of S and swap them.
Find the minimum number of operations required to make S equal atcoder.
Constraints
- S is a string that is a permutation of
atcoder
Input
Input is given from Standard Input in the following format:
S
Output
Print the answer as an integer.
Sample Input 1
catredo
Sample Output 1
8
You can make S equal atcoder in 8 operations as follows:
catredo \rightarrow [ac]tredo \rightarrow actre[od] \rightarrow actr[oe]d \rightarrow actro[de] \rightarrow act[or]de \rightarrow acto[dr]e \rightarrow a[tc]odre \rightarrow atcod[er]
This is the minimum number of operations achievable.
Sample Input 2
atcoder
Sample Output 2
0
In this case, the string S is already atcoder.
Sample Input 3
redocta
Sample Output 3
21