AtCoder Beginner Contest 107

A - Train

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 100 点

問題文

N 両編成の列車があります。この列車の前から i 両目は、後ろから何両目でしょうか？

制約

1 \leq N \leq 100
1 \leq i \leq N

入力

入力は以下の形式で標準入力から与えられる。

N i

出力

答えを出力せよ。

入力例 1

4 2

出力例 1

4 両編成の列車において、前から 2 両目の車両は、後ろから 3 両目です。

入力例 2

1 1

出力例 2

入力例 3

15 11

出力例 3

Score : 100 points

Problem Statement

There is an N-car train.

You are given an integer i. Find the value of j such that the following statement is true: "the i-th car from the front of the train is the j-th car from the back."

Constraints

1 \leq N \leq 100
1 \leq i \leq N

Input

Input is given from Standard Input in the following format:

N i

Output

Print the answer.

Sample Input 1

4 2

Sample Output 1

The second car from the front of a 4-car train is the third car from the back.

Sample Input 2

1 1

Sample Output 2

Sample Input 3

15 11

Sample Output 3

B - Grid Compression

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 200 点

問題文

縦 H 行、横 W 列のマス目があります。上から i 行目、左から j 列目のマスを (i, j) と表します。各マスは白または黒です。マス目の配色は、H 行 W 列の行列 (a_{i, j}) によって与えられます。 a_{i, j} が . ならばマス (i, j) は白であり、a_{i, j} が # ならばマス (i, j) は黒です。

すぬけ君はこのマス目を圧縮しようとしています。そのために、白いマスのみからなる行または列が存在する間、次の操作を繰り返し行います。

操作: 白いマスのみからなる行または列をひとつ任意に選び、その行または列を取り除いて空白を詰める。

各操作でどの行または列を選ぶかによらず、最終的なマス目は一意に定まることが示せます。最終的なマス目を求めてください。

制約

1 \leq H, W \leq 100
a_{i, j} は . または # である。
マス目全体で少なくともひとつは黒いマスが存在する。

入力

入力は以下の形式で標準入力から与えられる。

H W
a_{1, 1}...a_{1, W}
:
a_{H, 1}...a_{H, W}

出力

最終的なマス目を、入力と同様のフォーマットで出力せよ。ただし、行数および列数は省くこと。詳しくはサンプルを参照せよ。

入力例 1

4 4
##.#
....
##.#
.#.#

出力例 1

###
###
.##

元のマス目における第 2 行および第 3 列がそれぞれ取り除かれます。

入力例 2

3 3
#..
.#.
..#

出力例 2

#..
.#.
..#

白いマスのみからなる行または列が存在しないので、操作は行われません。

入力例 3

4 5
.....
.....
..#..
.....

出力例 3

入力例 4

7 6
......
....#.
.#....
..#...
..#...
......
.#..#.

出力例 4

..#
#..
.#.
.#.
#.#

Score : 200 points

Problem Statement

There is a grid of squares with H horizontal rows and W vertical columns. The square at the i-th row from the top and the j-th column from the left is represented as (i, j). Each square is black or white. The color of the square is given as an H-by-W matrix (a_{i, j}). If a_{i, j} is ., the square (i, j) is white; if a_{i, j} is #, the square (i, j) is black.

Snuke is compressing this grid. He will do so by repeatedly performing the following operation while there is a row or column that consists only of white squares:

Operation: choose any one row or column that consists only of white squares, remove it and delete the space between the rows or columns.

It can be shown that the final state of the grid is uniquely determined regardless of what row or column is chosen in each operation. Find the final state of the grid.

Constraints

1 \leq H, W \leq 100
a_{i, j} is . or #.
There is at least one black square in the whole grid.

Input

Input is given from Standard Input in the following format:

H W
a_{1, 1}...a_{1, W}
:
a_{H, 1}...a_{H, W}

Output

Print the final state of the grid in the same format as input (without the numbers of rows and columns); see the samples for clarity.

Sample Input 1

4 4
##.#
....
##.#
.#.#

Sample Output 1

###
###
.##

The second row and the third column in the original grid will be removed.

Sample Input 2

3 3
#..
.#.
..#

Sample Output 2

#..
.#.
..#

As there is no row or column that consists only of white squares, no operation will be performed.

Sample Input 3

4 5
.....
.....
..#..
.....

Sample Output 3

Sample Input 4

7 6
......
....#.
.#....
..#...
..#...
......
.#..#.

Sample Output 4

..#
#..
.#.
.#.
#.#

C - Candles

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 300 点

問題文

数直線上に N 本のろうそくが置かれています。左から i 番目のろうそくは座標 x_i に置かれています。ただし、x_1 < x_2 < ... < x_N が成り立ちます。

最初、どのろうそくにも火が付いていません。すぬけ君は、N 本のうち K 本のろうそくに火を付けることにしました。

今、すぬけ君は座標 0 にいます。すぬけ君は、数直線上を左右に速度 1 で移動することができます。また、自分と同じ座標のろうそくに火を付けることができます。このとき、火を付けるのに掛かる時間は無視できます。

K 本のろうそくに火を付けるのに必要な最小の時間を求めてください。

制約

1 \leq N \leq 10^5
1 \leq K \leq N
x_i は整数である。
|x_i| \leq 10^8
x_1 < x_2 < ... < x_N

入力

入力は以下の形式で標準入力から与えられる。

N K
x_1 x_2 ... x_N

出力

K 本のろうそくに火を付けるのに必要な最小の時間を出力せよ。

入力例 1

5 3
-30 -10 10 20 50

出力例 1

次のように移動しながらろうそくに火を付ければよいです。

座標 0 から -10 へ移動する。
左から 2 番目のろうそくに火を付ける。
座標 -10 から 10 へ移動する。
左から 3 番目のろうそくに火を付ける。
座標 10 から 20 へ移動する。
左から 4 番目のろうそくに火を付ける。

入力例 2

3 2
10 20 30

出力例 2

入力例 3

1 1
0

出力例 3

座標 0 にろうそくが置かれていることもあります。

入力例 4

8 5
-9 -7 -4 -3 1 2 3 4

出力例 4

Score : 300 points

Problem Statement

There are N candles placed on a number line. The i-th candle from the left is placed on coordinate x_i. Here, x_1 < x_2 < ... < x_N holds.

Initially, no candles are burning. Snuke decides to light K of the N candles.

Now, he is at coordinate 0. He can move left and right along the line with speed 1. He can also light a candle when he is at the same position as the candle, in negligible time.

Find the minimum time required to light K candles.

Constraints

1 \leq N \leq 10^5
1 \leq K \leq N
x_i is an integer.
|x_i| \leq 10^8
x_1 < x_2 < ... < x_N

Input

Input is given from Standard Input in the following format:

N K
x_1 x_2 ... x_N

Output

Print the minimum time required to light K candles.

Sample Input 1

5 3
-30 -10 10 20 50

Sample Output 1

He should move and light candles as follows:

Move from coordinate 0 to -10.
Light the second candle from the left.
Move from coordinate -10 to 10.
Light the third candle from the left.
Move from coordinate 10 to 20.
Light the fourth candle from the left.

Sample Input 2

3 2
10 20 30

Sample Output 2

Sample Input 3

1 1
0

Sample Output 3

There may be a candle placed at coordinate 0.

Sample Input 4

8 5
-9 -7 -4 -3 1 2 3 4

Sample Output 4

D - Median of Medians

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 700 点

問題文

長さ M の数列 b の 中央値 を次のように定義します。

b を昇順にソートして得られる数列を b' とする。このとき、b' の M / 2 + 1 番目の要素の値を、b の中央値とする。ここで、/ は小数点以下を切り捨てる除算である。

例えば、(10, 30, 20) の中央値は 20 であり、(10, 30, 20, 40) の中央値は 30 であり、(10, 10, 10, 20, 30) の中央値は 10 です。

すぬけ君は次のような問題を思いつきました。

長さ N の数列 a があります。各 (l, r) (1 \leq l \leq r \leq N) について、a の連続部分列 (a_l, a_{l + 1}, ..., a_r) の中央値を m_{l, r} とします。すべての (l, r) に対する m_{l, r} を並べ、新たに数列 m を作ります。 m の中央値を求めてください。

制約

1 \leq N \leq 10^5
a_i は整数である。
1 \leq a_i \leq 10^9

入力

入力は以下の形式で標準入力から与えられる。

N
a_1 a_2 ... a_N

出力

m の中央値を出力せよ。

入力例 1

3
10 30 20

出力例 1

a のそれぞれの連続部分列の中央値は次のようになります。

(10) の中央値は 10
(30) の中央値は 30
(20) の中央値は 20
(10, 30) の中央値は 30
(30, 20) の中央値は 30
(10, 30, 20) の中央値は 20

よって、m = (10, 30, 20, 30, 30, 20) となり、m の中央値は 30 です。

入力例 2

1
10

出力例 2

入力例 3

10
5 9 5 9 8 9 3 5 4 3

出力例 3

Score : 700 points

Problem Statement

We will define the median of a sequence b of length M, as follows:

Let b' be the sequence obtained by sorting b in non-decreasing order. Then, the value of the (M / 2 + 1)-th element of b' is the median of b. Here, / is integer division, rounding down.

For example, the median of (10, 30, 20) is 20; the median of (10, 30, 20, 40) is 30; the median of (10, 10, 10, 20, 30) is 10.

Snuke comes up with the following problem.

You are given a sequence a of length N. For each pair (l, r) (1 \leq l \leq r \leq N), let m_{l, r} be the median of the contiguous subsequence (a_l, a_{l + 1}, ..., a_r) of a. We will list m_{l, r} for all pairs (l, r) to create a new sequence m. Find the median of m.

Constraints

1 \leq N \leq 10^5
a_i is an integer.
1 \leq a_i \leq 10^9

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_N

Output

Print the median of m.

Sample Input 1

3
10 30 20

Sample Output 1

The median of each contiguous subsequence of a is as follows:

The median of (10) is 10.
The median of (30) is 30.
The median of (20) is 20.
The median of (10, 30) is 30.
The median of (30, 20) is 30.
The median of (10, 30, 20) is 20.

Thus, m = (10, 30, 20, 30, 30, 20) and the median of m is 30.

Sample Input 2

1
10

Sample Output 2

Sample Input 3

10
5 9 5 9 8 9 3 5 4 3