アルゴリズム問題におけるデータ構造の応用
本稿では、効率的なデータ処理を目的とした 5 つのアルゴリズム問題について解説します。特に、樹状配列（Binary Indexed Tree）や座標圧縮、篩を用いた前処理などの技術に焦点を当てます。
問題 1：自然数の出現頻度计数
入力された自然数の出現回数を统计し、数値の昇順で出力する問題です。値の範囲が非常に大きいため（1e10 超）、直接配列でインデックスとして扱うことはできません。ここでは座標圧縮（Discretization）を用いて値を小さい範囲に映射します。
実装時の注意点として、入力サイズに応じた適切な配列確保が必要です。メモリ制限を超えないよう、動的配列または十分な大きさの静的配列を用意します。
実装コード
#include <bits/stdc++.h>
using namespace std;
struct Data {
long long value;
int original_index;
long long compressed_value;
};
bool compareData(const Data& a, const Data& b) {
return a.value < b.value;
}
bool compareIndex(const Data& a, const Data& b) {
return a.original_index < b.original_index;
}
int main() {
int n;
scanf("%d", &n);
vector<Data> items(n);
vector<long long> sorted_vals(n);
for (int i = 0; i < n; ++i) {
scanf("%lld", &items[i].value);
items[i].original_index = i;
sorted_vals[i] = items[i].value;
}
sort(sorted_vals.begin(), sorted_vals.end());
for (int i = 0; i < n; ++i) {
items[i].compressed_value = lower_bound(sorted_vals.begin(), sorted_vals.end(), items[i].value) - sorted_vals.begin();
}
map<long long, int> count_map;
for (int i = 0; i < n; ++i) {
count_map[items[i].value]++;
}
vector<pair<long long, int>> result;
for (auto const& [val, count] : count_map) {
result.push_back({val, count});
}
sort(result.begin(), result.end());
for (const auto& p : result) {
printf("%lld %d\n", p.first, p.second);
}
return 0;
}
問題 2：非素数の计数
1 から n までの整数のうち、素数でないものの総数を求める問題です。エラトステネスの篩（Sieve of Eratosthenes）を用いて効率的に素数判定を行います。各素数の倍数をマークしていくことで、合成数を特定できます。
実装コード
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
scanf("%d", &n);
if (n < 2) {
printf("0\n");
return 0;
}
vector<bool> is_prime(n + 1, true);
is_prime[0] = is_prime[1] = false;
int non_prime_count = 0;
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j += i) {
is_prime[j] = false;
}
}
}
for (int i = 1; i <= n; ++i) {
if (!is_prime[i]) {
non_prime_count++;
}
}
printf("%d\n", non_prime_count);
return 0;
}
問題 3：Self-Number の探索
ある数 n に対して、d(n) = n + (n の各桁の和) と定義します。d(n) によって生成されない数を Self-Number と呼びます。n 以下の Self-Number の個数と、指定された順序の Self-Number を出力します。
すべての数について生成元となり得るかを布尔配列で管理し、生成された数をマークしていきます。マークされていない数が Self-Number となります。
実装コード
#include <iostream>
#include <vector>
using namespace std;
int generate_next(int n) {
int sum = n;
int temp = n;
while (temp > 0) {
sum += temp % 10;
temp /= 10;
}
return sum;
}
int main() {
int n, k;
cin >> n >> k;
vector<int> queries(k);
for (int i = 0; i < k; ++i) {
cin >> queries[i];
}
vector<bool> generated(n + 1, false);
vector<int> self_numbers;
for (int i = 1; i <= n; ++i) {
if (!generated[i]) {
self_numbers.push_back(i);
}
int next_val = generate_next(i);
if (next_val <= n) {
generated[next_val] = true;
}
}
cout << self_numbers.size() << endl;
for (int i = 0; i < k; ++i) {
if (queries[i] - 1 < self_numbers.size()) {
cout << self_numbers[queries[i] - 1] << " ";
}
}
cout << endl;
return 0;
}
問題 4：区間更新と単点查询
初期値 0 の配列に対し、区間 [l, r] の値を反転させる操作と、特定のインデックスの状態を查询する操作を行います。樹状配列を用いた差分管理により、区間更新を単点查询に変換して処理します。更新時には l に 1 を加え、r+1 に -1 を加えることで区間内の値に影響を与えます。
実装コード
#include <bits/stdc++.h>
using namespace std;
vector<int> fenwick;
int size_n;
void update(int idx, int val) {
for (; idx <= size_n; idx += idx & -idx)
fenwick[idx] += val;
}
int query(int idx) {
int sum = 0;
for (; idx > 0; idx -= idx & -idx)
sum += fenwick[idx];
return sum;
}
int main() {
int m;
scanf("%d%d", &size_n, &m);
fenwick.assign(size_n + 1, 0);
while (m--) {
int type;
scanf("%d", &type);
if (type == 1) {
int l, r;
scanf("%d%d", &l, &r);
update(l, 1);
update(r + 1, -1);
} else {
int idx;
scanf("%d", &idx);
printf("%d\n", query(idx) % 2);
}
}
return 0;
}
問題 5：区間内の出現回数 2 の要素计数
配列の区間 [L, R] において、ちょうど 2 回出現する値の個数を求める問題です。データ規模が大きいため、オフラインクエリと樹状配列を組み合わせます。右端点を固定しながら走査し、各値の出現履歴に基づいて樹状配列を更新します。
具体的には、ある値が 2 回目に出た時点で 1 を加算し、3 回目に出た時点で之前的贡献を調整します。これにより、任意の左端点に対する条件満たす要素数を前缀和で取得できます。クエリは右端点の昇順に処理する必要があります。
実装コード
#include <bits/stdc++.h>
using namespace std;
struct Query {
int l, r, id;
};
vector<int> bit_array;
int max_n;
void add(int idx, int val) {
for (; idx <= max_n; idx += idx & -idx)
bit_array[idx] += val;
}
int sum(int idx) {
int res = 0;
for (; idx > 0; idx -= idx & -idx)
res += bit_array[idx];
return res;
}
int main() {
int n, q;
scanf("%d%d", &n, &q);
max_n = n;
bit_array.assign(n + 1, 0);
vector<int> arr(n + 1);
map<int, int> last_pos;
vector<int> prev1(n + 1, -1);
vector<int> prev2(n + 1, -1);
for (int i = 1; i <= n; ++i) {
scanf("%d", &arr[i]);
if (last_pos.count(arr[i])) {
prev1[i] = last_pos[arr[i]];
if (prev1[i] != -1 && prev1[prev1[i]] != -1) {
prev2[i] = prev1[prev1[i]];
}
}
last_pos[arr[i]] = i;
}
vector<Query> queries(q);
for (int i = 0; i < q; ++i) {
scanf("%d%d", &queries[i].l, &queries[i].r);
queries[i].id = i;
}
sort(queries.begin(), queries.end(), [](const Query& a, const Query& b) {
return a.r < b.r;
});
vector<int> answers(q);
int current_r = 0;
for (const auto& qry : queries) {
while (current_r < qry.r) {
current_r++;
if (prev1[current_r] != -1) {
add(prev1[current_r], 1);
}
if (prev2[current_r] != -1) {
add(prev2[current_r], -2);
}
if (prev1[current_r] != -1 && prev1[prev1[current_r]] != -1 && prev2[prev1[current_r]] != -1) {
// Logic adjustment for 4th occurrence based on original pattern
int p3 = prev2[prev1[current_r]];
if(p3 != -1) add(p3, 1);
}
}
answers[qry.id] = sum(qry.r) - sum(qry.l - 1);
}
for (int i = 0; i < q; ++i) {
printf("%d\n", answers[i]);
}
return 0;
}
実装上の技術的検討事項
問題 1 においては、座標圧縮を用いる際に配列のサイズ設定に注意が必要です。入力値の範囲ではなく、入力个数に基づいてメモリを確保する必要があります。問題 5 のような複雑な区間クエリでは、オフライン処理による順序制御が不可欠です。右端点の昇順で処理を行うことで、樹状配列の状態を効率的に維持し、重複计数の調整を O(log N) で実現できます。