srupのメモ帳

競プロで解いた問題や勉強したことを記録していくメモ帳

二分探索

ABC 034 D - 食塩水

問題 問題概要 n個の中から、k個を選んで濃度を最大にするときの最大値。 解法 単純に貪欲ではできない。蟻本p132の平均の最大化で紹介されているように、濃度を決めた上で、式変形をしてから、それを元に貪欲に選んでいけばその濃度を達成できるかを確かめ…

ARC 033 C - データ構造

問題 問題概要 タイプ 1 : S に数 X を追加する。 タイプ 2 : S に含まれる数のうち X 番目に小さい数を答え、その数を S から削除する。 この2つを高速に行うことができるデータ構造を使えばよい。 解法 今回の問題は、Xがあまり大きくない。よって、バ…

ARC 037 C - 億マス計算

問題 問題概要 100マス計算のようなマスが与えられる。その中で積の値が、小さいほうから数えて、K番目に位置する値を求めよ。 解法 editorialがわかりやすい。 AtCoder Regular Contest 037 解説 from AtCoder Inc. www.slideshare.net 答えをmidとすると、…

SRM 699 div2 medium LastDigit

問題 問題概要 564が与えられた場合は答えは、509となる。これは、564=509+50+5となるからである。このように、下1桁を消していって、その合計が、与えられた数と同じになる数字があるかを調べる。同じものがなければ、-1を返す。 解法 二分探索でやった。…

ABC 026 D - 高橋君ボール1号

問題 問題概要 省略 解法 2分探索でとく。関数はだいたい増加しているような関数であるので、解をもつ範囲の左端をL、右端をR、真ん中をM とすると、t=Mの時に、関数の値が100を超えるなら、中間地の定理より(あたりまえ)、左側の部分に解を必ず一つはもつ…

abc 020 C - 壁抜け

問題 問題概要 省略 解法 2分探索and最短経路問題。 xを小さくしていけば、かならず、ゴールにたどり着け、無限に大きくしていけば、どこかで、たどり着けなくなる。このような場合、求めるxを2分探索で効率よく絞り込んでいける。あとは、そのxに対して、ダ…

yukicoder No.67 よくある棒を切る問題 (1)

問題 問題概要 条件を満たす最大の値を求める問題。 解法 求める棒の長さは条件を満たす最大の値であり、その値より棒の長さを短くしても条件を満たすが、それより大きくすると条件を満たさなくなる。よって、このような場合は、二分探索をして効率よく求め…

aoj 2301 - Sleeping Time

問題 問題概要 LとRをK回2分探索をして、最終的な答えが、T-E < h' < T + Eに入る確率を求める問題。確率Pで誤った2分探索をして、確率(1-P)で適切な2分探索をする。 解法 全探索で、やろうと思うと、2k(k=30)でTLE?? ただし、2分探索をしていく途中で、 (T …

yukicoder No.168 ものさし

問題 問題概要 頂点1からnまで達するために、必要な辺の長さの最小値。ただし、最小値は10の倍数 解法 大まかな方針として、必要な辺の長さを求めるので、Xcm以下の辺の長さだけでunion-findを使いグラフを形成して、1からnに達するか(同じ連結成分に含まれ…

ARC 060 E - 高橋君とホテル / Tak and Hotels

問題 問題概要 省略 解法 参考サイト imulan.hatenablog.jp 上のサイトを見たらだいぶわかった。 ダブリングと2分探索を使うらしい。蟻本の最後の方にもかいてあった。 int now = a; for (int i = 19; i >= 0; --i){ if(nx[i][now] < b){ now = nx[i][now];…

aoj 0524 - Pizza

問題 問題概要 探索問題。2分探索で値の前後を求める。 解法 まず、storeに店の位置を入れる。この時、少しsample1を使って、考察してみる。本店の位置を0にしてしまうと、宅配先1からの距離は4-0=4で正確に求まるが、宅配先2からの距離は6-0=6で正確なもの…

aoj 0529 - Darts

問題 問題概要 探索問題。単純に全探索してしまうと、TLE。 解法 まず、単純に考える。全てのパターンを考えれば良いので、以下のコードのように単純に4つの矢が刺さるマスを全探索すればいい。 int main(void){ while(1){ int n, m; cin >> n >> m; if(n ==…