AtCoder Beginner Contest 025

A - 25個の文字列

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

高橋君は短めの呼び名を考えています。呼び名は半角小文字アルファベット 2 文字で構成されます。

高橋君には好きな 5 種類のアルファベットがあります。高橋君は、以下の条件を満たす長さ 2 の文字列すべてを考え、それらの集合を「呼び名候補の集合」と呼ぶことにします。

条件 : 文字列の 1 文字目も 2 文字目も高橋君が好きな 5 種類のアルファベットのいずれかである。

ここで、2 つの長さ 2 の異なる文字列 S,T に関して、S が T よりも辞書順で先に来るというのは、以下の条件のうちのいずれかが満たされたときです。

文字列 S の 1 文字目と文字列 T の 1 文字目が異なり、かつ文字列 S の 1 文字目が文字列 T の 1 文字目よりもアルファベット順 (ABC 順) で先である。
文字列 S の 1 文字目と文字列 T の 1 文字目が同じで、かつ文字列 S の 2 文字目が文字列 T の 2 文字目よりもアルファベット順 (ABC 順) で先である。

例えば、好きなアルファベットが a, b, c, d, e のとき、「呼び名候補の集合」に含まれる文字列は、辞書順に、aa, ab, ac, ad, ae, ba, bb, bc, bd, be, ca, cb, cc, cd, ce, da, db, dc, dd, de, ea, eb, ec, ed, ee となります。

「呼び名候補の集合」を構成する文字列は全部で 25 個あります。高橋君はそれらの文字列を辞書順に並べたときに先頭から N 番目となる文字列を最終的な呼び名にすることにしました。

あなたの課題は、高橋君が定めた最終的な呼び名を求めることです。

入力

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

S
N

1 行目には、長さ 5 の文字列 S が与えられる。S の各文字はいずれも半角小文字アルファベットであり、S に使われている文字には重複がなく、かつ昇順に並んでいる。すなわち文字列 S の左から i (1 ≦ i ≦ 5) 文字目の文字を c_i としたとき、c_i ≠ c_j (i≠j) であり、i＜j ならアルファベット c_i はアルファベット c_j よりもアルファベット順で前である。
2 行目には、整数 N (1 ≦ N ≦ 25) が与えられる。

出力

高橋君が定めた最終的な呼び名を 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

abcde
8

出力例1

bc

「呼び名候補の集合」は、問題文中の例と同一です。「呼び名候補の集合」の中で、辞書順で 8 番目の文字列は bc なので、bc を出力します。

入力例2

aeiou
22

出力例2

ue

入力例3

vwxyz
25

出力例3

zz

B - 双子とスイカ割り

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

直大くんと直子さんは双子の兄妹です。今日は家の廊下でスイカ割りの練習をすることになりました。

廊下は東西方向に無限に長く、途中の 1 箇所に直大くんの部屋の入り口があります。最初、直大くんの部屋の前に直大くんと直子さんがいます。

スイカ割りの練習では、以下の N 回の移動を順に実行します。

i 番目の移動 : 最初に直子さんが方角とメートル単位の距離 d_iを指定します。指定する方角は東か西で、d_i は正整数です。その後、直大くんが指定された方向を向いて、距離 d_i を目標に移動します。

直大くんは 1 回の移動において A メートルよりも少ない距離を移動することと、B メートルよりも多い距離を移動することが苦手です。そのため、目標移動距離が d_i メートルだったときの最終移動距離は以下のようになります。

d_i ＜ A のとき、直大くんは向いている方向に A メートル進む。
A ≦d_i ≦ B のとき、直大くんは向いている方向に d_i メートル進む。
d_i ＞ B のとき、直大くんは向いている方向に B メートル進む。

あなたの課題は、直大くんが N 回の移動を終えたときにどこにいるのかを求めることです。

入力

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

N A B
s_1 d_1
s_2 d_2
:
s_N d_N

1 行目には、3 つの整数 N (1 ≦ N ≦ 100) と A と B (1 ≦ A ≦ B ≦ 100) が空白区切りで書かれている。
2 行目からの N 行には、移動の情報が書かれている。N 行のうちの i (1 ≦ i ≦ N) 行目には、文字列 s_i と整数 d_i (1 ≦ d_i ≦ 100) が空白区切りで書かれている。文字列 s_i は East または West であり、直子さんが指定する方角がそれぞれ東、西であることを表す。

出力

直大くんの最終的な位置が直大くんの部屋の前よりも X (1 ≦ X) メートル東になったとき、文字列 East と X をこの順に空白区切りで 1 行に出力せよ。
直大くんの最終的な位置が直大くんの部屋の前よりも X (1 ≦ X) メートル西になったとき、文字列 West と X をこの順に空白区切りで 1 行に出力せよ。
直大くんの最終的な位置が直大くんの部屋の前と同じ場所になったとき、整数 0 を 1 行に出力せよ。

いずれの場合においても、出力の末尾に改行を入れること。

入力例1

3 5 10
East 7
West 3
West 11

出力例1

West 8

1 番目の移動では、直子さんは東に 7 メートルと指定しました。直大くんは東に 7 メートル移動し、この時点で直大くんは直大くんの部屋の前から東に 7 メートルの位置にいます。
2 番目の移動では、直子さんは西に 3 メートルと指定しました。直大くんは西に 5 メートル移動し、この時点で直大くんは直大くんの部屋の前から東に 2 メートルの位置にいます。
3 番目の移動では、直子さんは西に 11 メートルと指定しました。直大くんは西に 10 メートル移動し、この時点で直大くんは直大くんの部屋の前から西に 8 メートルの位置にいます。
最終的に直大くんは直大くんの部屋の前から西に 8 メートルの位置にいます。

入力例2

3 3 8
West 6
East 3
East 1

出力例2

この例では、最終的に直大くんは直大くんの部屋の前と同じ位置にいることになります。

入力例3

5 25 25
East 1
East 1
West 1
East 100
West 1

出力例3

East 25

C - 双子と○×ゲーム

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

直大くんと直子さんは双子の兄妹です。時々、休日に 2 人でゲームをしています。

ゲームは○×ゲームをベースにしており、以下の要領でゲームが行われます。

ゲームは縦 3 マス、横 3 マスの盤面を使います。ゲーム開始時点ではどのマスにも文字が書かれていません。
挨拶した後、直大くんから始めて交互に文字を書いていきます。文字は盤面上のまだ文字が書かれていないマスの上にのみ書くことができます。そのようなマスが複数ある場合は好きな 1 箇所を選んで書きます。書く文字は、直大くんが○、直子さんが×です。
合わせて 9 回文字を書いた時点で、すべてのマスが埋まります。その後、得点計算を行い、得点の高い方が勝ちます。

得点計算は以下の方法で行われます。ここで、盤面の左上のマスをマス (1, 1) とし、左上から下に i-1 (1 ≦ i ≦ 3) マス、右に j-1 (1 ≦ j ≦ 3) マス進んだところにあるマスをマス (i, j) と呼ぶことにします。

1 ≦ i ≦ 2 および 1 ≦ j ≦ 3 を満たすすべての整数組 (i,j) に対して、マス (i,j) とマス (i+1,j) に書かれているマスを見て、同じ文字が書かれていたなら直大くんに、違う文字が書かれていたなら直子さんに b_{i,j} 点が入る。
1 ≦ i ≦ 3 および 1 ≦ j ≦ 2 を満たすすべての整数組 (i,j) に対して、マス (i,j) とマス (i,j+1) に書かれているマスを見て、同じ文字が書かれていたなら直大くんに、違う文字が書かれていたなら直子さんに c_{i,j} 点が入る。

直大くんも直子さんも、最終的に得られる自分の得点ができるだけ多くなるようにゲームを行います。両者が最善を尽くしたときのそれぞれの得点を計算してください。

入力

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

b_{1,1} b_{1,2} b_{1,3}
b_{2,1} b_{2,2} b_{2,3}
c_{1,1} c_{1,2}
c_{2,1} c_{2,2}
c_{3,1} c_{3,2}

1 行目には、3 つの整数 b_{1,1} (0 ≦ b_{1,1} ≦ 100) と b_{1,2} (0 ≦ b_{1,2} ≦ 100) と b_{1,3} (0 ≦ b_{1,3} ≦ 100) が空白区切りで書かれている。
2 行目には、3 つの整数 b_{2,1} (0 ≦ b_{2,1} ≦ 100) と b_{2,2} (0 ≦ b_{2,2} ≦ 100) と b_{2,3} (0 ≦ b_{2,3} ≦ 100) が空白区切りで書かれている。
3 行目には、2 つの整数 c_{1,1} (0 ≦ c_{1,1} ≦ 100) と c_{1,2} (0 ≦ c_{1,2} ≦ 100) が空白区切りで書かれている。
4 行目には、2 つの整数 c_{2,1} (0 ≦ c_{2,1} ≦ 100) と c_{2,2} (0 ≦ c_{2,2} ≦ 100) が空白区切りで書かれている。
5 行目には、2 つの整数 c_{3,1} (0 ≦ c_{3,1} ≦ 100) と c_{3,2} (0 ≦ c_{3,2} ≦ 100) が空白区切りで書かれている。

出力

出力は 2 行からなる。1 行目には直大くんの得点を、2 行目には直子さんの得点を出力せよ。出力の末尾に改行を入れること。

入力例1

出力例1

15
80

例えば、マス (2,1) →マス (1,1) →マス (2,2) →マス (1,3) →マス (1,2) →マス (2,3) →マス (3,1) →マス (3,2) →マス (3,3) の順に文字が書かれた場合を考えます。この場合、盤面は最終的に以下のようになります。

×	○	×
○	○	×
○	×	○

この場合、直大くんの得点は、(b_{1,2} + b_{1,3} + b_{2,1} + c_{1,2} = ) 15 + 0 + 0 + 0 = 15 点となります。
一方、直子さんの得点は、(b_{1,1} + b_{2,2} + b_{2,3} + c_{1,1} + c_{1,2} + c_{2,2} + c_{3,1} + c_{3,2} = ) 0 + 0 + 25 + 20 + 10 + 0 + 25 + 0 = 80 点となります。

入力例2

出力例2

72
107

D - 25個の整数

Time Limit: 5 sec / Memory Limit: 256 MB

問題文

高橋君は縦 5 マス、横 5 マスの盤面に 1 から 25 までの整数を 1 つずつ書き込もうとしています。

高橋君は以下の条件をすべて満たすように整数を配置しようと考えています。

整数は各マスに 1 つずつ割り当てる。
縦または横に連続する 3 つの整数をどのように取り出しても、それらは昇順または降順になっていない。すなわち、上から i (1 ≦ i ≦ 5) 番目、左から j (1 ≦ j ≦ 5) 番目のマスに書かれた整数を n_{i,j} としたとき、以下の 2 条件が成立する。

n_{i,j} ＜ n_{i+1,j} ＜ n_{i+2,j} あるいは n_{i,j} ＞ n_{i+1,j} ＞ n_{i+2,j} を満たす整数組 (i,j) (1 ≦ i ≦ 3, 1 ≦ j ≦ 5) が存在しない。
n_{i,j} ＜ n_{i,j+1} ＜ n_{i,j+2} あるいは n_{i,j} ＞ n_{i,j+1} ＞ n_{i,j+2} を満たす整数組 (i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 3) が存在しない。

すでにいくつかのマスについては、どの整数を書き込むかは決まっています。あなたの課題は、上記の条件を満たすような残りの整数の配置の総数を計算することです。

入力

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

x_{1,1} x_{1,2} x_{1,3} x_{1,4} x_{1,5}
x_{2,1} x_{2,2} x_{2,3} x_{2,4} x_{2,5}
x_{3,1} x_{3,2} x_{3,3} x_{3,4} x_{3,5}
x_{4,1} x_{4,2} x_{4,3} x_{4,4} x_{4,5}
x_{5,1} x_{5,2} x_{5,3} x_{5,4} x_{5,5}

1 行目には、5 つの整数 x_{1,1} (0 ≦ x_{1,1} ≦ 25) と x_{1,2} (0 ≦ x_{1,2} ≦ 25) と x_{1,3} (0 ≦ x_{1,3} ≦ 25) と x_{1,4} (0 ≦ x_{1,4} ≦ 25) と x_{1,5} (0 ≦ x_{1,5} ≦ 25) が空白区切りで書かれている。
2 行目には、5 つの整数 x_{2,1} (0 ≦ x_{2,1} ≦ 25) と x_{2,2} (0 ≦ x_{2,2} ≦ 25) と x_{2,3} (0 ≦ x_{2,3} ≦ 25) と x_{2,4} (0 ≦ x_{2,4} ≦ 25) と x_{2,5} (0 ≦ x_{2,5} ≦ 25) が空白区切りで書かれている。
3 行目には、5 つの整数 x_{3,1} (0 ≦ x_{3,1} ≦ 25) と x_{3,2} (0 ≦ x_{3,2} ≦ 25) と x_{3,3} (0 ≦ x_{3,3} ≦ 25) と x_{3,4} (0 ≦ x_{3,4} ≦ 25) と x_{3,5} (0 ≦ x_{3,5} ≦ 25) が空白区切りで書かれている。
4 行目には、5 つの整数 x_{4,1} (0 ≦ x_{4,1} ≦ 25) と x_{4,2} (0 ≦ x_{4,2} ≦ 25) と x_{4,3} (0 ≦ x_{4,3} ≦ 25) と x_{4,4} (0 ≦ x_{4,4} ≦ 25) と x_{4,5} (0 ≦ x_{4,5} ≦ 25) が空白区切りで書かれている。
5 行目には、5 つの整数 x_{5,1} (0 ≦ x_{5,1} ≦ 25) と x_{5,2} (0 ≦ x_{5,2} ≦ 25) と x_{5,3} (0 ≦ x_{5,3} ≦ 25) と x_{5,4} (0 ≦ x_{5,4} ≦ 25) と x_{5,5} (0 ≦ x_{5,5} ≦ 25) が空白区切りで書かれている。

上記 25 個の整数は、以下の情報を表している。

整数 x_{i,j} (1 ≦ i ≦ 5, 1 ≦ j ≦ 5) は上から i 番目、左から j 番目のマスに書かれる整数に関する情報である。x_{i,j} = 0 ならそのマスに書かれる整数が決まっていないことを、x_{i,j} ≠ 0 ならそのマスに書かれる整数が x_{i,j} であることを表す。

また、入力は以下の条件を満たす。

1 以上 5 以下の 4 つの整数組 i,j,k,l に関して、x_{i,j} ≧ 1 かつ x_{k,l} ≧ 1 かつ (i,j) ≠ (k,l) ならば、x_{i,j} ≠ x_{k,l}。
x_{i,j} ≠ 0 を満たす整数組 (i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 5) は 5 個以上存在する。

部分点

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

データセット 1 において、すべての入力には、x_{i,j} ≠ 0 を満たす整数組 (i,j) (1 ≦ i ≦ 5, 1 ≦ j ≦ 5) が 17 個以上存在する。データセット 1 に正解した場合は、30 点が与えられる。
追加制約のないデータセット 2 に正解した場合は、上記とは別に 70 点が与えられる。

出力

条件を満たすような残りの整数の配置の総数を 1000000007 (= 1,000,000,007) で割った余りを 1 行に出力せよ。出力の末尾に改行を入れること。

入力例1

0 0 15 2 7
0 0 16 1 22
20 25 4 19 0
3 23 9 18 10
17 0 5 21 8

出力例1

まだ書かれていない整数は 6, 11, 12, 13, 14, 24 の 6 つです。以下の 2 通りが、条件を満たす配置です。

14	12	15	2	7
13	11	16	1	22
20	25	4	19	6
3	23	9	18	10
17	24	5	21	8

14	13	15	2	7
12	11	16	1	22
20	25	4	19	6
3	23	9	18	10
17	24	5	21	8

入力例2

10 14 13 15 11
16 0 17 0 18
0 19 0 20 9
21 12 22 0 23
0 24 0 25 0

出力例2

どのように残りを書いても条件を満たします。

入力例3

1 2 3 4 5
6 7 8 9 10
11 12 13 14 15
16 17 18 19 20
0 0 0 0 0

出力例3

どのように置いても条件を満たさない場合があります。

入力例4

1 25 2 24 3
23 4 22 5 21
6 20 7 19 8
18 9 17 10 16
11 15 12 14 13

出力例4

すでにすべての整数の配置が決まっている場合もあります。