コンテンツにスキップ

いもす法

タグ「いもす法」の記事 4 件

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 が入るので打ち消し合います。

累積和・いもす法のリンク集

累積和といもす法について、参考になる記事や資料をまとめました。

累積和は、数列 a0,…,aN−1a_0, \dots, a_{N-1} に対して S0=0S_0 = 0、Si+1=Si+aiS_{i+1} = S_i + a_i を前計算しておき、区間 [l,r)[l, r) の和を Sr−SlS_r - S_l で O(1)O(1) で求める手法です。2 次元に広げると、長方形の範囲の和も 4 つの値の足し引きで求められます。

いもす法は、その逆の操作です。「区間 [l,r)[l, r) に xx を足す」を ll に +x+x、rr に −x-x と記録するだけで済ませ、最後に累積和をとって全体の値を一度に求めます。2 次元(長方形への加算)や、木の上(部分木への加算)にも使えます。

資料によって、区間を半開区間 [l,r)[l, r) で書くものと閉区間 [l,r][l, r] で書くものがあります。読み比べるときは、どちらの流儀かに気をつけてください。

  • 累積和を何も考えずに書けるようにする!(けんちょん、Qiita)
    • 半開区間と S0=0S_0 = 0 の流儀で 1 次元の累積和を丁寧に説明し、2 次元の累積和まで扱っています。例題 5 問の C++ の解答つきで、最後にいもす法やしゃくとり法などの発展の話題も紹介しています。
    • 2-1 節の検算で「s13=a1+⋯+a12s_{13} = a_1 + \dots + a_{12}」のように添字が 1 ずれています(定義どおりなら a0a_0 からの和です)。差をとった結果は正しいです。
  • 区間の和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 1 次元の累積和を、図を多く使って初心者向けに説明しています。C++ の実装と練習問題つきです。
  • 二次元での区間和を求めるアルゴリズム(区間の更新なし)(アルゴリズムロジック)
    • 2 次元の累積和の作り方と長方形の和の求め方を、たくさんの図で説明しています。
    • 最後の「更新がある場合」で 2 次元 BIT の計算量を O(log⁡HW)O(\log HW) としていますが、正しくは O(log⁡Hlog⁡W)O(\log H \log W) です。

コードは int で書かれているものが多いので、和が大きくなる問題では long long を使ってください。

  • いもす法(いもす研)
    • 考案者のいもすさんによる解説です。1 次元の基本から、2 次元、三角形・六角形の座標系、高次(2 次関数など)まで、図を多く使って説明しています。コードは C/C++ で、区間は半開区間です。英語版もあります。
    • 区間の右端 EiE_i が TT になり得るのに、配列を大きさ TT で扱っています。書き写すときは、配列を 1 つ大きく取ってください。
    • 2 次元の説明で、(Ai,Di)(A_i, D_i) を「右上」、(Bi,Ci)(B_i, C_i) を「左下」と呼んでいますが、コードの座標の向きでは逆です。どちらも −1-1 を足す点なので、結果は変わりません。
  • Pythonで累積和・累積積(itertools.accumulate)(note.nkmk.me)
    • itertools.accumulate の使い方の解説です。initial=0 を指定すると先頭に 00 がついた長さ N+1N + 1 の累積和になること、max や operator.mul を渡して累積 max や累積積を作れることが分かります。

木の上のいもす法を一般的に解説した定番の記事は見つからなかったので、問題の解説記事を挙げます。

  • AtCoder ABC 138 D - Ki(けんちょんの競プロ精進記録)
    • 部分木全体への加算を、根の頂点に記録しておき、最後に根から子へ値を配ることで O(N+Q)O(N + Q) にする方法です。配列のいもす法から順に木へ移していく流れで説明しています。コードは C++ の再帰 DFS です。
  • AtCoder ABC 187 E - Through Path(けんちょんの競プロ精進記録)
    • 「部分木の外への加算」を「全体に足して、部分木から引く」に言い換えて、上と同じ方法に帰着させています。
  • いもす法のカテゴリ(けんちょんの競プロ精進記録)
    • いもす法を使う問題の解説がまとまっていて、問題集としても使えます。

累積和・いもす法そのものを解説した講座はありません。

  • 転置原理入門
    • 転置原理の講座で、具体例として区間和クエリ(累積和)の解法を転置すると、区間加算クエリの解法が得られることを示しています。5.4 節で、それが imos 法であると紹介しています。累積和といもす法の関係を知りたい人向けの発展的な読み物で、累積和は前提知識として扱われています。
  • 累積和(日本語版 Wikipedia)、Prefix sum(英語版 Wikipedia)
    • 定義と、inclusive scan・exclusive scan の違い、並列計算での求め方が中心です。区間和を求める使い方の説明はほとんどないので、用語を確かめる程度に使ってください。いもす法(差分配列)の記事は日本語版・英語版ともにありません。
  • Summed-area table(英語版 Wikipedia)
    • 2 次元の累積和の記事で、画像処理(integral image)の文脈で書かれています。dd 次元への一般化の式も載っています。dd 次元の段落では、2 次元の段落と点の名前の付け方が入れ替わっています。
  • Introduction to Prefix Sums(USACO Guide)
    • 1 次元の累積和の入門で、C++・Java・Python のコードと練習問題の一覧があります。
    • 最初の Python のコードは psums[-1] を psum[-1] と書き間違えていて、そのままでは動きません。
  • More on Prefix Sums(USACO Guide)
    • 最大部分配列和、2 次元の累積和(構築の様子が見られる図つき)、差分配列(いもす法)を扱っています。区間は閉区間で書かれています。
  • An Introduction To Difference Arrays(arujbansal、Codeforces)
    • 1 次元の差分配列の短い入門です。閉区間 [L,R][L, R] で書いていて、配列を N+2N + 2 の大きさで取る理由も説明しています。

ABC479 E - Larger Component

NN 頂点の木があり、辺 ii は頂点 AiA_i と BiB_i を結びます(NN は奇数)。各 i=1,…,N−1i = 1, \dots, N - 1 について、辺 ii を取り除いてできる 2 つの連結成分のうち、頂点数が多い方のすべての頂点 vv の xvx_v に ii を足します。最終的な x1,…,xNx_1, \dots, x_N を求める問題です(3≤N≤2×105−13 \le N \le 2 \times 10^5 - 1)。

頂点 11 を根とする根付き木で考えます。辺 ii が親 uu と子 vv を結ぶとき、辺 ii を取り除いてできる連結成分は「vv の部分木」と「それ以外」です。vv の部分木の頂点数 szv\mathrm{sz}_v は、葉の側から足し合わせれば全頂点について O(N)O(N) で求められます。

  • 2 szv>N2 \, \mathrm{sz}_v > N なら、vv の部分木の全頂点に ii を足します。
  • そうでなければ、vv の部分木以外の全頂点に ii を足します。これは「全頂点に ii を足し、vv の部分木の全頂点から ii を引く」と言い換えられます。

どちらも「ある頂点の部分木全体に値を足す」操作になります(全頂点は根の部分木です)。これは木の上のいもす法で処理できます。頂点 ww の部分木全体に cc を足すときは、配列の ww の位置にだけ cc を足しておきます。すべて記録したら、根から葉に向かって親の値を子に足していきます。すると、各頂点の値は根からその頂点までの経路上の記録の合計になります。これは、その頂点を部分木に含む頂点への加算の合計なので、求める xvx_v です。

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

Python
N = int(input())
G = [[] for _ in range(N)]
for i in range(1, N):
a, b = map(int, input().split())
G[a - 1].append((b - 1, i))
G[b - 1].append((a - 1, i))
par = [-1] * N
pid = [0] * N
order = [0]
for u in order:
for v, i in G[u]:
if v != par[u]:
par[v] = u
pid[v] = i
order.append(v)
sz = [1] * N
for v in reversed(order[1:]):
sz[par[v]] += sz[v]
x = [0] * N
for v in order[1:]:
i = pid[v]
if sz[v] * 2 > N:
x[v] += i
else:
x[0] += i
x[v] -= i
for v in order[1:]:
x[v] += x[par[v]]
print(*x)

頂点 11(コード上は 0)から BFS して、order に訪問順、par[v] に親、pid[v] に親と結ぶ辺の番号を記録しています。order を逆順に見ると子が親より先に来るので、部分木のサイズ sz が求まります。最後に order の順に親の値を子に足すことで、いもす法の記録を伝えています。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/tree.hpp"
void solve() {
LL(N);
Tree<> tree(N);
tree.read();
RootedTree<> rooted(tree, 0);
vl sz(N, 1);
for (ll u : rooted.postorder) {
for (ll v : rooted.child[u]) {
sz[u] += sz[v];
}
}
vl ans(N, 0);
for (auto e : rooted.edges()) {
ll u = e.src;
ll v = e.dst;
if (rooted.depth[u] > rooted.depth[v]) {
std::swap(u, v);
}
if (sz[v] * 2 > N) {
ans[v] += e.id + 1;
} else {
ans[0] += e.id + 1;
ans[v] -= e.id + 1;
}
}
for (ll u : rooted.preorder) {
for (ll v : rooted.child[u]) {
ans[v] += ans[u];
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

RootedTree は頂点 0 を根とする根付き木で、postorder(帰りがけ順)、preorder(行きがけ順)、child、depth を持っています。各辺について深い方の端点を v とし、v が子になるようにしています。辺の番号 e.id は 0 始まりなので、11 を足しています。

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

ABC478 D - Range Set Insertion Query

はじめ空の集合 S1,…,SNS_1, \ldots, S_N に対して、「SL,…,SRS_L, \ldots, S_R に値 XX を追加する」という操作を QQ 回行います。最後に各 SiS_i の要素数を求める問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

SiS_i の要素数は「ii を含む区間が 1 つ以上ある値 XX の個数」です。同じ XX の区間が重なっていると、単純にいもす法で数えたときに XX を 2 回以上数えてしまうのが問題です。

そこで、値 XX ごとに区間をまとめ、重なっている区間を併合して互いに重ならない区間の集まりにしてから、いもす法で +1+1 します。こうすれば、各位置で同じ XX が数えられるのは高々 1 回です。

区間の併合は、区間を左端でソートして前から見ていき、今の区間の左端が直前にまとめた区間の右端以下なら右端を伸ばし、そうでなければ新しい区間として追加すればできます。

XX でソートしてから同じ XX ごとに処理し、計算量はソートの O(Qlog⁡Q)O(Q \log Q) といもす法の O(N)O(N) を合わせて O(N+Qlog⁡Q)O(N + Q \log Q) です。

コードでは区間を半開区間 [L−1,R)[L - 1, R) で持っているので、隣り合っているだけの区間(右端 == 次の左端)も併合されますが、和集合は変わらないので問題ありません。

Python
from operator import itemgetter
N, Q = map(int, input().split())
LRX = [tuple(map(int, input().split())) for i in range(Q)]
LRX.sort(key=itemgetter(2))
imos = [0] * (N + 1)
i = 0
while i < Q:
x = LRX[i][2]
tmp = [(LRX[i][0] - 1, LRX[i][1])]
i += 1
while i < Q and LRX[i][2] == x:
tmp.append((LRX[i][0] - 1, LRX[i][1]))
i += 1
tmp.sort()
l = []
for a, b in tmp:
if l and l[-1][1] >= a:
l[-1] = (l[-1][0], max(l[-1][1], b))
else:
l.append((a, b))
for a, b in l:
imos[a] += 1
imos[b] -= 1
for i in range(N):
imos[i + 1] += imos[i]
print(*imos[:N])