C - Make a Rectangle

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 300 点

問題文

太さが無視できる棒が N 本あります． i 番目の棒の長さは A_i です．

すぬけ君は，これらの棒から 4 本の異なる棒を選び，それらの棒を辺として長方形（正方形を含む）を作りたいです． 作ることができる最大の長方形の面積を求めてください．

制約

  • 4 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • A_i は整数

入力

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

N
A_1 A_2 ... A_N

出力

すぬけ君が作ることのできる最大の長方形の面積を出力せよ． ただし，長方形を作れない場合は，0 を出力せよ．

入力例 1

6
3 1 2 4 2 1

出力例 1

2

1 \times 2 の長方形を作ることができます．

入力例 2

4
1 2 3 4

出力例 2

0

長方形を作ることはできません．

入力例 3

10
3 3 3 3 4 4 4 5 5 5

出力例 3

20

Score : 300 points

Problem Statement

We have N sticks with negligible thickness. The length of the i-th stick is A_i.

Snuke wants to select four different sticks from these sticks and form a rectangle (including a square), using the sticks as its sides. Find the maximum possible area of the rectangle.

Constraints

  • 4 \leq N \leq 10^5
  • 1 \leq A_i \leq 10^9
  • A_i is an integer.

Input

Input is given from Standard Input in the following format:

N
A_1 A_2 ... A_N

Output

Print the maximum possible area of the rectangle. If no rectangle can be formed, print 0.

Sample Input 1

6
3 1 2 4 2 1

Sample Output 1

2

1 \times 2 rectangle can be formed.

Sample Input 2

4
1 2 3 4

Sample Output 2

0

No rectangle can be formed.

Sample Input 3

10
3 3 3 3 4 4 4 5 5 5

Sample Output 3

20
D - Coloring Dominoes

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 400 点

問題文

2 \times N のマス目があります． すぬけ君は，このマス目に N 個のドミノを，重ならないように敷き詰めました． ここで，ドミノは，1 \times 2 または 2 \times 1 のマス目を覆うことができます．

すぬけ君は，赤色，水色，緑色の 3 色を使って，これらのドミノを塗ることにしました． このとき，辺で接しているドミノは異なる色で塗るようにします． ここで，必ずしも 3 色すべてを使う必要はありません．

このような塗り方が何通りあるかを mod 1000000007 で求めてください．

ただし，ドミノの敷き詰め方は，文字列 S_1, S_2 を用いて，次のようにして与えられます．

  • 各ドミノは，それぞれ異なる英小文字または英大文字で表される．
  • S_i の j 文字目は，マス目の上から i 番目，左から j 番目のマスにどのドミノがあるかを表す．

制約

  • 1 \leq N \leq 52
  • |S_1| = |S_2| = N
  • S_1, S_2 は英小文字または英大文字からなる
  • S_1, S_2 は正しいドミノの敷き詰め方を表している

入力

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

N
S_1
S_2

出力

ドミノを塗る方法の数を mod 1000000007 で出力せよ．

入力例 1

3
aab
ccb

出力例 1

6

次の 6 通りあります．

入力例 2

1
Z
Z

出力例 2

3

必ずしもすべての色を使わなくてもよいことに注意してください．

入力例 3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

出力例 3

958681902

Score : 400 points

Problem Statement

We have a board with a 2 \times N grid. Snuke covered the board with N dominoes without overlaps. Here, a domino can cover a 1 \times 2 or 2 \times 1 square.

Then, Snuke decided to paint these dominoes using three colors: red, cyan and green. Two dominoes that are adjacent by side should be painted by different colors. Here, it is not always necessary to use all three colors.

Find the number of such ways to paint the dominoes, modulo 1000000007.

The arrangement of the dominoes is given to you as two strings S_1 and S_2 in the following manner:

  • Each domino is represented by a different English letter (lowercase or uppercase).
  • The j-th character in S_i represents the domino that occupies the square at the i-th row from the top and j-th column from the left.

Constraints

  • 1 \leq N \leq 52
  • |S_1| = |S_2| = N
  • S_1 and S_2 consist of lowercase and uppercase English letters.
  • S_1 and S_2 represent a valid arrangement of dominoes.

Input

Input is given from Standard Input in the following format:

N
S_1
S_2

Output

Print the number of such ways to paint the dominoes, modulo 1000000007.

Sample Input 1

3
aab
ccb

Sample Output 1

6

There are six ways as shown below:

Sample Input 2

1
Z
Z

Sample Output 2

3

Note that it is not always necessary to use all the colors.

Sample Input 3

52
RvvttdWIyyPPQFFZZssffEEkkaSSDKqcibbeYrhAljCCGGJppHHn
RLLwwdWIxxNNQUUXXVVMMooBBaggDKqcimmeYrhAljOOTTJuuzzn

Sample Output 3

958681902
E - Don't Be a Subsequence

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 600 点

問題文

文字列 S に対して，その文字列を構成する文字を 0 文字以上取り除き，残った文字を元の順番で並べて得られる文字列を S の部分列と呼びます． たとえば，arc や artistic や (空文字列) は artistic の部分列ですが，abc や ci は artistic の部分列ではありません．

英小文字からなる文字列 A が与えられます． このとき，英小文字からなる文字列で，A の部分列ではないようなもののうち，最も短いものを求めてください． ただし，そのようなものが複数ある場合には，辞書順で最小のものを求めてください．

制約

  • 1 \leq |A| \leq 2 \times 10^5
  • A は英小文字のみからなる．

入力

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

A

出力

英小文字からなる A の部分列でないような最短の文字列のうち，辞書順最小のものを出力せよ．

入力例 1

atcoderregularcontest

出力例 1

b

atcoderregularcontest という文字列は a を部分列として含みますが，b は含みません．

入力例 2

abcdefghijklmnopqrstuvwxyz

出力例 2

aa

入力例 3

frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn

出力例 3

aca

Score : 600 points

Problem Statement

A subsequence of a string S is a string that can be obtained by deleting zero or more characters from S without changing the order of the remaining characters. For example, arc, artistic and (an empty string) are all subsequences of artistic; abc and ci are not.

You are given a string A consisting of lowercase English letters. Find the shortest string among the strings consisting of lowercase English letters that are not subsequences of A. If there are more than one such string, find the lexicographically smallest one among them.

Constraints

  • 1 \leq |A| \leq 2 \times 10^5
  • A consists of lowercase English letters.

Input

Input is given from Standard Input in the following format:

A

Output

Print the lexicographically smallest string among the shortest strings consisting of lowercase English letters that are not subsequences of A.

Sample Input 1

atcoderregularcontest

Sample Output 1

b

The string atcoderregularcontest contains a as a subsequence, but not b.

Sample Input 2

abcdefghijklmnopqrstuvwxyz

Sample Output 2

aa

Sample Input 3

frqnvhydscshfcgdemurlfrutcpzhopfotpifgepnqjxupnskapziurswqazdwnwbgdhyktfyhqqxpoidfhjdakoxraiedxskywuepzfniuyskxiyjpjlxuqnfgmnjcvtlpnclfkpervxmdbvrbrdn

Sample Output 3

aca
F - Flip and Rectangles

Time Limit: 2 sec / Memory Limit: 256 MB

配点 : 700 点

問題文

H \times W のマス目があります． マス目の各マスは黒か白かに塗られており，上から i 番目，左から j 番目のマスは，S_i の j 文字目が # のとき黒マス，. のとき白マスです．

すぬけ君は，マス目に対して次の操作を好きな回数行うことができます．

  • マス目の任意の行または列を選び，その行または列のすべてのマスの色を反転する (すなわち，黒で塗られたマスを白に，白で塗られたマスを黒に塗り替える)．

操作の後，すぬけ君はマス目に沿った長方形を 1 個選びます．このとき，選んだ長方形に含まれるすべてのマスは黒で塗られていなければなりません．

うまく操作を行うとき，すぬけ君が選ぶことができる最大の長方形の面積を求めてください．

制約

  • 2 \leq H \leq 2000
  • 2 \leq W \leq 2000
  • |S_i| = W
  • S_i は #, . のみからなる．

入力

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

H W
S_1
S_2
:
S_H

出力

すぬけ君が選ぶことができる最大の長方形の面積を出力せよ．

入力例 1

3 3
..#
##.
.#.

出力例 1

6

下図のように，上から 1 行目，左から 3 列目を反転させると，2 \times 3 の長方形を選ぶことができます．

入力例 2

4 4
....
....
....
....

出力例 2

16

入力例 3

10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

出力例 3

27

Score : 700 points

Problem Statement

We have a board with an H \times W grid. Each square in the grid is painted in black or white. The square at the i-th row from the top and j-th column from the left is black if the j-th character in S_i is #, and white if that character is ..

Snuke can perform the following operation on the grid any number of times:

  • Select a row or column in the grid, and invert the color of all the squares in that row or column (that is, black squares become white and vice versa).

Then, Snuke draws a rectangle along grid lines. Here, all the squares contained in the rectangle must be painted in black.

Find the maximum possible area of Snuke's rectangle when the operation is performed optimally.

Constraints

  • 2 \leq H \leq 2000
  • 2 \leq W \leq 2000
  • |S_i| = W
  • S_i consists of # and ..

Input

Input is given from Standard Input in the following format:

H W
S_1
S_2
:
S_H

Output

Print the maximum possible area of Snuke's rectangle.

Sample Input 1

3 3
..#
##.
.#.

Sample Output 1

6

If the first row from the top and the third column from the left are inverted, a 2 \times 3 rectangle can be drawn, as shown below:

Sample Input 2

4 4
....
....
....
....

Sample Output 2

16

Sample Input 3

10 8
##...#.#
##...#.#
..###.#.
#.##.#.#
.#..#.#.
..##.#.#
##.#.#..
...#.#..
###.#.##
###..###

Sample Output 3

27