AtCoder Regular Contest 074

C - Chocolate Bar

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

縦 H ブロック、横 W ブロックの板チョコがあります。すぬけ君は、この板チョコをちょうど 3 つのピースに分割しようとしています。ただし、各ピースはブロックの境目に沿った長方形でなければなりません。

すぬけ君は、3 つのピースの面積 (ブロック数) をできるだけ均等にしようとしています。具体的には、3 つのピースの面積の最大値を S_{max}、最小値を S_{min} としたとき、S_{max} - S_{min} を最小化しようとしています。 S_{max} - S_{min} の最小値を求めてください。

制約

2 ≤ H, W ≤ 10^5

入力

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

H W

出力

S_{max} - S_{min} の最小値を出力せよ。

入力例 1

3 5

出力例 1

次図のように分割すると、S_{max} - S_{min} = 5 - 5 = 0 となります。

入力例 2

4 5

出力例 2

次図のように分割すると、S_{max} - S_{min} = 8 - 6 = 2 となります。

入力例 3

5 5

出力例 3

次図のように分割すると、S_{max} - S_{min} = 10 - 6 = 4 となります。

入力例 4

100000 2

出力例 4

入力例 5

100000 100000

出力例 5

Score : 400 points

Problem Statement

There is a bar of chocolate with a height of H blocks and a width of W blocks. Snuke is dividing this bar into exactly three pieces. He can only cut the bar along borders of blocks, and the shape of each piece must be a rectangle.

Snuke is trying to divide the bar as evenly as possible. More specifically, he is trying to minimize S_{max} - S_{min}, where S_{max} is the area (the number of blocks contained) of the largest piece, and S_{min} is the area of the smallest piece. Find the minimum possible value of S_{max} - S_{min}.

Constraints

2 ≤ H, W ≤ 10^5

Input

Input is given from Standard Input in the following format:

H W

Output

Print the minimum possible value of S_{max} - S_{min}.

Sample Input 1

3 5

Sample Output 1

In the division below, S_{max} - S_{min} = 5 - 5 = 0.

Sample Input 2

4 5

Sample Output 2

In the division below, S_{max} - S_{min} = 8 - 6 = 2.

Sample Input 3

5 5

Sample Output 3

In the division below, S_{max} - S_{min} = 10 - 6 = 4.

Sample Input 4

100000 2

Sample Output 4

Sample Input 5

100000 100000

Sample Output 5

D - 3N Numbers

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 500 点

問題文

N を 1 以上の整数とします。

長さ 3N の数列 a = (a_1, a_2, ..., a_{3N}) があります。すぬけ君は、a からちょうど N 個の要素を取り除き、残った 2N 個の要素を元の順序で並べ、長さ 2N の数列 a' を作ろうとしています。このとき、a' のスコアを (a' の前半 N 要素の総和) - (a' の後半 N 要素の総和) と定義します。

a' のスコアの最大値を求めてください。

制約

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

部分点

300 点分のテストケースでは、N ≤ 1,000 が成り立つ。

入力

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

N
a_1 a_2 ... a_{3N}

出力

a' のスコアの最大値を出力せよ。

入力例 1

2
3 1 4 1 5 9

出力例 1

a_2, a_6 を取り除くと、a' = (3, 4, 1, 5) となり、スコアは (3 + 4) - (1 + 5) = 1 となります。

入力例 2

1
1 2 3

出力例 2

-1

例えば、a_1 を取り除くと、a' = (2, 3) となり、スコアは 2 - 3 = -1 となります。

入力例 3

3
8 2 2 7 4 6 5 3 8

出力例 3

例えば、a_2, a_3, a_9 を取り除くと、a' = (8, 7, 4, 6, 5, 3) となり、スコアは (8 + 7 + 4) - (6 + 5 + 3) = 5 となります。

Score : 500 points

Problem Statement

Let N be a positive integer.

There is a numerical sequence of length 3N, a = (a_1, a_2, ..., a_{3N}). Snuke is constructing a new sequence of length 2N, a', by removing exactly N elements from a without changing the order of the remaining elements. Here, the score of a' is defined as follows: (the sum of the elements in the first half of a') - (the sum of the elements in the second half of a').

Find the maximum possible score of a'.

Constraints

1 ≤ N ≤ 10^5
a_i is an integer.
1 ≤ a_i ≤ 10^9

Partial Score

In the test set worth 300 points, N ≤ 1000.

Input

Input is given from Standard Input in the following format:

N
a_1 a_2 ... a_{3N}

Output

Print the maximum possible score of a'.

Sample Input 1

2
3 1 4 1 5 9

Sample Output 1

When a_2 and a_6 are removed, a' will be (3, 4, 1, 5), which has a score of (3 + 4) - (1 + 5) = 1.

Sample Input 2

1
1 2 3

Sample Output 2

-1

For example, when a_1 are removed, a' will be (2, 3), which has a score of 2 - 3 = -1.

Sample Input 3

3
8 2 2 7 4 6 5 3 8

Sample Output 3

For example, when a_2, a_3 and a_9 are removed, a' will be (8, 7, 4, 6, 5, 3), which has a score of (8 + 7 + 4) - (6 + 5 + 3) = 5.

E - RGB Sequence

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

N 個のマスが横一列に並んでいます。マスには左から順に 1, 2, ..., N と番号が振られています。

すぬけ君は、各マスを赤 / 緑 / 青のどれかの色で塗ろうとしています。すぬけ君の美的感覚によると、次の M 個の条件がすべて成り立つ必要があるそうです。 i 番目の条件は次のようなものです。

マス l_i, l_i + 1, ..., r_i の色の種類数がちょうど x_i である。

条件がすべて成り立つようなマスの配色は何通りでしょうか？ 10^9+7 で割った余りを求めてください。

制約

1 ≤ N ≤ 300
1 ≤ M ≤ 300
1 ≤ l_i ≤ r_i ≤ N
1 ≤ x_i ≤ 3

入力

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

N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

出力

条件がすべて成り立つようなマスの配色は何通りか？ 10^9+7 で割った余りを出力せよ。

入力例 1

3 1
1 3 3

出力例 1

次の 6 通りです。

ただし、R / G / B はそれぞれ赤 / 緑 / 青のマスを表します。

入力例 2

4 2
1 3 1
2 4 2

出力例 2

次の 6 通りです。

RRRG
RRRB
GGGR
GGGB
BBBR
BBBG

入力例 3

出力例 3

次の 0 通りです。

入力例 4

出力例 4

Score : 800 points

Problem Statement

There are N squares arranged in a row. The squares are numbered 1, 2, ..., N, from left to right.

Snuke is painting each square in red, green or blue. According to his aesthetic sense, the following M conditions must all be satisfied. The i-th condition is:

There are exactly x_i different colors among squares l_i, l_i + 1, ..., r_i.

In how many ways can the squares be painted to satisfy all the conditions? Find the count modulo 10^9+7.

Constraints

1 ≤ N ≤ 300
1 ≤ M ≤ 300
1 ≤ l_i ≤ r_i ≤ N
1 ≤ x_i ≤ 3

Input

Input is given from Standard Input in the following format:

N M
l_1 r_1 x_1
l_2 r_2 x_2
:
l_M r_M x_M

Output

Print the number of ways to paint the squares to satisfy all the conditions, modulo 10^9+7.

Sample Input 1

3 1
1 3 3

Sample Output 1

The six ways are:

where R, G and B correspond to red, green and blue squares, respectively.

Sample Input 2

4 2
1 3 1
2 4 2

Sample Output 2

The six ways are:

RRRG
RRRB
GGGR
GGGB
BBBR
BBBG

Sample Input 3

Sample Output 3

There are zero ways.

Sample Input 4

Sample Output 4

F - Lotus Leaves

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 800 点

問題文

長方形の池があります。池は縦 H 行、横 W 列のマス目状に分割されています。上から i 行目、左から j 列目のマスを (i,\ j) と表します。

池のいくつかのマスには蓮 (はす) の葉が浮かんでいます。ある葉 S にはカエルが乗っており、別の葉 T まで移動しようとしています。マス (i,\ j) の情報は、文字 a_{ij} によって次のように表されます。

. : 葉が浮かんでいないマスである。
o : 葉が浮かんでいるマスである。
S : 葉 S が浮かんでいるマスである。
T : 葉 T が浮かんでいるマスである。

カエルは「今乗っている葉と同じ行または同じ列に浮かんでいる葉へジャンプする」ことを繰り返し行い、葉 T まで移動しようとしています。

すぬけ君の目標は、あらかじめ葉 S, T 以外の葉を何枚か取り除いておくことで、カエルが葉 T まで移動できないようにすることです。この目標が達成可能か判定し、可能ならば取り除く葉の枚数の最小値を求めてください。

制約

2 ≤ H, W ≤ 100
a_{ij} は ., o, S, T のどれかである。
a_{ij} のうち S はちょうど 1 個存在する。
a_{ij} のうち T はちょうど 1 個存在する。

入力

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

H W
a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

出力

目標が達成可能ならば、取り除く葉の枚数の最小値を出力せよ。そうでなければ、代わりに -1 を出力せよ。

入力例 1

3 3
S.o
.o.
o.T

出力例 1

右上と左下の葉を取り除けばよいです。

入力例 2

3 4
S...
.oo.
...T

出力例 2

入力例 3

4 3
.S.
.o.
.o.
.T.

出力例 3

-1

入力例 4

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo

出力例 4

Score : 800 points

Problem Statement

There is a pond with a rectangular shape. The pond is divided into a grid with H rows and W columns of squares. We will denote the square at the i-th row from the top and j-th column from the left by (i,\ j).

Some of the squares in the pond contains a lotus leaf floating on the water. On one of those leaves, S, there is a frog trying to get to another leaf T. The state of square (i,\ j) is given to you by a character a_{ij}, as follows:

. : A square without a leaf.
o : A square with a leaf floating on the water.
S : A square with the leaf S.
T : A square with the leaf T.

The frog will repeatedly perform the following action to get to the leaf T: "jump to a leaf that is in the same row or the same column as the leaf where the frog is currently located."

Snuke is trying to remove some of the leaves, other than S and T, so that the frog cannot get to the leaf T. Determine whether this objective is achievable. If it is achievable, find the minimum necessary number of leaves to remove.

Constraints

2 ≤ H, W ≤ 100
a_{ij} is ., o, S or T.
There is exactly one S among a_{ij}.
There is exactly one T among a_{ij}.

Input

Input is given from Standard Input in the following format:

H W
a_{11} ... a_{1W}
:
a_{H1} ... a_{HW}

Output

If the objective is achievable, print the minimum necessary number of leaves to remove. Otherwise, print -1 instead.

Sample Input 1

3 3
S.o
.o.
o.T

Sample Output 1

Remove the upper-right and lower-left leaves.

Sample Input 2

3 4
S...
.oo.
...T

Sample Output 2

Sample Input 3

4 3
.S.
.o.
.o.
.T.

Sample Output 3

-1

Sample Input 4

10 10
.o...o..o.
....o.....
....oo.oo.
..oooo..o.
....oo....
..o..o....
o..o....So
o....T....
....o.....
........oo