imos-累積和法

2020 年 5 月 14 日
筆記
演算法----------

在解AOJ 0531 Paint Color時，學到了一個累積和的妙用——imos法，由於原文是日語，所以特意翻譯過來。值得一提的是，作者Kentaro Imajo跟鄙人同齡，卻已取得如此多的成就，而鄙人一無所成，實在汗顏。

imos法

imos法是將累積和演算法拓展到多次元、高次空間的方法。雖然程式競賽中出題最多不過2次元1次，但是2012年Kentaro Imajo將其用於高次元高次空間，在訊號處理/影像處理領域取得了成就。

基礎imos法

最簡單的imos法是1次元0次係數的求解思想。如圖，有三個俄羅斯方塊在一起，懸空的部分會掉下去，求從左到右的高度？這個高度就是橫坐標固定時，上面矩形高度之和。這就是最簡單的imos法。

例題

你在經營一個咖啡廳，你的咖啡廳里每個客人在S_i時刻進店，E_i時刻出店。求店裡最多有多少客人？（客人最多C個，時刻在T內。如果有多人同時進店出店，先算出店的人）。

樸素的解法

樸素的思想是，計算每個時刻客戶的數量，從中找出最大值。但是，複雜度是\(O(CT)\)

#include <iostream>
#include <algorithm>
using namespace std;
 
#define C 4
#define T 10
// 每個客人的進入時間
int S[C] = { 1, 3, 5, 7 };
// 每個客人的離開時間
int E[C] = { 2, 8, 6, 8 };
// 店裡的人數
int table[T];
 
int main(int argc, char *argv[])
{
	memset(table, 0, sizeof(table));
	for (int i = 0; i < C; i++) 
	{
		// 從時間 S[i] 到 E[i] - 1 店裡人數計數加一
		for (int j = S[i]; j < E[i]; j++) 
		{
			table[j]++;
		}
	}
	// 找最大値
	cout << *max_element(table, table + T) << endl;
	system("pause");
	return 0;
}

imos法解法

imos法的基本方向是，只統計出入店時刻的人數變化（我個人理解相當於求導），入店+1，出店-1。最終統計的時候，需要將每個時刻加上前一個時刻的統計量（我個人理解相當於求積分），其中的最大值就是所求。記錄複雜度O(C)，累加複雜度O(T)，所以整體複雜度O(C+T)。

#include <iostream>
#include <algorithm>
using namespace std;
 
#define C 4
#define T 10
// 每個客人的進入時間
int S[C] = { 1, 3, 5, 7 };
// 每個客人的離開時間
int E[C] = { 2, 8, 6, 8 };
// 店裡的人數
int table[T];
 
int main(int argc, char *argv[])
{
	memset(table, 0, sizeof(table));
	for (int i = 0; i < C; i++) 
	{
		table[S[i]]++;  // 入店+1
		table[E[i]]--;  // 出店-1
	}
	// 累加
	for (int i = 1; i < T; i++) 
	{
		table[i] += table[i - 1];
	}
	// 找最大値
	cout << *max_element(table, table + T) << endl;
	system("pause");
	return 0;
}

推廣到二次元

\(imos\)相對於樸素方法的一個優點就是隨著次元增大複雜度的降低越明顯。

例題

你在玩一個抓怪獸的遊戲，現在你面前是一張W*H的地圖，地圖裡有N種怪物。怪物i只會在左下角為（B_i,C_i），右上角為(A_i,D_i)的矩形區域內出現。求單位區域內最多有多少種怪獸？

樸素解法

樸素的解法就是計算每一個單位區域內出現的怪獸數，然後找出最大值。複雜度是O（NWH）。

#include <iostream>
#include <algorithm>
using namespace std;
#define  W  6
#define  H  6
#define  N  4
// 左下角坐標
int B[N] = {3,4,3,5,};
int C[N] = {0,1,2,2,};
// 右上角坐標
int A[N] = {0,3,2,2,};
int D[N] = {3,2,3,5,};
// 地圖上的分布結果
int tiles[H][W];

int main(int argc, char *argv[])
{
	memset(tiles, 0, sizeof(tiles));
	for (int i = 0; i < N; i++) 
	{
		// 怪獸 i 出現的範圍 [(A[i],C[i]), (B[i],D[i])) 內的計數加一
		for (int y = C[i]; y < D[i]; y++) 
		{
			for (int x = A[i]; x < B[i]; x++) 
			{
				tiles[y][x]++;
			}
		}
	}
	// 求最大値
	cout << *max_element(tiles[0], tiles[0] + H * W) << endl;
	system("pause");
	return 0;
}

imos法解法

矩形的左上角 (A[i],C[i]) +1 ，右上角 (A[i],D[i]) −1，左下角 (B[i],C[i]) −1 ，右下角(B[i],D[i]) +1 ，統計最終結果之前累加。加一減一 O(N)，累加(WH) 整體複雜度 O(N+WH) 。

#include <iostream>
#include <algorithm>
using namespace std;
#define  W  6
#define  H  6
#define  N  4
// 左下角坐標
int B[N] = {3,4,3,5,};
int C[N] = {0,1,2,2,};
// 右上角坐標
int A[N] = {0,3,2,2,};
int D[N] = {3,2,3,5,};
// 地圖上的分布結果
int tiles[H][W];
 
int main(int argc, char *argv[])
{
	memset(tiles, 0, sizeof(tiles));
	// 影響力計算 (圖 3)
	for (int i = 0; i < N; i++) 
	{
		tiles[C[i]][A[i]]++;
		tiles[C[i]][B[i]]--;
		tiles[D[i]][A[i]]--;
		tiles[D[i]][B[i]]++;
	}
	// 橫向累積和 (圖 4, 5)
	for (int y = 0; y < H; y++) 
	{
		for (int x = 1; x < W; x++) 
		{
			tiles[y][x] += tiles[y][x - 1];
		}
	}
	// 縱向累積和 (圖 6, 7)
	for (int y = 1; y < H; y++) 
	{
		for (int x = 0; x < W; x++) 
		{
			tiles[y][x] += tiles[y - 1][x];
		}
	}
 
	cout << *max_element(tiles[0], tiles[0] + H * W) << endl;
	system("pause");
	return 0;
}

圖三：影響力計算

圖四：橫向累加

圖五：橫向累加結果

圖六：縱向累加

圖七：縱向累加結果

更高級的用法

暫時用不到，記錄一個地址，有空再看。

參考資料

//imoz.jp/algorithms/imos_method.html

Tags: 演算法----------