この記事は 【AtCoder】初中級者が解くべき過去問精選 100 問を緑色コーダーが C++ で解いてみた の子記事です。お読みになる前に親記事をご確認ください。
二分探索について、以下の記事が参考になります。
18. ALDS_4_B – 二分探索
線形に探索すると \Omega(nq) = 10^9 程度かかり、実行時間制限をクリアするのは難しそうです。S が昇順に整理されていることもあり、二分探索で求めることを考えます。
lower_bound を使うと、vector S に整数 t が含まれているか否かの判定は次の関数でできます。
bool contains(const vector<int> &S, int t)
{
auto lb = lower_bound(S.begin(), S.end(), t);
return (lb != S.end()) && (*lb == t);
}
上記の関数の計算量は O(\log n ) であるため、 全体の計算量は O(q \log n) = 10^6 程度となり、実行時間制限に違反せずに解答できます。
S を set を使って保持すると、入力に O(n \log n) かかりますが、制限時間内に解答できます。set を使う場合は S が予め昇順に整列してなくても求解できます。
T の方もソートして、しゃくとり法で求解することも可能です。しゃくとり法については例えば、しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ を参照ください。
S = \{s_1, \dots, s_n\}, T =\{t_1, \dots, t_q\} として、t_1 の時点で s_1 から s_{i_1} まで調べたとします。このとき、s_{i_1-1}<t_1\leq s_{i_1} が成立するため、t_2(>t_1) が S に属するかを調べる際に \{s_1, \dots, s_{i_1 – 1} \} を調べる必要はありません。これまでの探索の結果を使い、探索範囲を絞ることで計算量を O(n + q) に抑えることができます。計算量に q が入るのは s_{i_1} のように t_1 との比較と t_2 との比較の 2 回の比較が発生する要素が q – 1 個あるためです。
全体の計算量は O(n + q \log q) になります。
19. JOI 2009 本選 2 – ピザ
線形探索の場合、\Omega(mn) = 10^9 程度の計算量になるため、二分探索を使うことを考えます。
d_j をソート後、k_i \leq \underset{j}{\max}\,d_j を満たす k_i に対しては以下の手順で最寄りの店舗までの距離を求められます。
- lower_bound で k_i \leq d_j を満たす最小の d_{j} (d_{j_i} とおく) を求める。
- もし k_i = d_{j_i} ならば、0 が最寄りの店舗までの距離である。
- もし k_i \neq d_{j_i} ならば、d_{j_i – 1}<k_i<d_{j_i} のため、最寄りの店舗までの距離 \min(k_i – d_{j_i-1}, d_{j_i} – k_i) を計算する。
k_i>\underset{j}{\max}\,d_j となる k_i について、最寄りが本店なのか、時計回りで本店から最も遠い店舗なのか、を判定する処理を別途入れるのは面倒です。本店の位置を 0 と d の 2 通り入れておくと、すべての k_i が k_i \leq \underset{j}{\max}\,d_j を満たすため、場合分けが不要になります。
計算量は O((m + n) \log n) = 10^6 程度で制限時間内に計算できます。
JOI の解説 の別解のように k_1, \dots k_m の方もソートした後、しゃくとり法で求解することも可能です。
k_1, d_{j_1 – 1}, d_{j_1} が d_{j_1 – 1}<k_1 \leq d_{j_1} を満たすとします。このとき、k_2 は以下のいずれかを満たします。
場合 1 d_{j_1 – 1}<k_1 \leq k_2 \leq d_{j_1}
場合 2 d_{j_1 – 1}<k_1 \leq d_{j_1} \leq k_2
そのため、k_2 の最寄りの店舗の位置は d_{j_1 – 1} から調べれば良いことがわかります。このようにして、k_{i-1} までの結果を使って d_j の探索範囲を狭めると探索の計算量は O(m + n) になります。m も計算量に入る理由は、注文 k_i の最寄りの店舗まで分かった時点では d_{j_i} まで調べていますが、k_{i + 1} の最寄りを調べる際は 1 つ戻って d_{j_i – 1} から調べるためです。
全体の計算量は d_j, k_i のソートがボトルネックになり、O(m \log m + n \log n) となります。
20. AtCoder Beginner Contest 077 C – Snuke Festival
全探索の計算量は \Omega(N^3) = 10^{15} 程度となり実行時間制限に違反しそうです。
まず、上部のパーツ A_i を固定した際に中部のパーツ B_i と下部のパーツ C_i の組み合わせの数を計算できないか考えます。入力例 1 からわかるように下部のパーツの候補は中部のパーツの選び方に依存するため、上部のパーツを固定しただけでは、中部のパーツと下部のパーツの組み合わせを計算するのは難しそうです。
次に、中部のパーツ B_i を固定したときに上部のパーツ A_i と下部のパーツ C_i の組み合わせの数を計算できないか考えます。上部のパーツの候補は A_i のうち、B_i より真に小さいもの、下部のパーツの候補は C_i のうち B_i より真に大きいものになります。これらの個数の積が組み合わせの数になります。
A_i, C_i がソートされているとして、この組み合わせの個数は下記の関数で計算量 O(\log N) で計算できます。
int64_t count(const vector<int> &A, const_vector<int> &C, int B_i)
{
int64_t cnt_A = lower_bound(A.begin(), A.end(), B_i) - A.begin();
int64_t cnt_C = C.end() - upper_bound(C.begin(), C.end(), B_i);
return cnt_A * cnt_C;
}
A_i, C_i をソートして、上記の関数を N 回実行するため、全体の計算量は O(N \log N) = 10^6 程度です。制限時間内に解答できます。
B_i もソートするとしゃくとり法で求解できます。B_i が大きくなるにつれて、条件を満たす A_i の個数は単調に非減少し、C_i の個数は単調に非増加するためです。
各 B_i に対し i_A を A_{i_A} \geq B_i を満たす最小の添字、i_C をB_i<C_{i_C} を満たす最小の添字とすると B を固定したときのパーツの組み合わせは i_A \times (N – i_C) になります。(添字は 0 始まりとします) A_i, B_i, C_i すべて単調非減少性があるため、i_A と i_C は初期値を 0 としてプログラム全体で高々 N 回しかインクリメントされません。
ソート後の処理の計算量は O(N) で、全体の計算量は O(N \log N) となります。
21. AtCoder Beginner Contest 023 D – 射撃王
風船は N \leq 100,000 個もあるため、風船を割る順番を全列挙するのは難しそうです。
この競技では、ある得点 S が与えられたときに 2 つの性質があることに着目します。
- もし、S を得ることが可能ならば、S 以上の任意の得点を得ることは可能です。
得点 S が得られるときと同じ手順で風船を割っていき、最後の 1 つを割る前に適当に休憩します。 - もし、S を得ることが不可能ならば、S 以下の任意の得点を得ることは不可能です。
得点 S 以下の得点が獲得可能と仮定すると、性質 1 を用いて S を得られます。
上記の性質より、S を得ることが可能か不可能かを判定する関数があれば、二分探索を使って得点の最小値を計算できます。
以下に着目して判定の関数を設計します。
- ある j \,(0 \leq j \leq N – 1) に対し、j 秒以内に j + 1 個より多くの風船を割る必要があるならば、S を得ることは不可能です。
風船を 1 個割るたびに 1 秒のクールタイムが発生します。
j 秒以内に割ることができる風船の個数は高々 j + 1 個です。 - 各 j に対し、j 秒以内に割る必要がある風船の個数が j + 1 以内ならば、S を得ることは可能です。
j について j = 0 から帰納的に考えると S が獲得可能であることがわかります。 - 得点 S を獲得するための風船 i を割るタイムリミットは \lfloor (S – H_i) / S_i \rfloor 秒です。
正確には (S – H_i) / S_i 秒 (有理数) ですが以下の理由から小数部分を切り捨てられます。- 1 個風船を割るたびに 1 秒のクールタイムが発生します。
- 余分な休憩を取らない場合は競技開始から風船を割るまでの時間は整数秒になります。
1, 2 から j 秒以内に割る必要がある風船の個数が分かれば S を獲得できるか判定できます。3 とバケットを使って j 秒がタイムリミットである風船の個数を数えた後に累積和を使うと、j 秒以内に割る必要がある風船の個数が計算できます。
風船 i のタイムリミットを計算する際、以下の 2 つの場合では個別の処理が必要です。
場合 1 S – H_i が負の場合
風船 i を割るときの高度が初期高度未満でなければならないことを示します。問題設定から風船 i の高度は初期高度以上のため、S を得ることは不可能と判定します。
場合 2 \lfloor (S – H_i) / S_i \rfloor が N 以上の場合
余分な休憩を取らないならば風船 i を最後 (N 番目) に割っても良いことを示します。判定に不要なタイムリミットのため、バケットに入れません。
1 つの S についての判定の計算量はタイムリミットの計算と累積和で O(N) です。計算量のオーダーは変わりませんが、累積和の for 文の中で逐次判定を行うことで累積和の計算を判定に必要な j までで打ち切ることができます。
二分探索の探索範囲の下限と上限は次のように決められます。
下限 \max_i H_i
どの風船も割られるときの高度は初期高度以上です。
上限 \max_{i} (H_i + S_i (N – 1))
休憩を取らなければ N – 1 秒にはすべての風船を割ることができます。
\max_{i} (H_i + S_i (N – 1)) – \max_i H_i \leq N \max_i S_i であるため、二分探索の実行回数のオーダーは O(\log (N \max_i S_i)) になります。
全体の計算量は O(N \log(N \max_i S_i)) = 10^7 程度で実行時間制限に違反せず解答できます。
全体の計算量 O((N \log(N \max_i S_i)) が 10^7 程度であることから、二分探索の回数が増えますが、下限と上限をより粗く定数で設定することができます。
下限 1
H_i \geq 1
上限 10^{14}
N \leq 10^5, H_i \leq 10^9, S_i \leq 10^9 から H_i + S_i (N – 1) \leq 10^9 + 10^9 (10^5 – 1) = 10^{14}
\log_2 (10^{14}) = 47 程度のため、全体の計算量は 10^7 程度です。
この見積から入力ごとの二分探索の下限と上限の算出処理を除外できます。
AtCoder の解説 のように判定の処理にソートを使う方法もあります。方法の概要は以下の通りです。
- 各風船のタイムリミットの数列をソートします。
この数列の順で風船を割ることはタイムリミットが早い風船から順に割ることになります。 - 1 の数列の j 番目 (0 始まり) の要素が j 未満ならば、S は獲得不能だと判定します。
タイムリミットが j 未満の風船が j + 1 個以上あることから、どのような順序で風船を割っても、遅くとも j 秒後に割る風船のタイムリミットは超える場合です。 - 1 の数列の各要素が添字以上の値であれば、S は獲得可能だと判定します。
タイムリミットが早い風船から順に割っていき、すべての風船をタイムリミット以内に割ることができる場合です。
各風船のタイムリミットの数列をソートする方法ですが、タイムリミットの範囲を絞れることから、以下の 2 つの方法があります。
- バケットソート
\lfloor (S – H_i) / S_i \rfloor が N 以上の場合はタイムリミットの数列に追加しない、もしくは N – 1 に丸める、として数列の値の範囲を [0, N – 1] に絞ることで計算量 O(N) でソートできます。 - 標準ライブラリの sort
C++11 以降は計算量が O(N \log N) であることが規定されているそうです。
全体の計算量はそれぞれ O((N \log(N \max_i S_i)) = 10^7 程度、O((N (\log N)^2 \log(\max_i S_i)) = 10^7 程度となり、実行時間制限を満たして解答できます。
22. AtCoder Regular Contest 054 B – ムーアの法則
高校の数学で習う増減表と指数関数の導関数が分かれば O(1) で計算できます。
x 年後に計算を開始したときの計算時間 f(x) は以下のように立式できます。
f(x) = x + 2^{-x/1.5} P
f の導関数 f^{\prime} は下記の通りです。
f^{\prime}(x) = 1 + \left (- \frac{2 \log 2}{3} \right ) 2^{-x/1.5} P
f^{\prime}(x) = 0 の解を x_0 とおくと
x_0 = \frac{3}{2\log 2} \log \frac{2 P \log 2}{3}
です。
x \geq 0 より x_0 の大きさによって場合分けします。
場合 1 x_0 \geq 0, すなわち P \geq \frac{3}{2 \log 2} の場合
増減表は下記のようになります。
| x | 0 | \cdots | x_0 | \cdots | \infty |
|---|---|---|---|---|---|
| f^{\prime} | – | 0 | + | ||
| f | P | \searrow | f(x_0) | \nearrow | \infty |
増減表から f(x) は x = x_0 で最小になり、最小値は
f(x_0) = \frac{3}{2\log 2} \log \frac{2 P \log 2}{3} + \frac{3}{2 \log 2}
です。
場合 2 x_0<0, すなわち P<\frac{3}{2 \log 2} の場合
増減表は下記のようになります。
| x | 0 | \cdots | \infty |
|---|---|---|---|
| f^{\prime} | + | ||
| f | P | \nearrow | \infty |
増減表から f(x) は x = 0 で最小になり、最小値は P です。
x_0 を二分探索で求める方法もあります。
x_0 を仮決めして f^{\prime}(x_0)<0 なら右半分、f^{\prime}(x_0)>0 なら左半分に探索範囲を絞って行きます。
下限は 0, 上限は P を設定できます。上限については y^{-1} \log y \leq e^{-1} より y = (2P \log 2) / 3 とおくと x_0 / P \leq e^{-1} となり x_0<P が示せるため P を設定できます。
終了条件は探索範囲の長さが 10^{-8} 以下になるまでとします。
二分探索の実行回数は \log_2 (10^{18} / 10^{-8}) = 87 程度です。
精度、すなわち、二分探索の結果 [x_1, x_2] まで探索範囲を絞ったとき、任意の x_3 \in [x_1, x_2] に対して |f(x_3) – f(x_0)| \leq 10^{-8} であることを確認します。
ラグランジュの平均値の定理と f の第二次導関数 f^{(2)} を使って確認します。
ラグランジュの平均値の定理から以下の式を満たす \theta \in (0, 1) が存在します。
f(x_3) – f(x_0) = f^{\prime}(\theta (x_3 – x_0) + x_0) (x_3 – x_0)
x_0, x_3 \in [x_1, x_2] であるため、
|f(x_3) – f(x_0)| \leq \max_{x \in [x_1, x_2]} |f^{\prime}(x)| |x_2 – x_1|
という不等式が成立します。
\max_{x \in [x_1, x_2]} |f^{\prime}(x)| ですが、
f^{(2)} (x) = \left (\frac{2 \log 2}{3} \right )^2 2^{-x/1.5} P > 0
より f^{\prime} は単調増加関数であるため、\max_{x \in [x_1, x_2]} |f^{\prime}(x)| = \max \{|f^{\prime}(x_1)|, |f^{\prime}(x_2)| \} となります。
f^{\prime}(x_1) のとりうる範囲を調べます。
天下り的ですが x_4 を以下のように定義します。
x_4 \coloneqq \frac{3}{2\log 2} \log \frac{P \log 2}{3}
このとき x_4 – x_0 = – 3 / 2, f^{\prime}(x_4) = -1 が成立します。
よって f^{\prime} の単調増加性と x_4<x_1 \leq x_0 の関係から -1<f^{\prime}(x_1) \leq 0 が成立します。
f^{\prime}(x_2) については単調増加性、x_0 \leq x_2 及び f^{\prime} の形から 0 \leq f^{\prime}(x_2) \leq 1 が成立します。
以上から \max_{x \in [x_1, x_2]} |f^{\prime}(x)| \leq 1 が成立するため、
|f(x_3) – f(x_0)| \leq |x_2 – x_1|
が成り立ちます。| x_2 – x_1 | \leq 10^{-8} になるまで二分探索を行ったため、|f(x_3) – f(x_0)| \leq 10^{-8} となり、要求された精度を満たすことを確認できます。
f^{(2)}(x)>0 より f が下に凸であることがわかるため、三分探索を使って求解することもできます。
三分探索については 二分探索と三分探索の数学的な解説とバグらせない実装方法 に解説があります。
下限を 0, 上限を P, 終了条件を探索範囲の長さが 10^{-8} 以下になるまでとすると、三分探索の実行回収は \log_{3/2} (10^{18} / 10^{-8}) = 148 回程度です。
精度については二分探索のときと同様の方法で確認できます。
23. JOI 2008 本選 3 – ダーツ
全探索すると \Omega(N^4) = 10^{12} 程度で実行時間制限に違反しそうです。3 本目のダーツの得点までは探索し、4 本目のダーツについては合計が M 以下になる最大の P_i を二分探索を使って選ぶことにすると計算量は \Omega(N^3 \log N) = 10^{10} 程度となり、全探索よりは計算量は減りますが、まだ実行時間制限を満たすのは難しそうです。
4 本のダーツの得点の組み合わせの列挙から 3 本のダーツの得点の組み合わせの列挙 + 二分探索に変更すると計算量が減りました。このことを踏まえて 2 本のダーツの得点の組み合わせから最大の得点を計算できないか考えます。
3 本のダーツの得点の組み合わせの列挙 + 二分探索の際は P_1, \dots, P_N を二分探索しましたが、二分探索の対象を 2 本のダーツの得点の合計の一覧とすれば、はじめに列挙するのは 2 本のダーツの組み合わせで十分です。言い換えると 2 本のダーツの組み合わせを列挙し、残りの 2 本のダーツの合計については 4 本の合計が M 以下になる値を二分探索で探します。
下記の手順で計算します。
- ダーツ 2 本の得点の合計の数列 Q_1, \dots, Q_K を作成します。K = (N + 1)^2 とおきます。
- 数列 Q_1, \dots, Q_K をソートします。
- 各 Q_j に対し M – Q_j 以下の最大の Q_{i_j} を二分探索で見つけ、Q_j + Q_{i_j} の最大値を探索します。
ダーツを投げない選択肢もあるため、数列 Q_1, \dots, Q_K には P_i + 0 や 0 + 0 も入れることに注意します。
計算量は O(N^2 \log N) = 10^7 程度で実行時間制限に違反せずに解答できます。
数列 Q_1, \dots, Q_K を降順にソートすると lower_bound を使って Q_{j_i} を見つけられます。
数列 Q_1, \dots, Q_K を昇順に並べた際、j_1 \leq j_2 ならば Q_{j_1} \leq Q_{j_2} であることから Q_{i_{j_1}} \geq Q_{i_{j_2}} となり、i_{j_1} \geq i_{j_2} が成立します。そのため、M – Q_j 以下の最大の Q_{i_j} を探すのはしゃくとり法でも可能です。計算量は {Q_i}_i のソートが必要なため、O(N^2 \log N) です。
