問題 n個のドアがある。 i番目のドアを開けるのに、赤の鍵がdoorR[i]個、緑の鍵がdoorG[i]個必要である。 i番目のドアを開けると、（最初の一回だけ） 赤の鍵がroomR[i]個、緑の鍵がroomG[i]個、白の鍵がroomW[i]個得られる。 一度使った鍵は壊れるのですぐ…

問題 n個の歌があり、それぞれの歌の長さはduration[i], トーンがtone[i]である。 Tの時間のうちに異なる歌をできるだけ多く歌いたい。 トーンがaである歌の直後にトーンがbの歌を歌おうとすると、|a - b|の時間の休憩が必要である。 最大でいくつの歌を歌え…

問題 n個の数列a[i]を互いに素な二つのグループにわける。片方が空であってもよい。 f(i, j)を、i, jが違うグループのときa[i] + a[j] + h, 同じグループのときa[i] + a[j]とする。max{f(i, j) | 1≦i＜j≦n} - min{f(i, j) | 1≦i＜j≦n}が最小となるようなわけ…

問題 hxwの行列がある。 この行列のうち、(a, b)を左上(c, d)を右下とするような長方形を選ぶ。 角の4つの数字の最小値の最大値を求めよ。 制約条件 h, w≦1000 数字≦10^9

問題 n人の人がいて、それぞれの人の大きさはa[i]である。 n人はn!通りの並び方を等しい確率で選んで並ぶ。 大きさの和がp以下であるような部分だけ、列の先頭から人がレストランに入れる。 入る人が、入れない人を飛ばすことはできない。 レストランに入れ…

問題 無向木が与えられる。 この木上を、m個の出発点とゴールの組(ui, vi)について、 uiから一人が出発し、viへゴールする。 それぞれの辺について、合計何人が通るか求めよ。 制約条件 n≦10^5 m≦10^5