YUHA presents C83 新刊『競技プログラミング The Boss Rush!!!』

A - Revenge of Voronoi - ボロノイの逆襲

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

「離散ボロノイ図」はボロノイ図の亜種である。離散ボロノイ図では、図は画素の集合として表現される。各母点はいくつかの画素の中心に位置しており、各画素はマンハッタン距離で最も近い母点に所属している。ここでマンハッタン距離は2つの点 (x_{1}, y_{1}) と (x_{2}, y_{2}) に対して以下の式で与えられる距離である。

d = |x_{1} - x_{2}| + |y_{1} - y_{2}|

あなたの仕事は与えられた離散ボロノイ図に対し、各母点の座標を計算するプログラムを書くことである。与えられる離散ボロノイ図において、各母点は他の母点と重複しない英小文字で表される。また各画素は、その点が所属する母点の文字で表される。一つの画素が複数の母点から等距離にある場合は、その画素は等距離にある母点のうち、最も若い英小文字で表される母点に所属する。

入力

入力の1行目には二つの整数、 W (1 ≤ W ≤ 50) と H (1 ≤ H ≤ 50) からなり、それぞれ離散ボロノイ図の幅と高さを表す。続く H 行には、 W 文字の英小文字が含まれており、各文字が一つの画素を表す。

出力

サンプル出力に示されている通りに母点の座標を出力せよ。各行は母点を表す英小文字、X座標、Y座標からなる。母点はそれぞれを表す英小文字のアルファベット順で出力せよ。座標は (0,0) を左上の画素の中心とする。各テストケースにつき、少なくともひとつは解が存在すると仮定して良い。また、複数の解が存在する場合は、いずれを出力しても構わない。

部分点

1 ≤ W, H ≤ 8 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます
1 ≤ W, H ≤ 16 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます

入力例 1

4 3
ooxx
ooxx
ooxx

出力例 1

o 0 0
x 2 0

入力例 2

4 1
null

出力例 2

l 2 0
n 0 0
u 1 0

入力例 3

4 4
aabb
aabb
ccdd
ccdd

出力例 3

Source Name

ICPC OB/OG会

B - Sun and Moon - 秘密結社太陽と月の団

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

西暦20XX年、人類は未曾有の危機に瀕していた。皆既日蝕により太陽と月のパワーバランスが崩れ、終末が訪れたのである。終わりの迫った世界を救うため、秘密結社『太陽と月の団』は、日蝕の x 日後に『太陽と月の儀式』と呼ばれる太陽と月のパワーバランスを整える儀式を執り行うことにした。

太陽と月の儀式は『太陽の儀式』と『月の儀式』から構成される。儀式において各社員は初期状態としていくつかの供物といくらかの魔力を持っている。また、各社員は太陽の加護を授かった『太陽の使者』と、月の加護を授かった『月の使者』に分けられている。

儀式では初めに太陽の儀式を執り行う。太陽の儀式において、各社員は所持する供物を一つ生贄に捧げる。ここで供物を所持していない社員は以降の儀式から除外される。儀式の後、各社員の魔力は初めに彼らが持っていた供物の数だけ倍増する。 (i番目の社員が初期状態で生贄Oi個、魔力Piを持っていた場合、魔力がOi×Piに変化する。) 全ての社員はこの儀式を丁度一回ずつ行う。

続いて、月の儀式を執り行う。この儀式で各社員は、所持する供物全てを生贄に捧げる。儀式のあと、各社員の魔力は x^{p} 倍に増加する。ここで x は日蝕からの経過日数、 p は各社員がその時点(月の儀式が行われる直前)で所持している供物の数である。太陽の儀式で残った全ての社員は丁度一回ずつ儀式を行う。

これらの儀式の後、太陽の使者と月の使者は全ての魔力を『魔力リアクター』に注ぎ込む。このとき太陽の使者の魔力の総和と月の使者の魔力の総和が等しければ、儀式は成功し世界は救われる。

さて、太陽の儀式には大量の資金がいるのだが、秘密結社は不景気のため予算を捻出することができない可能性がある。あなたの仕事は太陽と月の儀式のうち、太陽の儀式を行った場合／行わなかった場合のどちらの場合においても儀式全体が成功するような、日蝕からの経過日数 x を求めるプログラムを書くことである。日蝕の起こった日(0日目)に儀式を行うことはできない。

入力

入力形式は以下の通りである。

N 
O_{1} P_{1} 
...
O_{N} P_{N}

初めの行は一つの整数 N (0 ≤ N ≤ 1,000) からなり、これは秘密結社の社員数を表す。続く N 行には二つの整数 O_{i} (0 ≤ O_{i} ≤ 10^{9}) と P_{i} (1 ≤ |P_{i}| ≤ 10^{15}) が与えられる。 O_{i} は i 番目の社員が持つ生贄の数を表し、 P_{i} は i 番目の社員が持つ魔力を表す。 P_{i} が正の数の場合は i 番目の社員は太陽の使者に属し、 P_{i} が負の数の場合は i 番目の社員は月の使者に属する。

出力

問題文の条件を満たすような日蝕からの経過日数がある場合は Yes と、その経過日数を出力せよ。それ以外の場合は No を出力せよ。当然のことながら、経過日数は正の数でなければならない。

部分点

1 ≤ |P_{i}| ≤ 10^{3} を満たす入力にのみ正解した場合、部分点として 175 点が与えられます
1 ≤ |P_{i}| ≤ 10^{9} を満たす入力にのみ正解した場合、部分点として 25 点が与えられます

入力例 1

出力例 1

Yes 2

入力例 2

2
1 1
0 -1

出力例 2

No

Source Name

ICPC OB/OG会

C - Dendrogram - 樹形図

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

Nathan. O. Davisは情報工学科に所属する学生である。彼は学科の『人工知能概論』という授業の期末課題のため、階層的クラスタリングのプログラムを書いている。

クラスタリングとは、オブジェクトの集合をクラスタと呼ばれる複数の部分集合に分ける処理である。ここで同一のクラスタに所属するオブジェクトは何らかの基準により似ていると判定されたものとなるようにする。階層的クラスタリングはこれを間接的に行う手法の一つで、オブジェクトの集合を樹形図と呼ばれる木構造で扱う。ただし、本問題では木の集合も樹形図として扱う。樹形図はオブジェクト間の類似度を表現する。以下に樹形図の例を示す。

図：綺麗な樹形図

上記の図において、末端の葉は各オブジェクトを表す。水平の線分はオブジェクトの集合の2つ以上のサブグループへの分割を表す。別のサブグループに所属するオブジェクトは類似度が低く、同一のサブグループに所属するオブジェクトは類似度が高いことを表す。これは水平線が上に位置するほど、その水平線に所属するオブジェクトやオブジェクトの集合の類似度が低いことを表している。例として、上の図の上から2本目の水平線によって、オブジェクトの集合が3つのクラスタに分けられていることが分かる。

Nathanの書いたプログラムは系統樹を出力すること自体はできるのだが、 2つのバグが含まれていた。一点目は系統樹が連結になっていない点、つまり出力された系統樹が複数の木構造からなる点である。これについては本問題では扱わないことにする。二点目は出力された系統樹の見た目が非常に汚いことである。具体的には(図:汚い樹形図)のように線分同士が交差してしまっており、

図：汚い樹形図

読み取りづらくなってしまっているのである。あなたの仕事は入力としてNathanの出力した系統樹を受け取り、綺麗な系統樹を出力するプログラムを書くことである。ここで綺麗な系統樹とは垂直の線分と水平の線分が接点以外で接触せず、かつ末端の葉の番号の並びが辞書順で最も若いものとする。

詳細な仕様については入力と出力の欄を参考にせよ。

入力

入力形式は以下の通りである。

N M Q
SplitInfo_{1}
SplitInfo_{2}
...
SplitInfo_{M}
Query_{1}
Query_{2}
...
Query_{Q}

初めの行は3つの整数 N ( 1 ≤ N ≤ 100,000 )、 M ( 0 ≤ M < N )、 Q ( 1 ≤ Q ≤ 1,000 , Q ≤ N )からなる。 N はオブジェクトの数、 M は水平な線分の数、 Q はクエリの数を表す。

続く M 行には水平な線分の情報が与えられる。各行の形式は以下の通りである。

Y L V_1 V_2 ... V_L

Y ( 0 ≤ Y ≤ 10^9 )は各水平線の上下の位置を表し、座標が小さいほど上に位置する(類似度が低い)ことを表す。入力中のYは互いに異なる値であることが保証されている。 L (2 ≤ L) は水平線に接続する垂直な線分(オブジェクトまたはオブジェクトの集合)の数を表す。 V_i ( 1 ≤ i ≤ L )はそれぞれ垂直な線分を表す。各オブジェクトは他と重複しない1から N までの整数で表される。またオブジェクト集合は、その集合に所属するいずれかのオブジェクトを表す整数で表される。互いに異なるi, jについて、V_{i} = V_{j}となるようなSplitInfoは存在しない。

続く Q 行には各行にクエリを表す一つの整数 I_{i} が与えられる。

出力

入力の各クエリ I_{i} について、綺麗な系統樹の左から I_{i} 番目の葉のオブジェクトを表す整数を出力せよ。ここで I_{i} は1から始まるものとする。

部分点

1 ≤ N ≤ 8 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます

入力例 1

出力例 1

1
2
3

入力例 2

出力例 2

入力例3

出力例 3

入力例 4

出力例 4

入力例 5

出力例 5

入力例 6

出力例 6

入力例 7

出力例 7

1
2
3

入力例 8

1 0 1
1

出力例 8

本問題は入力データサイズが大きいため、C++のcinやJavaのScannerの使用は速度面で推奨しない。scanf()やStringTokenizerの使用を推奨する。

Source Name

ICPC OB/OG会

D - Psychic Accelerator - とある超能力の物体加速器

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

東京の西に『学園都市』と呼ばれる都市がある。そこには超能力者を育成するための学校や研究所が多数存在している。

あなたは学園都市のとある学校に通う超能力者である。あなたの超能力は物体に対して加速度を与えるというものである。

あなたはいつでもどこでも超能力を行使することができる。しかし、超能力の行使にはいくつかの条件がある。まず、物体が静止している場合は、任意の方向に加速度を与えることができる。一方、物体が動いている場合は、1) 物体の移動方向 2) その逆方向 3) 移動方向に対して垂直な方向のいずれかにのみ加速度を与えることができる。

今日の訓練メニューは与えられたコースに沿って物体を動かすというものである。簡単のため、コースは2次元平面上の線分と円弧からなるものとする。コースに分岐はなく、すべての線分と円弧はなめらかに繋がっているものとする (鋭いコーナーはないものとする)。コースは1本目の線分の始点で始まり、最後の線分の終点で終わっている。

初期状態において、物体はコースの始点に置かれている。あなたは物体に加速度を与え、コースに沿って物体を動かし、コースの終点まで運び、その位置で停止させなければならない。

実際の訓練に入る前に、教官が物体を始点から終点に動かすまでの最短時間をシミュレートションにより計算するように指示をしてきた。あなたの仕事は、入力としてコースの形状と物体に与えられることができる最大加速度 A_{max} が与えられたとき、物体を始点から終点まで動かすために必要な最短時間を求めるプログラムを書くことである。

物体は以下の基本的な物理公式に従う。

物体がある方向に動いていており、前方または後方に加速度が働いている場合、以下の公式が成り立つ。

v = v_{0} + at
s = v_{0}t + \frac{1}{2}at^{2}

ここで、 v 、 s 、 v_{0} 、 a 、 t はそれぞれ、速度、始点からの距離、初期速度(始点での速度)、加速度および物体の移動時間を表す。また、これらの式から以下の式が導かれる。

v^{2} - v_{0}^{2} = 2as

物体が円弧上にあり、円弧の中心方向に加速度が与えられている場合、以下の公式が成り立つ。

a = \frac{v^{2}}{r}

ここで、 v 、 a 、 r はそれぞれ、速度、加速度および円弧の半径を表す。超能力の行使条件により、円弧上では物体の速さを変化させることができない点に注意せよ。

入力

入力形式は以下の通りである。

N A_{max}
x_{a,1} y_{a,1} x_{b,1} y_{b,1}
x_{a,2} y_{a,2} x_{b,2} y_{b,2} 
...
x_{a,N} y_{a,N} x_{b,N} y_{b,N}

入力の1行目は二つの正の整数、 N (0 < N ≤ 40,000) 、 A_{max} (1 ≤ A_{max} ≤ 100) からなり、 N は線分の本数、 A_{max} は物体に対して与えることのできる加速度の最大値を表す。続く N 行には線分の情報が与えられる。各行は整数 x_{a,i} 、 y_{a,i} 、 x_{b,i} 、 y_{b,i} (-100 ≤ x_{a,i}, y_{a,i}, x_{b,i}, y_{b,i} ≤ 100) からなり、 (x_{a,i}, y_{a,i}) が i 番目の線分の始点、 (x_{b,i}, y_{b,i}) が i 番目の線分の終点を表す。 i 番目の線分の終点が i+1 番目の始点に、円弧によって滑らかにつながることが保証されている。与えられたコースは自己交差する場合があるが、それらの地点で向きを変えてはならない。

出力

物体を始点から終点まで動かすために必要な最短時間を出力せよ。出力には 10^{-6} 以上の絶対または相対誤差を含んではならない。

部分点

N = 1 を満たす入力にのみ正解した場合、部分点として 50 点が与えられます
1 ≤ N ≤ 2 を満たす入力にのみ正解した場合、部分点として 75 点が与えられます

入力例 1

2 1
0 0 1 0
1 1 0 1

出力例 1

5.2793638507

入力例21

1 1
0 0 2 0

出力例 2

2.8284271082

入力例 3

出力例 3

11.1364603512

Source Name

ICPC OB/OG会

E - Camera Control - カメラ・コントロール

Time Limit: 2 sec / Memory Limit: 128 MB

問題文

『ACM48』は日本で話題のダンスボーカルグループである。この冬、ACM48はワールドツアーを行うことになり、あなたはそのツアーにカメラエンジニアとして参加することになった。

あなたの役割はステージ上に設置されたカメラの制御プログラムを書くというものである。簡単のためステージは2次元座標上にあるものとする。カメラは360度自由な向きに回転させることができるが、位置を移動させることはできない。

ステージパフォーマンスの間、ACM48の各メンバーは予め決められた通りに移動し、割り当てられたパートを歌っていく。ここで、メンバーが移動するルートは折れ線により与えられるものとする。

あなたの制御するカメラはステージパフォーマンスの間、一人のメンバーのみに焦点を合わせることができる。また、カメラから向かって複数のメンバーが同じ方向に位置している場合に限り、カメラの焦点を合わせるメンバーをそれらのメンバーの中で自由に切り替えることができる。 (カメラから伸ばした半直線上に複数のメンバーがいる場合、カメラから見て奥のメンバーに焦点を合わせておくことができる。) たとえ歌い終わった歌手に焦点を合わせていた場合でも、カメラからそのメンバーに引いた半直線上に別のメンバーがいない限り、カメラの焦点を他のメンバーに写すことはできない。

あなたの仕事はステージパフォーマンスの段取りが与えられたとき、歌を歌っているメンバーに焦点を合わせることができる最大の時間を求めるプログラムを書くことである。

問題を解くに当たり以下の条件を満たしていると仮定して良い。

ステージパフォーマンスの開始時点ではカメラの焦点を任意のメンバーに合わせることができる
各メンバーの移動ルートはカメラに触れない
各メンバーは移動ルートの終点に到達したあと、その位置に留まる

入力

入力形式は以下の通りである。

N
c_{x} c_{y}
MEMBER\_INFORMATION\_1
MEMBER\_INFORMATION\_2
...
MEMBER\_INFORMATION\_N

N ( 1 ≤ N ≤ 50 ) はメンバーの数を表し、 (c_{x}, c_{y}) はカメラの座標を表す。続いて N 人のメンバーの情報が与えられる。

i 番目のメンバーの情報は以下の形式である。

M_{i}
x_{i,1} y_{i,1} t_{i,1}
...
x_{i,M_{i}} y_{i,M{i}} t_{i,M_{i}}
L_{i}
b_{i,1} e_{i,1}
...
b_{i,L_{i}} e_{i,L_{i}}

M_{i} (1 ≤ M_{i} ≤ 100) はルート上の頂点の数、 (x_{i,j}, y_{i,j}) は j 番目の頂点の座標、 t_{i,j} (0 = t_{i,0} < t_{i,j} < t_{i,j+1} ≤ 10^{3}) は i 番目のメンバーが j 番目の頂点に到達する時刻、 L_{i} (0 ≤ L_{i} ≤ 100) は i 番目のメンバーが歌うボーカルパートの数、 b_{i,k} 及び e_{i,k} (0 ≤ b_{i,k} < e_{i,k} < b_{i,k+1} < e_{i,k+1} ≤ 10^{3}) は k 番目のボーカルパートの開始時刻と終了時刻を表す。

入力中のすべての値は整数である。また入力中の全ての座標の絶対値は 10^{3} 以下である。

出力

歌を歌っているメンバーに焦点を合わせることができる最大の時間を出力せよ。出力には 10^{-6} 以上の絶対または相対誤差を含んではならない。

部分点

M_{i} = 1 を満たす入力にのみ正解した場合、部分点として 125 点が与えられます

入力例 1

出力例 1

1.00000000000000000000

入力例2

出力例 2

2.00000000000000000000

入力例 3

出力例 3

1.00000000000000000000

入力例 4

出力例 4

9.00000000

入力例 5

出力例 5

2.00000000

入力例 6

出力例 6

5.98862017