Donutsプロコンチャレンジ2015

A - ドーナツの体積

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

問題設定に不備がありました．また，R>Dであるようなテストケースが存在していました．R＜Dという制約を問題に付け加え，テストケースの修正作業を行います．作業が完了次第リジャッジを行います．(19:14)

リジャッジが完了しました．(19:21)

ドーナツの体積を計算してみましょう。

平面図形をある直線を軸に回転させてできる立体の体積は、

「平面図形の面積」\times 「平面図形の重心が描く円の周長」

という式で求めることができます。

半径 R の円を、円の中心からの距離が D である直線を軸に回転させてできるドーナツ型の立体の体積を計算してください。

入力

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

R D

1 行目には、2 つの整数 R (1 ≦ R ≦ 100), D (R ＜ D ≦ 100) が空白区切りで与えられる。これは、問題文中の通りの変数である。

出力

半径が R の円を、円の中心からの距離が D である直線を軸に回転させてできる立体の体積を 1 行に出力せよ。小数点以下何桁でも出力してよいが、10^{−2} を超える絶対誤差を含んではならない。出力の末尾に改行を入れること。

入力例1

3 5

出力例1

888.264396

半径が 3 の円を、円の中心からの距離が 5 である直線を軸に回転させてできる立体の体積を出力すれば良いです。

「平面図形の面積」は 3^2 \times π で、「平面図形の重心が描く円の周長」は 5 \times 2 \times π なので、体積は 90 \times π^2 となります。

円の重心は中心であることに注意してください。

入力例2

46 96

出力例2

4009743.9192393753

以前のサンプル2の入力は制約を満たしていなかったため，変更されました．

B - Tokyo 7th シスターズ

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

Tokyo 7th シスターズは、iPhoneやAndroidでプレイ可能な、アイドル育成カード＆リズムアドベンチャーゲームです。あなたは、このゲームのいくつかの仕様を簡略化したものについて考えています。

いくつかの仕様が簡略化されたこのゲームでは、複数人のアイドルの中から異なる 9 人を選び、ユニットを 1 つ組むことで、リズムゲームをしたり、ステージバトルを行うことが可能です。この際、ゲームで使われるユニットの基礎能力値は、選んだアイドルの能力値の和で決まります。

また、このゲームにはコンボというシステムがあり、コンボの条件を満たすことでコンボボーナスを得られます。組んだユニットにコンボで指定されている条件を満たすメンバーが 3 人以上いれば、そのコンボのボーナスを得ることが出来ます。各コンボについて、どのアイドルが指定されている条件を満たすかあらかじめ分かっています。

ユニットの最終的な能力値は、ユニットの基礎能力値に得られた全てのコンボボーナスの和を足したものです。

あなたは、アイドルを組み合わせて、ユニットの最終的な能力値を出来るだけ大きくしたいと思っています。最終的な能力値の最大値を求めてください。

なお、本問題に出てくるユニットの組み方やコンボは簡略化された仕様であり、Tokyo 7th シスターズの仕様とは少し異なることに注意してください。

入力

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

N M
A_1 A_2 ．．． A_N
B_1 C_1 I_{1,1} I_{1,2} ．．． I_{1,C_1}
B_2 C_2 I_{2,1} I_{2,2} ．．． I_{2,C_2}
:
B_M C_M I_{M,1} I_{M,2} ．．． I_{M,C_M}

1 行目には、あなたが選択可能なアイドルの数 N (9≦N≦16) と、選択可能なアイドルのみを使って発生させることが可能なコンボの数 M (0≦M≦50) が空白区切りで与えられる。
2 行目には、N 個の整数が空白区切りで与えられる。そのうち i 番目の整数は、i 番目のアイドルの基礎能力値 A_i(1≦A_i≦10,000) を表す。
3 行目から M 行には、それぞれのコンボの情報が与えられる。このうち i (1≦i≦M) 行目には i 番目のコンボの情報が空白区切りで与えられる。コンボの情報は、複数の整数からなり、1 つ目の整数は、i 番目のコンボのコンボボーナスを表す整数 B_i(1≦B_i≦10,000) である。2 つ目の整数は、そのコンボの条件を満たすアイドルが何人いるかを表す整数 C_i(3≦C_i≦N) である。続く 3 つ目以降の整数のうち j (1≦j≦C_i) 番目の整数は、条件を満たすアイドルが何番目にいるかを表す整数 I_{i,j}(1≦I_{i,j}≦N) である。この時、j≠k であれば、I_{i,j} ≠ I_{i,k} を満たす。

出力

ユニットの最終的な能力値の最大値を 1 行に出力せよ。

出力の末尾に改行を入れること。

入力例1

10 1
100 200 300 400 500 600 700 800 900 1000
1000 3 1 2 3

出力例1

1 番目から 3 番目、5 番目から 10 番目までの 9 人のアイドルを選んでユニットを組むと、基礎能力値が 5100、コンボボーナスが 1000 となり、最終的な能力値は 6100 になります。

入力例2

12 10
1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000
1000 4 1 2 4 7
1000 4 1 9 11 12
1000 4 3 5 8 9
1000 4 6 10 11 12
1000 4 2 4 7 10
1000 4 1 8 9 10
1000 3 1 9 12
1000 4 3 8 11 12
1000 4 1 2 3 4
1000 4 7 8 9 10

出力例2

基礎能力値は必ず 9000 となります。一例として、 1, 2, 4, 5, 8, 9, 10, 11, 12 番目のアイドルを選んでユニットを組むことで、全てのコンボボーナスを得ることが出来ます。

入力例3

13 8
328 781 104 102 132 108 100 102 104 108 168 102 100
184 4 10 11 3 4
190 4 9 6 2 5
282 6 9 1 3 12 10 8
205 8 13 10 1 12 7 2 8 11
122 8 13 5 4 3 8 9 12 10
112 7 11 6 12 8 2 13 5
102 4 4 13 6 12
109 6 7 2 13 1 8 6

出力例3

C - 行列のできるドーナツ屋

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ドーナツ町には、毎日行列ができる超人気のドーナツ屋があります。このドーナツ屋には今 N 人の人がまっすぐ一列に並んでいます。行列に並んでいる人は、自分の番が来る前にドーナツが売り切れてしまうのではないかと不安に思っています。ドーナツ屋の店長は、それぞれの人がどれくらい不安に思っているのかを表す「不安度」を計算してみることにしました。

前から i 番目 (1 ≦ i ≦ N) に並んでいる人を人 i と呼ぶことにします。人 i の身長は H_i です。人 i の「不安度」は「人 i が前を見たときに見える人の数」です。人 i が前を見たときに人 j が見えるための条件は以下の通りです。

人 i よりも人 j の方が前に並んでいる。すなわち、j < i である。
人 i と人 j の間に人 j より身長の高い人がいない。すなわち、j < k < i かつ H_j < H_k を満たすような k が存在しない。

例えば、行列に並んでいる人の身長が前から順に 2,5,3,4,1 なら、一番後ろに並んでいる人 5 が前を見たときに見える人は人 2 と人 4 の 2 人なので、人 5 の「不安度」は 2 となります。

入力

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

N
H_1 H_2 ... H_N

1 行目には、行列に並んでいる人数を表す整数 N (1 ≦ N ≦ 10^5) が与えられる。
2 行目には、行列に並んでいる人の身長を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 H_i (1 ≦ H_i ≦ 10^6) は、人 i の身長を表す。ただし、p \neq q のとき H_p \neq H_q であることが保証される。

部分点

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

N ≦ 100 を満たすテストケースすべてに正解した場合は 10 点が与えられる。
N ≦ 5000 を満たすテストケースすべてに正解した場合は 40 点が与えられる。

出力

出力は N 行からなる。このうち i 行目には、人 i の「不安度」を表す 1 つの整数を出力せよ。出力の末尾にも改行を入れること。

入力例1

5
2 5 3 4 1

出力例1

入力例2

1
1000000

出力例2

入力例3

8
66 52 56 32 27 50 72 23

出力例3

D - ドーナツの箱詰め

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

ドーナツ屋の店員の須藤なつきさんはドーナツの箱詰めの担当です。なつきさんは今、K 個のドーナツを N 個の箱に箱詰めしようとしています。箱 i (1 ≦ i ≦ N) の体積は C_i で、どの箱もドーナツを 1 つ入れることができます。

なつきさんは全ての箱を使いたいと思っています。しかし、ドーナツの個数よりも箱の個数の方が多いため、箱の中に箱を入れ子にすることによって箱を使い切ることにしました。各箱の中には、ドーナツまたは箱のいずれか一方を必ずちょうど 1 個入れることにしました。箱 i には箱 i よりも体積が小さい箱を入れることができます。また、中に入れる箱の中にさらに箱やドーナツが入っていた場合でもその箱は 1 個として数えます。箱 i の中に箱 j を入れた場合には、箱 i と箱 j の間に C_{i} - C_{j} の量の緩衝材を入れなければなりません。このとき、必要な緩衝材の量の和の最小値を求めてください。

また、なつきさんはとても不器用なので箱詰めの途中で箱を潰してしまうことがあります。なつきさんが箱を潰すごとに、その時点で残っている箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を求めてください。なつきさんは合計 Q 個の箱を潰し、i 個目に潰した箱は箱 D_i です。

入力

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

N K
C_1 C_2 ... C_N
Q
D_1
D_2
:
D_Q

1 行目には、2 つの整数 N (1 ≦ N ≦ 200,000), K (1 ≦ K ≦ N) が空白区切りで与えられる。これは、はじめに箱が N 個とドーナツが K 個あるということを表す。
2 行目には、箱の体積を表す N 個の整数が空白区切りで与えられる。このうち i 番目の整数 C_i (1 ≦ C_i ≦ 200,000) は、箱 i の体積を表す。ただし、p \neq q のとき C_p \neq C_q であることが保証される。
3 行目には、なつきさんが潰した箱の個数を表す整数 Q (0 ≦ Q ≦ N-K) が与えられる。
4 行目からの Q 行には、なつきさんが潰した箱の情報が与えられる。このうち i 行目には、整数 D_i (1 ≦ D_i ≦ N) が与えられる。これは、なつきさんが i 個目に潰した箱が箱 D_i であることを表す。ただし、p \neq q のとき D_p \neq D_q であることが保証される。

部分点

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

Q = 0 かつ K = 2 を満たすデータセット 1 に正解した場合は、15 点が与えられる。
Q = 0 を満たすデータセット 2 に正解した場合は、上記とは別に 25 点が与えられる。
K = 2 を満たすデータセット 3 に正解した場合は、上記とは別に 30 点が与えられる。

出力

出力は Q+1 行からなる。1 行目には、N 個の箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を出力し、2 行目から Q+1 行目までのうち i (1 ≦ i ≦ Q) 行目には、i 個目までの箱を潰した時点で残っている箱を全て使って箱詰めをするときに必要な緩衝材の量の和の最小値を出力せよ。出力の末尾にも改行を入れること。

入力例1

5 4
1 9 3 7 4
0

出力例1

このケースでは図のような箱詰めの仕方をすると必要な緩衝材の量が 1 となり最小となります。青い部分は緩衝材を入れる部分を表しています。

また、このケースではなつきさんは箱を 1 個も潰しません。

入力例2

出力例2

4
1
0

このケースでは図のような箱詰めの仕方をすると良いです。青い部分は緩衝材を入れる部分を表しています。

入力例3

7 3
2 12 3 13 7 17 1
4
4
3
1
6

出力例3