緑diff埋めをしています。
ABC160 D – Line++
問題ページはこちら。
ややこしく考えず、まず、閉路のない無向グラフ
$G = (V, E) \ $ $(V = \left\{v_1,v_2, \dots, v_{N}\right\},$ $E = \left\{(v_i, v_{i + 1}) \mid i = 1, 2, \dots, N – 1\right\})$
を考えてみます。
このとき、整数の組$(i, j) (1 \leq i < j \leq N)$について、頂点$v_i$と頂点$v_j$の間の最短距離を$d$とすると、
$d = j – i$
となります。
ここで、辺集合$E$に対して新たに辺$e_{new} = (v_X, v_Y)$を追加することを考えます。
上述の整数の組$(i, j)$について、辺$e_{new}$を必ず通らなければならない場合の頂点$v_i$と頂点$v_j$の間の最短距離を$d^{\prime}$とすると、
$d^{\prime} = (v_iからv_Xまでの距離) + (v_jからv_Yまでの距離) + 1$
すなわち、
$d^{\prime} = |i – X| + |j – Y| + 1$
となります。
この問題において、$v_i$から$v_j$に向かう場合の最短経路は、$v_i$から$v_j$にかけて番号順に頂点を辿るか、途中で辺$e_{new}$を通るかの2通りしかないため、$d$と$d^{\prime}$の小さい方が頂点$v_i$と頂点$v_j$の間の最短距離となります。
#include <bits/stdc++.h>#define TYPE(c) remove_reference_t<decltype(c)>#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)#define ALL(c) c.begin(), c.end()#define SORT(c) sort(ALL(c))#define RSORT(c) sort(ALL(c), greater<TYPE(c)::value_type>())#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())using namespace std;
using ll = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr int INF = (int)1e9 + 1;
constexpr ll LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b) { if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b) { if(b < a) { a = b; return true; } else { return false; } }
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
int N, X, Y;
cin >> N >> X >> Y;
vector<ll> ans(N - 1);
for(int i = 1; i <= N - 1; i++) {
for(int j = i + 1; j <= N; j++) {
auto unuse = j - i;
auto use = abs(i - X) + abs(j - Y) + 1;
ans[min(use, unuse) - 1]++;
}}for(const auto& v : ans) {
cout << v << endl;
}return 0;
}
ABC160 E – Red and Green Apples
問題ページはこちら。
制約を見ると、$X \leq A, Y \leq B$であると書かれています。
よって、赤色のりんご、緑色のりんごそれぞれについて、美味しさの大きい順にそれぞれ$X$個、$Y$個のりんごのみを考えれば良いことが分かります。
あとは、$X$個の赤色のりんごと$Y$個の緑色のりんごについて、美味しさの小さい（手持ちの無色のりんご内もっとも美味しさの大きいものの方が美味しさが大きい）りんごを置き換えるだけです。
これにはpriority_queueを使いたくなってしまいますが（私は最初使って解きました）、実は、$X$個の赤色のりんごと$Y$個の緑色のりんごと$C$個の無色のりんごから、美味しさの大きい順に$X+Y$個取ってくるだけで良いです（絵を描くと分かりやすかった）。
#include <bits/stdc++.h>#define TYPE(c) remove_reference_t<decltype(c)>#define REP(i, n) for(TYPE(n) i = 0; i < n; i++)#define FOR(v, c) for(TYPE(c.begin()) v = c.begin(); v != c.end(); v++)#define ALL(c) c.begin(), c.end()#define SORT(c) sort(ALL(c))#define RSORT(c) sort(ALL(c), greater<TYPE(c)::value_type>())#define UNIQUE(c) c.erase(unique(ALL(c)), c.end())using namespace std;
using ll = long long;
constexpr int MOD = (int)1e9 + 7;
constexpr int INF = (int)1e9 + 1;
constexpr ll LINF = (ll)1e18 + 1;
template<typename T> constexpr bool chmax(T& a, const T& b) { if(a < b) { a = b; return true; } else { return false; } }
template<typename T> constexpr bool chmin(T& a, const T& b) { if(b < a) { a = b; return true; } else { return false; } }
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
ll X, Y, A, B, C;cin >> X >> Y >> A >> B >> C;
vector<int> pv(A), qv(B), rv(C);
REP(i, A) {
cin >> pv[i];
}REP(i, B) {
cin >> qv[i];
}REP(i, C) {
cin >> rv[i];
}RSORT(pv);
RSORT(qv);
REP(i, X) {
rv.push_back(pv[i]);
}REP(i, Y) {
rv.push_back(qv[i]);
}RSORT(rv);
cout << accumulate(rv.begin(), rv.begin() + X + Y, 0LL) << endl;
return 0;
}