D1T1 - Bus
この問題は、各クエリに最適なバスの乗車時間を計算するため、離線処理を活用します。乗車時間の最適化は、バスの到着時間を基準に、最遅乗車時間を求めることで達成されます。バスの到着時間をソートし、各バスの出発時間を管理します。クエリの処理には、バスの到着時間を基準にソートし、必要なバスのみを検索します。
時間計算の複雑度は、\( \mathcal{O}((N + M + Q) \log M) \)です。
struct BusInfo {
int index;
i64 arrival;
BusInfo(int i, i64 a) : index(i), arrival(a) {}
bool operator<(const BusInfo& b) const {
return arrival == b.arrival ? index < b.index : arrival < b.arrival;
}
};
int n, m, q;
i64 L[100001], ans[100001];
vector<BusInfo> buses, final_buses;
void solve() {
// 入力読み込みと初期化
for (int i = 0; i < m; ++i) {
int a, b, x, y;
// 入力
buses.push_back(BusInfo(i, x));
// 到着時刻の管理
}
sort(buses.begin(), buses.end(), [](const BusInfo& a, const BusInfo& b) {
return a.arrival < b.arrival;
});
// 最終バスの管理
for (int i = 0; i < buses.size(); ++i) {
if (buses[i].index == n) {
final_buses.push_back(buses[i]);
}
}
// クエリの処理
sort(final_buses.begin(), final_buses.end(), [](const BusInfo& a, const BusInfo& b) {
return a.arrival > b.arrival;
});
// 結果計算
for (int i = 0; i < q; ++i) {
if (final_buses.empty()) {
ans[i] = -1;
} else {
ans[i] = final_buses.back().arrival;
}
}
// 結果出力
}
D1T2 - Growing Vegetables is Fun
この問題は、配列を単峰配列として構成し、逆序数を計算します。単峰配列の形成には、最大値を基準に左右に展開します。逆序数の計算には、BIT（Fenwick Tree）を用いて効率的に管理します。
時間計算の複雑度は、\( \mathcal{O}(N \log N) \)です。
struct FenwickTree {
int size;
vector<int> tree;
FenwickTree(int s) : size(s), tree(s + 1, 0) {}
void update(int index, int val) {
while (index <= size) {
tree[index] += val;
index += index & -index;
}
}
int query(int index) {
int res = 0;
while (index > 0) {
res += tree[index];
index -= index & -index;
}
return res;
}
};
int n;
int a[100001], id[100001];
i64 result;
void solve() {
// 入力読み込み
// 配列のソート
sort(id, id + n, [](int a, int b) {
return a > b;
});
// BITの初期化
FenwickTree ft(n);
// 逆序数の計算
for (int i = 0; i < n; ++i) {
result += ft.query(id[i]);
ft.update(id[i], 1);
}
// 結果出力
}
D1T4 - Ramen
この問題は、配列の要素を交互に比較し、最大値と最小値を分離します。交互比較の回数は、\( \lfloor \frac{N}{2} \rfloor \)です。
#include <vector>
#include <algorithm>
using namespace std;
const int MAX = 1003;
int left[MAX], right[MAX];
int numL = 0, numR = 0;
void Ramen(int N) {
for (int i = 0; i < N; i += 2) {
if (i + 1 < N) {
if (Compare(i, i + 1) == 1) {
left[numL++] = i;
right[numR++] = i + 1;
} else {
left[numL++] = i + 1;
right[numR++] = i;
}
}
}
if (numL == 0) {
Answer(right[numR - 1], right[numR - 1]);
return;
}
int maxL = left[0];
for (int i = 1; i < numL; ++i) {
if (Compare(left[i], maxL) == 1) {
maxL = left[i];
}
}
int minR = right[0];
for (int i = 1; i < numR; ++i) {
if (Compare(minR, right[i]) == 1) {
minR = right[i];
}
}
Answer(maxL, minR);
}
D2T2 - Making Friends is Fun
この問題は、グラフの連結性を管理します。各頂点の出次数と入次数を管理し、完全グラフの形成を検出します。検出された完全グラフの数を計算します。
時間計算の複雑度は、\( \mathcal{O}(N) \)です。
struct UnionFind {
vector<int> parent, rank;
int size;
UnionFind(int s) : size(s), parent(s), rank(s, 1) {
iota(parent.begin(), parent.end(), 0);
}
int find(int x) {
if (parent[x] != x) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x == y) return;
if (rank[x] < rank[y]) swap(x, y);
parent[y] = x;
if (rank[x] == rank[y]) ++rank[x];
}
};
int n, m;
vector<int> graph[100001];
bool visited[100001];
UnionFind uf(n);
void dfs(int u) {
visited[u] = true;
for (int v : graph[u]) {
if (v != u) {
uf.unite(u, v);
if (!visited[v]) {
dfs(v);
}
}
}
}
i64 count = 0;
void solve() {
// 入力読み込み
// Union-Find初期化
// グラフ構築
// DFS実行
// 結果計算
for (int i = 0; i < n; ++i) {
int root = uf.find(i);
if (root == i) {
count += uf.rank[i];
}
}
// 結果出力
}
D2T3 - Stamp Rally
この問題は、各駅での決断を管理します。4つの決断を分析し、最適な道順を計算します。決断の管理には、動的計画法を用いて、未マッチの左括号数を管理します。
時間計算の複雑度は、\( \mathcal{O}(N^2) \)です。
int n;
i64 T;
int U[100001], V[100001], E[100001], D[100001];
i64 dp[100001][100001];
void solve() {
// 入力読み込み
// 初期化
dp[0][0] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j <= n; ++j) {
// 状態遷移
if (j > 0) {
dp[i][j] = min(dp[i][j], dp[i - 1][j - 1] + V[i] + D[i]);
}
if (j < n) {
dp[i][j] = min(dp[i][j], dp[i - 1][j + 1] + U[i] + E[i]);
}
}
}
// 結果計算
// 結果出力
}
D3T1 - JOIOJI
この問題は、文字列の前処理を用いて、特定の文字組み合わせを検出します。前処理の結果を基準に、最適な区間を検出します。
時間計算の複雑度は、\( \mathcal{O}(N) \)です。
int n;
string s;
int preJ, preO, preI;
map<pair<int, int>, int> mp;
void solve() {
// 初期化
mp[{0, 0}] = 0;
// 文字列前処理
for (int i = 0; i < n; ++i) {
if (s[i] == 'J') preJ++;
if (s[i] == 'O') preO++;
if (s[i] == 'I') preI++;
// 状態管理
auto key = make_pair(preJ - preO, preO - preI);
if (mp.find(key) != mp.end()) {
result = max(result, i - mp[key]);
} else {
mp[key] = i;
}
}
// 結果出力
}
D3T2 - Scarecrows
この問題は、点の分布を管理します。点の分布を分析し、特定の条件を満足する点の数を計算します。
時間計算の複雑度は、\( \mathcal{O}(N \log^2 N) \)です。
struct Point {
int x, y;
Point(int xx, int yy) : x(xx), y(yy) {}
};
int n;
Point p[100001];
int sortedY[100001];
void solve() {
// 入力読み込み
// Y座標のソート
sort(sortedY, sortedY + n);
// 点のソート
sort(p, p + n, [](const Point& a, const Point& b) {
return a.x < b.x;
});
// 分割統治法
// 結果計算
// 結果出力
}
D4T1 - Constellation 2
この問題は、ベクトルの交差を管理します。ベクトルの交差を計算し、特定の条件を満足するベクトルの数を計算します。
時間計算の複雑度は、\( \mathcal{O}(N^2) \)です。
struct Vector2D {
int x, y, c;
Vector2D(int xx, int yy, int cc) : x(xx), y(yy), c(cc) {}
};
int n;
Vector2D v[100001];
i64 result = 0;
void solve() {
// 入力読み込み
// 初期化
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
if (i == j) continue;
// 交差計算
result += computeCross(v[i], v[j]);
}
}
// 結果出力
}
D4T3 - Straps
この問題は、特定の条件を満足する数列を管理します。数列の条件を満足するため、動的計画法を用いて最適解を計算します。
時間計算の複雑度は、\( \mathcal{O}(N^2) \)です。
int n;
int a[100001];
i64 b[100001];
i64 dp[100001][100001];
void solve() {
// 初期化
sort(a, a + n, greater<int>());
// DP計算
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= n + 1; ++j) {
dp[i][j] = max(dp[i][j], dp[i - 1][j]);
// 状態遷移
}
}
// 結果計算
// 結果出力
}