A. 全ての長さの減算
思考問題。
長さが \(k(k \in [1,n])\) の区間を選び1を引く操作を繰り返す場合、まず\(a_i = n\) の位置を特定します。次に、\(n\) が存在する区間を維持し、\(n-k+1\) がその両側に存在するか確認し、存在すれば区間を拡張します。存在しない場合は操作は不可能です。
コードを表示``` #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() { int size; cin >> size;
int left = 0, right = size;
vector<int> positions(size + 1);
for (int i = 1; i <= size; i++) {
cin >> positions[i];
if (positions[i] == size) {
left = right = i;
}
}
for (int i = size - 1; i >= 1; i--) {
if (right + 1 <= size && positions[right + 1] == i) {
right += 1;
} else if (left - 1 >= 1 && positions[left - 1] == i) {
left -= 1;
} else {
cout << "NO\n";
return;
}
}
cout << "YES\n";
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
B. 割引
============
貪欲法。
価値\\(x\\)のクーポンを使用するには、\\(x-1\\)個の最も高価な商品を購入する必要があります。支払いを最小限に抑え、無料で入手できる商品の価値を最大化するため、価値\\(x\\)が小さいクーポンを使用して、ソートされた商品の上位\\(x\\)個を購入する戦略が最適です。
コードを表示```
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() {
int item_count, coupon_count;
cin >> item_count >> coupon_count;
vector<int> items(item_count + 1), coupons(coupon_count + 1);
for (int i = 1; i <= item_count; i++) {
cin >> items[i];
}
for (int i = 1; i <= coupon_count; i++) {
cin >> coupons[i];
}
sort(items.begin() + 1, items.end());
sort(coupons.begin() + 1, coupons.end());
i64 total_cost = 0;
int coupon_index = 1;
for (int i = item_count; i >= 1; i--) {
if (coupon_index <= coupon_count && i - coupons[coupon_index] + 1 >= 1) {
for (int j = i; j > i - coupons[coupon_index] + 1; j--) {
total_cost += items[j];
}
i = i - coupons[coupon_index] + 1;
coupon_index++;
} else {
total_cost += items[i];
}
}
cout << total_cost << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
C. 最大値木
トポロジーソート。
貪欲に考えると、各辺の貢献度を最大化するために、親の値が子より大きくなるように辺の向きを決定します。これにより、キューに入れられた頂点に\(n, n-1, n-2...\)の順に値を割り当てることができます。
ここでは、辺の向きを貢献度に基づいて決定しましたが、辺の数が\(n-1\)しかないため、各辺の貢献度を比較して向きを決定するだけで十分です。
コードを表示``` #include <bits/stdc++.h>
using namespace std;
using i64 = long long;
void solve() { int node_count; cin >> node_count;
vector<array<int,3>> edge_list;
for (int i = 1; i < node_count; i++) {
int u, v, x, y;
cin >> u >> v >> x >> y;
edge_list.push_back({x, u, v});
edge_list.push_back({y, v, u});
}
vector<int> in_degree(node_count + 1);
vector<vector<int>> graph(node_count + 1);
set<array<int,2>> edge_set;
sort(edge_list.begin(), edge_list.end(), greater<>());
for (auto &[weight, from, to] : edge_list) {
if (edge_set.count({from, to}) || edge_set.count({to, from})) {
continue;
}
edge_set.insert({from, to});
in_degree[to]++;
graph[from].push_back(to);
}
int current_value = node_count;
vector<int> node_values(node_count + 1);
queue<int> q;
for (int i = 1; i <= node_count; i++) {
if (in_degree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
auto node = q.front();
q.pop();
node_values[node] = current_value--;
for (auto &neighbor : graph[node]) {
if (!--in_degree[neighbor]) {
q.push(neighbor);
}
}
}
for (int i = 1; i <= node_count; i++) {
cout << node_values[i] << " \n"[i == node_count];
}
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
D1. 転置グラフ彩色（簡単版）
================================
動的計画法。
手動で計算またはテーブルを作成すると、\\(i a\_k\\)となるような存在は不合法であることがわかります。これは3つの頂点がすべて異なる色で塗られる必要があるためですが、2色しか使用できないためです。つまり、最長単調減少部分列の長さが2以下でなければなりません。
\\(dp\_{i,j,k}\\)を前\\(i\\)個の数値の中で、最長単調減少部分列の最初の数が\\(j\\)、2番目の数が\\(k\\)である場合の数と定義します。
\\(i\\)番目の数を選ばない場合、遷移は以下のようになります：
\[dp_{i,j,k}=dp_{i-1,j,k} \]\\(i\\)番目の数を選ぶ場合、遷移は以下のようになります：
\[\begin{aligned} dp_{i,a_i,k} = dp_{i,a_i,k} + dp_{i-1,j,k} & & a_i \ge j \\ dp_{i,j,a_i} = dp_{i,j,a_i} + dp_{i-1,j,k} & & j > a_i \ge k \end{aligned} \]\\(a\_i < k\\)の場合、長さが3の単調減少部分列が形成されるため、不合法な遷移となります。
コード中のZ型は modulo クラスです。
コードを表示```
using Z = ModInt<MOD[0]>;
void solve() {
int n;
cin >> n;
vector<int> sequence(n + 1);
for (int i = 1; i <= n; i++) {
cin >> sequence[i];
}
Z result = 0;
vector<vector<Z>> dp(n + 1, vector<Z>(n + 1));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
vector<vector<Z>> new_dp(n + 1, vector<Z>(n + 1));
for (int j = 0; j <= n; j++) {
for (int k = 0; k <= j; k++) {
new_dp[j][k] += dp[j][k];
if (sequence[i] >= j) {
new_dp[sequence[i]][k] += dp[j][k];
} else if (sequence[i] >= k) {
new_dp[j][sequence[i]] += dp[j][k];
}
}
}
dp = move(new_dp);
}
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
result += dp[i][j];
}
}
cout << result << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
D2. 転置グラフ彩色（難しい版）
データ構造による動的計画法の最適化。
上記の遷移を観察すると、\(dp_{i,a_i,k} = \sum_{j=0}^{a_i}dp_{i-1,j,k}\)と\(dp_{i,j,a_i}=\sum_{k=0}^{a_i}dp_{i-1,j,k}\)であることがわかります。
これらの接頭和は、Binary Indexed Tree (BIT) を使用して管理できます。\(j\)と\(k\)を2次元に展開すると、\(k\)列の前\(j\)行の和を維持するものと、\(j\)行の前\(k\)列の和を維持するものの2つが必要になります。
\(n\le 2000\)であるため、必ずローリングが必要です。1つの方法は、遷移する状態と値を保存し、最後にまとめて遷移させることです。
BITが1から始まらない場合は、1つずつオフセットしてください。
コード中のZは modulo クラスです。
コードを表示``` using Z = ModInt<MOD[0]>;
template<typename T> struct BIT { int size; vector<T> tree;
BIT() {}
BIT(int n) {
this->size = n;
tree.resize(n + 1);
}
void update(int index, T value) {
for (; index <= size; index += index & -index) {
tree[index] += value;
}
}
T query(int index) {
T result = 0;
for (; index; index -= index & -index) {
result += tree[index];
}
return result;
}
T query(int left, int right) {
return query(right) - query(left - 1);
}
};
void solve() { int n; cin >> n;
vector<int> sequence(n + 1);
for (int i = 1; i <= n; i++) {
cin >> sequence[i];
}
Z result = 0;
vector f(2, vector(n + 1, BIT<Z>(n + 2)));
f[0][0].update(1, 1);
f[1][0].update(1, 1);
for (int i = 1; i <= n; i++) {
vector<tuple<int,int,Z>> updates;
for (int j = 0; j <= sequence[i]; j++) {
Z value = f[0][j].query(sequence[i] + 1);
updates.emplace_back(sequence[i], j, value);
}
for (int j = sequence[i] + 1; j <= n; j++) {
Z value = f[1][j].query(sequence[i] + 1);
updates.emplace_back(j, sequence[i], value);
}
for(auto &[first, second, value] : updates){
f[0][second].update(first + 1, value);
f[1][first].update(second + 1, value);
}
}
for (int i = 0; i <= n; i++) {
result += f[1][i].query(n + 1);
}
cout << result << "\n";
}
int main() { ios::sync_with_stdio(false); cin.tie(nullptr);
int test_cases;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}