コンテンツにスキップ

ブログ

ABC482 E - Diameter Endpoint Colors

NN 頂点の木 TT があり、頂点 vv は色 CvC_v で塗られています。同じ色で、間の距離(パスの辺の本数)が木の直径と等しい頂点の組 (u,v)(u, v)(u<vu < v)の個数を求める問題です(N≤2×105N \le 2 \times 10^5)。

直径の長さを DD とします。木の直径の中点を中心と呼ぶと、距離がちょうど DD になる組は中心を使って次のように分けられます。

  • D=2rD = 2r が偶数のとき、中心は頂点 cc です。どの頂点も cc からの距離が rr 以下なので、距離が DD になる組は、cc からの距離がどちらも rr で、パスが cc を通るもの、つまり cc の異なる隣接頂点の側(部分木)にあるものです。
  • D=2r+1D = 2r + 1 が奇数のとき、中心は辺 (c1,c2)(c_1, c_2) です。この辺を除いて c1c_1 側と c2c_2 側に分けると、距離が DD になる組は、c1c_1 側で c1c_1 からの距離が rr の頂点と、c2c_2 側で c2c_2 からの距離が rr の頂点の組です。

どちらの場合も、直径の端点になる頂点をいくつかのグループに分けると、「距離が DD になる」ことと「異なるグループに属する」ことが同値になります。偶数のときは cc の隣接頂点ごと、奇数のときは c1c_1 側と c2c_2 側の 22 つがグループです。

あとは、異なるグループにある同じ色の頂点の組を数えればよいです。グループを順に見ていき、色ごとに「それまでのグループに含まれる頂点の個数」を持っておきます。各頂点について、その色の個数を答えに足してから、グループ内の頂点をまとめて個数に加えます。

直径と中心は BFS を 22 回するなどして求められるので、全体の計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/graph/tree_util.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N);
Tree<ll> tree(N);
tree.read();
VL(C, N);
C--;
vl cnt(N);
ll ans = 0;
for (auto g : tree_diameter_endpoint_groups(tree)) {
for (ll u : g)
ans += cnt[C[u]];
for (ll u : g)
cnt[C[u]]++;
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

tree_diameter_endpoint_groups は、上の解法のとおり直径の端点をグループに分けて返す関数です。C-- で色を 0 始まりにし、cnt に色ごとの個数を持っています。

使用ライブラリ:cpp_include@cb82602

ABC482 D - Wannabe Zombie

数直線上に NN 人が立っていて、人 ii の座標は XiX_i です(XiX_i は偶数で、X1<X2<⋯<XNX_1 < X_2 < \cdots < X_N)。時刻 00 に人 kk だけがゾンビになり、以降は全員が速さ 11 以下で自由に動けます。ゾンビと人が同じ座標にいると、その人はゾンビになります。各 kk について、全員がゾンビになる時刻の最小値を求める問題です(N≤2×105N \le 2 \times 10^5)。

以下、人 kk より左の人(人 1,…,k−11, \dots, k - 1)を「左側」、右の人を「右側」と呼びます。

人 jj がゾンビになったとき、その感染は「人 kk が誰かと出会い、その人が別の誰かと出会い、……」という連鎖で人 jj まで届いています。連鎖をたどって各区間の人の動きをつなげると、時刻 00 に XkX_k を出発し、速さ 11 以下で動いて、人 jj と出会う経路が 1 本できます。これを人 jj への感染経路と呼びます。

人 jj は時刻 tt に XjX_j から距離 tt 以内にいて、感染経路も XkX_k から距離 tt 以内にいます。なので、人 jj がゾンビになる時刻は ∣Xj−Xk∣/2|X_j - X_k| / 2 以上です。

k=1k = 1 なら、全員が人 11 に向かって速さ 11 で進み、人 11 は右に速さ 11 で進めば、人 jj とは時刻 (Xj−X1)/2(X_j - X_1) / 2 に出会います。上の下界と一致するので、答えは (XN−X1)/2(X_N - X_1) / 2 です。k=Nk = N のときも同じです。

次の動き方を考えます。

  • 左側の人は右に、右側の人は左に、速さ 11 で進み続ける。
  • 人 kk は左に速さ 11 で進む。
  • 人 k−1k - 1 は人 kk と出会ったら、向きを変えて右に速さ 11 で進む。

人 kk が左に進むので、左側の人 jj は時刻 (Xk−Xj)/2(X_k - X_j) / 2 にゾンビになります。人 k−1k - 1 は向きを変える前も右に速さ 11 で進んでいたので、ずっと「時刻 tt に座標 Xk−1+tX_{k-1} + t」にいます。なので、右側の人 jj は時刻 (Xj−Xk−1)/2(X_j - X_{k-1}) / 2 にゾンビになります(人 k−1k - 1 がゾンビになるより前に出会うことはありません)。全員がゾンビになる時刻は

max⁡(Xk−X1, XN−Xk−1)2\frac{\max(X_k - X_1,\ X_N - X_{k-1})}{2}

です。左右を入れ替えて、人 kk が先に右へ進む動き方では max⁡(XN−Xk, Xk+1−X1)/2\max(X_N - X_k,\ X_{k+1} - X_1) / 2 になります。答えはこの 22 つの小さいほうです。

この 22 つより早くはできないことを確かめます。人 kk が最初に誰かと出会う時刻を τ\tau、出会う人を pp とし、pp が左側だとします。人 NN への感染経路は、時刻 τ\tau まではまだ人 kk の動きそのものなので、時刻 τ\tau には人 pp と同じ座標、つまり Xp+τ≤Xk−1+τX_p + \tau \le X_{k-1} + \tau 以下の座標にいます。そこから速さ 11 以下で人 NN と出会うので、人 NN がゾンビになる時刻は (XN−Xk−1)/2(X_N - X_{k-1}) / 2 以上です。人 11 についての (Xk−X1)/2(X_k - X_1) / 2 以上という下界とあわせて、11 つ目の値以上になります。pp が右側のときも同様に 22 つ目の値以上になります。

XiX_i はすべて偶数なので、答えは整数です。計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
void solve() {
LL(N);
VL(X, N);
rep(k, N) {
if (k == 0 || k == N - 1) {
print((X.back() - X.front()) / 2);
} else {
print(min(max(X[k] - X.front(), X.back() - X[k - 1]) / 2, max(X.back() - X[k], X[k + 1] - X.front()) / 2));
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

人は 0 始まりで、N=1N = 1 のときも k == 0 の分岐で 00 を出力します。

使用ライブラリ:cpp_include@cb82602

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 未満の要素の個数です。

ABC482 B - Blank Bingo

5×55 \times 5 のマス目があり、いくつかのマスに印が付いています(o が印あり、. が印なし)。縦・横・斜めのいずれか一列の 55 マスすべてに印が付いた状態(ビンゴ)にするために、追加で付ける印の個数の最小値を求める問題です。

ある一列でビンゴにするには、その列で印が付いていないマスすべてに印を付ける必要があり、それで十分です。なので、各列について . の個数を数え、その最小値が答えです。

調べる列は、横 55 本・縦 55 本・斜め 22 本の計 1212 本です。

Python
S = [input() for i in range(5)]
l = S.copy()
for i in range(5):
l.append("".join(S[j][i] for j in range(5)))
l.append("".join(S[j][j] for j in range(5)))
l.append("".join(S[j][4 - j] for j in range(5)))
print(min(i.count(".") for i in l))

l に 1212 本の列を文字列として集めています。横の列は SiS_i そのもの、縦の列は各行の ii 文字目をつなげたもの、斜めの列は (j,j)(j, j) と (j,4−j)(j, 4 - j) のマスをつなげたものです(0 始まり)。

ABC482 A - Nigiri

o と . からなる文字列 SS が与えられます。SS に含まれる o の個数が奇数なら odd、偶数なら even を出力する問題です。

o の個数を数えて 22 で割った余りを求めます。余りが 00 なら even、11 なら odd なので、["even", "odd"] の余り番目を出力すれば答えになります。

Python
print(["even", "odd"][input().count("o") % 2])

多角形のモーメントとは何か

shogo-library の多角形のライブラリには、PolygonMoment という型と polygon_edge_moment という関数があります。どちらも「面積と一次モーメント」を扱うものですが、モーメントという言葉はなじみが薄いと思います。この記事では、モーメントとは何か、なぜ重心を求めるのに便利なのか、ライブラリでは何ができるのかを説明します。

数直線上に、重さ m1,m2,…,mnm_1, m_2, \dots, m_n のおもりが位置 x1,x2,…,xnx_1, x_2, \dots, x_n に置かれているとします。このとき

  • 零次モーメント:M0=∑imiM_0 = \sum_i m_i(重さの合計)
  • 一次モーメント:M1=∑imixiM_1 = \sum_i m_i x_i(重さ × 位置の合計)
  • 二次モーメント:M2=∑imixi2M_2 = \sum_i m_i x_i^2(重さ × 位置の 2 乗の合計)

をモーメントと呼びます。kk 次モーメントは「重さ × 位置の kk 乗」の合計です。

重心(重さの平均位置)は g=M1/M0g = M_1 / M_0 です。一次モーメントを零次モーメントで割ると重心になる、というのがこの記事でいちばん大事な式です。

名前の由来はてこです。位置 cc を支点にすると、おもり ii が回そうとする強さ(力のモーメント)は mi(xi−c)m_i (x_i - c) で、合計は M1−cM0M_1 - c M_0 です。これが 00 になる、つまり釣り合う支点が c=M1/M0c = M_1 / M_0、すなわち重心です。

平面の図形 DD では、おもりの代わりに面積を重さと考え、和を積分に置き換えます。

S=∬D1 dA,Mx=∬Dx dA,My=∬Dy dAS = \iint_D 1 \, dA, \qquad M_x = \iint_D x \, dA, \qquad M_y = \iint_D y \, dA

SS は面積(零次モーメント)、(Mx,My)(M_x, M_y) は一次モーメントです。図形の重心は

(gx,gy)=(MxS,MyS)(g_x, g_y) = \left( \frac{M_x}{S}, \frac{M_y}{S} \right)

です。言いかえると、一次モーメントは「面積 × 重心」です:(Mx,My)=S⋅(gx,gy)(M_x, M_y) = S \cdot (g_x, g_y)。

モーメントは足せる、重心は足せない

Section titled “モーメントは足せる、重心は足せない”

モーメントが便利なのは、図形を分割したとき、各部分のモーメントを足すと全体のモーメントになることです。積分の範囲を分けているだけなので当然です。面積が足せるのと同じ理由で、一次モーメントも足せます。

一方、重心はそのままでは足せません。図形 AA と BB をくっつけた図形の重心は、AA の重心と BB の重心の平均ではなく、面積で重みを付けた平均

g=SAgA+SBgBSA+SBg = \frac{S_A g_A + S_B g_B}{S_A + S_B}

です。分子は一次モーメントの和、分母は面積の和なので、これは「モーメントを足してから割る」と言っているだけです。

例として、L 字形の図形 (0,0),(2,0),(2,1),(1,1),(1,2),(0,2)(0,0), (2,0), (2,1), (1,1), (1,2), (0,2) の重心を求めます。

  • 下の長方形 [0,2]×[0,1][0,2] \times [0,1]:S=2S = 2、重心 (1,0.5)(1, 0.5)、一次モーメント (2,1)(2, 1)
  • 左上の長方形 [0,1]×[1,2][0,1] \times [1,2]:S=1S = 1、重心 (0.5,1.5)(0.5, 1.5)、一次モーメント (0.5,1.5)(0.5, 1.5)

足すと S=3S = 3、一次モーメント (2.5,2.5)(2.5, 2.5) なので、重心は (2.5/3,2.5/3)=(5/6,5/6)(2.5/3, 2.5/3) = (5/6, 5/6) です。

引き算もできます。穴の開いた図形のモーメントは「外側のモーメント − 穴のモーメント」です。このように足し算と引き算ができることが、あとで累積和に載せるときに効いてきます。

多角形のモーメントを辺ごとに分解する

Section titled “多角形のモーメントを辺ごとに分解する”

三角形 a,b,ca, b, c の面積は外積で S=12(b−a)×(c−a)S = \frac{1}{2} (b - a) \times (c - a)、重心は 3 頂点の平均 a+b+c3\frac{a + b + c}{3} です。したがって一次モーメントは

S⋅a+b+c3S \cdot \frac{a + b + c}{3}

です。

原点を頂点にした三角形に分ける

Section titled “原点を頂点にした三角形に分ける”

反時計回りの多角形 p0,p1,…,pn−1p_0, p_1, \dots, p_{n-1} を、辺 pi→pi+1p_i \to p_{i+1} ごとに原点 OO と結んだ三角形 O,pi,pi+1O, p_i, p_{i+1} に分けます(pn=p0p_n = p_0)。この三角形の符号付き面積は 12 pi×pi+1\frac{1}{2} \, p_i \times p_{i+1} で、OO から見て反時計回りなら正、時計回りなら負です。

O p₀ p₁ p₂ p₃
青は正(反時計回り)の三角形、赤は負(時計回り)の三角形。太線が多角形。

図では Op0p1O p_0 p_1, Op1p2O p_1 p_2, Op2p3O p_2 p_3 の 3 つが正で、これらを合わせると多角形よりはみ出します。はみ出した部分はちょうど負の三角形 Op3p0O p_3 p_0 と重なり、打ち消されます。凹多角形でも、原点が多角形の外にあっても同じことが起き、各点は「多角形の内部なら合計 1 回、外部なら合計 0 回」数えられます(正確には、その点のまわりを多角形が何周するか、つまり回転数の回数だけ数えられます)。

面積だけでなく一次モーメントも積分なので、同じように符号付きで足せば打ち消し合いが起きます。三角形 O,pi,pi+1O, p_i, p_{i+1} の重心は pi+pi+13\frac{p_i + p_{i+1}}{3} なので、多角形全体は

S=12∑ipi×pi+1,(Mx,My)=16∑i(pi×pi+1)(pi+pi+1)S = \frac{1}{2} \sum_i p_i \times p_{i+1}, \qquad (M_x, M_y) = \frac{1}{6} \sum_i (p_i \times p_{i+1}) (p_i + p_{i+1})

となります。面積の式は、よく知られた外積で多角形の面積を求める式(靴ひも公式)そのものです。一次モーメントの式はそれを一歩進めたものです。

polygon_edge_moment(p, q) は、辺 p→qp \to q の寄与(三角形 O,p,qO, p, q の符号付き面積と一次モーメント)を返します。分母の 2 と 6 を払った値を持っているので、整数座標なら誤差なく計算できます。

メンバ中身式
area2面積の 2 倍p×qp \times q
mxxx の一次モーメントの 6 倍(p×q)(px+qx)(p \times q)(p_x + q_x)
myyy の一次モーメントの 6 倍(p×q)(py+qy)(p \times q)(p_y + q_y)

全辺の寄与を足すと、多角形全体の PolygonMoment になります。area() は area2 / 2、centroid() は

gx=MxS=mx/6area2/2=mx3⋅area2g_x = \frac{M_x}{S} = \frac{\texttt{mx} / 6}{\texttt{area2} / 2} = \frac{\texttt{mx}}{3 \cdot \texttt{area2}}

を計算しています(gyg_y も同様)。polygon_centroid は、これを全辺について足して重心を返すだけの関数です。

さきほどの L 字形で確かめると、辺ごとの (area2, mx, my) は

辺area2mxmy
(0,0)→(2,0)(0,0) \to (2,0)000
(2,0)→(2,1)(2,0) \to (2,1)282
(2,1)→(1,1)(2,1) \to (1,1)132
(1,1)→(1,2)(1,1) \to (1,2)123
(1,2)→(0,2)(1,2) \to (0,2)228
(0,2)→(0,0)(0,2) \to (0,0)000
合計61515

で、面積 6/2=36/2 = 3、重心 15/(3⋅6)=5/615 / (3 \cdot 6) = 5/6 と、長方形に分けて求めた結果と一致します。

座標が 10910^9 程度だと mx は 102710^{27} 程度になるので、整数座標のときは __int128_t で値を持ちます。

部分多角形の面積と重心を O(1)O(1) で求める

Section titled “部分多角形の面積と重心を O(1)O(1)O(1) で求める”

いちばんの使いみちです。多角形の頂点 u,u+1,…,vu, u+1, \dots, v を順に結んで閉じた部分多角形の面積や重心を、たくさん求めたいとします。

部分多角形の辺は、元の多角形の辺 u→u+1,…,v−1→vu \to u+1, \dots, v-1 \to v と、閉じる辺 v→uv \to u です。モーメントは辺ごとの寄与の和なので、前者は寄与の累積和で O(1)O(1) で求まり、そこに閉じる辺の寄与を 1 つ足せば完成です。PolygonMoment は + と - が使えるので、そのまま累積和に載せられます。頂点の番号が一周をまたぐ場合もあるので、円環上の区間和 CircularSum を使うと便利です。

using P = Vector<long long>;
std::vector<PolygonMoment<long long>> e(n);
for (int i = 0; i < n; i++) e[i] = polygon_edge_moment(ps[i], ps[(i + 1) % n]);
CircularSum cs(e);
// 頂点 u, u+1, ..., v を結んだ部分多角形
auto m = cs.sum(u, v) + polygon_edge_moment(ps[v], ps[u]);
m.area(); // 符号付き面積
m.centroid(); // 重心

辺の寄与は原点の位置によって変わりますが、閉じた多角形について足した合計は原点によりません(打ち消し合いの議論は原点の位置を問わないからです)。途中までの和だけでは意味のある値にならず、閉じる辺を足して初めて部分多角形の値になる、という点に注意してください。

凸多角形を対角線で 2 つに切ったときの面積の差を最小化する、といった問題では、切り方ごとに両側の面積が O(1)O(1) で求まるので、尺取り法や二分探索と組み合わせられます。重心が要る問題でも同じように扱えます。

頂点 pip_i を動かすと、寄与が変わるのは辺 pi−1→pip_{i-1} \to p_i と pi→pi+1p_i \to p_{i+1} の 2 つだけです。PolygonMoment の和は結合的なので、セグメント木に載せれば、頂点の更新と部分多角形のモーメントの取得がそれぞれ O(log⁡n)O(\log n) でできます。

離れた複数の多角形をまとめた図形の重心は、それぞれの PolygonMoment を足してから centroid() を呼べば求まります。穴の開いた図形は、外側から穴を引きます。時計回りの多角形の寄与は符号が反転するので、穴を時計回りで与えれば、外側と穴の寄与をすべて足すだけでも同じ結果になります。

整数座標なら area2, mx, my はすべて整数で、重心は gx=mx/(3⋅area2)g_x = \texttt{mx} / (3 \cdot \texttt{area2}) という分数です。2 つの図形の重心の xx 座標の大小や、重心がある点と一致するかどうかは、分母を払って整数のまま比べられます(分母の符号に注意してください)。centroid() は double を返すので、厳密な判定が必要なときはメンバを直接使います。

ライブラリにはありませんが、同じ考え方で二次モーメントも辺ごとに分解できます。

Ixx=∬Dx2 dA=112∑i(pi×pi+1)(xi2+xixi+1+xi+12)I_{xx} = \iint_D x^2 \, dA = \frac{1}{12} \sum_i (p_i \times p_{i+1}) (x_i^2 + x_i x_{i+1} + x_{i+1}^2)

(xix_i は pip_i の xx 座標。IyyI_{yy} も同様)。L 字形で計算すると Ixx=3I_{xx} = 3 になり、長方形ごとに積分した 83+13\frac{8}{3} + \frac{1}{3} と一致します。

二次モーメントがあると、たとえば図形内の一様ランダムな点と点 cc の距離の 2 乗の期待値が

Ixx+IyyS−2 c⋅g+∣c∣2\frac{I_{xx} + I_{yy}}{S} - 2 \, c \cdot g + |c|^2

で求まります。物理でいう慣性モーメント(回転させにくさ)も、この Ixx+IyyI_{xx} + I_{yy} です。

  • kk 次モーメントは「重さ × 位置の kk 乗」の合計で、図形なら積分。零次は面積、一次は「面積 × 重心」
  • モーメントは図形を分割すると足し算・引き算できるが、重心はそのままでは足せない。だからモーメントで持って、最後に割る
  • 多角形は原点と各辺の三角形に符号付きで分けられるので、モーメントは辺ごとの寄与の和になる
  • 寄与の累積和を取れば、部分多角形の面積と重心が O(1)O(1) で求まる。PolygonMoment はそのための型

ABC477 F - Count Cells in a Window

NN 行 MM 列のグリッドがあり、上から ii 行目は左から LiL_i 列目から RiR_i 列目までのマスが黒、それ以外のマスが白です。QQ 個のクエリで A,B,C,DA, B, C, D が与えられるので、AA 行目から BB 行目、CC 列目から DD 列目までの長方形に含まれる黒いマスの個数をそれぞれ答える問題です(1≤N,M,Q≤2×1051 \le N, M, Q \le 2 \times 10^5)。

上から kk 行目までのうち、CC 列目から DD 列目までにある黒いマスの個数を f(k)f(k) とすると、クエリの答えは f(B)−f(A−1)f(B) - f(A - 1) です。

列ごとの黒いマスの個数を表す長さ MM の配列を用意し、11 行目から順に、ii 行目を加えるたびに LiL_i 列目から RiR_i 列目までに 11 を足していきます。kk 行目まで加えたところでこの配列の CC 列目から DD 列目までの和をとれば、f(k)f(k) が求まります。

そこで、各クエリを「A−1A - 1 行目まで加えたときに ff を引く」と「BB 行目まで加えたときに ff を足す」の 2 つに分け、行の順にまとめて処理します(クエリを先に全部読んでおくので、オフラインで解くことになります)。

必要な操作は、配列の区間に 11 を足すことと、区間の和を求めることです。これは区間加算・区間和の遅延評価セグメント木か、BIT を 2 本使う方法で、どちらも O(log⁡M)O(\log M) でできます。クエリを行の順にソートするのとあわせて、全体の計算量は O(N+M+Qlog⁡Q+(N+Q)log⁡M)O(N + M + Q \log Q + (N + Q) \log M) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/lazy-segtree.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, Q);
VAL(LR, N, 2);
VAL(ABCD, Q, 4);
val<5> tmp;
for (auto &[l, r] : LR)
l--;
rep(i, Q) {
auto &[a, b, c, d] = ABCD[i];
a--, c--;
tmp.push_back({a, c, d, -1, i});
tmp.push_back({b, c, d, 1, i});
}
sort(tmp);
RAddSumQ<ll> seg(M);
ll k = 0;
vl ans(Q);
for (auto [x, c, d, y, i] : tmp) {
while (k < x) {
auto [l, r] = LR[k++];
seg.apply(l, r, 1);
}
ans[i] += y * seg.prod(c, d);
}
rep(i, Q) print(ans[i]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

VAL(LR, N, 2) は長さ 22 の配列を NN 個読み込むマクロです。列は 0 始まりの半開区間 [Li−1,Ri)[L_i - 1, R_i)、[C−1,D)[C - 1, D) で扱っています。

tmp には各クエリを (行数, C, D, 符号, クエリ番号) の 2 つに分けて入れ、行数の順にソートしています。k はすでに加えた行数で、行数 x のクエリを処理する前に x 行目まで加えます。RAddSumQ は区間加算・区間和の遅延評価セグメント木で、apply(l, r, 1) で区間に 11 を足し、prod(c, d) で区間の和を求めています。

使用ライブラリ:cpp_include@6519da7

repovive standard round 9 A - Pair Distances

位置 1,2,…,n1, 2, \dots, n に nn 人が並んでいます(nn は偶数)。全員を 2 人ずつのペアに分けます。人 ii は「自分とペアの相手の位置の差は did_i だ」と言っています。全員の言っていることが正しくなるようにペアに分けられるか判定する問題です(2≤n≤2×1052 \le n \le 2 \times 10^5、1≤di<n1 \le d_i < n、テストケースは最大 10410^4 個で nn の総和は 2×1052 \times 10^5 以下)。

左から順に、まだ相手が決まっていない人を見ていきます。

まだ相手が決まっていない人のうち一番左の人を ii とします。ii の相手は位置 i−dii - d_i か i+dii + d_i にいるはずです。しかし ii より左の人はすでに全員相手が決まっているので、i−dii - d_i は候補になりません。したがって、相手は j=i+dij = i + d_i に決まります。

このペアが作れるのは、次の 3 つをすべて満たすときです。

  • j≤nj \le n である。
  • jj の相手がまだ決まっていない。
  • dj=did_j = d_i である(jj から見ても相手との距離は did_i なので)。

満たしていれば ii と jj をペアにして先に進み、満たしていなければ答えは No です。最後までペアを作れれば答えは Yes です。相手が一通りにしか決まらないので、この方法で作れなければ、どう分けても作れません。

計算量は O(n)O(n) です。

Python
for _ in range(int(input())):
N = int(input())
D = list(map(int, input().split()))
pair = [None] * N
for i in range(N):
if pair[i] is not None:
continue
j = i + D[i]
if j not in range(N) or pair[j] is not None or D[j] != D[i]:
print("No")
break
pair[i] = j
pair[j] = i
else:
print("Yes")

位置は 0 始まりにしています。pair[i] は人 ii の相手の位置で、まだ決まっていなければ None です。j not in range(N) で、相手の位置が列の外に出ていないかを調べています。

for 文に付けた else は、break せずに最後まで回ったときだけ実行されます。途中で No を出力して break したときは Yes を出力しません。

ABC479 F - Narrow Passage

NN 人が数直線上に立っていて、人 ii ははじめ座標 SiS_i にいます。1 回の操作では、1 人を選んで座標 xx から x−1x - 1 か x+1x + 1 に動かします。移動先に人がいれば、その人は同時に座標 xx に移ります(2 人が入れ替わります)。

すべての人 ii が座標 TiT_i にいる状態にするための操作回数の最小値を求める問題です(1≤N≤2×1051 \le N \le 2 \times 10^5、0≤Si,Ti≤1090 \le S_i, T_i \le 10^9、SiS_i はそれぞれ相異なり、TiT_i もそれぞれ相異なる)。

1 回の操作は、次のどちらかです。

  • 空いている座標への移動:1 人の座標が 11 変わります。人の並び順は変わりません。
  • 隣の人との入れ替え:隣り合う 2 人の並び順が入れ替わります。2 人がいる座標の集合は変わりません。

人の並び順の変化は入れ替えでしか起こらないので、入れ替えの回数は、はじめと最後で前後関係が逆になっている 2 人の組の個数以上必要です。これは、人を SiS_i の小さい順に並べ、それぞれの TT での順位を書いた列の転倒数です。

空いている座標への移動の回数を見積もるため、人 ii について

ui=(人 i の座標)−(人 i より左にいる人数)u_i = (\text{人 } i \text{ の座標}) - (\text{人 } i \text{ より左にいる人数})

を考えます。座標がすべて 00 以上なら、uiu_i は座標 00 から人 ii の手前までにある空いている座標の個数です。

  • 空いている座標へ移動すると、動いた人の uiu_i がちょうど 11 変わり、ほかの人の uu は変わりません。
  • 入れ替えでは、右に動いた人は座標が 11 増えて左にいる人数も 11 増え、左に動いた人はどちらも 11 減るので、2 人とも uu は変わりません。

SS の中で SiS_i より小さいものの個数を rir_i、TT の中で TiT_i より小さいものの個数を ri′r'_i とすると、はじめの uiu_i は Si−riS_i - r_i、最後の uiu_i は Ti−ri′T_i - r'_i です。したがって、空いている座標への移動は少なくとも ∑i∣最後の ui−はじめの ui∣\sum_i |\text{最後の } u_i - \text{はじめの } u_i| 回必要です。

1 回の操作で減らせるのは、転倒数と ∑i∣ui の差∣\sum_i |u_i \text{ の差}| のどちらか一方だけで、それも 11 ずつです。したがって、答えは少なくとも

(転倒数)+∑i∣最後の ui−はじめの ui∣(\text{転倒数}) + \sum_i |\text{最後の } u_i - \text{はじめの } u_i|

です。実はこの回数で必ず達成でき、これが答えになります。現在の状態で、上の値を 11 減らす操作が必ずあることを示します。以下、目標の uiu_i を ui′u'_i と書きます。左から並べたとき uu は広義単調増加で、2 人の uu が等しいのは座標が隣り合っているときです。u′u' も目標の並び順で広義単調増加です。

  • ui<ui′u_i < u'_i の人がいるとき:そのような人のうち最も右にいる人を ii とします。ii の右隣の座標が空いていれば、ii を右に動かすと uiu_i が ui′u'_i に 11 近づきます。右隣に人 jj がいるとき、uj=uiu_j = u_i です。jj は ii より右にいるので uj≥uj′u_j \ge u'_j で、uj′≤uj=ui<ui′u'_j \le u_j = u_i < u'_i です。目標では u′u' が並び順に広義単調増加なので、jj は ii より左に来るはずです。ii と jj を入れ替えると、転倒数が 11 減ります。
  • ui>ui′u_i > u'_i の人だけがいるとき:左右を逆にして同様です。
  • すべての人で ui=ui′u_i = u'_i のとき:転倒数が正なら、目標と前後が逆の隣り合う 2 人 ii(左)、jj(右)がいます。ui≤uju_i \le u_j かつ uj′≤ui′u'_j \le u'_i なので ui=uju_i = u_j となり、2 人は座標が隣り合っています。入れ替えれば転倒数が 11 減ります。

SS と TT をそれぞれソートして順位を求め、転倒数を BIT などで数えれば、計算量は O(Nlog⁡N)O(N \log N) です。

Python
N = int(input())
S = list(map(int, input().split()))
T = list(map(int, input().split()))
os = sorted(range(N), key=S.__getitem__)
ot = sorted(range(N), key=T.__getitem__)
rs = [0] * N
rt = [0] * N
for k in range(N):
rs[os[k]] = k
rt[ot[k]] = k
ans = 0
bit = [0] * (N + 1)
for k, i in enumerate(os):
x = rt[i] + 1
c = 0
while x > 0:
c += bit[x]
x -= x & -x
ans += k - c
x = rt[i] + 1
while x <= N:
bit[x] += 1
x += x & -x
for i in range(N):
ans += abs((T[i] - rt[i]) - (S[i] - rs[i]))
print(ans)

os は人を SiS_i の小さい順に並べたもので、rs[i] は人 ii の SS での順位(0 始まり)、つまり SiS_i より小さい SS の個数です。rt も同様に TT での順位です。

転倒数は、os の順に人を見ながら、それまでに見た人のうち TT での順位が人 ii より小さい人数 c を BIT で数え、k - c(順位が大きい人数)を足して求めています。最後に ∣ui′−ui∣|u'_i - u_i| を足しています。

C++
#include "shogo-library/base/all"
#include "shogo-library/others/inversion-number.hpp"
#include "shogo-library/utility/vector_func.hpp"
void solve() {
LL(N);
VL(S, N);
VL(T, N);
vl rs = rank(S), rt = rank(T);
ll ans = inversion_number(select(rt, argsort(S)));
rep(i, N) ans += abs((T[i] - rt[i]) - (S[i] - rs[i]));
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

rank(S) は各要素の SS での順位(0 始まり)、argsort(S) は SS の小さい順に並べた添字の列です。select(rt, argsort(S)) で、人を SS の小さい順に並べたときの TT での順位の列を作り、inversion_number でその転倒数を求めています。inversion_number はマージソートで転倒数を数えます。

使用ライブラリ:cpp_include@6519da7

SamCoding Round 9 (Div. 4) D - Printer Queue

nn 人の生徒が 1 台のプリンターで書類を印刷します。生徒 ii の書類の印刷には tit_i 秒かかります。プリンターは一度に 1 つの書類しか印刷できず、時刻 00 から休みなく順に印刷します。各生徒の待ち時間を「時刻 00 から自分の書類が印刷し終わるまでの時間」とするとき、印刷する順番をうまく決めて、待ち時間の合計の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、1≤ti≤1061 \le t_i \le 10^6)。

印刷時間の短い順に印刷するのが最適です。

jj 番目に印刷する書類の印刷時間を sjs_j とすると、jj 番目の生徒の待ち時間は s1+s2+⋯+sjs_1 + s_2 + \dots + s_j です。待ち時間の合計では、sjs_j は jj 番目以降の n−j+1n - j + 1 人の待ち時間に含まれるので、

∑j=1n(n−j+1) sj\sum_{j=1}^{n} (n - j + 1) \, s_j

になります。前に印刷するものほど大きな係数が掛かるので、短いものを前に置けばよいです。

実際、隣り合う sj>sj+1s_j > s_{j+1} があれば、2 つを入れ替えると合計は sj−sj+1>0s_j - s_{j+1} > 0 だけ減ります。そのため、最適な順番では印刷時間が短い順に並んでいます。

あとは tt をソートして累積和をとり、その合計を出力すれば答えです。O(nlog⁡n)O(n \log n) です。

Python
from itertools import accumulate
input()
print(sum(accumulate(sorted(list(map(int, input().split()))))))

accumulate でソート後の累積和、つまり各生徒の待ち時間を求め、その合計を出力しています。

SamCoding Round 9 (Div. 4) G - No Cheating

nn 個の椅子に kk 人の生徒を、どの 2 人も隣り合わないように座らせる方法の数を 109+710^9 + 7 で割った余りで求める問題です。どの椅子に人が座るかだけを区別します。クエリが qq 個あり、それぞれで次の 2 種類のどちらかが与えられます(1≤q≤1051 \le q \le 10^5、3≤n≤1063 \le n \le 10^6、0≤k≤n0 \le k \le n)。

  • t=1t = 1:椅子が 11 列に並んでいる。椅子 ii と隣り合うのは椅子 i−1,i+1i - 1, i + 1 だけ。
  • t=2t = 2:椅子が円形に並んでいる。上に加えて、椅子 11 と椅子 nn も隣り合う。

k=0k = 0 のときは 11 通り、k=1k = 1 のときはどちらの場合も nn 通りなので、以下では k≥2k \ge 2 とします。

空いている椅子 n−kn - k 個を先に並べると、その間と両端に n−k+1n - k + 1 個の隙間ができます。生徒が隣り合わないのは、生徒を異なる隙間に 1 人ずつ入れるときなので、答えは隙間から kk 個を選ぶ方法の数

(n−k+1k)\binom{n - k + 1}{k}

です。n−k+1<kn - k + 1 < k、つまり 2k−1>n2k - 1 > n のときは 00 です。

1 列の場合の数え方では、椅子 11 と椅子 nn の両方に座る並べ方も数えてしまっているので、それを引きます。

椅子 11 と椅子 nn の両方に座るとき、椅子 22 と椅子 n−1n - 1 は空いていなければなりません。残りの k−2k - 2 人は、椅子 33 から n−2n - 2 までの n−4n - 4 個の椅子に 1 列の場合と同じ条件で座るので、((n−4)−(k−2)+1k−2)=(n−k−1k−2)\binom{(n - 4) - (k - 2) + 1}{k - 2} = \binom{n - k - 1}{k - 2} 通りです。よって答えは

(n−k+1k)−(n−k−1k−2)\binom{n - k + 1}{k} - \binom{n - k - 1}{k - 2}

です。円形では kk 人の間に空いた椅子が kk 個以上必要なので、2k>n2k > n のときは 00 です。

二項係数は、10610^6 程度までの階乗とその逆元を前計算しておけば O(1)O(1) で求まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/math/combinatorics.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint1000000007;
using C = Combination<mint>;
void solve() {
LL(t, n, k);
if (k <= 1) {
if (k == 0)
print(1);
else
print(n);
return;
}
if (t == 1) {
if (k + k - 1 <= n) {
print(C::C(n - k + 1, k));
} else {
print(0);
}
} else {
if (2 * k <= n) {
print(C::C(n - k + 1, k) - C::C(n - k - 1, k - 2));
} else {
print(0);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(q);
rep(q)
solve();
}

Combination<mint> は階乗とその逆元の表を使って二項係数を求めるクラスで、C::C(n, r) が (nr)\binom{n}{r} です。

使用ライブラリ:cpp_include@4b58304

SamCoding Round 9 (Div. 4) F - Two-Coloured Graph

nn 頂点 mm 辺の無向グラフが与えられます。多重辺はありますが、自己ループはありません。連結とは限りません。各頂点を白か黒に塗り、どの辺も両端の色が異なるようにするとき、黒い頂点の数の最小値を求める問題です(1≤n≤2×1051 \le n \le 2 \times 10^5、0≤m≤2×1050 \le m \le 2 \times 10^5)。そのような塗り方がなければ −1-1 を出力します。

どの辺も両端の色が異なるように 2 色で塗れるのは、グラフが二部グラフのときです。二部グラフでなければ答えは −1-1 です。

二部グラフのとき、連結成分ごとに考えます。連結成分の中では、1 つの頂点の色を決めると、辺をたどって隣の頂点の色が次々に決まるので、成分全体の色も決まります。そのため、各連結成分の塗り方は、BFS や DFS で 2 色に塗り分けたものと、その白黒を入れ替えたものの 2 通りしかありません。

連結成分ごとに独立に選べるので、それぞれの成分で 2 色のうち少ないほうを黒にし、その個数を足し合わせたものが答えです。辺のない頂点だけの成分は白にすればよいので 00 個です。全体で O(n+m)O(n + m) です。

例えば入力例 1 では、成分 {1,2,3,4}\{1, 2, 3, 4\} は {1}\{1\} と {2,3,4}\{2, 3, 4\}、成分 {5,6}\{5, 6\} は {5}\{5\} と {6}\{6\} に分かれ、成分 {7}\{7\} は 00 個なので、答えは 1+1+0=21 + 1 + 0 = 2 です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M);
auto tmp = bipartite_coloring(g);
if (tmp.empty()) {
print(-1);
return;
}
auto cc = connected_components(g);
ll ans = 0;
for (const auto &c : cc) {
al<2> cnt = {0, 0};
for (ll u : c) {
cnt[tmp[u]]++;
}
ans += min(cnt);
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

bipartite_coloring は各頂点の色(00 か 11)を返し、二部グラフでなければ空の配列を返します。connected_components は連結成分ごとの頂点の一覧です。成分ごとに色 00 と色 11 の個数を数え、少ないほうを足しています。

使用ライブラリ:cpp_include@4b58304

SamCoding Round 9 (Div. 4) E - Carpet Pattern

レベル 00 の絨毯は黒いマス 1 個です。レベル nn の絨毯は、レベル n−1n - 1 の絨毯を 3×33 \times 3 に 9 個並べ、真ん中の 1 個だけを同じ大きさの真っ白な正方形に置き換えたものです(シェルピンスキーのカーペット)。レベル nn の絨毯は 3n×3n3^n \times 3^n になります。

レベル nn の絨毯の rr 行 cc 列のマスが黒か白かを答えるクエリが qq 個与えられます(1≤q≤1051 \le q \le 10^5、0≤n≤300 \le n \le 30、1≤r,c≤3n1 \le r, c \le 3^n)。黒なら #、白なら . を出力します。

行と列を 00 始まりにして、r,cr, c を 33 進数で見ます。

レベル nn の絨毯を 3×33 \times 3 のブロックに分けたとき、マス (r,c)(r, c) が入るブロックは、r,cr, c の 33 進数の一番上の桁(下から nn 桁目)で決まります。これが両方 11 なら真ん中のブロックなので白です。そうでなければレベル n−1n - 1 の絨毯の中にいるので、残りの桁で同じことを繰り返します。最後まで真ん中のブロックに入らなければ黒です。

つまり、r,cr, c の 33 進数の同じ桁がどちらも 11 になるところが 1 つでもあれば白、なければ黒です。どの桁から調べても結果は同じなので、下の桁から 33 で割った余りを見ていけば、11 クエリあたり O(n)O(n) で判定できます。

Python
for _ in range(int(input())):
N, R, C = map(int, input().split())
R -= 1
C -= 1
for _ in range(N):
if R % 3 == C % 3 == 1:
print(".")
break
R //= 3
C //= 3
else:
print("#")

for の else は、break せずにループが終わったとき、つまり両方 11 の桁がなかったときに実行されます。

SamCoding Round 9 (Div. 4) C - Old Phone

ボタン式の古い携帯電話で単語 ss を入力するのにかかる時間を求める問題です(1≤∣s∣≤1051 \le |s| \le 10^5、ss は英小文字のみ)。

ボタンには abc、def、ghi、jkl、mno、pqrs、tuv、wxyz の文字が割り当てられていて、ボタンの中の jj 番目の文字を入力するにはそのボタンを jj 回押します。1 回押すのに 11 秒かかります。また、次の文字が直前の文字と同じボタンにあるときは、区切るために 11 秒待つ必要があります。

各文字について、それがどのボタンの何番目の文字かを調べ、その番号を足していきます。さらに、直前の文字と同じボタンなら 11 を足します。

例えば hello は、h が 2 回、e が 2 回、l が 3 回、もう一度 l が 3 回と待ち時間 1 秒、o が 3 回で、合計 1414 秒です。

Python
l = ["abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
ans = 0
S = input()
d = []
for c in S:
for i, a in enumerate(l):
if c in a:
d.append(i)
for i, c in enumerate(S):
ans += l[d[i]].index(c) + 1
if i > 0 and d[i - 1] == d[i]:
ans += 1
print(ans)

d[i] は S[i] が何番目のボタンにあるかで、l[d[i]].index(c) + 1 がそのボタンを押す回数です。

SamCoding Round 9 (Div. 4) B - Fire Streak

nn 日間の歩数 a1,a2,…,ana_1, a_2, \dots, a_n と目標の歩数 kk が与えられます。歩数が kk 以上の日が連続する最大の日数を求める問題です(1≤n,k≤1051 \le n, k \le 10^5、0≤ai≤1050 \le a_i \le 10^5)。そのような日が 1 日もなければ 00 を出力します。

前から順に見ていき、「今日まで目標を達成した日が何日続いているか」を tt として持ちます。ai≥ka_i \ge k なら tt を 11 増やし、そうでなければ tt を 00 に戻します。各日の tt の最大値が答えです。

Python
t = 0
ans = 0
N, K = map(int, input().split())
A = list(map(int, input().split()))
for a in A:
if a >= K:
t += 1
else:
t = 0
ans = max(ans, t)
print(ans)

SamCoding Round 9 (Div. 4) A - Elevator or Stairs

Bobur は aa 階にいて、bb 階の教室へ行きたいです。階段を使うと、1 階分の移動に xx 秒かかります。エレベーターは今 cc 階にあり、呼ぶとまず cc 階から aa 階まで来て、そのあと bb 階まで運んでくれます。エレベーターは 1 階分の移動に yy 秒かかります。bb 階に着くまでの最短時間を求める問題です(1≤a,b,c≤1001 \le a, b, c \le 100、1≤x,y≤1001 \le x, y \le 100)。

階段を使うときにかかる時間は ∣a−b∣⋅x|a - b| \cdot x 秒です。

エレベーターを使うときは、エレベーターが cc 階から aa 階まで ∣c−a∣|c - a| 階、そこから bb 階まで ∣a−b∣|a - b| 階動くので、(∣c−a∣+∣a−b∣)⋅y(|c - a| + |a - b|) \cdot y 秒です。

この 2 つの小さいほうが答えです。

Python
a, b, c, x, y = map(int, input().split())
print(min(abs(a - b) * x, (abs(c - a) + abs(a - b)) * y))

DOJ Beginner Contest 13 F - Advance

NN 個の地域があり、軍隊が地域 ii を通るときは、まず兵士 BiB_i 人を守備隊として残し(その直後に 11 人以上残っていなければなりません)、そのあと兵士 AiA_i 人が合流します。次の 2 種類のクエリを QQ 個処理する問題です(1≤N,Q≤2000001 \le N, Q \le 200000、0≤Ai,Bi≤1090 \le A_i, B_i \le 10^9)。

  • 1 i a b:AiA_i を aa に、BiB_i を bb に変える。
  • 2 l r:地域 l,l+1,…,rl, l+1, \dots, r を順に通るとき、地域 ll に入る時点で必要な兵士の最小人数を答える。

区間を通る過程を「入るときに必要な最小人数 xx」と「ちょうど xx 人で入ったときに出ていく人数 yy」の組 (x,y)(x, y) で表します。xx 人より多く入れば、その分だけ出ていく人数も増えるので、この 2 つで区間の通り方が決まります。

地域 ii 1 つだけなら、BiB_i 人を残したあとに 11 人以上必要なので x=Bi+1x = B_i + 1 で、そのとき y=Ai+1y = A_i + 1 です。

区間 (x1,y1)(x_1, y_1) を通ったあとに区間 (x2,y2)(x_2, y_2) を通るとき、つなげた区間の組は次のようになります。

  • y1≥x2y_1 \ge x_2 のとき:x1x_1 人で入れば 2 つ目の区間にも入れるので、(x1, y1−x2+y2)(x_1, \ y_1 - x_2 + y_2)。
  • y1<x2y_1 < x_2 のとき:2 つ目の区間に入るのに x2−y1x_2 - y_1 人足りないので、最初にその分多く入る必要があり、(x1+x2−y1, y2)(x_1 + x_2 - y_1, \ y_2)。

この演算は結合的です(区間をつなげる順によらず、実際に通ったときの結果を表しているため)。単位元は (0,0)(0, 0) です。よってセグメント木に載せれば、クエリ 1 は 1 点の更新、クエリ 2 は区間の積の xx で、それぞれ O(log⁡N)O(\log N) で処理できます。

値は最大で (109+1)×200000≈2×1014(10^9 + 1) \times 200000 \approx 2 \times 10^{14} 程度なので、64 bit 整数で足ります。

C++
#include "shogo-library/base/all"
#include "shogo-library/data_structures/segtree.hpp"
struct M {
using S = pl;
S op(const S &l, const S &r) const {
if (l.second >= r.first) {
return {l.first, l.second - r.first + r.second};
} else {
return {l.first + r.first - l.second, r.second};
}
}
S e() const {
return {0, 0};
}
};
void solve() {
LL(N, Q);
vec<M::S> init;
init.reserve(N);
rep(i, N) {
LL(a, b);
init.push_back({b + 1, a + 1});
}
SegTree<M> seg(init);
rep(Q) {
LL(q);
if (q == 1) {
LL(i, a, b);
seg.set(i - 1, {b + 1, a + 1});
} else {
LL(l, r);
print(seg.prod(l - 1, r).first);
}
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

SegTree<M> は、モノイド M の演算 op と単位元 e を使うセグメント木です。要素の first が xx(必要な最小人数)、second が yy(出ていく人数)です。

使用ライブラリ:cpp_include@4b58304

DOJ Beginner Contest 13 D - Vassals

頂点 11 を根とする NN 頂点の根付き木があり、頂点 ii (i≥2)(i \ge 2) の親は PiP_i です。各頂点 ii には容量 BiB_i があります。辺をいくつか選び、各頂点 ii に接する選んだ辺が BiB_i 本以下になるようにするとき、選べる辺の最大本数を求める問題です(2≤N≤2000002 \le N \le 200000、0≤Bi≤2000000 \le B_i \le 200000)。

葉の側から貪欲に決めます。頂点 uu を見るときには、uu の子の部分木の中の辺はすでに決まっているとして、次のようにします。

  1. uu の各子 vv について、vv の容量が残っていて、uu の容量も残っていれば、辺 (u,v)(u, v) を選びます。
  2. そのあと uu の容量が残っていれば、uu と親を結ぶ辺の候補になります。実際に選ぶかは親を見るときに決めます。

この貪欲が最適であることは、次の 2 つの入れ替えで示せます。

  • 子の部分木の中の辺を、親への辺より優先してよい。 子 vv が親への辺 (u,v)(u, v) を選ぶために、部分木の中の辺 (v,w)(v, w) をあきらめたとします。(u,v)(u, v) を外して (v,w)(v, w) を選び直しても本数は変わらず、uu の容量が 11 空くだけです。
  • 子への辺を、親への辺より優先してよい。 子への辺 (u,v)(u, v) を選べるのに、uu の容量を親への辺に使い切った最適解があるとします。親への辺を外して (u,v)(u, v) を選んでも本数は変わりません。vv の容量はほかに使い道がなく、親の容量は 11 空きます。

子どうしの間では、どの子との辺を選んでも uu の容量を 11 使うだけで、子の残りの容量はほかで使えないので、どれから選んでも同じです。

各頂点を帰りがけ順に 1 回ずつ見るだけなので、計算量は O(N)O(N) です。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N);
VL(P, N - 1);
VL(B, N);
Tree<> tree(N);
rep(i, N - 1) {
tree.add_edge(i + 1, P[i] - 1);
}
RootedTree<> rooted(tree, 0);
vl dp(N);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
if (dp[v] && B[u]) {
B[u]--;
} else {
dp[v] = 0;
}
}
if (B[u] && u != rooted.root) {
dp[u] = 1;
} else {
dp[u] = 0;
}
}
print(sum(dp));
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

rooted.postorder は帰りがけ順に並べた頂点の列、rooted.child[u] は uu の子です。B[u] は子との辺を選ぶたびに減らすので、uu の残りの容量になります。

dp[u] は、uu を見終わった時点では「uu の容量が残っていて、親への辺の候補になるか」を表します。親を見たときに、その辺を選ばなかった子の dp[v] を 00 に戻すので、最後には dp[v] が「vv と親を結ぶ辺を選んだか」になり、その総和が答えです。

使用ライブラリ:cpp_include@4b58304

DOJ Beginner Contest 13 C - Measures

ある標準錘の重さを NN 個の都市で量った記録があります。ii 番目の都市の 11 ポンドは UiU_i グレインで、その都市は標準錘を AiA_i ポンド(11 ポンド未満は切り捨て)と記録しました。標準錘の実際の重さは、グレインで表すと正の整数です。残った記録がすべて正しくありうるように、除く記録の最小個数を求める問題です(1≤N≤2000001 \le N \le 200000、1≤Ui≤100001 \le U_i \le 10000、0≤Ai≤1000000 \le A_i \le 100000)。

標準錘の重さを WW グレインとすると、記録 ii が正しいのは ⌊W/Ui⌋=Ai\lfloor W / U_i \rfloor = A_i、つまり

UiAi≤W<Ui(Ai+1)U_i A_i \le W < U_i (A_i + 1)

のときです。さらに W≥1W \ge 1 なので、記録 ii が正しくなる WW は半開区間 [max⁡(UiAi,1),Ui(Ai+1))[\max(U_i A_i, 1), U_i (A_i + 1)) です。Ui=1,Ai=0U_i = 1, A_i = 0 のときはこの区間は空で、その記録は必ず除くことになります。

WW を固定すると、残せる記録は WW を含む区間の個数です。よって、NN 個の区間が最も多く重なっている点での重なりの数を cc とすると、答えは N−cN - c です。

区間の端点は 10910^9 程度まで大きくなるので、端点を座標圧縮してからいもす法で各点の重なりの数を求めます。重なりの数が変わるのは区間の左端だけなので、左端と右端の座標だけ見れば十分です。計算量は O(Nlog⁡N)O(N \log N) です。

W≥1W \ge 1 の条件を区間の左端に入れておくのが大事です。左端を UiAiU_i A_i のままにして、座標 00 での重なりの数を最大値の候補から除くだけだと、Ai=0A_i = 0 の記録の区間 [0,Ui)[0, U_i) が数えられなくなります。例えば N=1N = 1、(U1,A1)=(4,0)(U_1, A_1) = (4, 0) では、W=1W = 1 なら記録が正しいので答えは 00 ですが、座標 00 を除くと 11 になってしまいます。

Python
import bisect
N = int(input())
lr = []
comp = []
for i in range(N):
u, a = map(int, input().split())
l = max(u * a, 1)
lr.append((l, u * (a + 1)))
comp.append(l)
comp.append(u * (a + 1))
comp = sorted(set(comp))
imos = [0] * len(comp)
for l, r in lr:
imos[bisect.bisect_left(comp, l)] += 1
imos[bisect.bisect_left(comp, r)] -= 1
for i in range(1, len(imos)):
imos[i] += imos[i - 1]
print(N - max(imos))

comp が座標圧縮した端点の座標で、imos[i] は累積和をとったあと、点 comp[i] を含む区間の個数になります。空の区間は、同じ位置に +1+1 と −1-1 が入るので打ち消し合います。

DOJ Beginner Contest 13 B - Chronicler

NN 日分の竹簡があり、ii 日目の竹簡は AiA_i 枚です。これを 1 日目から順に、容量 KK の本に綴じていきます。1 日分の竹簡は分けられません。今の本にその日の竹簡を加えて KK 枚以下なら今の本に綴じ、KK 枚を超えるなら次の本にその日の竹簡をすべて綴じます。本の冊数が MM 冊以下になる最小の KK を求める問題です(1≤M≤N≤10001 \le M \le N \le 1000、1≤Ai≤1001 \le A_i \le 100、∑Ai≤10000\sum A_i \le 10000)。

1 日分の竹簡が 1 冊に収まらないといけないので、K≥max⁡AK \ge \max A です。また K=∑AK = \sum A なら全部が 1 冊に収まるので、条件を満たします。

そこで KK を max⁡A\max A から ∑A\sum A まで小さい順に試し、それぞれについて問題文の規則どおりに本を綴じて冊数を数えます。冊数が初めて MM 以下になった KK が答えです。

試す KK は ∑A≤10000\sum A \le 10000 通り以下で、1 回のシミュレーションは O(N)O(N) なので、全体で O(N∑A)O(N \sum A)、最大 10710^7 回程度です。

なお、KK を大きくしても冊数は増えないので、KK を二分探索すれば O(Nlog⁡∑A)O(N \log \sum A) でも求まります。

Python
N, M = map(int, input().split())
A = list(map(int, input().split()))
for k in range(max(A), sum(A) + 1):
t = 0
f = 1
for a in A:
if t + a > k:
f += 1
t = a
else:
t += a
if f <= M:
print(k)
break

t が今の本に綴じた竹簡の枚数、f が冊数です。

DOJ Beginner Contest 13 A - Era

NN 個の年号の名前 SiS_i と、その年号が始まった西暦年 AiA_i が与えられます(A1<A2<⋯<ANA_1 < A_2 < \dots < A_N)。各年号は始まった年を 11 年として数え、次の年号が始まるまで使われます。西暦 YY 年に使われていた年号の名前と、その年号での年数を求める問題です(1≤N≤1001 \le N \le 100、A1≤Y≤9999A_1 \le Y \le 9999)。

西暦 YY 年に使われているのは、Ai≤YA_i \le Y を満たす ii のうち最大のものです。AA は昇順に並んでいるので、後ろから見ていって最初に Ai≤YA_i \le Y となったものが答えの年号です。A1≤YA_1 \le Y なので必ず見つかります。

年数は、AiA_i 年が 11 年なので Y−Ai+1Y - A_i + 1 年です。

Python
N = int(input())
S = []
A = []
for _ in range(N):
s, a = input().split()
S.append(s)
A.append(int(a))
Y = int(input())
for i in reversed(range(N)):
if Y >= A[i]:
print(S[i], Y - A[i] + 1)
break

尺取り法のリンク集

尺取り法(しゃくとり法)について、参考になる記事や資料をまとめました。

尺取り法は、数列の区間 [l,r)[l, r) の左端と右端をどちらも右にだけ動かしながら、条件を満たす区間を調べる手法です。「区間が条件を満たすなら、それに含まれる区間も満たす」(または「それを含む区間も満たす」)という単調性があると、左端 ll ごとの右端の境目が ll について単調になります。そのため、右端を伸ばせるだけ伸ばし、次に左端を 1 つ縮める、を繰り返すと、全体で O(N)O(N) 回の操作で済みます。条件を満たす区間の最大長・最小長・個数を求めるときによく使われます。

区間の和で判定するときは、値が非負(正)であることが単調性の前提です。負の値があると使えないので、累積和と二分探索やデータ構造を組み合わせる方法を考えます。また、ソートした配列の両端から 2 本のポインタを寄せていく方法も、two pointers と呼ばれます。

  • しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ(drken、Qiita)
    • 尺取り法が使える場面を「条件を満たす区間の最小長・最大長・個数」の 3 つに整理し、AOJ DSL_3_C を例に、素朴な O(n2)O(n^2) の方法から「右端の境目が左端について広義単調増加」という観察を経て O(n)O(n) にするまでを、図と C++ のコードで説明しています。使える条件、二分探索との類似、スライド最小値や Convex Hull Trick との関係まで扱い、最後に AtCoder などの問題例が並んでいます。
    • 細かい誤記がいくつかあります。たとえば最後の問題「L番目のK番目の数」の出典が、冒頭では JOI 2017 予選 E、本文では予選 F となっています(AtCoder 上では JOI 2018 予選 F)。また、ABC098 D の問題概要は「正の整数列」とありますが、実際は 00 も含みます。
  • 競プロ典型 90 問 034 の解説(E869120、画像)
    • 値の種類が KK 以下の最長の区間を求める問題を例に、左端 ii ごとの右端の限界 cic_i を表にし、c1≤c2≤⋯c_1 \le c_2 \le \cdots という単調性から操作が合計 2N2N 回で済むことを 1 枚で説明しています。C++ の解答コードと、類題の一覧もあります。
  • しゃくとり法のDequeを使ったバグりにくい実装(keroru、Qiita)
    • 添字を動かす代わりに、右端の要素を deque に入れ、条件を満たさない間は先頭から取り出す実装を、ABC032 C を例に Python で説明しています。deque の中身の推移をデバッグ出力で見せ、一般形のテンプレートも載せています。単調性の説明はないので、上の記事とあわせて読んでください。
  • 尺取り法の実装で嵌ったあの日の涙を数え切れないあなたにお送りする、尺取り法実装の † ソウル † です。(ngtkana、Qiita)
    • 尺取り法の難しさを「左右の端を動かしたときの状態の更新」と「どう動かすか」に分けて、和が KK 以下・KK より大きい区間の数え上げ、最大長・最小長などを C# で書き分けています。要素が 00 以上であることを「大事な仮定」として明示しています。図はありません。
    • コードにそのままでは誤答になる誤りがあります。和が KK 以下の区間を数えるコードで、左端を進めるときに sum += a[l++] となっている箇所(正しくは -=)、最小長のコードで ans を 00 で初期化したまま Math.Min を取っている箇所などです。
  • 二分探索のリンク集:左端ごとの右端の境目は、累積和の上の二分探索でも求められます。尺取り法より log⁡\log が付きますが、考えやすいこともあります。
  • 累積和・いもす法のリンク集:区間の和の判定や、区間内の特定の要素の個数を O(1)O(1) で求めるのに使います。
  • スライド最小値のリンク集:両端が単調に動く区間の最小値・最大値を deque で求める手法で、尺取り法と組み合わせてよく使われます。

尺取り法を扱う講座はまだありません。競技プログラミング基本用語集の 6.2「区間」(半開区間の表記)、6.3「部分列,部分配列(連続部分列)」、6.6「単調性」の節で、関連する用語を確認できます。

日本語版・英語版の Wikipedia には、尺取り法(two pointers)の記事はありません。

  • Two Pointers(USACO Guide)
    • 両端から寄せる型(ソートした配列で和が xx になる 2 要素を探す CSES Sum of Two Values)と、同じ向きに動かす型(Codeforces 279B Books)を、表やアニメーションで説明しています。C++・Java・Python のコードと、12 問の問題一覧があります。
    • 末尾の小テストは、two pointers を「2 つの添字の組を探す手法」とする選択肢だけを正解にしていて、本文の同じ向きに動かす型と噛み合いません。
  • Competitive Programmer’s Handbook(Antti Laaksonen、PDF)
    • 8 章「Amortized analysis」の 8.1 節「Two pointers method」で、正の整数の列で和がちょうど xx の区間を探す問題と、2SUM(和が xx になる 2 要素)を図で説明しています。コードはありません。8.3 節はスライド最小値です。
  • Two Pointers Method(Codeforces EDU)
    • ITMO Academy の講座の 1 レッスンです。中身を見るには Codeforces へのログインが必要です。

左端を 1 つ進めるたびに右端を伸ばせるだけ伸ばす、という基本の形の問題です。

ソートした配列の上で 2 本のポインタを動かす形の問題です。

  • ABC481 E - Most Brilliant Starry Sky
    • 星を偏角の順に並べ、偏角に 2π2\pi を足した写しを後ろにつなげた列の上で、偏角の幅が π\pi 未満の区間を尺取り法で求めています。円環の上の尺取り法の例です。

ABC481 F - Evil Shortest Path

NN 頂点 MM 辺の有向グラフがあり、各辺には 11 以上 99 以下の数字が書かれています。通った辺の数字を順につなげた整数をその移動のスコアとします。v=2,3,…,Nv = 2, 3, \ldots, N のそれぞれについて、頂点 11 から頂点 vv へ移動するときのスコアの最小値を 998244353998244353 で割ったあまりを求める問題です。

同じ頂点や辺を何度通ってもよく、頂点 11 から全頂点に到達できることが保証されます(2≤N≤2×1052 \le N \le 2 \times 10^5、N−1≤M≤2×105N - 1 \le M \le 2 \times 10^5)。

辺の数字はどれも 11 以上なので、スコアの桁数は通った辺の本数に等しく、桁数が少ないほどスコアは小さくなります。よって、スコアが最小になる移動は、頂点 11 からの最短路(辺の本数が最小の移動)のどれかです。桁数が同じ整数どうしの大小は、数字の列の辞書順と一致するので、最短路のうち数字の列が辞書順で最小のものを求めればよいです。

頂点 11 からの最短距離 dd を BFS で求めます。最短路で使える辺は、dv=du+1d_v = d_u + 1 を満たす辺 u→vu \to v だけです。頂点 vv への辞書順最小の列を svs_v とすると、

sv=min⁡u→v, dv=du+1(su の後ろに辺の数字をつなげた列)s_v = \min_{u \to v,\ d_v = d_u + 1} (s_u \text{ の後ろに辺の数字をつなげた列})

です。長さの同じ列どうしでは、sus_u より大きい列の後ろに数字をつなげても、sus_u の後ろにつなげた列より小さくはならないからです。dd の小さい順に頂点を見ていけば、sus_u を使うときには sus_u が確定しています。

列 svs_v の長さは最大で N−1N - 1 になるので、すべての列をそのまま持つと間に合いません。そこで、列を Trie のノードで表します。sus_u のノードから辺の数字で 1 文字進んだノードが「sus_u の後ろに数字をつなげた列」です。1 本の辺でノードは高々 1 個しか増えないので、ノードは M+1M + 1 個以下です。

2 つのノードの列の辞書順の比較は、2 つのノードの最小共通祖先(LCA)のすぐ下の文字を比べればできます。ノードごとに祖先への飛び先を持っておけば、LCA は O(log⁡N)O(\log N) で求まります。

答えのあまりは、svs_v を更新するたびに (su のあまり)×10+(数字)(s_u \text{ のあまり}) \times 10 + (\text{数字}) として一緒に更新します。計算量は O((N+M)log⁡N)O((N + M) \log N) です。

なお、Trie を使わなくても、同じ距離の頂点どうしの svs_v の順位を距離ごとに求めておき、「sus_u の順位、辺の数字」の組をソートして次の距離の順位を決める方法でも解けます。

別解:スコアを距離にしてダイクストラ法

Section titled “別解:スコアを距離にしてダイクストラ法”

スコアを「数字の列の長さで比べ、長さが同じなら辞書順で比べる」値と考えると、この問題はスコアを距離とする最短路問題です。この距離には次の 2 つの性質があります。

  • 辺をたどると、列が 1 文字長くなるので、距離は必ず大きくなる。
  • 列 aa が列 bb より小さければ、同じ数字をつなげた後も、aa のほうが bb 以下になる。

この 2 つが成り立つので、ダイクストラ法がそのまま使えます。距離は上と同じく Trie のノードで持ち、比較 1 回が O(log⁡N)O(\log N) なので、全体の計算量は O(Mlog⁡Mlog⁡N)O(M \log M \log N) です。BFS の層ごとに処理する工夫を、ダイクストラ法に任せる形になります。

C++(BFS)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
#include "shogo-library/utility/vector_func.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, false).dist;
Trie<9, 1> trie;
vl node(N, -1);
vec<mint> ans(N);
node[0] = 0;
for (ll u : sorted_idx(d)) {
for (auto &e : g[u]) {
if (d[e.dst] != d[u] + 1)
continue;
ll v = trie.extend(node[u], e.cost);
if (node[e.dst] == -1 || trie.less(v, node[e.dst])) {
node[e.dst] = v;
ans[e.dst] = ans[u] * 10 + e.cost;
}
}
}
rep(v, 1, N) print(ans[v]);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, true, true) は、辺の数字を重みとして、有向辺を MM 本読みます。shortest_path(g, 0, false) の第 3 引数 false は重みを無視することを表し、BFS で辺の本数の最短距離を求めます。

Trie<9, 1> は、文字 11 から 99 を使う Trie です。根(ノード 00)が空の列で、頂点 11 の列に対応します。node[v] は svs_v のノード、ans[v] はそのあまりです。

sorted_idx(d) は d の小さい順に並べた頂点の番号の列です。trie.extend(node[u], e.cost) で sus_u の後ろに辺の数字をつなげた列のノードを(なければ作って)求め、trie.less(v, node[e.dst]) で、いまの svs_v より辞書順で小さいかを O(log⁡N)O(\log N) で比べています。

使用ライブラリ:cpp_include@4b58304

C++(ダイクストラ法)
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/math/modint.hpp"
#include "shogo-library/string/trie.hpp"
using mint = modint998244353;
Trie<9, 1> trie;
struct Score {
ll node = 0;
ll digit = 0;
mint val = 0;
Score() = default;
Score(ll digit) : digit(digit) {}
static Score inf() {
Score res;
res.node = -1;
return res;
}
friend Score operator+(const Score &a, const Score &e) {
Score res;
res.node = trie.extend(a.node, e.digit);
res.val = a.val * 10 + e.digit;
return res;
}
friend bool operator<(const Score &a, const Score &b) {
if (a.node == -1)
return false;
if (b.node == -1)
return true;
if (trie.depth(a.node) != trie.depth(b.node))
return trie.depth(a.node) < trie.depth(b.node);
return trie.less(a.node, b.node);
}
friend bool operator>(const Score &a, const Score &b) { return b < a; }
friend bool operator==(const Score &a, const Score &b) { return a.node == b.node; }
friend std::istream &operator>>(std::istream &is, Score &s) { return is >> s.digit; }
};
void solve() {
LL(N, M);
Graph<Score> g(N);
g.read(M, -1, true, true);
auto d = shortest_path(g, 0, true, Score::inf()).dist;
rep(v, 1, N) print(d[v].val);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

Score は距離と辺のコストの両方に使う型です。距離としては、node がスコアの列の Trie のノード、val がそのあまりです。辺のコストとしては、digit に辺の数字を入れます。

  • operator+ は、距離に辺のコストを足す操作で、Trie を辺の数字で 1 文字進めます。
  • operator< は、列の長さ(Trie の深さ)で比べ、同じなら trie.less で辞書順に比べます。node == -1 は到達できないことを表す最大の値 inf() です。
  • operator> と operator== は、ライブラリのダイクストラ法の中で、距離の比較と未到達の判定(inf との比較)に使われます。
  • shortest_path の inf の既定値は std::numeric_limits<Cost>::max() / 4 で、この型では使えないので、Score::inf() を渡しています。
  • g.read は、重みを Cost c(1) で作ってから std::cin >> c で読むので、整数からのコンストラクタと operator>> を用意しています。始点の距離 0 は Score(0) で、Trie の根(空の列)になります。

使用ライブラリ:cpp_include@4b58304

ABC481 E - Most Brilliant Starry Sky

xyxy 平面上に NN 個の星 (Xi,Yi)(X_i, Y_i) があります。原点を通り、どの星も通らない直線を 1 本引き、分けられた 2 つの領域のどちらかを選びます。選んだ領域に含まれる星の個数の最大値を求める問題です。

どの 2 個の星も原点と一直線上に並ぶことはありません。TT 個のテストケースに答えます(NN の総和は 2×1052 \times 10^5 以下、∣Xi∣,∣Yi∣≤109|X_i|, |Y_i| \le 10^9)。

原点を通る直線で分けた一方の領域は、偏角(原点から見た向きの角度)が長さ π\pi の開区間 (α,α+π)(\alpha, \alpha + \pi) に入る点の集まりです。よって、偏角が長さ π\pi の区間に入る星の個数の最大値を求めればよいです。

ある領域 (α,α+π)(\alpha, \alpha + \pi) が星を含むとき、含まれる星のうち偏角が最小のものを θ\theta とします。含まれる星の偏角はどれも θ\theta 以上 α+π\alpha + \pi 未満で、α<θ\alpha < \theta なので、どれも [θ,θ+π)[\theta, \theta + \pi) に入ります。逆に、偏角が [θ,θ+π)[\theta, \theta + \pi) に入る星は、α\alpha を θ\theta より少しだけ小さくした領域でちょうど全部含められます。偏角がちょうど θ+π\theta + \pi の星はないので(原点と一直線上に並ばないため)、α\alpha を θ\theta に十分近くすれば余計な星は入りません。

したがって、各星 ii について、偏角が [θi,θi+π)[\theta_i, \theta_i + \pi) に入る星を数え、その最大値が答えです。

星を偏角の順に並べます。偏角は一周すると元に戻るので、偏角に 2π2\pi を足した写しを後ろにつなげた長さ 2N2N の列を作ります。この列で、各 ll (0≤l<N)(0 \le l < N) について、偏角が θl+π\theta_l + \pi 未満である範囲の右端 rr を求めると、r−lr - l が [θl,θl+π)[\theta_l, \theta_l + \pi) に入る星の個数です。ll が増えると rr も減らないので、尺取り法で全体 O(N)O(N) で求まります。

計算量は、偏角ソートの O(Nlog⁡N)O(N \log N) です。

偏角は atan2 などの浮動小数点数で求めると、偏角の近い星の比較で誤差が出るおそれがあります。外積を使って比べると、整数だけで正確に比べられます。座標の絶対値は 10910^9 以下なので、外積は 64 bit 整数に収まります。

C++
#include "shogo-library/base/all"
#include "shogo-library/geometry/angle.hpp"
#include "shogo-library/utility/container_func.hpp"
#include "shogo-library/utility/two-pointers.hpp"
void solve() {
LL(N);
vec<Angle<ll>> A(N);
for (auto &a : A)
std::cin >> a;
sort(A);
rep(i, N) A.push_back(A[i].next_turn());
auto right = two_pointers(2 * N, [&](ll l, ll r) { return A[r] < A[l].opposite(); });
ll ans = 0;
rep(l, N)
chmax(ans, right[l] - l);
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

Angle<ll> はベクトル (x,y)(x, y) の偏角を表す型で、周回数 turn を持ち、偏角 2π⋅turn+[0,2π)2\pi \cdot \mathrm{turn} + [0, 2\pi) として外積で比べます。next_turn() は偏角に 2π2\pi を足したもの、opposite() は π\pi を足したもの(逆向きのベクトル)です。

sort(A) で偏角の順に並べ、next_turn() で 2π2\pi を足した写しを後ろにつなげます。two_pointers(n, can_add) は、各 l について、区間 [l, r) に r を加えてよい(can_add(l, r) が真)間だけ r を伸ばし、伸ばし終えた r を並べた列を返します。ここでは「A[r] の偏角が A[l] の偏角 +π+ \pi 未満」を条件にしています。

使用ライブラリ:cpp_include@4b58304

ABC481 D - Autopilot

NN 頂点 MM 辺の有向グラフがあります。いまいる頂点から、次のどちらかの方法で移動できます。

  • 出ている辺の行き先のうち、番号が最小の頂点に燃料 00 で移動する。
  • 出ている辺の行き先を好きに選び、燃料 11 で移動する。

頂点 SS から頂点 TT へ移動するのに必要な燃料の最小値を求める問題です。到達できなければ −1-1 を出力します(2≤N≤2×1052 \le N \le 2 \times 10^5、1≤M≤2×1051 \le M \le 2 \times 10^5)。

各頂点 uu から出ている辺の行き先のうち、番号が最小の頂点へはコスト 00、それ以外の頂点へはコスト 11 の辺を張った新しいグラフを作ります。このグラフで SS から TT への最短距離が答えです。

辺のコストは 00 か 11 で非負なので、ダイクストラ法で求められます。計算量は、行き先のソートも含めて O((N+M)log⁡(N+M))O((N + M) \log (N + M)) です。コストが 00 と 11 だけなので 01-BFS でも求められ、その場合は最短路の部分が O(N+M)O(N + M) になります。

ダイクストラ法については ダイクストラ法のリンク集 も見てください。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/shortest-path.hpp"
#include "shogo-library/utility/container_func.hpp"
void solve() {
LL(N, M, S, T);
S--, T--;
Graph<> g(N), h(N);
g.read(M, -1, false, true);
rep(u, N) {
vl tmp;
for (ll v : g[u])
tmp.push_back(v);
sort(tmp);
rep(i, len(tmp)) {
h.add_directed_edge(u, tmp[i], i > 0);
}
}
ll ans = shortest_path(h, S).dist[T];
print(ans > M ? -1 : ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

g.read(M, -1, false, true) は、頂点番号から 11 を引き、重みなしの有向辺として MM 本の辺を読みます。

g で頂点 u から出ている辺の行き先を tmp に集めてソートし、先頭(番号が最小の頂点)へはコスト i > 0 すなわち 00、それ以外へは 11 の辺を h に張ります。

shortest_path(h, S) は、h での S から各頂点への最短距離をダイクストラ法で求めます。到達できない頂点の距離はとても大きな値になります。到達できるときの答えは、同じ辺を 2 回使わない経路で考えれば MM 以下なので、MM より大きければ −1-1 を出力しています。

使用ライブラリ:cpp_include@4b58304

ABC481 C - Bank Accounts

名前 ss が QQ 回与えられます。各回について、ss にすでに ID が割り当てられていればその ID を、そうでなければまだ使われていない最小の正の整数を ss の ID として割り当て、その ID を出力する問題です(1≤Q≤2×1051 \le Q \le 2 \times 10^5、1≤∣s∣≤101 \le |s| \le 10)。

ID は 1,2,3,…1, 2, 3, \ldots の順に割り当てられるので、新しく割り当てる ID は「それまでに出てきた名前の種類数 +1+ 1」です。

名前から ID への辞書(連想配列)を持ち、名前が辞書になければ、そのときの辞書の大きさ +1+ 1 を ID として登録します。そのあと辞書から ID を引いて出力します。

Python
d = {}
for _ in range(int(input())):
S = input()
if S not in d:
d[S] = len(d) + 1
print(d[S])

ABC481 B - Polyline

xyxy 平面上の NN 個の点 (i,Ai)(i, A_i) を、点 1,2,…,N1, 2, \ldots, N の順に線分で結んで折れ線を作ります。この折れ線上(端点も含む)にある点のうち、yy 座標が KK であるものの個数を求める問題です(2≤N≤1002 \le N \le 100、Ai≠Ai+1A_i \ne A_{i+1})。

条件を満たす点は、次の 2 種類です。

  • Ai=KA_i = K である点 ii そのもの。
  • 点 ii と点 i+1i + 1 を結ぶ線分の内部の点で、AiA_i と Ai+1A_{i+1} の一方が KK より大きく、もう一方が KK より小さいとき。yy 座標が KK を横切るので、線分の内部にちょうど 1 個あります。

Ai≠Ai+1A_i \ne A_{i+1} なので、線分が y=Ky = K の上に重なることはありません。

ただし、隣り合う 2 本の線分が共有する端点を 2 回数えないように注意が必要です。そこで、点 11 は単独で数え、それ以降は線分ごとに「右端の点と線分の内部」だけを数えます。

点 i−1i - 1 と点 ii を結ぶ線分を見るとき、

  • Ai−1=KA_{i-1} = K なら、左端は前の線分(または点 11)ですでに数えています。Ai≠KA_i \ne K なので、この線分にはほかに条件を満たす点はありません。
  • そうでなければ、Ai=KA_i = K(右端)か、Ai−1A_{i-1} と AiA_i が KK をはさんでいる(内部)ときに、1 個数えます。

計算量は O(N)O(N) です。

Python
N, K = map(int, input().split())
A = list(map(int, input().split()))
ans = 0
if A[0] == K:
ans += 1
for i in range(1, N):
if A[i - 1] == K:
continue
if A[i] == K or (A[i] > K) != (A[i - 1] > K):
ans += 1
print(ans)

A[i - 1] と A[i] がどちらも KK でないとき、(A[i] > K) != (A[i - 1] > K) は、2 点が y=Ky = K をはさんでいることを表します。

ABC481 A - Digits of A+B

11 以上 99 以下の整数 A,BA, B が与えられます。A+BA + B の桁数を求める問題です。

A+BA + B を文字列にして、その長さを出力します。

A+BA + B は 22 以上 1818 以下なので、A+B≥10A + B \ge 10 なら 22、そうでなければ 11 と場合分けしても求まります。

Python
print(len(str(sum(map(int, input().split())))))

座標圧縮のリンク集

座標圧縮について、参考になる記事や資料をまとめました。

座標圧縮(座圧)は、値を「全体の中で何番目に小さいか」に置き換える手法です。値の大小関係だけが大事で、値そのものが 10910^9 のように大きいときに、00 から N−1N - 1 までの添字に直して配列で扱えるようにします。同じ値には同じ番号を付けます。

C++ では、値をコピーしてソートし、std::unique と erase で重複を除いたあと、std::lower_bound で各値の番号を求めます。Python では sorted(set(A)) で重複のない昇順の列を作り、辞書で値から番号を引くか、bisect_left で番号を求めます。どちらも計算量は O(Nlog⁡N)O(N \log N) です。

よく使うのは、次のような場面です。

  • データ構造に載せる:値を添字にして BIT やセグメント木に載せるとき、値を圧縮して大きさを O(N)O(N) に抑えます。後から来るクエリの値も含めて圧縮するため、クエリを先読みすることが多いです。転倒数を求めるときも、値が大きければまず圧縮します。
  • 区間を扱う:区間の端点だけを集めて圧縮すると、数直線が「端点から次の端点まで」の小区間の並びになり、どの区間も小区間をいくつか並べたものになります。区間を半開区間 [l,r)[l, r) で表して端点 l,rl, r を集めると、扱いが簡単です。閉区間 [l,r][l, r] なら ll と r+1r + 1 を集めます。小区間の長さは、圧縮前の値の差で求めます。いもす法と組み合わせることもよくあります。
  • 2 次元のグリッド:x 座標と y 座標をそれぞれ別に圧縮して、小さなグリッドに直します。長方形や線分で区切られた領域を扱うときは、端点だけを残すと隙間が消えてしまうことがあり、端点の隣の座標も残す必要があります。
  • 座標圧縮 (座圧)(けんちょんの競プロ精進記録)
    • 「全体の中で何番目に小さいか」という定義から始めて、C++(ソート、unique と erase、lower_bound)と Python(sorted(set(A)) と辞書)の実装、例題の ABC036 C と ABC113 C、発展として 2 次元の点の座標圧縮(ABC213 C)を説明しています。初心者向けです。
  • 座標圧縮の解説(1次元から2次元の圧縮まで)(アルゴリズムロジック)
    • 1 次元の座標圧縮の手順と C++ の実装から、線分や長方形を扱う 2 次元の座標圧縮に進みます。端点だけでなく「一つ隣」の座標も残さないと隙間が消えてしまう理由を、圧縮の前後の図で説明しているのが特徴です。例題は AOJ DSL_4_A(長方形の面積の和)で、座標圧縮と 2 次元のいもす法で解いています。練習問題の一覧もあります。
    • 2.4 節のコードは for (T d = 0; d < 1; d++) になっていて、d = 0 しか回らないので、説明している「一つ隣の座標」が追加されません。最後の DSL_4_A のコードのように d <= 1 にしてください。
  • 座標圧縮(北海道大学 HCPC、PDF)
    • 2017 年の勉強会のスライドです。1 次元(ABC036 C)のあと、蟻本の「領域の個数」を例に、線分の端点だけを残すと誤る例を示して、端点の隣に余白の座標を足す方法を図で説明しています。応用として AOJ 2426 Treasure Hunt(座標圧縮と 2 次元の累積和)も扱っています。
    • スライドにコードはなく、GitHub へのリンクは切れています。コードは今はこちらにあります。スライド自身に、コードは verify していないと書かれています。
  • 座標圧縮に関する解説と練習問題(Baby Stepsなブログ)
    • 端点とその隣の座標を登録する圧縮の関数と、それを使った 3 問の C++ の解答です。AOJ DSL_4_A(2 次元のいもす法)、JOI 2008 本選「ペンキの色」(領域の個数を BFS で数える)、JOI 2013 予選「魚の生息範囲」(3 次元)を扱っています。説明は短く、コードが中心です。
  • 座標圧縮について勉強した java(バイトの競プロメモ)
    • 壁で区切られたグリッドを、まず x 方向だけ圧縮する様子を図で示しています。長方形の右端を半開区間の端として持てば、端点だけを残しても領域が小区間の並びとして正しく残ることが、具体的な数で分かります。両端の座標を入れ忘れると外側の余白が消えることにも触れています。コードは Java の断片です。
  • 転倒数を Binary Indexed Tree(BIT)で求める(embermaverick05、Qiita)
    • 転倒数を BIT で求める入門記事で、最後に値が 10910^9 まである場合に、sorted(set(A)) から作った辞書で値を圧縮してから BIT に載せる方法を説明しています。コードは Python です。
  • 平面走査について(Shirotsume、Qiita)
    • 転倒数を例に、片方の座標の順に処理しながら、もう片方の座標を BIT で数える平面走査の考え方を一般化して説明しています。座標圧縮そのものの解説ではありませんが、クエリを先読みして圧縮し、データ構造に載せるオフライン処理の考え方が分かります。コードはなく、数式と文章で説明しています。

AtCoder Library(ACL)に座標圧縮の機能はありません。

  • std::unique(cpprefjp)
    • std::unique は隣り合う重複を除いた要素を先頭に集めるだけで、要素数は減らないこと、実際に消すには戻り値を使って erase する必要があることが書かれています。隣り合う重複しか消さないので、先にソートが必要なことも例で分かります。
  • misc/compress.hpp(Nyaan’s Library)
    • 座標圧縮の構造体の C++ の実装です。説明の文章はなく、コードだけのページです。値の番号を求める get(x) は、x が登録されていなくても「xx 以上の最初の位置」を返すので、区間の端を求めるのにも使えます。
  • other/compress.hpp(Luzhiled’s Library)
    • 値を add で登録してから build で整える形の C++ の実装で、こちらもコードだけのページです。コンストラクタで値を渡しても build は呼ばれないので、番号を求める前に必ず build を呼んでください。

座標圧縮そのものを扱う講座はありませんが、座標圧縮を使う講座があります。

  • Wavelet Matrix(発展)
    • 6 章「2 次元点群に対する矩形処理」で、点の座標を圧縮して 00 から N−1N - 1 に直してから Wavelet Matrix に載せています。点の追加・削除がある問題では、クエリをすべて先読みしてから座標圧縮する方法も説明しています。難易度の高い講座です。
  • 区間クエリのためのモノイド設計
    • 8.1 節「転倒数」の補足で、値を添字にするときは座標圧縮してセグメント木の大きさを O(N)O(N) に抑えればよい、と触れています。

日本語版・英語版の Wikipedia と cp-algorithms には、座標圧縮の記事も節もありません。

  • Custom Comparators and Coordinate Compression(USACO Guide、英語)
    • 前半はソートの比較関数の話で、後半が座標圧縮です。2 次元の点の座標をソートした順位に置き換える例(USACO 2020 Dec Silver「Rectangular Pasture」)と、長さ 10910^9 の配列への区間加算と区間和を、端点を集めて圧縮し、圧縮前の値の差を小区間の長さとして使って解く例(Codeforces Gym 102951 D)があります。コードは C++・Java・Python から選べます。
    • 1 つ目の例のコードは、ソートした順に番号を振るだけで、重複を除いていません。この問題では座標がすべて異なることが保証されているので正しく動きますが、重複がある問題にそのまま使うと誤ります。
  • Spoj Problem: Election Posters(Codeforces、英語)
    • 区間を塗り重ねる問題についての質問スレッドです。端点だけを圧縮すると、間にある隙間が消えて答えが変わってしまう反例がコメントで示されていて、端点の扱いの落とし穴の実例になっています。
  • ABC188 D - Snuke Prime:料金が変わる日だけを取り出して(座標圧縮して)、いもす法で各期間の料金を求めます。
  • ABC221 D - Online games:ログイン人数が変わる日だけを取り出し、人数が同じ期間の日数を数えます。
  • ABC231 F - Jealous Two:片方の嬉しさの順に処理しながら、もう片方の嬉しさを圧縮して BIT で数えます。
  • AOJ DSL_4_A - Union of Rectangles:長方形の面積の和を、座標圧縮と 2 次元のいもす法で求めます。上のアルゴリズムロジックの記事が解説です。
  • ABC168 F - . (Single Dot):線分の端点で座標を圧縮してグリッドにし、牛のいる領域を BFS で探索して面積を足し合わせます。領域が外まで広がっていれば INF です。
  • SamCoding Round 7 (Div. 2) I - Subarrays in Range L-R
    • 最大 101410^{14} 程度になる累積和の値を座標圧縮し、BIT(セグメント木)で個数を数えています。
  • AALC001 J - Long Binary String
    • クエリを先読みして区間の端点を座標圧縮し、長さ 10910^9 の文字列を小区間の並びに直して、セグメント木で反転を処理しています。
  • AALC001 K - Multiset
    • クエリを先読みして現れる値を座標圧縮し、値ごとの情報をセグメント木で管理しています。

二分探索のリンク集

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

二分探索は、答えの候補が並んでいて、ある境目より手前では条件を満たさず、そこから先ではずっと満たす(単調性がある)ときに、その境目を 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 回以内の質問で探します。列も同じです。