二分探索
問題文勉強会
問題文Pair of Numbers概要長さ$n$ の列が与えられる. 次の性質を満たす最長の部分列をすべて求めよ. $a_l,\ a_{l+1},\ \cdots,\ a_r$ を全て割り切る$a_j\ (l \leqq j \leqq r)$ が存在する. $1 \leqq n \leqq 3 \times 10^5,\ 1 \leqq a_i \leqq 10^6$
問題文 : IkaNumber
問題文 : ウォッチング解法 (ただし人と違う解き方をしているらしい) : 50 点分の解法は, dp[i][j][k] : 位置i までを小カメラj 個, 大カメラk 個で覆うときの距離の最小値, として, O(N^4) で計算できる. (二分探索とは概念)これを高速化するために, dp[i][…
問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.点のソートをするときに, x 座標…
問題文 : コンテスト解法 : まずは, 国C の得点を最大化する. これは, 得点が不明なチームの降順に点数を2 つ(若しくは足りない分)取れば良い.次に, 国C の順位を最大化する. これは, 二分探索を行なって位置を定めてやれば良い. (X 位になれる -> X + 1 位…
問題文 : 住み心地解法 : もし, ランク X がある区画Aの住み心地の中央値になれば, ランクX + 1 が他のどの地点にあったとしても, 区画A での中央値はX となる. そこで, ランクについて二分探索を行い, 中央値になりうるかを確かめる. ランクの地点が影響を…
問題文 : スキー解法 : 全体の平均速度について2 分探索を行う. ある平均速度vを決めると, その平均速度でt 秒間高原を滑るとtv [m] 進むこととなる. 通った道のりの総和S と, 滑った時間の総和Tについて, S ≦ Tvを満たせば, その平均速度vで高原を滑り抜け…
問題文 : 数当て解法 : 最初に, 1の数をO(N)時間で当てる. あとは, 1の情報を元に二分探索を行う. Σ[i = 2, 99] ceil(log_{2}i) ＝ 580 くらいなので, 最悪でも580 + 100 コード : #include <cstdio> #include <cstring> using namespace std; void print(int *p, int n) { fo</cstring></cstdio>…
問題文 : 戦国時代解法 :見張り達の見張るエリアを, 左上と右上の線で分ける.まずは左上側の線の処理を以下のように行う.点P(x, y)を, 点P'(0, y - x)に移して, 簡単な場合分けでその点にいる見張りがどれだけの領地を見張っているかを求めることが出来る.右…
問題文 : 国際情報オリンピック解法 :まず,"G を，N 問の合計点が G 点以上の選手の人数が全体の 1 / 12 以上となるような最大の値とする．このとき，金メダルが与えられる条件は，N 問の合計点が G 点以上であることである．"ということを, 問題を解きやす…
問題文 : 米集積場 (pdf注意)解法 : C(x) : Bバーツ以内でx個の水田から米を届けられるか, とすると, C(A)が成り立つ時, C(A - 1)も成立する. よって, xについて二分探索を行う.このとき, 集める水田が連続していたほうがいいことは明らかなので, R - x個の,…
問題文 : カンニング対策 (pdf注意, 3枚目)解法 : 監視する装置の範囲の最大値を求めれば良いから, すべての装置の精度を等しいものとして考える. すると, 端から貪欲的に装置を置いていける. 装置の範囲の最大値は, 二分探索で決めてやることで, O(Mlog(max…
