座表圧縮 (ABC188D)
昨日のABC188、Dが解けず３完だった。
いもす法と座表圧縮かなと思いつつ、座標圧縮への理解が曖昧だった＋本番の焦りもありACできなかった。
最近なんとなく解法が浮かぶのは成長だなと思いつつも、あと一歩詰めきれないところが甘いので書いていく。
座標圧縮
座標圧縮とはある数列に対して位置関係や大小関係などを保存しつつ、より小さい数値で表現し直す手法。
例えば、という数列に対して大小関係を保持しつつ数値変換を行うと
のように表現できる。
この時、当然スケールの情報は失われるが位置関係や大小関係が重要な問題などでは有効な場合がある。
どう適用するか
今回のABC188 Dは区間の問題である。問題文から、imos法を知っていれば明らかにそれ(いもす法で解くやつ)だなとわかる。
ただし、今回はありうる区間の座標が1e9のため、そのままではシミュレートができない。
そこで座標圧縮で区間の位置関係を保持しつつ小さい値へ変換を行う。
具体的には、あり得る座標群を取得し、それに対して昇順でindexを付ければ良い。
C++ならば例えば下記のように実現できる。
/* a,bは区間の始点終点を保持したvector */ //あり得る座標群を重複なしで取得 set<int> day_set; rep(i, n) { day_set.insert(a[i]); day_set.insert(b[i]+1); // いもす法用に+1しておく } //座標群を昇順にsort vector<int> day_list(day_set.begin(), day_set.end()); sort(day_list.begin(), day_list.end()); //この時点でday_listに保持された順序が圧縮後の座標になる
これで座標圧縮できたが、いもす法を行うために実座標->圧縮座標への変換用のhash mapを持っておくと便利なので作っておく。
//実座標->圧縮座標への変換hash mapを作る map<int, int> real2comp; rep(i, L) { real2comp[day_list[i]] = i; }
これで前準備ができたので、いもす法を行なっていく
vector<long long> dp(L + 1, 0); //メモ rep(i, n) { dp[real2comp[a[i]]] += c[i]; dp[real2comp[b[i]+1]] -= c[i]; } //シミュレート rep(i, L) { dp[i + 1] += dp[i]; }
最終的に計算すべき料金は期間を通しての合計料金なので、実座標での期間を考慮しつつ加算していけばok
// 元座標の区間長さを考慮しながら加算していく long long res = 0; rep(i, L - 1) { res += (day_list[i + 1] - day_list[i]) * min(C, dp[i]); } //prime料金Cとdp[i]の低いほうを選ぶのが最適
全コード
#include <algorithm> #include <cmath> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define rep(i, n) for (int i = 0; i < (n); i++) #define reps(i, n, s) for (int i = (s); i < (n); i++) #define rrep(i, n) for (int i = (n - 1); i >= 0; i--) #define rreps(i, n, s) for (int i = s; i >= n; i--) using ll = long long; using namespace std; constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int MOD = 1000000007; int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, C; cin >> n >> C; vector<ll> a(n), b(n), c(n); rep(i, n) { cin >> a[i] >> b[i] >> c[i]; b[i] += 1; //いもす法での立ち下がり点 } //あり得る座標群を重複なしで取得 set<ll> day_set; rep(i, n) { day_set.insert(a[i]); day_set.insert(b[i]); } //座標群を昇順にsort vector<ll> day_list(day_set.begin(), day_set.end()); sort(day_list.begin(), day_list.end()); ll L = day_list.size(); //座標圧縮後の座標の長さ //実座標->圧縮座標への変換hash mapを作る map<ll, ll> real2comp; rep(i, L) { real2comp[day_list[i]] = i; } //圧縮後の座標でいもす法をやっていく vector<ll> dp(L + 1, 0); //メモ rep(i, n) { dp[real2comp[a[i]]] += c[i]; dp[real2comp[b[i]]] -= c[i]; } //シミュレート rep(i, L) { dp[i + 1] += dp[i]; } // 元座標の区間長さを考慮しながら加算していく ll res = 0; rep(i, L - 1) { res += (day_list[i + 1] - day_list[i]) * min(C, dp[i]); } cout << res << endl; return 0; }
おまけ
今回の問題に関しては解説における解のように、sort＋変化点だけに着目して前から見てく方式の方がコード自体はシンプル。
#include <algorithm> #include <cmath> #include <cstring> #include <deque> #include <iomanip> #include <iostream> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> #define pb push_back #define rep(i, n) for (int i = 0; i < (n); i++) #define reps(i, n, s) for (int i = (s); i < (n); i++) #define rrep(i, n) for (int i = (n - 1); i >= 0; i--) #define rreps(i, n, s) for (int i = s; i >= n; i--) using ll = long long; using namespace std; constexpr long long MAX = 5100000; constexpr long long INF = 1LL << 60; constexpr int MOD = 1000000007; int main() { cin.tie(0); ios::sync_with_stdio(false); ll n, C; cin >> n >> C; vector<pair<ll, ll>> event; rep(i, n) { ll a, b, c; cin >> a >> b >> c; event.pb({a, c}); event.pb({b + 1, -c}); } sort(event.begin(), event.end()); ll res = 0, t = 0, fee = 0; for (auto v : event) { if (v.first != t) { res += min(C, fee) * (v.first - t); t = v.first; } fee += v.second; } cout << res << endl; return 0; }
