A - クイズゲーム

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君はクイズゲームを作っています。
ヒント機能として、「不正解の選択肢を 1 つ消す」という機能を作りたいです。
あなたには選択肢の数 N と、その問題の正解である番号 M が与えられます。
消してもよい選択肢の番号を 1 つ出力してください（消す選択肢は、正解である番号でなければ何でも構いません）。

入力

入力は以下の形式で標準入力から与えられる。 
N M
  1. 1 行目には、選択肢を示す整数 N(2≦N≦5) と、正解の番号を示す整数である M(1≦M≦N) が与えられる。
    • 選択肢の範囲は 1 から N までである。

出力

消してもよい選択肢の番号を出力せよ。
また、出力の末尾には改行を入れること。

入力例 1

4 4

出力例 1

1
  • 正解である番号は 4 なので、1 、2、3 を選択肢から外すことができます。
  • 1 を出力していますが、2 も 3 も正解です。

入力例 2

2 1

出力例 2

2
  • 正解である番号は 1 なので、2 を選択肢から外すことができます。
B - 音楽ゲーム

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

楽器を演奏できない高橋君は、音楽ゲームが大好きです。
このゲームでは 9 個のボタンが存在し、曲に合わせてボタンをタイミングよく押したり、押しっぱなしにすることによって楽器を演奏してしている気分になります。
あなたには高橋くんがプレイした楽曲の譜面が与えられます。
ボタンを押す場所はx、押しっぱなしにする部分はo で与えられます。他は.です。
高橋くんが譜面をミスなくプレイしたとき、ボタンを押した回数を出力してください。

入力

入力は以下の形式で標準入力から与えられる。 
N
x_{11}x_{12}...x_{18}x_{19}
x_{21}x_{22}...x_{28}x_{29}
:
x_{N1}x_{N2}...x_{N8}x_{N9}
  1. 1 行目に、譜面の行数を表す整数 N (1≦N≦100) が与えられる。
    • 譜面は常に 9 列であることが保証されている。
  2. 2 行目からの N 行で、高橋くんが遊ぶ譜面が与えられる。
    • 譜面の種類は x o . の 3 種類である。
    • 譜面が x のとき、高橋くんはボタンを押す。
    • 譜面が o のとき、高橋くんはボタンを押し、同じ列で o が続く限り押しっぱなしにする。
    • 譜面が . のとき、高橋くんは何もしない。

出力

高橋くんが譜面をミスなくプレイしたとき、ボタンを押した回数を出力せよ。
なお、出力の最後には改行をいれること。

入力例 1

15
.........
.x.......
.........
...x.....
.........
.......o.
.......o.
.......o.
.........
..x.....o
........o
........o
....x...o
.x......o
........o

出力例 1

7
  • 一瞬だけ押す必要がある部分は 5 つあります。
  • 長押しは 2 つです。
  • 合わせて 7 が答えです。

入力例 2

6
..o..x.o.
..o..x.o.
..x..o.o.
..o..o.o.
..o..x.o.
..o..x.o.

出力例 2

9
  • 一瞬だけ押す必要がある部分は 5 つあります。
  • x が連続している場合、何度もボタンを押す必要があることに注意してください。
  • 長押しは 4 つです。
  • 合わせて 9 が答えです。

入力例 3

2
.........
.........

出力例 3

0
C - ソーシャルゲーム

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は、アイドルを集めるカードゲームが大好きです。
このゲームでは、お金を払ってくじを引くことにより、ある確率分布によって決定されるアイドルが 1 人、手に入ります。
高橋君は、すべてのアイドルを集めたいです。
くじは M 種類あり、それぞれのくじで、各アイドルの出現確率や、1 回くじをひくために必要な金額が違います。
高橋君がすべてのアイドルを集めるために最適な戦略を取った場合、必要な金額の期待値を求めなさい。

入力

入力は以下の形式で標準入力から与えられる。 
N M
C_1 cost_1 
idol_{1,1} p_{1,1}
idol_{1,2} p_{1,2}
:
idol_{1,C_1} p_{1,C_1}
:
C_M cost_M 
idol_{M,1} p_{M,1}
idol_{M,2} p_{M,2}
:
idol_{M,C_M} p_{M,C_M}
  1. 1 行目に、アイドルの総数を表す整数 N(1≦N≦10)、くじの種類を表す整数 M(1≦M≦4)が半角空白区切りで与えられる。
  2. 2 行目以降で i(1≦i≦M) 回、くじに関する情報が半角空白区切りで与えられる。
    • 整数 C_i (1≦C_i≦N) は、i 番目のくじに含まれるアイドルの枚数を表す。
    • 整数 cost_i (1≦cost_i≦3000) は、i 番目のくじをひくのにかかる値段を表す。
  3. C_i と cost_i 以降で、i 番目のくじに含まれるアイドルの情報が j(1≦j≦C_i) 回与えられる。
    • 整数 idol_{i,j} (1≦idol_{i,j}≦N) は、i 番目のくじに含まれる j 番目のアイドルである。
    • 整数 p_{i,j} (1≦p_{i,j}≦100) は、i 番目のくじに含まれる j 番目のアイドルの、百分率表記での出現確率を表す。
    • i 番目のくじに含まれるすべてのアイドルの出現率を足すと、100 になる。

部分点

    この問題には部分点が設定されている。
  • N=1 かつ M=1 を満たす全ての入力に正解した場合、10 点。
  • N=1 を満たす全ての入力に正解した場合、さらに 10 点。
  • C_i=1 を満たす全ての入力に正解した場合、さらに 10 点。
  • N≦2 を満たす全ての入力に正解した場合、さらに 20 点。
  • M=1 を満たす全ての入力に正解した場合、さらに 20 点。
  • すべてのテストケースに正解した場合、さらに 30 点が追加され、合計で 100 点となる。

出力

高橋君がすべてのアイドルを集めるために最適な戦略を取った場合、必要な金額の期待値を求めなさい。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。
なお、出力の最後には改行をいれること。

解き方が解らない方へ

この問題は、非常に多くの部分点が設定されています。満点が取れる解法が解らない場合も、部分点だけを狙ったコードを提出してみましょう。
また、D問題の難易度も同程度となっております。両方の問題を読んでみることをお勧めします。

入力例 1

5 2
2 300
3 5
4 95
3 500
5 20
1 30
2 50

出力例 1

9343.17042606516
  • アイドルは 5 種類、くじは 2 種類です。
    1. 1 番目のくじでは 2 種類のアイドルを獲得することができ、1 回ごとに費用が 300 だけかかります。
      • 1 番目のくじに含まれる 1 番目のアイドルは、アイドル 3 で、出現確率は 5% です。
      • 1 番目のくじに含まれる 2 番目のアイドルは、アイドル 4 で、出現確率は 95% です。
    2. 2 番目のくじでは 3 種類のアイドルを獲得することができ、1 回ごとに費用が 500 だけかかります。
      • 2 番目のくじに含まれる 1 番目のアイドルは、アイドル 5 で、出現確率は 20% です。
      • 2 番目のくじに含まれる 2 番目のアイドルは、アイドル 1 で、出現確率は 30% です。
      • 2 番目のくじに含まれる 3 番目のアイドルは、アイドル 2 で、出現確率は 50% です。
  • この入力では、2 つのくじで手に入るアイドルが全て違います。
  • 1 つめのくじでかかる金額が 6015.789473684 、2 つめのくじでかかる金額が 3327.380952381 なので、合わせて 9343.17042606516 が答えとなります。

入力例 2

3 3
1 10
1 100
1 10
2 100
1 10
3 100

出力例 2

30
  • 1 番目のくじ、2 番目のくじ、3 番目のくじをそれぞれ 1 回ずつひくと、アイドルをすべて集めることができます。

入力例 3

1 1
1 1000
1 100

出力例 3

1000
  • アイドルもくじも 1つずつしかないので、くじを 1 回引くだけで良いです。

入力例 4

2 2
2 1000
1 30
2 70
2 800
1 80
2 20

出力例 4

2128.57142857143

入力例 5

3 3
2 50
1 99
2 1
3 300
1 90
2 9
3 1
3 3000
1 80
2 15
3 5

出力例 5

30333.4291970656
D - 軍艦ゲーム

Time Limit: 2 sec / Memory Limit: 64 MB

問題文

高橋君は艦長である。
高橋艦長の任務は、鎮守府のある海域から最終目的地となる海域へ進軍することである。
高橋艦長は次の順序で行動する。
  1. 航路選択
    • 進軍する航路を選択する。現在の海域から異なる海域へ移動できる航路が 1 本も存在しない場合、4 の海域離脱を行う。
    • また、現在の海域から異なる海域への航路が複数本存在する場合、何者かの陰謀によって等確率で航路が選択される。
      • たとえば、鎮守府のある海域から、他の海域への航路が 4 本存在する場合、それぞれ 25% の確率で選択されます。
  2. 進軍
    • 選択された航路によって、海域を移動する。
  3. 戦闘
    • 進軍先の海域 i には敵艦が待ち構えており、戦闘が発生する。
    • 鎮守府から出港したとき、高橋艦長が率いる軍艦の体力は H であり、戦闘によって軍艦の体力は D_i だけ減少する。
    • 軍艦の体力が 0 以下になると、軍艦は沈没してしまう。
    • 軍艦が沈没すると高橋艦長は失意のあまりこれ以上出撃することが出来なくなってしまうため、絶対に沈没させてはいけない。
    • なお、鎮守府のある海域では戦闘は発生しないが、最終目的地である海域では必ず戦闘が発生する。
  4. 海域離脱 or 航路選択に戻る
    • 海域離脱とは、鎮守府のある海域へ戻ることを意味する。
    • 海域離脱した際に、軍艦の残り体力が C であった場合、H-C だけ体力回復のために時間を消費する。
上記1,2,3,4のサイクル1回につき時間を 1 だけ使う。
海域と航路について
  • いま、N 個の海域と M 個の航路がある。
  • これら M 個の航路は、すべて一方通行である。
そのため、任意の異なる海域 A,B において、ある 1 本の航路を利用して、海域 A から海域 B へ移動し、海域 B から海域 A へ移動することはできない。
あなたは高橋艦長の参謀であり、高橋艦長が消費する時間を最小となるよう行動した場合、最終目的地における戦闘で生存するまでに経過する時間の期待値を求めることが仕事である。
どのようにしても高橋艦長が任務を完遂できない場合は-1と出力せよ。
ただし、出力する期待値が 10^6 より大きくなる入力は与えられない。

入力

入力は以下の形式で標準入力から与えられる。 
N M H
f_1 t_1
f_2 t_2
:
f_M t_M
D_1
D_2
:
D_N
  1. 1 行目は、海域数を表す整数 N (2≦N≦100)、航路数を表す整数 M (0≦M≦N * (N - 1) / 2)、出港時の艦隊の体力を表す整数 H (1≦H≦100) が半角空白区切りで与えられる。
    • 鎮守府のある海域は 1 で、最終目的地である海域は N です。
  2. 2 行目から M 行は、 i 番目の航路を表す。移動元の海域を表す整数 f_i (1≦f_i≦N)、移動先の海域を表す整数 t_i (1≦t_i≦N) が、スペース区切りで与えられる。
    • f_i<t_i であることが保証されている。
  3. 2+M 行目から N 行は、i 番目の海域での戦闘で受けるダメージを表す整数 D_i (0≦D_i≦100) が、一行で与えられる。
    • D_1 の値は常に 0 である（鎮守府のある海域です）。
  • 出力する期待値が 10^6 より大きくなる入力が与えられないことに留意せよ。

出力

高橋艦長が消費する時間が最小となるよう行動した場合、最終目的地における戦闘で生存するまでに経過する時間の期待値を出力せよ。
出力は絶対誤差あるいは相対誤差の少なくとも片方が 10^{-6} 以下であれば許容される。
また、どのようにしても高橋艦長が任務を完遂できない場合は-1と出力せよ。
なお、出力の最後には改行をいれること。

入力例 1

6 6 8
1 2
1 3
2 4
3 5
4 6
5 6
0
1
1
2
3
4

出力例 1

5.0
  • 鎮守府のある 1 から、最終目的地である 6 までは、2 通りの経路があります。
    1. 1 -> 2 -> 4 -> 6
      • このルートが選択される確率は 50% です。
      • このルートで軍艦が受けるダメージは 0+1+2+4=7 です。
      • このルートで消費する時間は、サイクル 3 回の時間のみなので、3 です。
    2. 1 -> 3 -> 5 -> 6
      • このルートが選択される確率は 50% です。
      • このルートで軍艦が受けるダメージは 0+1+3+4=8 です。
      • 出港時の軍艦の体力は 8 なので、このルートでは沈没してしまいます。
      • 高橋艦長は、沈没を避けるため、海域 3 の戦闘終了時に海域離脱を選択します。
      • このルートで消費する時間は、サイクル 1 回の時間 + 体力の回復にかかる時間 = 1+1=2 です。
    1 -> 3 -> 5 -> 6 で 1 度撤退してから 1-> 2-> 4 -> 6
    • 50% の確率で 1 -> 3 -> 5 -> 6 が選択され、時間 2 を使って鎮守府に戻る。
    • その後、 50% の確率で 1 -> 2 -> 4 -> 6 が選択され、時間 3 を使って最終目的地に到達する。
    • つまり、25% の確率で時間 5 を使って最終目的地に到達。
    1 -> 3 -> 5 -> 6 で 2 度撤退してから 1-> 2-> 4 -> 6
    • 12.5% の確率で時間 7 を使って最終目的地に到達。
    1 -> 3 -> 5 -> 6 で 3 度撤退してから 1-> 2-> 4 -> 6
    • 6.25% の確率で時間 9 を使って最終目的地に到達。
  • 上記から、求める期待値は 3*0.5+5*0.25+7*0.125+...=5 となります。

入力例 2

3 2 5
1 2
1 3
0
5
1

出力例 2

-1
  • 鎮守府のある 1 から、2 通りの航路があります。
    1. 1 -> 2
      • このルートが選択される確率は 50% です。
      • このルートで軍艦が受けるダメージは 0+5=5 です。
      • 出港時の軍艦の体力は 5 なので、このルートでは沈没してしまいます。
    2. 1 -> 3
      • このルートが選択される確率は 50% です。
      • このルートで軍艦が受けるダメージは 0+1=1 です。
      • このルートで消費する時間は、サイクル 1 回の時間のみなので、1 です。
    • このように、1 -> 3の航路が選択されれば、最終目的地にたどり着くことが出来ますが、1 -> 2の航路が選択される可能性が残ってしまい、鎮守府から進軍することが出来ません。
    • そのため、-1を出力します。

入力例 3

3 2 6
1 2
1 3
0
5
1

出力例 3

7
  • 入力例 2 と同じマップですが、体力が入力例 2 と比べて1増えています。
  • このため、鎮守府から進軍して海域 2 に移動してしまったとしても、ダメージ 5を受けた後に海域離脱を行うことができます。
  • よって、高橋艦長は最終目的地に到達することが可能になります。

入力例 4

9 13 4
1 2
1 3
2 4
2 5
2 7
3 5
3 6
4 7
5 8
6 8
7 8
7 9
8 9
0
1
1
1
1
1
1
1
1

出力例 4

36.9999999999999
  • 1 -> 2 -> 7 -> 9の経路でのみ、最終目的地に到達することが可能となります。
  • それ以外の海域に入ってしまった場合、即撤退をすることが最善となります。
  • 期待値は 37ですが、出力に誤差が許容されているので、上記のような出力でも問題ありません。