AtCoder Beginner Contest 018

A - 豆まき

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

太郎君と次郎君と三郎君の 3 人の人が豆まきで対戦をした。得点が高いほうが上の順位である。それぞれの得点が与えられるので、それぞれの順位を答えよ。

入力

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

A
B
C

1 行目には、太郎君の得点を表す整数 A (1 ≦ A ≦ 100) が与えられる。
2 行目には、次郎君の得点を表す整数 B (1 ≦ B ≦ 100) が与えられる。
3 行目には、三郎君の得点を表す整数 C (1 ≦ C ≦ 100) が与えられる。
A, B, C は互いに異なる。

出力

出力は 3 行からなる。

1 行目には太郎君の順位を表す整数を出力せよ。
2 行目には次郎君の順位を表す整数を出力せよ。
3 行目には三郎君の順位を表す整数を出力せよ。

(21:49 表現の変更)出力の末尾に改行を入れること。

入力例1

12
18
11

出力例1

2
1
3

太郎くんは次郎君には負けて、三郎君には勝っている。太郎君の順位は 2 位である。
次郎くんは太郎君と三郎君に勝っている。次郎君の順位は 1 位である。
三郎くんは太郎君と次郎君に負けている。三郎君の順位は 3 位である。

入力例2

10
20
30

出力例2

3
2
1

B - 文字列の反転

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

半角の小文字アルファベットのみからなる文字列 S が与えられる。文字列 S に対して以下の操作 1 から操作 N までを番号の昇順に行う。

操作 i : 左から l_i 番目の文字を左端、左から r_i (1 ≦ l_i ＜ r_i ≦ |S|) 番目の文字を右端とした部分文字列を逆順にする。

例えば，文字列 abcdef に対して、左から 3 番目の文字 c を左端、左から 5 番目の文字 e を右端とした部分文字列を逆順にすると、文字列 abedcf が得られる。

操作 1 から操作 N までを番号の昇順に行った後の文字列を出力せよ。

入力

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

S
N
l_1 r_1
l_2 r_2
:
l_N r_N

1 行目には、半角の小文字アルファベットのみからなる文字列 S (1 ≦ |S| ≦ 100) が与えられる。
2 行目には、操作の回数を表す整数 N (1 ≦ N ≦ 100) が与えられる。
3 行目から N 行では、操作に関する情報が与えられる。N 行のうち i 行目では、2 つの整数 l_i と r_i (1 ≦ l_i ＜ r_i ≦ |S|) が空白区切りで与えられる。これは、操作 i が左から l_i 番目の文字を左端、左から r_i 番目の文字を右端とした部分文字列を逆順にする操作であることを表す。

出力

全操作後の文字列を 1 行に出力せよ。(21:49 表現の変更)出力の末尾に改行を入れること。

入力例1

abcdef
2
3 5
1 4

出力例1

debacf

操作 1 の後、文字列は abedcf となっている。
操作 2 の後、文字列は debacf となっている。

入力例2

redcoat
3
1 7
1 2
3 4

出力例2

atcoder

C - 菱型カウント

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

縦 R 行、横 C 列の長方形領域がある。上から i (1 ≦ i ≦ R) 行目、左から j (1 ≦ j ≦ C) 列目にあるマスをマス (i, j) と呼ぶことにする。これらのマスのうちいくつかのマスは黒く、他のマスは白く塗られている。

また、ある整数 K が定められている。

ここで、以下の条件を満たすように新たに緑色を塗ることを考える。この操作は1 回だけ行う。

ある整数の組 x (K ≦ x ≦ R - K + 1), y (K ≦ y ≦ C - K + 1) に対して、|i-x|+|j-y|≦ K - 1 を満たすすべてのマス (i,j) について、マス (i,j) は元々白いマスで、かつ、この操作で緑色に塗られる。さらに、|i-x|+|j-y|≧ K を満たすすべてのマスについて、そのマスは緑色に塗らない。

このような色の塗り方の総数はいくらか。ただし、ここでいう塗り方とは、どのマスがどの色になったかという組み合わせのことで、色の塗る順番は考慮しないものとする。

入力

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

R C K
s_1
s_2
:
s_R

1 行目には、3 つの整数 R (3 ≦ R ≦ 500), C (3 ≦ C ≦ 500), K (2 ≦ K ≦ 500) が空白区切りで書かれている。これは、長方形領域が縦 R 行、横 C 列あることを表す。K は文中で定められた整数である。
2 行目から R 行には、マスに関する情報が与えられる。R 行のうち i (1 ≦ i ≦ R) 行目には、長さ C の文字列 s_i が与えられる。文字列 s_i は o, x の 2 種類の文字でのみ構成されており、s_i の左から j (1 ≦ j ≦ C) 文字目の文字が o ならマス (i,j) が白いマスであることを、x ならマス (i,j) が黒いマスであることを表す。

部分点

この問題には部分点が設定されている。

R ≦ 50 かつ C ≦ 50 を満たすデータセット 1 に正解した場合は、30 点が与えられる。

出力

緑色の塗り方の総数を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

4 5 2
xoooo
oooox
ooooo
oxxoo

出力例1

以下の 3 通りが考えられます (o は白いマス、x は黒いマス、* は緑色のマスを表します)。

x	*	o	o	o
*	*	*	o	x
o	*	o	o	o
o	x	x	o	o

x	o	*	o	o
o	*	*	*	x
o	o	*	o	o
o	x	x	o	o

x	o	o	o	o
o	o	o	*	x
o	o	*	*	*
o	x	x	*	o

入力例2

4 5 2
ooooo
oxoox
oooox
oxxoo

出力例2

入力例3

8 6 3
oooooo
oooooo
oooooo
oooooo
oxoooo
oooooo
oooooo
oooooo

出力例3

D - バレンタインデー

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あるクラスには女子が N 人、男子が M 人いる。女子には 1 から N までの出席番号が、男子には 1 から M までの出席番号が割り当てられている。

幸運のキューピットはここから女子 P 人と男子 Q 人からなる、1 つの旅行グループを作る。

N 人の女子は合わせて R 個のチョコレートを持っており、チョコレートには 1 から R までの番号が付けられている。

チョコレート i (1 ≦ i ≦ R) は出席番号が x_i である女子が持っており、旅行中に出席番号が y_i である男子に渡す予定である。そのため旅行グループに出席番号が x_i である女子と出席番号が y_i である男子が両方含まれていた場合に限り渡すことができる。無事にチョコレート i が渡された場合の幸福度は z_i である。

無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値はいくらか。

入力

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

N M P Q R
x_1 y_1 z_1
x_2 y_2 z_2
:
x_R y_R z_R

1 行目には、5 つの整数 N (1 ≦ N ≦ 18), M (1 ≦ M ≦ 18), P (1 ≦ P ≦ N), Q (1 ≦ Q ≦ M), R (1 ≦ R ≦ N×M) が空白区切りで書かれている。これは、クラスに女子が N 人、男子が M 人おり、旅行グループは女子 P 人、男子 Q 人からなり、チョコレートが R 個あることを表す。
2 行目から R 行には、チョコレートに関する情報が与えられる。R 行のうち i (1 ≦ i ≦ R) 行目には、3 つの整数 x_i (1 ≦ x_i ≦ N), y_i (1 ≦ y_i ≦ M), z_i (1 ≦ z_i ≦ 10,000) が空白区切りで与えられる。これは、チョコレート i を出席番号が x_i である女子が持っており、旅行中に出席番号が y_i である男子に渡す予定であり、チョコレート i の幸福度が z_i であることを表す。
1 ≦ i ＜ j ≦ R である整数 i,j に対して、x_i≠x_j または y_i≠y_j が成り立つ。

部分点

この問題には部分点が設定されている。

N ≦ 8 かつ M ≦ 8 を満たすデータセット 1 に正解した場合は、30 点が与えられる。

出力

無事に渡されたチョコレートによる幸福度の合計値として考えられる最大値を 1 行に出力せよ。(21:51 表現の変更)出力の末尾に改行を入れること。

入力例1

出力例1

出席番号が 1, 2 の女子と出席番号が 2, 3, 4 の男子からなる旅行グループを考えます。

チョコレート 1 は出席番号が 1 の男子が旅行に参加しないため、渡されません。
チョコレート 2 は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は 7 です。
チョコレート 3 は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は 15 です。
チョコレート 4 は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は 6 です。
チョコレート 5 は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は 3 です。
チョコレート 6 は受け渡しする男女がともに旅行に参加するため、無事に渡されます。チョコレートの幸福度は 6 です。
チョコレート 7 は出席番号が 3 の女子が旅行に参加しないため、渡されません。

幸福度の合計値は 7 + 15 + 6 + 3 + 6 = 37 となり、これが最大値となります。

入力例2