二分探索
問題 長方形の板がN枚並んで出来ているフェンスがある。 i番目の板は幅1, 高さがh[i]の長方形で、下側の辺は地面にぴったりとくっついている。 このフェンスに看板を貼る候補がQ通りある。 各候補は、l, r, wで表され、l枚目からr枚目の板の内部に幅wの長方…
問題 座標平面の原点が恒星。その周囲を円軌道で惑星が反時計回りに速度vpで周っていて、 惑星はt = 0のとき(xp, yp)にいる。 宇宙船が(x, y)にいて、宇宙船は好きな方向に速度vで動くことができる。 太陽から距離r以内に入ると熱くて死ぬ。宇宙船は最短で何…
問題 n個の点(si, fi, ti)が与えられるので次のQ個のクエリに答えよ。 クエリ:点(x, y, z)に対して、最初のn個の点の中から、s≦x, f≧y, t≧zを満たす点のうち、tがもっとも小さいものの番号を答える。 ただし、最初のn点のtiは全て異なる。 制約条件 n, Q≦10…
問題 ハンバーガー一個を作るにはSがrs個, Bがrb個, Cがrc個必要である。 最初Sをns個、Bをnb個、Cをnc個持っている。 足りない材料はSを一個ps円、Bを一個pb円、Cを一個pc円で買えるが、 予算はr円。 最大でハンバーガーはいくつ作れるか求めよ。 制約条件 …
問題 座標平面上にn個の滑車と2本の釘がある。 i番目の滑車は((i+1) * d, 0)の位置にあり、釘は(0, 0)および((n + 1) * d, 0)にある。 滑車の半径はrで、どの二つの滑車も接触しないことが保証されている。 原点の釘からもう一方の釘へ、ロープをたるまない…
問題 日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_07) 夏休みがM日あって、N人の掃除当番を使って、 「連続して掃除がされない日数の最大値」をなるべく小さくしたい。 i番目の人はa[i]日目〜b[i]日目のうち一日だけ掃除がで…
問題 日本語なので本文参照(http://utpc2013.contest.atcoder.jp/tasks/utpc2013_02) うなぎ暦はy年には13 + (y - 2013)月まである。(2013年は13月、2014年は14月…) 西暦のy年m月が与えられたとき、うなぎ暦のy'年m'月に変換せよ。 制約条件 y≦10^17 m≦12…
問題 nxnのグリッドがあり、(x, y)の点がt = 0において色がついている。 1秒ごとに、色のついているマスと辺を共有している色のついてないマスに色がつく。 全体でc個以上のマスに色がつくのにかかる時間を求めよ。 制約条件 n≦10^9
問題 n x nの行列がある。 それぞれの成分はスイッチで、ONかOFFの状態をとる。 1秒ごとに、ONに隣接するOFFのスイッチはONになる。 最初、(x, y)のスイッチだけがONのとき、オンになっているスイッチがc個以上になるには何秒かかるか、求めよ。 制約条件 n≦…
問題 長さLの丸太がある。 整数A,Kが与えられて、 この丸太を、 ( (A * i) mod (L - 1) ) + 1 (1≦i≦K)の位置で切ることができる。 丸太を最大でC回まで切ることができ、 丸太の最長の部分の長さを最小にするように切りたい。 最長の部分の長さの最小値およ…
問題 n人の人がいて、それぞれの人の背の高さはheights[i]である。 このn人が円上に並ぶ。 隣り合う人同士の背の高さの差の絶対値の最大値を最小にしたい。 そのような並び順を出力せよ。 複数あるときは、辞書順で最も最初に来るものを出力せよ。 制約条件 …
問題 燃料が空の時の質量がempty mass,離陸時に燃料を積んだ状態での質量がtake-off massであるような飛行機はKを定数として、 R = K * ln(take-off mass / empty mass) の距離だけ飛行できる。 distanceの距離を飛行機が飛ぶには最低でどれだけの燃料が必要…
問題 n種類のカードがそれぞれcards[i]枚と、jokers枚のジョーカーがある。 これらを使って、 それぞれのカードが一種類一枚ずつ、あるいは、 それぞれのカードがどれか一種類以外一枚ずつと、ジョーカー一枚のデッキをできるだけ多く作りたい。 デッキは最…
問題 ドミノが一列に並んでいて、それぞれのx座標x[i]および高さh[i]が与えられる。 x座標xにあるドミノを倒すと、x座標x+1以上x+h-1以下のドミノが全て倒れる。 ドミノ倒しは連鎖する。 i番目のドミノを倒したときに倒れるドミノの数をそれぞれ求めよ。 制…
これは本番中気づくべきだった…… 問題概要 数直線上のp[i]の位置にv[i]人のホットドッグ売りがいる。 彼らはどの二人も最低距離D[m]だけ離れていないといけないので、移動しなければならない。 移動速度は一律1m/sである。 全員が最低D[m]離れるまでにかかる…
問題概要 日本語なので本文参照 (http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=0539)
問題概要 K台の搾乳機およびC頭の牛がいる。搾乳機はM頭の牛から乳を搾れる。 各牛と搾乳機の距離が与えられる。各搾乳機にM頭以下の牛が割り当てられた状態になるよう牛が移動するとき、 最も移動距離の長い牛の移動距離の最小値を求めよ。 K≦30,M≦15,C≦300…
問題概要 mページの本をk人の写本屋が写本する。 各ページにはそれぞれコピーにかかる時間が設定されている。 k人の写本屋を使うために、本を連続する区間k個に分割する。 写本にかかる全体の時間は、それぞれの区間のコピーにかかる時間の最大値である。 写…
問題概要 m枚の扉を順に、なるべく多くの枚数を開けたい。 扉には二つの錠があり、どちらかの錠を開ければ扉は開く。 錠は2*n種類あり、全ての錠にはただ一つの異なる錠が対応している。 錠の鍵を一度使用すると、対応する錠の鍵は消滅して使用不可能になる…