C - AtCoder Quiz

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

AtCoder では現在、 ABC , ARC , AGC , AHC の 4 つのコンテストが定期的に開催されています。

AtCoder で現在定期的に開催されているコンテストは S_1 , S_2 , S_3 とあと 1 つは何ですか?

制約

  • S_1 , S_2 , S_3 はそれぞれ、 ABC , ARC , AGC , AHC のいずれかである。
  • S_1 , S_2 , S_3 は相異なる。

入力

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

S_1
S_2
S_3

出力

答えを出力せよ。

入力例 1

ARC
AGC
AHC

出力例 1

ABC

ARC , AGC , AHC の 3つが入力として与えられているので、 残りの 1 つはABC です。

入力例 2

AGC
ABC
ARC

出力例 2

AHC

Score : 200 points

Problem Statement

AtCoder currently holds four series of regular contests: ABC, ARC, AGC, and AHC.

What is the series of regular contests currently held by AtCoder in addition to S_1, S_2, and S_3?

Constraints

  • Each of S_1, S_2, and S_3 is ABC, ARC, AGC, or AHC.
  • S_1, S_2, and S_3 are pairwise different.

Input

Input is given from Standard Input in the following format:

S_1
S_2
S_3

Output

Print the answer.

Sample Input 1

ARC
AGC
AHC

Sample Output 1

ABC

Given in input are ARC, AGC, and AHC. The rest is ABC.

Sample Input 2

AGC
ABC
ARC

Sample Output 2

AHC
D - Heavy Snake

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 200 点

問題文

N 匹のヘビがいます。

はじめ、i 匹目のヘビの太さは T_i、長さは L_i です。

ヘビの重さは太さと長さの積となります。

1 \leq k \leq D を満たす各整数 k について、すべてのヘビの長さが k 伸びたときの最も重いヘビの重さを求めてください。

制約

  • 1 \leq N, D \leq 100
  • 1 \leq T_i, L_i \leq 100
  • 入力される値はすべて整数

入力

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

N D
T_1 L_1
T_2 L_2
\vdots
T_N L_N

出力

D 行出力せよ。k 行目には、すべてのヘビの長さが k 伸びたときの最も重いヘビの重さを出力せよ。

入力例 1

4 3
3 3
5 1
2 4
1 10

出力例 1

12
15
20

すべてのヘビの長さが 1 伸びたとき、ヘビの重さはそれぞれ 12, 10, 10, 11 となるので 1 行目には 12 を出力します。

すべてのヘビの長さが 2 伸びたとき、ヘビの重さはそれぞれ 15, 15, 12, 12 となるので 2 行目には 15 を出力します。

すべてのヘビの長さが 3 伸びたとき、ヘビの重さはそれぞれ 18, 20, 14, 13 となるので 3 行目には 20 を出力します。

入力例 2

1 4
100 100

出力例 2

10100
10200
10300
10400

Score : 200 points

Problem Statement

There are N snakes.

Initially, the thickness of the i-th snake is T_i, and its length is L_i.

The weight of a snake is defined as the product of its thickness and length.

For each integer k satisfying 1 \leq k \leq D, find the weight of the heaviest snake when every snake's length has increased by k.

Constraints

  • 1 \leq N, D \leq 100
  • 1 \leq T_i, L_i \leq 100
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N D
T_1 L_1
T_2 L_2
\vdots
T_N L_N

Output

Print D lines. The k-th line should contain the weight of the heaviest snake when every snake's length has increased by k.

Sample Input 1

4 3
3 3
5 1
2 4
1 10

Sample Output 1

12
15
20

When every snake’s length has increased by 1, the snakes' weights become 12, 10, 10, 11, so print 12 on the first line.

When every snake’s length has increased by 2, the snakes' weights become 15, 15, 12, 12, so print 15 on the second line.

When every snake’s length has increased by 3, the snakes' weights become 18, 20, 14, 13, so print 20 on the third line.

Sample Input 2

1 4
100 100

Sample Output 2

10100
10200
10300
10400
E - RANDOM

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

# と . からなる H 行 W 列の図形 S,T が与えられます。
図形 S は H 個の文字列として与えられ、 S_i の j 文字目は S の i 行 j 列にある要素を表します。 T についても同様です。

S の列を並べ替えて T と等しくできるか判定してください。

但し、図形 X の列を並べ替えるとは、以下の操作を言います。

  • (1,2,\dots,W) の順列 P=(P_1,P_2,\dots,P_W) をひとつ選択する。
  • その後、全ての 1 \le i \le H を満たす整数 i について、以下の操作を同時に行う。
    • 1 \le j \le W を満たす全ての整数 j について同時に、 X の i 行 j 列にある要素を i 行 P_j 列にある要素に置き換える。

制約

  • H,W は整数
  • 1 \le H,W
  • 1 \le H \times W \le 4 \times 10^5
  • S_i,T_i は # と . からなる長さ W の文字列

入力

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

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

出力

S を T と等しくできるなら Yes 、 そうでないなら No と出力せよ。

入力例 1

3 4
##.#
##..
#...
.###
..##
...#

出力例 1

Yes

例えば S の 3,4,2,1 列目をこの順に左から並べ替えた場合、 S を T と等しくできます。

入力例 2

3 3
#.#
.#.
#.#
##.
##.
.#.

出力例 2

No

この入力では、 S を T と等しくすることができません。

入力例 3

2 1
#
.
#
.

出力例 3

Yes

S=T である場合もあります。

入力例 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

出力例 4

Yes

Score : 300 points

Problem Statement

You are given patterns S and T consisting of # and ., each with H rows and W columns.
The pattern S is given as H strings, and the j-th character of S_i represents the element at the i-th row and j-th column. The same goes for T.

Determine whether S can be made equal to T by rearranging the columns of S.

Here, rearranging the columns of a pattern X is done as follows.

  • Choose a permutation P=(P_1,P_2,\dots,P_W) of (1,2,\dots,W).
  • Then, for every integer i such that 1 \le i \le H, simultaneously do the following.
    • For every integer j such that 1 \le j \le W, simultaneously replace the element at the i-th row and j-th column of X with the element at the i-th row and P_j-th column.

Constraints

  • H and W are integers.
  • 1 \le H,W
  • 1 \le H \times W \le 4 \times 10^5
  • S_i and T_i are strings of length W consisting of # and ..

Input

The input is given from Standard Input in the following format:

H W
S_1
S_2
\vdots
S_H
T_1
T_2
\vdots
T_H

Output

If S can be made equal to T, print Yes; otherwise, print No.

Sample Input 1

3 4
##.#
##..
#...
.###
..##
...#

Sample Output 1

Yes

If you, for instance, arrange the 3-rd, 4-th, 2-nd, and 1-st columns of S in this order from left to right, S will be equal to T.

Sample Input 2

3 3
#.#
.#.
#.#
##.
##.
.#.

Sample Output 2

No

In this input, S cannot be made equal to T.

Sample Input 3

2 1
#
.
#
.

Sample Output 3

Yes

It is possible that S=T.

Sample Input 4

8 7
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
#..#..#
.##.##.
....###
####...
....###
####...
....###
####...
....###
####...

Sample Output 4

Yes
F - Perfect Standings

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 300 点

問題文

高橋くんは、プログラミングコンテストを主催することにしました。

コンテストは A 問題、B 問題、C 問題、D 問題、E 問題の 5 問からなり、それぞれの配点は a 点、b 点、c 点、d 点、e 点です。

コンテストには 31 人が参加し、全員が 1 問以上解きました。

より具体的には、文字列 ABCDE の空でない（連続するとは限らない）部分列すべてについて、その部分列を名前とする参加者が存在し、その参加者は名前に含まれる文字に対応する問題をすべて解き、それ以外の問題は解きませんでした。

例えば、A さんは A 問題のみを、BCE さんは B 問題、C 問題、E 問題を解きました。

参加者の名前を、取った点数が大きいほうから順に出力してください。 ただし、参加者が取った点数は、その参加者が解いた問題の配点の合計です。

ただし、同じ点数を獲得した参加者については、名前が辞書順で小さいほうを先に出力してください。

辞書順で小さいとは？

辞書順とは、一言で説明すると「単語が辞書に載っている順番」を意味します。

より厳密には、英大文字からなる相異なる文字列 S,T について、S が T より辞書順で小さいとは、以下の条件のどちらかが成り立つことを意味します。

  • S の長さ |S| が T の長さより短く、T の先頭 |S| 文字が S と一致する
  • ある整数 1\leq i\leq\min\lbrace|S|,|T|\rbrace が存在して、次の 2 つの条件を両方を満たす
    • 1\leq j\lt i を満たすすべての整数 j に対して S の j 文字目と T の j 文字目が等しい
    • S の i 文字目が T の i 文字目よりアルファベット順で小さい

例えば、S= AB ,T= ABC とすると、ひとつめの条件が成り立つため S は T より小さいです。 また、S= ABD ,T= ACD とすると、ふたつめの条件が i=2 で成り立つため S は T より小さいです。

制約

  • 100\leq a\leq b\leq c\leq d\leq e\leq 2718
  • 入力はすべて整数

入力

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

a b c d e

出力

31 行出力せよ。 i 行目 (1\leq i\leq 31) には、i 番目に高い得点を獲得した参加者の名前を出力せよ。 同じ得点を獲得した参加者については、それらのうち辞書順で小さい名前をもつ参加者を先に出力せよ。

入力例 1

400 500 600 700 800

出力例 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

それぞれの参加者の得点は以下のようになります。

例えば、ADE さんと BCE さんは同じ得点を獲得していますが、ADE さんのほうが辞書順で小さい名前をもつため、ADE さんを先に出力してください。

入力例 2

800 800 900 900 1000

出力例 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

入力例 3

128 256 512 1024 2048

出力例 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A

Score : 300 points

Problem Statement

Takahashi decided to hold a programming contest.

The contest consists of five problems: A, B, C, D, E, with scores a, b, c, d, e, respectively.

There are 31 participants, and all of them solved at least one problem.

More specifically, for every non-empty subsequence (not necessarily contiguous) of the string ABCDE, there is a participant named after that subsequence who solved the problems corresponding to the letters in their name and did not solve the other problems.

For example, participant A solved only problem A, and participant BCE solved problems B, C, and E.

Print the names of the participants in order of their obtained scores, from the largest to the smallest. The score obtained by a participant is the sum of the scores of the problems they solved.

If two participants obtained the same score, print the one whose name is lexicographically smaller first.

What does "lexicographically smaller" mean?

In short, "lexicographically smaller" refers to the order in which words would appear in a dictionary.

More precisely, for distinct strings S,T consisting of uppercase English letters, S is lexicographically smaller than T if either of the following conditions holds:

  • The length |S| of S is less than the length of T, and the first |S| characters of T match S.
  • There exists an integer 1\leq i\leq\min\{ |S|,|T|\} that satisfy both of the following two conditions:
    • For every integer j with 1\leq j\lt i, the j-th character of S equals the j-th character of T.
    • The i-th character of S is alphabetically smaller than the i-th character of T.

For example, if S= AB and T= ABC, the first condition holds, so S is lexicographically smaller than T. If S= ABD and T= ACD, the second condition holds for i=2, so S is lexicographically smaller than T.

Constraints

  • 100\leq a\leq b\leq c\leq d\leq e\leq 2718
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

a b c d e

Output

Print 31 lines. The i-th line (1\leq i\leq 31) should contain the name of the participant who obtained the i-th highest score. If multiple participants have the same score, print them in lexicographical order.

Sample Input 1

400 500 600 700 800

Sample Output 1

ABCDE
BCDE
ACDE
ABDE
ABCE
ABCD
CDE
BDE
ADE
BCE
ACE
BCD
ABE
ACD
ABD
ABC
DE
CE
BE
CD
AE
BD
AD
BC
AC
AB
E
D
C
B
A

The score of each participant is as follows:

For example, ADE and BCE obtained the same score, and ADE is lexicographically smaller, so print ADE before BCE.

Sample Input 2

800 800 900 900 1000

Sample Output 2

ABCDE
ACDE
BCDE
ABCE
ABDE
ABCD
CDE
ACE
ADE
BCE
BDE
ABE
ACD
BCD
ABC
ABD
CE
DE
AE
BE
CD
AC
AD
BC
BD
AB
E
C
D
A
B

Sample Input 3

128 256 512 1024 2048

Sample Output 3

ABCDE
BCDE
ACDE
CDE
ABDE
BDE
ADE
DE
ABCE
BCE
ACE
CE
ABE
BE
AE
E
ABCD
BCD
ACD
CD
ABD
BD
AD
D
ABC
BC
AC
C
AB
B
A
G - Magical Cookies

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 400 点

問題文

H \times W 枚のクッキーが H 行 W 列に並んでいます。
上から i 行目・左から j 列目のクッキーの色は英小文字 c_{i,j} で表されます。

これから、以下の手続きを行います。

1. 各行に対して次の操作を行う : その行に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

2. 各列に対して次の操作を行う : その列に 2 枚以上のクッキーが残っており、それらの色がすべて同じならば、それらに印をつける。

3. 印のついたクッキーがあればそれらをすべて取り除いて 1. に戻り、なければ手続きを終了する。

手続きを終了した時点で残っているクッキーの枚数を求めてください。

制約

  • 2 \leq H, W \leq 2000
  • c_{i,j} は英小文字である

入力

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

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

出力

答えを出力せよ。

入力例 1

4 3
aaa
aaa
abc
abd

出力例 1

2

以下で示す順で手続きを行います。

  • 1. により、1, 2 行目のクッキーに印をつける。
  • 2. により、1 列目のクッキーに印をつける。
  • 3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
.bc
.bd
  • 1. により、何もしない。
  • 2. により、2 列目のクッキーに印をつける。
  • 3. により、印を付けたクッキーを取り除く。

この時点でクッキーは以下のようになっています。ただし、クッキーを取り除いた箇所は . で表しています。

...
...
..c
..d
  • 1. により、何もしない。
  • 2. により、何もしない。
  • 3. により、印がついているクッキーが存在しないので手続きを終了する。

最終的に残っているクッキーの枚数は 2 枚です。

入力例 2

2 5
aaaaa
abcde

出力例 2

4

入力例 3

3 3
ooo
ooo
ooo

出力例 3

0

Score : 400 points

Problem Statement

There are H \times W cookies in H rows and W columns.
The color of the cookie at the i-row from the top and j-th column from the left is represented by a lowercase English letter c_{i,j}.

We will perform the following procedure.

1. For each row, perform the following operation: if there are two or more cookies remaining in the row and they all have the same color, mark them.

2. For each column, perform the following operation: if there are two or more cookies remaining in the column and they all have the same color, mark them.

3. If there are any marked cookies, remove them all and return to 1; otherwise, terminate the procedure.

Find the number of cookies remaining at the end of the procedure.

Constraints

  • 2 \leq H, W \leq 2000
  • c_{i,j} is a lowercase English letter.

Input

The input is given from Standard Input in the following format:

H W
c_{1,1}c_{1,2} \ldots c_{1,W}
c_{2,1}c_{2,2} \ldots c_{2,W}
\vdots
c_{H,1}c_{H,2} \ldots c_{H,W}

Output

Print the answer.

Sample Input 1

4 3
aaa
aaa
abc
abd

Sample Output 1

2

The procedure is performed as follows.

  • 1. Mark the cookies in the first and second rows.
  • 2. Mark the cookies in the first column.
  • 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
.bc
.bd
  • 1. Do nothing.
  • 2. Mark the cookies in the second column.
  • 3. Remove the marked cookies.

At this point, the cookies look like the following, where . indicates a position where the cookie has been removed.

...
...
..c
..d
  • 1. Do nothing.
  • 2. Do nothing.
  • 3. No cookies are marked, so terminate the procedure.

The final number of cookies remaining is 2.

Sample Input 2

2 5
aaaaa
abcde

Sample Output 2

4

Sample Input 3

3 3
ooo
ooo
ooo

Sample Output 3

0