コンテンツにスキップ

二分探索

タグ「二分探索」の記事 14 件

SamCoding Round 10 (Div. 4) B - Bookworm

Jasur は nn ページの本を読みます。11 日目は aa ページ読み、その後は毎日、前の日より kk ページ多く読みます(22 日目は a+ka + k ページ、33 日目は a+2ka + 2k ページ、…)。残りのページが予定より少ない日は、残りを読んで読み終えます。何日目に読み終えるかを求める問題です(1≤n,a≤10121 \le n, a \le 10^{12}、0≤k≤10120 \le k \le 10^{12})。

mm 日目までに読む予定のページ数の合計は

f(m)=ma+m(m−1)2kf(m) = ma + \frac{m(m - 1)}{2} k

です。f(m)≥nf(m) \ge n となる最小の mm が答えです。

ff は mm について単調増加なので、二分探索で求められます。a≥1a \ge 1 より f(n)≥nf(n) \ge n なので、答えは n≤1012n \le 10^{12} 以下です。探索の上限は 101510^{15} にしています。

Python
n, a, k = map(int, input().split())
ok = 10**15
ng = 0
while ok > ng + 1:
mid = (ok + ng) // 2
if n <= mid * a + mid * (mid - 1) // 2 * k:
ok = mid
else:
ng = mid
print(ok)

ok は f(m)≥nf(m) \ge n を満たす mm、ng は満たさない mm を保ちながら、区間を半分ずつ狭めています。

ABC482 C - Band Count

H×WH \times W のグリッドに NN 個の駒が置かれていて、ii 番目の駒はマス (Ri,Ci)(R_i, C_i) にあります。次の 22 種類のクエリ QQ 個に答える問題です(H,W≤109H, W \le 10^9、N,Q≤3×105N, Q \le 3 \times 10^5)。

  • 1 u d:uu 行目から dd 行目までにある駒の個数を出力する。
  • 2 l r:ll 列目から rr 列目までにある駒の個数を出力する。

行のクエリでは駒の列は関係なく、「u≤Ri≤du \le R_i \le d を満たす ii の個数」を答えればよいです。列のクエリも同様に「l≤Ci≤rl \le C_i \le r を満たす ii の個数」です。

H,WH, W が大きいので行ごとの個数の配列は作れませんが、RR と CC をそれぞれソートしておけば、二分探索で数えられます。ソートした RR で、dd 以下の個数から uu 未満の個数を引いたものが答えです。

計算量は O((N+Q)log⁡N)O((N + Q) \log N) です。

Python
import bisect
H, W, N, Q = map(int, input().split())
R = []
C = []
for _ in range(N):
r, c = map(int, input().split())
R.append(r)
C.append(c)
R.sort()
C.sort()
for _ in range(Q):
t, x, y = map(int, input().split())
l = R if t == 1 else C
print(bisect.bisect_right(l, y) - bisect.bisect_left(l, x))

bisect_right(l, y) は l の中の yy 以下の要素の個数、bisect_left(l, x) は xx 未満の要素の個数です。

二分探索のリンク集

二分探索について、参考になる記事や資料をまとめました。

二分探索は、答えの候補が並んでいて、ある境目より手前では条件を満たさず、そこから先ではずっと満たす(単調性がある)ときに、その境目を O(log⁡N)O(\log N) 回の判定で求める手法です。ソート済みの配列から値を探すのが基本の形で、C++ の std::lower_bound や Python の bisect がこれにあたります。

競プロでよく使うのは、その一般化です。「答えを xx 以下にできるか」のような判定問題が xx について単調なら、答えそのものを二分探索で求められます(答えで二分探索)。最小値の最大化・最大値の最小化や、平均値の最大化がこの形の典型です。実数の範囲でも同じように探せますが、打ち切り方に注意が必要です。

実装では、条件を満たす側の端を ok、満たさない側の端を ng として、ok と ng が隣り合うまで真ん中で区切る書き方(めぐる式二分探索)がよく使われます。範囲が大きいときは、真ん中を (ok + ng) / 2 で計算すると和が型の範囲を超えることがあるので、ok + (ng - ok) / 2 のように書くと安全です。

セグメント木の上を降りながら境目を求める「セグメント木上の二分探索」については、セグメント木のリンク集も見てください。

  • 二分探索アルゴリズムを一般化 〜 めぐる式二分探索法のススメ 〜(けんちょん、Qiita)
    • 値を探す素朴な二分探索から始めて、std::lower_bound の意味、「条件を満たす最小の xx を求める」形への一般化、ok と ng の 2 変数で大小の向きを気にせずに書くめぐる式、の順に説明しています。最後の例は年齢当てゲームです。コードは C++ です。
    • 最終形のコードは真ん中を (ok + ng) / 2 で計算しています。範囲が 101810^{18} 程度になる問題では、ok + (ng - ok) / 2 に直して使ってください。
    • 年齢当てゲームのコードのコメント「mid 歳以上 right 歳以下」は、本文の流儀(半開区間 [left,right)[\mathit{left}, \mathit{right}))では「right 歳未満」の誤りです。
  • 競プロ典型 90 問 001 - Yokan Party の解説(E869120、GitHub)
    • 「答えで二分探索」の入門です。「スコアを MM 以上にできるか」という判定問題に言い換え、それを貪欲法で O(N)O(N) で解いて、MM を二分探索します。「最小値の最大化」は答えで二分探索になることが多い、という指摘と類題もあります。解説は画像 1 枚で、C++ のサンプルコードは同じリポジトリの sol/001.cpp にあります。
  • 二分探索をはじめからていねいに(北海道大学 HCPC、PDF)
    • 2016 年の勉強会のスライドです。配列上の二分探索と lower_bound・upper_bound から始めて、実数の二分探索(回数を固定してループ)、最小値の最大化、最大値の最小化、平均値の最大化を、例題を 1 問ずつ解きながら説明しています。どれも蟻本の例題で、ジャッジは POJ です。コードは C++ で、画像なのでコピーはできません。
  • AtCoder ABC 034 D - 食塩水(けんちょんの競プロ精進記録)
    • 「濃度を xx % 以上にできるか」という判定問題に言い換え、式を変形して「(食塩の量) − (食塩水の量) × xx / 100 の大きいほうから KK 個の和が 00 以上か」で判定しています。実数の二分探索を 50 回のループで行う C++ のコードつきです。
  • 二分探索(Binary Search)のアルゴリズム(アルゴリズムロジック)
    • 値を探す二分探索、lower_bound、条件を満たす最小の位置を求める一般化、平均値の最大化(ABC034 D)を 1 ページで説明しています。Python と C++ のコードと、練習問題の一覧つきです。
    • 中級編の自作の my_lower_bound には誤りがあります。r を arr.size() - 1 から始めているので、xx がすべての要素より大きいときに arr.size() を返せません。また、x == arr[mid] で途中で返しているので、同じ値が複数あると左端を返しません。説明の「lower_bound 関数と upper_bound 関数」も、upper_bound は「xx より大きい値を持つ左端」なので正しくありません。
    • 食塩水のコードは while (ng - ok > 1e-10) で打ち切っています。この問題では止まりますが、値が大きい問題では止まらなくなることがあります(下の「実数の二分探索」を見てください)。
  • 実数の二分探索・三分探索はループ回数を決め打ちしようね(えびちゃんの日記)
    • while (hi - lo > eps) のように幅で打ち切ると、浮動小数点数で表せる値が飛び飛びなせいで止まらなくなる例を示し、ループの回数を決め打ちするよう勧めています。必要な回数の見積もり方(初めの幅を 101810^{18}、許される誤差を 10−910^{-9} とすると 90 回で足りる)と、三分探索の場合の回数も載っています。コードは C++ です。
  • 浮動小数点型で素朴に二分探索をして大丈夫?(えびちゃんの日記)
    • 上の記事の続きにあたる発展的な内容です。止まるかどうかだけでなく、判定関数の丸め誤差のせいで答えがずれる例を挙げて、結果が正しいかを議論しています。コードは Rust です。
  • Re: 浮動小数点数の二分探索(えびちゃんの日記)
    • double のビット列を大小関係を保つ 64 bit 整数に変換し、整数の二分探索として 64 回程度で済ませる方法です。例題は ABC026 D で、コードは Rust です。
    • 「C++ は bit_cast を C++20 まで待つ必要がある」とあるのは執筆当時の話で、今は C++20 で使えます。
  • 二分探索 二分法 違い(うさぎ小屋)
    • 「二分探索」と「二分法」という言葉の違いを整理した短い記事です。競プロで「にぶたん」と呼ぶものがどちらにあたるかも書いています。

複数の質問について、それぞれ「何番目の操作の時点で条件を満たすようになるか」を二分探索したいとき、全部の質問の二分探索を 1 段ずつまとめて進め、操作の列を各段で 1 回ずつ頭からたどる手法です。

  • CODE THANKS FESTIVAL 2017 H - Union Sets(並列二分探索解法)(ARMERIA)
    • 並列二分探索が使える問題の形、図を使った処理の流れ、各段で質問を mid ごとに振り分けて Union-Find の操作を頭からやり直す C++ の実装を説明しています。計算量の見積もりと、部分永続 Union-Find による別解の紹介もあります。
  • 並列二分探索(パラレルバイナリサーチ)(迷いませんか?)
    • SPOJ の Meteors と上の Union Sets を C++ で解いています。説明は短めで、著者自身が計算量の見積もりに自信がないと書いているので、上の記事の補助として読んでください。
  • Segtree(AtCoder Library のドキュメント)
    • max_right と min_left の仕様が載っています。返り値は「区間に ff を適用した結果が true から false に変わる境目」として定義されていて、ff が単調なら「true になる最大の rr」と読めます。計算量は O(log⁡N)O(\log N) です。仕様の説明だけで、セグメント木を降りる仕組みは書かれていません。
  • セグメント木上の二分探索のカテゴリ(けんちょんの競プロ精進記録)
    • セグメント木上の二分探索を使う問題の解説が並んでいて、問題集として使えます。
  • bisect --- 配列二分法アルゴリズム(Python 公式ドキュメント)
    • bisect_left・bisect_right・insort_left・insort_right の仕様と、ソート済みリストから「xx 未満の最大の要素」などを探すレシピがあります。key 引数は Python 3.10 で追加されたもので、それより古い環境では使えません。
    • 日本語訳が一部だけで、英語のまま残っている段落があります。レシピの find_ge のコメント「左端の項目がx以上であることを確認する」は、原文では「xx 以上の左端の項目を見つける」という意味です。
  • めぐる式二分探索 コピペで使えるPython実装(学習する天然ニューラルネット)
    • 判定関数 is_ok と ok・ng を渡すめぐる式二分探索の Python のテンプレートと、ABC146 C などでの使用例です。仕組みの説明は、けんちょんさんの記事などに任せています。
    • 「配列にできない関数を探索できる(bisect モジュールでは不可)」とありますが、Python 3.10 以降なら bisect_left(range(lo, hi), True, key=is_ok) のように、bisect でも判定関数のまま探せます。
  • std::lower_bound・std::upper_bound・std::partition_point(cpprefjp)
    • lower_bound は「指定した値以上の最初の位置」、upper_bound は「指定した値より大きい最初の位置」を返します。範囲がソートされていなくても、条件で区分化されていればよいこと、どちらも partition_point と同じ働きであることが書かれています。partition_point は判定関数を渡して境目を求める関数で、二分探索を一般化した形にあたります。
    • std::set や std::multiset に std::lower_bound を使うと、比較の回数は O(log⁡N)O(\log N) でもイテレータを進めるのに O(N)O(N) かかります。メンバ関数の s.lower_bound(x) を使ってください(cpprefjp の lower_bound のページにも、メンバ関数を使うようにと書いてあります)。

二分探索そのものを扱う講座はありませんが、二分探索を使う講座がいくつかあります。

  • Alien Trick
    • 「ちょうど kk 個選ぶ」という制約を、1 個ごとのペナルティ λ\lambda に置き換えて外し、λ\lambda を二分探索する手法の講座です。最適な個数が λ\lambda について単調になることを示し、二分探索の終了時に成り立つ条件まで丁寧に説明しています。難易度の高い講座です。
  • 永続セグメント木
    • 区間の kk 番目の値を求める問題で、ふつうに二分探索すると O(log⁡2N)O(\log^2 N) のところを、複数の木を同時に降りるセグメント木上の二分探索で O(log⁡N)O(\log N) にする方法を説明しています。
  • Wavelet Matrix(発展)
    • 「5. 総和に関する二分探索」の節で、単調な総和の条件を満たす境目を Wavelet Matrix の上で求めています。
  • 二分探索(日本語版 Wikipedia)、Binary search(英語版 Wikipedia)
    • 日本語版は英語版の訳です。重複がある場合に左端・右端を探す手続き(lower_bound・upper_bound にあたる)、順位や直前・直後の要素の求め方、指数探索などの変種が載っています。「実装上の問題」の節には、有名な本や Java の標準ライブラリで、真ん中の計算のオーバーフローのバグが長年見逃されていた話があります。答えで二分探索や実数の二分探索の話はありません。
    • 各言語のライブラリの節は、日本語版・英語版ともに古い情報を元にしています。
  • Binary search(cp-algorithms、英語)
    • 配列上の探索、lower_bound・upper_bound、単調な述語での探索とその正当性、答えで二分探索(平均値の最大化)、実数の探索(中間値の定理を使うので単調でなくてよい)、2 のべき乗の幅で進む方法、並列二分探索までを 1 ページで扱っています。オーバーフローの注意と C++20 の std::midpoint にも触れています。コードは C++ で、練習問題の一覧もあります。
    • 並列二分探索の節は、例の表と直後のコードで区間の取り方が違うので、読むときは混乱しないように気をつけてください。
  • Binary Search(USACO Guide、英語)
    • 単調な関数での二分探索の入門で、「true になる最後の位置」と「true になる最初の位置」の 2 つの書き方、よくある間違い(off-by-one、負の範囲、オーバーフロー)、練習問題の一覧があります。コードは C++・Java・Python から選べます。配列上の二分探索は、前提の別ページ Binary Search on a Sorted Array にあります。
    • 「Mistake 1」の Python のコードは hi = 0 になっていて(C++ と Java では hi = x)、説明している無限ループが起きません。「Mistake 2」の「負の奇数を 2 で割ると切り上がる」という説明は C++ と Java の話で、Python の // は切り捨てなので当てはまりません。
  • Binary Search(lovro、Topcoder、英語)
    • 述語が「no … no yes … yes」と並ぶときに二分探索できる、という形で一般化を説明した古典的なチュートリアルです。最後の no を探すときに真ん中を切り上げないと無限ループになる例や、実数の二分探索の打ち切り方(回数を固定する方法と、相対誤差で止める方法)もあります。
    • サイトの移行で表示が崩れていて、擬似コードのインデントが壊れていたり、例の数列が連結して表示されたりしています。練習問題のリンクは切れています。「Arrays.binary_search」は Java の Arrays.binarySearch の誤りです。
  • ABC146 C - Buy an Integer:値段は NN について単調増加なので、買える最大の NN を二分探索します。
  • 競技プログラミングの鉄則 A12 - Printer:tt 秒後までに印刷される枚数は tt について単調なので、KK 枚以上になる最小の tt を求めます。
  • 競プロ典型 90 問 001 - Yokan Party(★4):最小値の最大化です。上の解説を見てください。
  • ABC063 D - Widespread:爆発の回数を決め打ちして、すべての魔物を消せるかを判定します。
  • ABC023 D - 射撃王:得点を決め打ちすると風船ごとに割る期限が決まるので、期限の早い順に割れるかを判定します。
  • ABC174 E - Logs:最大値の最小化です。最も長い丸太を xx 以下にするのに必要な切断回数を数えます。
  • ABC144 E - Gluttony:成績を決め打ちし、組み合わせ方を貪欲に決めて、必要な修行の回数が KK 以下かを判定します。
  • ARC050 B - 花束:作る花束の個数を決め打ちして、作れるかを判定します。値が 101810^{18} まであるので、オーバーフローに注意が必要です。
  • ABC149 E - Handshake:幸福度の上がり方が xx 以上の握手が MM 通り以上あるような最大の xx を二分探索し、個数を数えるのにも二分探索を使います。
  • ABC034 D - 食塩水:平均値の最大化の典型です。上のけんちょんさんの記事が解説です。
  • ABC026 D - 高橋君ボール1号:f(t)f(t) は単調ではありませんが、f(0)<100f(0) < 100 で、tt が大きいと f(t)>100f(t) > 100 になるので、中間値の定理から f(t)=100f(t) = 100 となる tt を二分法で 1 つ見つけられます。
  • ABC269 E - Last Rook:行の範囲を半分に区切り、置かれているルークの数が行の数より少ないほうに空いた行がある、として 20 回以内の質問で探します。列も同じです。

競プロキャンプ2026関西 A - km - n = k

整数 XX が与えられます。1≤k,m,n≤X1 \le k, m, n \le X を満たす整数の組 (k,m,n)(k, m, n) のうち、km−n=kkm - n = k を満たすものの個数を求める問題です(2≤X≤1062 \le X \le 10^6)。

km−n=kkm - n = k は n=k(m−1)n = k(m - 1) と変形できます。nn は kk と mm から決まるので、nn が 11 以上 XX 以下になるような (k,m)(k, m) の組を数えればよいです。

t=m−1t = m - 1 とおくと、条件は 1≤t≤X−11 \le t \le X - 1 かつ kt≤Xkt \le X です(kt≥1kt \ge 1 は t≥1t \ge 1 から成り立ちます)。kk を固定すると、条件を満たす tt は 11 以上 min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) 以下のすべての整数です。これを k=1,…,Xk = 1, \dots, X について足し合わせれば答えです。

⌊X/k⌋\lfloor X / k \rfloor は割り算で直接求められますが、下のコードでは「kt≤Xkt \le X を満たす最大の tt」を二分探索で求めています。計算量は O(Xlog⁡X)O(X \log X) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
void solve() {
LL(X);
ll ans = 0;
rep(k, 1, X + 1) {
ans += binary_search(1, X, [=](ll mm) { return k * mm <= X; });
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

mm が上の t=m−1t = m - 1 です。binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ng を XX にしているので、返り値は XX 未満で kt≤Xkt \le X を満たす最大の tt、つまり min⁡(⌊X/k⌋,X−1)\min(\lfloor X / k \rfloor, X - 1) です。k≤Xk \le X なので、f(1) は常に真です。

使用ライブラリ:cpp_include@9c33ee7

ABC480 E - Product-Bounded Arithmetic Sequences

長さが 33 以上で、公差が正の、正整数からなる等差数列を良い数列と呼びます。良い数列のうち、要素の総積が NN 以下であるものの個数を求める問題です(1≤N≤10181 \le N \le 10^{18})。

良い数列は、長さ ll、初項 aa、公差 dd で決まります(l≥3l \ge 3、a≥1a \ge 1、d≥1d \ge 1)。総積は

a(a+d)(a+2d)⋯(a+(l−1)d)a (a + d) (a + 2d) \cdots (a + (l - 1)d)

です。答えは 101210^{12} 程度になる(入力例 2)ので 1 つずつ数えることはできませんが、ll と aa を全探索して、dd の個数をまとめて数えれば間に合います。

  • ll の範囲:総積が最小になるのは a=d=1a = d = 1 のときで、その値は l!l! です。20!≈2.4×1018>101820! \approx 2.4 \times 10^{18} > 10^{18} なので、l≤19l \le 19 です。
  • aa の範囲:総積は a3a^3 より大きいので、a<106a < 10^6 です。
  • dd の個数:ll と aa を決めると、総積は dd について単調増加です。よって総積が NN 以下になる dd は 11 以上のある値 DD 以下のすべての整数で、その個数 DD は二分探索で求められます。総積は 2d22d^2 より大きいので、D<109D < 10^9 です。

aa を大きくしても総積は増えるので、ある aa で D=0D = 0 になったら、それより大きい aa も調べる必要はありません。計算量は、l=3l = 3 のときの 10610^6 個の aa のそれぞれで二分探索をするのがいちばん重く、全体で 10810^8 回程度の計算です。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/saturating.hpp"
#include "shogo-library/utility/binary-search.hpp"
void solve() {
LL(N);
ll ans = 0;
rep(l, 3, 20) {
rep(a, 1, 1e6) {
ll ng = 1e9;
ll ok = binary_search(0, ng, [=](ll x) {
ll p = a, t = a;
rep(l - 1) {
t += x;
p = saturating_mul(p, t);
if (p > N)
break;
}
return p <= N;
});
if (ok == 0)
break;
ans += ok;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

binary_search(ok, ng, f) は、f(ok) が真、f(ng) が偽であるとして、f が真になる側の境界の値を返します。ここでは f(x) が「公差 x のときの総積が NN 以下か」なので、返り値がそのまま DD になります。f(0) が偽(つまり al>Na^l > N)のときも、すべての x で偽なので 00 が返り、D=0D = 0 として扱えます。

総積の計算では、saturating_mul で掛け算がオーバーフローしたときに long long の最大値に丸めています。

使用ライブラリ:cpp_include@9c33ee7

ABC480 D - Concatenation of Prefixes

長さ NN の整数列 AA が与えられます。i=1,2,…,Ni = 1, 2, \dots, N の順に (A1,…,Ai)(A_1, \dots, A_i) を末尾に連結して、長さ N(N+1)2\frac{N(N+1)}{2} の数列 BB を作ります。QQ 個の質問 (L,R)(L, R) について、BL+⋯+BRB_L + \dots + B_R を求める問題です(1≤N,Q≤1051 \le N, Q \le 10^5、−108≤Ai≤108-10^8 \le A_i \le 10^8)。

BB の先頭からの和 f(x)=B1+⋯+Bxf(x) = B_1 + \dots + B_x が求められれば、答えは f(R)−f(L−1)f(R) - f(L - 1) です。

BB は、kk 番目のかたまりが (A1,…,Ak)(A_1, \dots, A_k) であるようなかたまりの連結です。kk 番目のかたまりの長さは kk なので、はじめの ii 個のかたまりの長さの合計は Ti=i(i+1)2T_i = \frac{i(i+1)}{2} です。また、AA の累積和を Pj=A1+⋯+AjP_j = A_1 + \dots + A_j とすると、kk 番目のかたまりの和は PkP_k です。

f(x)f(x) を求めるには、まず Ti≤xT_i \le x となる最大の ii を求めます。B1,…,BxB_1, \dots, B_x は、はじめの ii 個のかたまりと、i+1i + 1 番目のかたまりの先頭 x−Tix - T_i 個からなります。したがって

f(x)=(P1+⋯+Pi)+Px−Tif(x) = (P_1 + \dots + P_i) + P_{x - T_i}

です。PP と、PP の累積和を前計算しておけば、f(x)f(x) は ii を求めるだけで計算できます。TiT_i は増加列なので、ii は二分探索で求められます。

計算量は O(N+Qlog⁡N)O(N + Q \log N) です。∣f(x)∣|f(x)| は最大で N(N+1)2×108≈5×1017\frac{N(N+1)}{2} \times 10^8 \approx 5 \times 10^{17} 程度なので、64 ビット整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/utility/binary-search.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, Q);
VL(A, N);
vl tmp = {0};
vl s0 = {0}, s1 = {0};
rep(i, N) {
s0.push_back(s0.back() + A[i]);
s1.push_back(s1.back() + s0.back());
tmp.push_back(tmp.back() + i + 1);
}
auto q = [&](ll x) {
ll i = bisect_right(tmp, x) - 1;
return s1[i] + s0[x - tmp[i]];
};
rep(Q) {
LL(L, R);
print(q(R) - q(L - 1));
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tmp[i] が TiT_i、s0[j] が PjP_j、s1[i] が P1+⋯+PiP_1 + \dots + P_i です。bisect_right(tmp, x) は tmp の中で x より大きい最初の要素の位置(Python の bisect.bisect_right と同じ)を返すので、そこから 11 を引くと Ti≤xT_i \le x となる最大の ii になります。q(x) が f(x)f(x) です。

使用ライブラリ:cpp_include@9c33ee7

AALC001 L - Swap between Arrays

長さ NN の整数列 AA, BB, CC に対して、次の 4 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤1051 \le N, Q \le 10^5, −109≤Ai,Bi,Ci≤109-10^9 \le A_i, B_i, C_i \le 10^9)。

  • 1 l r:l≤k≤rl \le k \le r のすべての kk について、AkA_k と BkB_k を入れ替える。
  • 2 l r:同様に BkB_k と CkC_k を入れ替える。
  • 3 l r:同様に CkC_k と AkA_k を入れ替える。
  • 4 i:∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる jj(i≤j≤Ni \le j \le N)の最小値を出力する。なければ N+1N + 1 を出力する。

まず、入れ替えがない場合のクエリ 4 を考えます。∑k=ijAk>0\sum_{k=i}^{j} A_k > 0 となる最小の jj は、「区間 [i,j][i, j] の接頭辞の和がすべて 00 以下である間、右に伸ばす」という二分探索で求まります。セグメント木の各ノードに区間の和と接頭辞の和の最大値を持たせれば、セグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で求まります。接頭辞の和の最大値は、区間 XX(左)と YY(右)について max⁡(preX,sumX+preY)\max(\mathrm{pre}^X, \mathrm{sum}^X + \mathrm{pre}^Y) で合成できます。

入れ替えに対応するために、AA, BB, CC の 3 本それぞれについて、和と接頭辞の和の最大値をノードに持たせます。区間内の AkA_k と BkB_k をすべて入れ替えると、ノードが持つ AA の値と BB の値もそのまま入れ替わります。そのため、入れ替えは「3 本の情報を並べ替える」作用として遅延評価セグメント木に載せられます。作用は (0,1,2)(0, 1, 2) の置換 ff で表し、新しい ii 本目には元の fif_i 本目の値が入るとします。作用 gg の後に ff を行うと、新しい ii 本目には元の gfig_{f_i} 本目の値が入るので、合成は (gf0,gf1,gf2)(g_{f_0}, g_{f_1}, g_{f_2}) です。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
void solve() {
using M = monoid::PrefixSumMax<ll>;
using A = acted_monoid::Rearrange<M, 3>;
LL(N, Q);
vec<A::S> init(N);
rep(j, 3) rep(i, N) {
LL(x);
init[i][j] = M::S(x);
}
LazySegTree<A> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(l, r);
seg.apply(l - 1, r, A::swap(0, 1));
} else if (q == 2) {
LL(l, r);
seg.apply(l - 1, r, A::swap(1, 2));
} else if (q == 3) {
LL(l, r);
seg.apply(l - 1, r, A::swap(0, 2));
} else {
LL(i);
print(1 + seg.max_right(i - 1, [](const auto &p) { return p[0].max <= 0; }));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

monoid::PrefixSumMax<ll> は区間の和 sum と接頭辞の和の最大値 max をもつモノイドで、M::S(x) が値 xx の 1 要素を表します。max は空の接頭辞(和 00)も含めた接頭辞の和の最大値なので、単位元では 00 になります。acted_monoid::Rearrange<M, 3> は、これを 3 つ並べた std::array に「成分の並べ替え」を作用させる作用付きモノイドで、A::swap(i, j) が成分 ii と jj を入れ替える作用です。入力は AA, BB, CC の順に 1 本ずつ読み、kk 番目の要素の成分 0, 1, 2 に入れています。LazySegTree の max_right は ACL と同じ仕様です。

max_right(i - 1, f) は、0 始まりの半開区間 [i−1,r′)[i - 1, r') の接頭辞の和がすべて 00 以下となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素まで足すと初めて和が正になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。

使用ライブラリ:cpp_include@397a51d

AALC001 C - Binary Search on a Segment Tree

長さ NN の非負整数列 AA に対して、次の 3 種類のクエリを合計 QQ 個処理する問題です(1≤N,Q≤2×1051 \le N, Q \le 2 \times 10^5)。

  • 1 i x:AiA_i を xx に変更する。
  • 2 l t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる rr(l≤r≤Nl \le r \le N)の最小値を出力する。なければ N+1N + 1 を出力する。
  • 3 r t:∑i=lrAi≥t\sum_{i=l}^{r} A_i \ge t となる ll(1≤l≤r1 \le l \le r)の最大値を出力する。なければ 00 を出力する。

和のセグメント木を使います。Ai≥0A_i \ge 0 なので、ll を固定すると ∑i=lrAi\sum_{i=l}^{r} A_i は rr について単調に増えます。そのため、クエリ 2 は「和が tt 未満である間、右に伸ばせるだけ伸ばす」という二分探索で求まります。これはセグメント木上の二分探索(ACL の max_right に当たる操作)で O(log⁡N)O(\log N) で行えます。クエリ 3 も同様に、左に伸ばす二分探索(min_left)で求まります。

全体の計算量は O(N+Qlog⁡N)O(N + Q \log N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
void solve() {
LL(N, Q);
VL(A, N);
RSumQ<ll> seg(A);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, x);
seg.set(i - 1, x);
} else if (q == 2) {
LL(l, t);
print(1 + seg.max_right(l - 1, [t](ll a) { return a < t; }));
} else {
LL(r, t);
print(seg.min_left(r, [t](ll a) { return a < t; }));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RSumQ<ll> は区間和のセグメント木で、max_right と min_left は ACL と同じ仕様です。

  • max_right(l - 1, f) は、0 始まりの半開区間 [l−1,r′)[l - 1, r') の和が tt 未満となる最大の r′r' を返します。0 始まりで r′r' 番目(1 始まりで r′+1r' + 1 番目)の要素を加えたときに初めて tt 以上になるので、答えは r′+1r' + 1 です。r′=Nr' = N のときは N+1N + 1 になり、「存在しない」場合の出力とも一致します。
  • min_left(r, f) は、半開区間 [l′,r)[l', r) の和が tt 未満となる最小の l′l' を返します。0 始まりで l′−1l' - 1 番目(1 始まりで l′l' 番目)の要素を加えたときに初めて tt 以上になるので、答えは l′l' です。l′=0l' = 0 のときも、そのまま「存在しない」場合の出力 00 になります。

使用ライブラリ:cpp_include@402f0cf

DOJ Beginner Contest 11 F - Laboratory

NN 種類の微生物があり、ii 番の微生物の xx 日目の個体数は Ai+BixA_i + B_i x です。BiB_i を成長係数とよびます。

xx 日目に、何種類かの微生物を選びます。ただし、選んだ微生物を次の 2 通りで並べたとき、番号の並びが一致しなければなりません。

  • 成長係数の小さい順
  • xx 日目の個体数の少ない順

どちらも、値が同じなら番号の小さい順に並べます。KK 種類以上選べる最も早い日 x≥0x \ge 0 を求める問題です。存在しなければ -1 を出力します。

1≤K≤N≤1051 \le K \le N \le 10^5、1≤Ai,Bi≤1091 \le A_i, B_i \le 10^9 です。

固定した日に選べる最大の種類数

Section titled “固定した日に選べる最大の種類数”

微生物を (Bi,i)(B_i, i) の昇順に並べておきます。選んだ微生物の並びがこの順で、(Ai+Bix,i)(A_i + B_i x, i) も昇順になっていれば条件を満たします。

つまり、(Bi,i)(B_i, i) の順に並べた列で、(Ai+Bix,i)(A_i + B_i x, i) の最長狭義増加部分列(LIS)の長さが、xx 日目に選べる最大の種類数です。LIS の長さは O(Nlog⁡N)O(N \log N) で求まります。

xx 日目に選べる組は、x+1x + 1 日目にも選べます。

(Bp,p)<(Bq,q)(B_p, p) < (B_q, q) の 2 つが xx 日目に条件を満たしているとします。1 日たつと、個体数の差 (Aq+Bqx)−(Ap+Bpx)(A_q + B_q x) - (A_p + B_p x) は Bq−Bp≥0B_q - B_p \ge 0 だけ増えます。Bp<BqB_p < B_q なら差が増えるので順序は保たれ、Bp=BqB_p = B_q なら差が変わらないので順序も変わりません。

よって、選べる最大の種類数は xx について広義単調増加です。KK 種類以上選べる最小の xx を二分探索で求めます。

問題文にあるとおり、答えが存在すれば 10910^9 以下です。x=109+1x = 10^9 + 1 で KK 種類選べなければ -1 を出力し、選べれば [0,109+1][0, 10^9 + 1] で二分探索します。

全体で O(Nlog⁡Nlog⁡max⁡)O(N \log N \log \max) です。

Python
from operator import itemgetter
from bisect import bisect_left
for _ in range(int(input())):
N, K = map(int, input().split())
ABi = [tuple(map(int, input().split())) + (i,) for i in range(N)]
ABi.sort(key=itemgetter(1))
def q(x):
dp = [(2 * 10**18, 10**18)] * (N + 1)
for a, b, i in ABi:
dp[bisect_left(dp, (a + b * x, i))] = (a + b * x, i)
for i in range(N + 1):
if dp[i][0] >= 2 * 10**18:
return i
assert False
ok = 10**9 + 1
ng = -1
if q(ok) < K:
print(-1)
continue
while ok > ng + 1:
mid = (ok + ng) // 2
if q(mid) >= K:
ok = mid
else:
ng = mid
print(ok)

sort は安定なので、BiB_i だけをキーにしても、BiB_i が等しいものは番号順に並びます。q(x) は (Ai+Bix,i)(A_i + B_i x, i) の LIS の長さを返します。dp[k] は長さ k+1k + 1 の増加部分列の末尾の最小値で、番兵の値が残っていない個数が LIS の長さです。

DOJ Beginner Contest 8 C - Mochi

NN 個の餅があり、ii 番目の餅の大きさは AiA_i です。まだ使っていない餅を 2 個選んで 1 組にできますが、上に置く餅は下に置く餅より真に大きくなければなりません。作れる組の最大数を求める問題です。

テストケースは T≤2×105T \le 2 \times 10^5 個あり、NN の総和は 2×1052 \times 10^5 以下です。

AA を小さい順に並べ替えておきます。

kk 組作れるなら、小さいほうから kk 個を下に、大きいほうから kk 個を上に、それぞれ小さい順に組にしても作れます。つまり、すべての ii (1≤i≤k1 \le i \le k) で Ai<AN−k+iA_i < A_{N - k + i} が成り立つかを調べれば判定できます。

理由を説明します。kk 組作れたとして、下の餅を小さい順に b1≤⋯≤bkb_1 \le \dots \le b_k、上の餅を小さい順に t1≤⋯≤tkt_1 \le \dots \le t_k とします。

  • 下の餅のうち大きいほうから k−i+1k - i + 1 個は、どれも bib_i 以上です。その上の餅は、それより真に大きいので bib_i より大きくなります。よって、bib_i より大きい上の餅は k−i+1k - i + 1 個以上あり、ti>bit_i > b_i です。
  • 小さいほうから ii 番目の AiA_i は bib_i 以下、大きいほうから数えた AN−k+iA_{N - k + i} は tit_i 以上です。

まとめると Ai≤bi<ti≤AN−k+iA_i \le b_i < t_i \le A_{N - k + i} が成り立ちます。

kk 組作れるなら、そこから 1 組外せば k−1k - 1 組も作れます。そのため、作れる最大の kk を二分探索で求められます。kk は ⌊N/2⌋\lfloor N / 2 \rfloor 以下です。

計算量は、並べ替えと二分探索で O(Nlog⁡N)O(N \log N) です。

Python
for _ in range(int(input())):
N = int(input())
A = list(map(int, input().split()))
A.sort()
ok = 0
ng = (N + 2) // 2
while ok + 1 < ng:
mid = (ok + ng) // 2
if all(A[i] < A[N - mid + i] for i in range(mid)):
ok = mid
else:
ng = mid
print(ok)

二分探索では、ok 組は作れて、ng 組は作れない、という状態を保っています。ng の初期値 ⌊N/2⌋+1\lfloor N / 2 \rfloor + 1 は、どうやっても作れない組数です。

ShareOJ - Truth or Lie

11 以上 NN 以下の秘密の整数 xx を当てるインタラクティブ問題です。

? l r と質問すると、xx が ll 以上 rr 以下かどうかが 11(はい)か 00(いいえ)で返ってきます。ただし、ジャッジは嘘つきかもしれません。嘘つきの場合は、常に逆の答えを返します。質問は 2020 回までで、N≤105N \le 10^5 です。

? 1 N と質問します。xx は必ず 11 以上 NN 以下なので、本当の答えは「はい」です。したがって、11 が返ってくればジャッジは正直者、00 が返ってくれば嘘つきだとわかります。

嘘つきなら、これ以降の応答をすべて反転すれば本当の答えになります。

あとは、ふつうの二分探索で xx を求めます。xx がありうる範囲を [l,r][l, r] として、真ん中 mm で区切り、xx が [l,m][l, m] にあるかを質問します。あれば r=mr = m、なければ l=m+1l = m + 1 とします。

範囲の大きさは 1 回ごとに半分(切り上げ)になるので、⌈log⁡2105⌉=17\lceil \log_2 10^5 \rceil = 17 回で 11 つに決まります。最初の 1 回と合わせて 1818 回なので、2020 回に収まります。

Python
N = int(input())
l = 1
r = N
print("?", 1, N, flush=True)
x = (int(input())) ^ 1
while l < r:
m = (l + r) // 2
print("?", l, m, flush=True)
res = int(input())
if res ^ x:
r = m
else:
l = m + 1
print("!", l, flush=True)

変数 x は秘密の整数ではなく、ジャッジが嘘つきなら 11、正直者なら 00 になるフラグです。res ^ x で応答を反転し、本当の答えに直しています。

牛客小白月赛138 C - AND and OR

長さ nn の非負整数列 a1,…,ana_1, \dots, a_n と非負整数 kk が与えられます(2≤n≤2×1052 \le n \le 2 \times 10^5、0≤ai,k≤1090 \le a_i, k \le 10^9)。

(aiandaj)+(aioraj)=k(a_i \mathbin{\mathrm{and}} a_j) + (a_i \mathbin{\mathrm{or}} a_j) = k

を満たす 1≤i<j≤n1 \le i < j \le n があれば 1 つ出力し、なければ −1-1 を出力してください(nn の総和 ≤2×105\le 2 \times 10^5)。

実は、どんな非負整数 a,ba, b についても

(aandb)+(aorb)=a+b(a \mathbin{\mathrm{and}} b) + (a \mathbin{\mathrm{or}} b) = a + b

が成り立ちます。ビットごとに確かめると分かります。各ビットについて、aa と bb のそのビットの組み合わせは次の 3 通りです。

a,ba, b のビットANDORAND + ORa+ba + b
両方 0000000000
片方だけ 1100111111
両方 1111112222

どのビットでも AND と OR の寄与の和が aa と bb の寄与の和に一致するので、全体でも等しくなります。

したがって、問題は「ai+aj=ka_i + a_j = k となる i<ji < j を 1 つ見つけよ」という、よくある問題に言い換えられます。

(ai,i)(a_i, i) の組を値でソートしておきます。各要素 aia_i について、相手の値 k−aik - a_i が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。

k−ai=aik - a_i = a_i のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。

計算量はソートと二分探索で O(nlog⁡n)O(n \log n) です。

Python
import bisect
for _ in range(int(input())):
N, K = map(int,input().split())
A = list(map(int,input().split()))
Ai = [(A[i],i) for i in range(N)]
Ai.sort()
for i in range(N):
j = bisect.bisect_left(Ai,(K-Ai[i][0],-1))
if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]:
print(*sorted((Ai[i][1]+1,Ai[j][1]+1)))
break
else:
print(-1)

Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が k−aik - a_i 以上である最初の位置が求まります。添字は 00 以上なので、第 2 要素に −1-1 を入れておけば、値が k−aik - a_i の組より必ず前に来ます。出力は i<ji < j の順にする必要があるので、元の添字をソートしてから出力しています。

SamCoding Round 7 (Div. 2) J - Lying Guard

11 以上 NN 以下の秘密の数 TT を当てるインタラクティブ問題です(N≤1018N \le 10^{18})。? i と質問すると、TT と ii の大小関係が >、<、= のいずれかで返ってきます。

ただし、答える番人はゲーム全体を通して 1 回だけ 嘘をつくことがあります。= の答えが嘘のこともあります。質問は 190190 回までです。

ふつうの二分探索で、同じ質問を 3 回ずつして多数決をとります。

嘘はゲーム全体で高々 1 回なので、同じ質問への 3 回の答えのうち、少なくとも 2 回は本当です。そのため、多数決をとれば必ず正しい答えが得られます。正しい答えだけで二分探索を進めれば、ふつうの二分探索と同じく TT が求まります。

範囲 [l,r][l, r] の真ん中 mm を聞き、> なら l=m+1l = m + 1、< なら r=m−1r = m - 1、= ならそこで終わりにします。範囲の大きさは 1 回ごとに半分以下になるので、繰り返しは ⌊log⁡21018⌋+1=60\lfloor \log_2 10^{18} \rfloor + 1 = 60 回以下です。1 回につき 3 回質問するので、合計 180180 回以下で、上限の 190190 回に収まります。

Python
from collections import Counter
N = int(input())
l = 1
r = N
while l < r:
m = (l + r) // 2
c = Counter()
for _ in range(3):
print("?", m, flush=True)
c[input()] += 1
k = c.most_common()[0][0]
if k == "=":
l = r = m
elif k == ">":
l = m + 1
else:
r = m - 1
print("!", l, flush=True)

3 回の答えを Counter で数え、most_common()[0][0] で最も多い答えを取り出しています。= のときは l = r = m としてループを抜けます。

SamCoding Round 7 (Div. 2) H - Mysterious Valley

NN 個の地点が一列に並び、それぞれの高さはすべて異なります。両隣より低い地点(谷)を 1 つ見つけるインタラクティブ問題です。端の地点では、外側に無限に高い山があるとみなします。

? i と質問すると地点 ii の高さが返ってきます。質問は 130130 回までで、NN は最大 101810^{18} です。

二分探索で谷を探します。

まず端を調べます。

  • h1<h2h_1 < h_2 なら、地点 11 が谷です。
  • hN−1>hNh_{N-1} > h_N なら、地点 NN が谷です。

どちらでもなければ、h1>h2h_1 > h_2(左端では下り)かつ hN−1<hNh_{N-1} < h_N(右端では上り)です。

「下り」と「上り」の間を狭める

Section titled “「下り」と「上り」の間を狭める”

ll を「hl>hl+1h_l > h_{l+1}(下り)」、rr を「hr<hr+1h_r < h_{r+1}(上り)」を満たす位置として、l=1l = 1、r=N−1r = N - 1 から始めます。

ll と rr の真ん中 mm で hmh_m と hm+1h_{m+1} を比べ、上りなら r=mr = m、下りなら l=ml = m とします。こうすれば、ll では下り、rr では上り、という状態がずっと保たれます。

r=l+1r = l + 1 になったら、hl>hrh_l > h_r かつ hr<hr+1h_r < h_{r+1} なので、地点 rr が谷です。

r−lr - l は 1 回ごとにほぼ半分になるので、繰り返しは ⌈log⁡21018⌉=60\lceil \log_2 10^{18} \rceil = 60 回以下です。1 回の繰り返しで質問するのは hmh_m と hm+1h_{m+1} の 2 つなので、最初の 4 回と合わせて 4+2×60=1244 + 2 \times 60 = 124 回以下に収まります。

Python
d = {}
def q(x):
if x not in d:
print("?", x)
d[x] = int(input())
return d[x]
N = int(input())
if N == 1:
print("!", 1)
exit(0)
if q(1) < q(2):
print("!", 1)
exit(0)
if q(N - 1) > q(N):
print("!", N)
exit(0)
l = 1
r = N - 1
while l + 1 < r:
m = (l + r) // 2
if q(m) < q(m + 1):
r = m
else:
l = m
print("!", r)

q(x) は地点 xx の高さを質問する関数で、同じ地点を 2 回質問しないように結果を d に覚えています。

問題文では出力のたびにフラッシュするように書かれていますが、Python の input() は読み込む前に標準出力をフラッシュするので、flush を書かなくても質問はジャッジに届きます。