A - 算盤の書

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

ある数学者は次の問題を考案したという。

  • 1 つがいの兎は、産まれて 2 か月後から毎月 1 つがいずつの兎を産む。
  • 兎が死ぬことはない。
  • この条件のもとで、産まれたばかりの 1 つがいの兎は 1 年の間に何つがいの兎になるか？

※つがい:オスとメスの一組


この問題は上の問題をもとにした問題です。
今、 1 つがいの産まれたばかりの兎がいるとします。
上の問題の条件と同様に兎が増えるとすると、 n ヶ月後に何つがいの兎がいるでしょう？
このとき、 n ヶ月後ちょうどに産まれた兎のつがいも数に含めます。

入力

入力は以下の形式で標準入力から与えられる。 
n
  • 何ヶ月後かを表す整数 n (0 \leq n \leq 45) が 1 行で与えられる。

出力

n ヶ月後の兎のつがいの数を標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

0

出力例 1

1

入力例 2

5

出力例 2

8
  • 2 ヶ月後に 1 つがい、 3 ヶ月後に 1 つがい、
    4 ヶ月後に 2 つがい、 5 ヶ月後に 3 つがいが産まれ、
    初めにいた 1 つがいと合わせて、合計 8 つがいとなる。

入力例 3

45

出力例 3

1836311903

Source Name

天下一プログラマーコンテスト2012 予選A
B - 分類たん

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

分類たんは、スペースをカンマ区切りにするのが大好き。
でも、スペースが続いたときは、カンマ 1 つで書きたい。

文字列が与えられるので、与えられた文字列のスペースをカンマ区切りにした文字列を出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
c_1c_2…c_N
  • 入力として文字列が 1 行で与えられる。
  • 入力の文字列長 N は、 1 \leq N \leq 2000 を満たす。
  • i 文字目の文字 c_i は大文字のアルファベット (A, …, Z) 、カンマ (,) 、スペース( ) のいずれかである。
  • 文字列の最初の文字 c_1 と最後の文字 c_N はスペースではない。

出力

入力として与えられた文字列のスペースをカンマ区切りにした文字列を標準出力に 1 行で出力せよ。
ただし、複数の連続したスペースは 1 つのカンマにする。
なお、行の終端には改行が必要である。

入力例 1

X Y Z

出力例 1

X,Y,Z

入力例 2

A  B, C

出力例 2

A,B,,C

入力例 3

QWERTY

出力例 3

QWERTY

Source Name

天下一プログラマーコンテスト2012 予選A
C - 敵対的引用

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

N 個のグループがあります。
それぞれのグループには、「group1」から「groupN」までの名前がついています。
ある日、あるグループがあるグループを呼び、そして、発言を引用するということが繰り返されました。


groupA が groupB に対して攻撃的であるとします。そのとき

  • groupA は groupB を呼ぶとき、グループの名前のうしろに w をつけ、「groupBw」 と発言します。
  • groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (") で囲んで引用し、うしろに ww をつけて発言します。

また、groupA が groupB に対して攻撃的でないとします。そのとき

  • groupA は groupB を呼ぶとき、「groupB」 と発言します。
  • groupA は groupB の発言を引用するとき、groupB の発言をダブルクォーテーション (") で囲んで引用し、うしろには何もつけずに発言します。

例えば、group2 が group1 に対して攻撃的であるとき、group2 は group1w と発言します。
さらに、group3 が group2 に対して攻撃的であるとき、group3 は "group1w"ww と発言します。
また、group2 が group3 に対して攻撃的でないとき、group2 は group3 と発言します。
さらに、group1 が group2 に対して攻撃的でないとき、group1 は "group3" と発言します。

groupA が groupB に攻撃的だが、groupB がgroupA に攻撃的ではないということもあります。
また、自虐的なグループ、つまり自分自身に対して攻撃的なグループもあります。


ある 1 つの発言が与えられるので、その発言をしそうなグループの総数を答えてください。

入力

入力は以下の形式で標準入力から与えられる。 
N M
a_1 b_1
a_2 b_2
 :
 :
a_M b_M
s
  • 1 行目は、グループの数を表す整数 N (1 \leq N \leq 10^5) , 敵対的関係を表す整数 M (1 \leq M \leq 10000) が与えられる。
  • 2 行目から M 行は、グループの敵対関係が与えられる。
  • a_i, b_i (1 \leq a_i, b_i \leq N) はグループ a_i がグループ b_i に対して攻撃的であることを表す。
  • i \neq j ならば、 a_i \neq a_j または b_i \neq b_j である。
  • M+2 行目は、あるグループの発言 s が与えられる。
  • s の文字列長は 300 以下である。
  • 少なくとも 1 グループは発言を行った可能性がある。

部分点

グループの数が少ない入力 ( 1 \leq N \leq 100 ) のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

発言 s を行った可能性のあるグループの数を、標準出力に 1 行で出力せよ。
なお、行の終端には改行が必要である。

入力例 1

3 6
1 2
1 3
2 1
2 3
3 1
3 2
"group1w"ww

出力例 1

3
  • group1w と発言したのは group2 または group3 である。
  • group2 が group1w と発言した場合、 "group1w"ww と発言したのは group1 または group3 である。
  • group3 が group1w と発言した場合、 "group1w"ww と発言したのは group1 または group2 である。
  • よって、発言 "group1w"ww を行った可能性のあるグループは、 group1, group2, group3 の 3 グループである。

入力例 2

3 2
1 2
2 3
"group3w"

出力例 2

2
  • この発言を行った可能性のあるグループは、 group2, group3 の 2 グループである。

入力例 3

3 1
1 1
""group1w"ww"ww

出力例 3

1
  • 自分自身のグループを呼ぶ場合や、自分自身のグループの発言を引用する場合もある。

Source Name

天下一プログラマーコンテスト2012 予選A
D - アリの巣

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

マス目からなる迷路があります。
迷路の各マスは、巣、角砂糖、壁、空き地のいずれかであり、アリ達は左上にある巣のマスから右下にある角砂糖のあるマスまで行きたいと思っています。
角砂糖のあるマスを含む、壁以外の任意の地点へは到達することができ、またループになっている経路はありません。
加えて、(奇数,奇数) の地点は必ず壁であり、(偶数,偶数) の地点は必ず空き地です。
ここでの座標は、左上の巣のある地点を (0,0) とし、1 つ右の座標は (1,0)、1 つ下の座標は (0,1) になります。


このような迷路の例を図 1 に示します。
黄緑色の部分が (奇数,奇数) の地点、橙色の部分が (偶数,偶数) の地点になります。

図 1：迷路の例

ここでのアリは、直進できる場合は直進し、壁にぶつかった場合は 1/2 の確率で左、1/2 の確率で右に曲がる性質を持っています。壁にぶつかっても左右のいずれかに壁がある場合は、その反対方向に必ず曲がります。
どちらにも曲がれないような場合(三方向が壁または迷路外になった場合)は、その場でアリは死亡してしまい壁になります。
なお、巣のマスの下は壁になっているので、最初は右方向にしか進めません。また、角砂糖のあるマスの左は壁になっているので、上方向からしか角砂糖のあるマスに到達できません。


例えば図 1 の場合を図 2 に示すと、1 匹目のアリは直進するので右上の地点 (4,0) で壁と迷路外に囲まれて死亡してしまいます。
2 匹目のアリは (4,0) が 1 匹目のアリにより壁になっているので、その 1 つ手前の (3,0) で死亡し壁になります。
その結果、3 匹目、4 匹目のアリは (2,0) で右に曲がり、(2,4)、(2,3) でそれぞれ死亡します。
5 匹目のアリは (2,2) で直進できないので、(1,2) または (3,2) に進みます。
(1,2) の方向に進んだ場合は (0,4) で死亡しますが、(3,2) の方向に進んだ場合は角砂糖へと到達できます。

図 2：図 1 の迷路に対する 1 〜 5 匹目のアリの動き方

アリが角砂糖にに辿り着くまでこのような行動を繰り返したとすると、辿り着くまでに必要なアリの数の期待値を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N
c_{(0,0)}c_{(1,0)}‥‥c_{(N-1,0)}
c_{(1,1)}c_{(1,1)}‥‥c_{(N-1,1)}
 :
 :
c_{(0,N-2)}c_{(1,N-2)}‥‥c_{(N-1,N-2)}
c_{(0,N-1)}c_{(1,N-1)}‥‥c_{(N-1,N-1)}
  • 入力は N+1 行ある。
  • 1 行目には、与えられる迷路の縦と横の長さを表す整数 N(5≦N≦49) が与えられる。
    • N は奇数である。
  • 2 行目からの N 行には、各行に図の形を表す状態 c_{(i,j)}(0≦i,j≦N-1) が N 文字与えられる。
    • c_{(i,j)} は下記のいずれかであり、それぞれ地点 (i,j) のマスが下記のような状態であることを表す。
      • S : そのマスが巣であることを表す。
      • G : そのマスに角砂糖があることを表す。
      • # : そのマスが壁であることを表す。
      • . : そのマスが空き地であることを表す。
    • c_{(0,0)} は必ず S であり、c_{(N-1,N-1)} は必ず Gである。また、S と G は、それぞれこの場所にしか存在しない。
    • S から 1 つ下の地点 c_{(1,0)} と G から 1 つ左の地点 c_{(N-1,N-2)} は必ず # である。
    • i と j が共に奇数の地点は必ず # であり、i と j が共に偶数の地点は必ず . である。

部分点

迷路のサイズが小さい入力(5≦N≦9)のみ正解すると、100 点満点に対して部分点として 50 点が与えられる。

出力

アリが角砂糖のあるマスに辿り着くまでに必要なアリの数の期待値を標準出力に 1 行で出力せよ。
誤差は絶対誤差あるいは相対誤差の少なくとも片方が 1e−6(10^{-6}) 以下であれば許容する。 なお、行の終端には改行が必要である。

入力例 1

5
S....
##.##
.....
.#.#.
.#.#G

出力例 1

5.937500000
  • それぞれの匹数で角砂糖まで到達できる確率を求めると、以下のようになる。
    • 5 匹で到達できる確率：1/2
    • 6 匹で到達できる確率：1/2×1/2
      • (2,2) の分岐で 5 匹目は (1,2) の方向へ、6 匹目は (3,2) の方向へ曲がった場合
    • 7 匹で到達できる確率：1/2^3
    • 8 匹で到達できる確率：1/2^4
    • 9 匹で到達できる確率：1/2^4×1
  • したがって、5×1/2+6×1/2×1/2+7×1/2^3+8×1/2^4+9×1/2^4×1=5.9375 となる。

入力例 2

9
S........
####.####
.........
.#####.##
...#.#...
.#.#.####
.#...#...
.#.#.#.#.
.#.#...#G

出力例 2

18.029407501

入力例 3

13
S............
####.#.#.####
.....#.#...#.
.###########.
.....#.#.....
.#.###.###.##
.#...#.#.....
##.#.#.#####.
.#.#.....#...
.#.###.#.#.##
...#...#.....
.#.#.#.#.###.
.#.#.#.#...#G

出力例 3

35.000000000

Source Name

天下一プログラマーコンテスト2012 予選A