H: プレゼント交換会
問題
無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。
複数ある場合は最小値を最大化せよ。
H: プレゼント交換会
無向グラフがある。全ての辺に向きをつけなさい。そのとき、すべての頂点の入次数の最大値と最小値の差が最小に成るようにし、その時の最大値・最小値を出力せよ。
複数ある場合は最小値を最大化せよ。
G: ワープ航法
平面上に2つのワープ場を設置したい。ワープ場にたどり着いた航空便は平面の任意の位置に瞬時に移動する事ができる。今、2次元平面上に n箇所の街がある。m本の航空便があり、航空便はある街a_iから他の街b_iへ、速さv_iで直線距離で最短のルートを選択し、移動するものである。
任意のワープポイントの置き方に対し、「各便について最短時間の2乗」の総和を最小化せよ。
E: 3D プリント
3次元空間に1辺長さsの立方体の設計図が n個ある。全ての立方体は3つの軸に平行で、頂点は整数座標。
ある2つの立方体が共通部分を持つとき連結しているといい、複数の立方体が次々に連結していれば大きな一つの立体になる。
n個の設計図からk個選んで立体を置いたとき、一つの立体に成るようにしなければならない。
このとき、その大きい立体の表面積の最小値を出力せよ。
入力のn個の立方体は次の条件を満たしている。
D: ダルマ落とし
長さnの数列aが与えられる。次の操作を好きなだけ繰り返す。
最大で幾つ取り除くことができるか。