CODE FESTIVAL 2018 qual B

A - Probability of Participation

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 100 点

問題文

E869120 君は, CODE FESTIVAL 予選に参加するか迷った. 迷いに迷った末, 彼は「魔法のサイコロ」で参加するかどうかを決めることにした.
魔法のサイコロは, 1 以上 100 以下の整数が等確率で出るように設計されている.
彼はサイコロを 1 回振り, 出た整数が N の倍数であればコンテストに参加しない. そうでない場合, 彼はコンテストに参加する.
彼がコンテストに参加する確率は何パーセントか？

制約

N は 1 以上 100 以下の整数

入力

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

出力

E869120 君が CODE FESTIVAL 予選に参加する確率は何パーセントか, 整数で出力しなさい.

入力例 1

出力例 1

サイコロの目が 3, 6, 9, 12, 15, 18, 21, ..., 96, 99 の場合コンテストに参加しない. そうでない場合参加する.
よって彼がコンテストに参加しない確率は 33 ％, 参加する確率は 67 ％である.

入力例 2

出力例 2

サイコロの目が 17, 34, 51, 68, 85 の場合コンテストに参加しない. そうでない場合参加する.
よって彼がコンテストに参加しない確率は 5 ％, 参加する確率は 95 ％である.

入力例 3

出力例 3

B - Tensai

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 200 点

問題文

CODE FESTIVAL 2015 本戦で, 「『天才』と書かれた大きな紙を持って立つ」という面白い行動をし, みんなを笑わせた人がいた.
そこで, CODE FESTIVAL 2018 本戦参加者の N 人全員が同じ行動をして, 集合写真を撮ることにした.

それぞれの人は「字の綺麗さ」「顔の面白さ」の 2 つの値を持ち, i 番目の人の「字の綺麗さ」は a_i, 「顔の面白さ」は b_i である. 「写真の好感度」は, 全ての人の (字の綺麗さ) × (顔の面白さ) の合計になる.

本戦の参加者たちは, 「写真の好感度」を最大化しようと思った. 「顔の面白さ」は変えることはできないが, ある人が 1 回トレーニングをすると, この人の「字の綺麗さ」は 1 上がる.
全ての人のトレーニング回数の合計を X 回以内にしなければならないとき, 写真の好感度の最大値を求めなさい.

制約

N は 1 以上 100 以下の整数
X は 0 以上 100 以下の整数
a_i, b_i \ (1 \leq i \leq N) は 1 以上 100 以下の整数

入力

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

N X
a_1 b_1
a_2 b_2
a_3 b_3
: :
a_N b_N

出力

写真の好感度の最大値を出力しなさい.

入力例 1

出力例 1

X=1 なので, トレーニングできる回数は 1 回までである. したがって, 次の 4 通りの方法が考えられる.

誰もトレーニングしない場合：写真の好感度は 12 \times 10 + 24 \times 20 + 36 \times 5 = 780
1 番目の人が 1 回トレーニングする場合：写真の好感度は 13 \times 10 + 24 \times 20 + 36 \times 5 = 790
2 番目の人が 1 回トレーニングする場合：写真の好感度は 12 \times 10 + 25 \times 20 + 36 \times 5 = 800
3 番目の人が 1 回トレーニングする場合：写真の好感度は 12 \times 10 + 24 \times 20 + 37 \times 5 = 785

よって, 写真の好感度の最大値は 800 である.

入力例 2

出力例 2

X=0 なので, 誰もトレーニングできない. したがって, 写真の好感度は 25 \times 20 + 17 \times 30 + 9 \times 50 = 1460 となる.

入力例 3

出力例 3

例えば, 1 番目の人が 2 回, 3 番目の人が 1 回トレーニングすると, 写真の好感度 385 が達成できる.
また, 写真の好感度を 385 より大きくすることはできない.

C - Special Cake for CODE FESTIVAL

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 500 点

問題文

AtCoder 社長の chokudai さんは, CODE FESTIVAL 2018 本戦で参加者に配る直方体のケーキを用意した.
このケーキは, 地面と垂直方向に, 縦に N 分割, 横に N 分割され, 合計 N^2 個のピースに分けられている.

chokudai さんの飼い犬のリチャードは, CODE FESTIVAL 2018 予選に参加したが, ギリギリ通過できなかった.
そこでリチャードは, 本戦で配られるケーキのいくつかのピースにスプレーをかけることで, すべてのピースを食べられなくしようと思った.
あるピースにスプレーがかけられると, このピースとこれに隣り合っているピースすべてが食べられなくなる.
ただし、隣り合っているとは、面で接していることを指すものとする.

リチャードが目標を達成できるようなスプレーのかけ方を 1 つ求めなさい. また, スプレーをかけるのに長く時間を使うと chokudai さんに見つかってしまうので, スプレーをかけるピースの個数を 201 \ 800 個以内にしなければならない.

制約

N は 1 以上 1 \ 000 以下の整数

入力

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

出力

1 行目から N 行目までに, それぞれ長さ N の文字列を出力しなさい. ただし, この N \times N の文字列はケーキを上から見た図 (各文字は 1 ピース) に対応しており, そのピースにスプレーをかける場合 X, かけない場合 . を出力する. X の個数は 201 \ 800 個以下でなければならない.

この問題の制約下で, 目標を達成するスプレーのかけ方が必ず存在することが示せる. そのようなスプレーのかけ方が複数存在する場合, そのうちのどれを出力してもよい.

入力例 1

出力例 1

X..
..X
X..

入力例 2

出力例 2

X.X..X
..X.X.
X..X..
.X...X
X..X..
.X..X.

入力例 3

出力例 3

XXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXX
X....X....X....X....X
X.XXXX.XX.XX.X.X.XXXX
X.XXXX.XX.XX.X.X....X
X.XXXX.XX.XX.X.X.XXXX
X....X....X....X....X
XXXXXXXXXXXXXXXXXXXXX
X....X....XX...X....X
X.XXXX.XXXX.XXXXXX.XX
X....X....XX..XXXX.XX
X.XXXX.XXXXXXX.XXX.XX
X.XXXX....X...XXXX.XX
XXXXXXXXXXXXXXXXXXXXX
XXX.XX.XX.X....X.XXXX
XXX.XX.XX.X.XX.X.XXXX
XXX.XX.XX.X....X.XXXX
XXX.XXX..XX.XX.X.XXXX
XXX.XXXX.XX.XX.X....X
XXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXX

D - Sushi Restaurant

Time Limit: 4 sec / Memory Limit: 1024 MB

配点: 700 点

問題文

CODE FESTIVAL 2018 本戦の参加者は N 人である. これから, 彼らは夕食で寿司を食べる.

それぞれの参加者は 空腹度 という整数の値を持つ. この値は, それぞれの参加者について独立に, 以下のように定まる.

確率 \frac{p_1}{q} で空腹度 x_1, 確率 \frac{p_2}{q} で空腹度 x_2, ... , 確率 \frac{p_M}{q} で空腹度 x_M.

あなたは寿司職人である. 厨房に N 枚の皿があり, あなたはそれぞれの皿に寿司を 1 個以上乗せる. 皿に乗せられる寿司の数に制限はなく, 皿ごとに異なる個数の寿司を乗せてもよい.

そして, これら N 枚の皿が参加者たちの座るテーブルに運ばれ, 彼らは皿をそれぞれ 1 枚取る.
空腹度 x の参加者が y 個の寿司の乗った皿を取ると, その参加者の 不満度 は |x - y| となる.
参加者たちは彼ら自身の空腹度を把握しており, 彼らは全員の不満度の合計が最小となるように皿を取る. このときの全員の不満度の合計を 不適合度 と呼ぶ.

あなたは, 不適合度の期待値が最小となるように皿に寿司を乗せたい. このように皿に寿司を乗せたときの不適合度の期待値を求めよ.

制約

N は 1 以上 2 \ 000 以下の整数
M は 1 以上 2 \ 000 以下の整数
1 \leq x_1 < x_2 < x_3 < ... < x_M \leq 1 \ 000 \ 000.
p_i \ (1 \leq i \leq M) は, 1 以上 1 \ 000 \ 000 以下の整数
q は 1 以上 1 \ 000 \ 000 以下の整数
p_1 + p_2 + p_3 + ... + p_M = q.

入力

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

N M q
x_1 p_1
x_2 p_2
x_3 p_3
 : :
x_M p_M

出力

不適合度の期待値の達成可能な最小値を出力しなさい.
ジャッジの解からの絶対誤差または相対誤差が \pm 0.0001 以内であれば正解とみなされる.

入力例 1

出力例 1

3.6000000000

この場合, 参加者は 1 人であり, 彼の空腹度は確率 30/100 = 0.3 で 1, 確率 20/100 = 0.2 で 3, 確率 50/100 = 0.5 で 9 となる.
1 枚の皿に 6 個の寿司を乗せることを考える. 唯一の参加者がこの皿を取り, 不適合度の期待値, すなわちこの参加者の不満度の期待値は |1-6| \times 0.3 + |3-6| \times 0.2 + |9-6| \times 0.5 = 3.6 となる.
これが達成可能な最小値である.

入力例 2

出力例 2

4.1600000000

この場合, 参加者は 2 人であり, 彼らを A, B と呼ぶことにする. 彼らの空腹度の確率分布はそれぞれ入力例 1 での参加者のそれと同じである. また, 2 枚の皿を皿 1, 皿 2 と呼ぶことにする.
皿 1 に 9 個, 皿 2 に 1 個の寿司を置くことを考える.
例えば, 確率 30/100 × 20/100 で A, B の空腹度がそれぞれ 1, 3 となる。このとき, A が皿 2, B が皿 1 を取ることで二人の不満度の合計が |1-1| + |3-9| = 6 となって最小化されるため, 不適合度は 6 である.
その他の場合についても同様に計算することで, 寿司をこのように置いたときの不適合度の期待値が 4.16 であることがわかる.
これが達成可能な最小値である.

入力例 3

3 2 2
111111 1
999999 1

出力例 3

666665.9999999997

1 枚目の皿に 111 \ 111 個, 2 枚目の皿に 999 \ 999 個, 3 枚目の皿に 555 \ 555 個の寿司を置くと, 不適合度の期待値は 666 \ 666 となり, これが達成可能な最小値である.

E - Game of +-

Time Limit: 2 sec / Memory Limit: 1024 MB

配点: 800 点

問題文

CODE FESTIVAL 本選で良い成績を取るために, いろはちゃんは 12 年前から毎日修行をしている.
今日は, 「足し引きゲーム」で修行を行うことにした. このゲームは以下のようなものである.

電光掲示板に数 G が書かれている. 最初, G = 0 である.
プレイヤーは以下の操作を 320 回以内行うことができる : 1 以上 N 以下の整数 x を選び, G に 1/x を足す, または G から 1/x を引く. ただし, G を負にしてはならない.
G を, このゲームにおいて G が取り得る値のうち 0 を除いて最小の値にすると, ゲームクリアである.

いろはちゃんは早くゲームクリアしたい. 彼女を助けるために, ゲームクリアする方法を一つ出力せよ.

制約

N は 1 以上 100 以下の整数

入力

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

出力

出力は, 以下のような形式で行うこと.

Q
op_1 x_1
op_2 x_2
op_3 x_3
...
op_Q x_Q

Q は, あなたが行う操作の回数である. Q の値は, 320 以下でなければならない.
op_i は, i 回目に行う操作の種類である. + のとき「1/{x_i} を足す」, - のとき「1/{x_i} を引く」という操作を行うことを意味する.

入力例 1

出力例 1

3
+ 2
+ 2
- 2

G が取り得る値のうち 0 以外で最小のものは, 1/2 である.
以下の出力において, G の値は以下のように変化する.

最初, G = 0 である.
次に, G に 1/2 を足す. G の値は 1/2 に変化する.
次に, G に 1/2 を足す. G の値は 1 に変化する.
最後に, G から 1/2 を引く. G の値は 1/2 に変化する.

入力例 2

出力例 2

3
+ 3
+ 3
- 2

G が取り得る値のうち 0 以外で最小のものは, 1/6 である.
以下の出力において, G の値は以下のように変化する.

最初, G = 0 である.
次に, G に 1/3 を足す. G の値は 1/3 に変化する.
次に, G に 1/3 を足す. G の値は 2/3 に変化する.
最後に, G から 1/2 を引く. G の値は 1/6 に変化する.

入力例 3

出力例 3

5
+ 3
+ 3
- 2
+ 4
- 3

G が取り得る値のうち 0 以外で最小のものは, 1/12 である.
以下の出力において, G の値は以下のように変化する.

最初, G = 0 である.
次に, G に 1/3 を足す. G の値は 1/3 に変化する.
次に, G に 1/3 を足す. G の値は 2/3 に変化する.
次に, G から 1/2 を引く. G の値は 1/6 に変化する.
次に, G に 1/4 を足す. G の値は 5/12 に変化する.
最後に, G から 1/3 を引く. G の値は 1/12 に変化する.

入力例 4

出力例 4

10
+ 1
- 3
- 7
- 7
+ 2
- 4
- 7
- 5
- 7
- 7