ABC195-D Shipping Center
条件の厳しいやつからペアを組ませる系
atcoder.jp
【問題】
箱と荷物がある。荷物には重さと価値があり、箱は重さXi以下の荷物を1つしか入れられない。
適切に箱に荷物を詰めて価値を最大化せよ。
ただし、クエリごとに詰められない箱の区間が与えられる。
【典型ポイント】
条件の厳しい順に貪欲
【方針】
直感的に、大きさの小さな箱から順に「詰められる荷物のうち価値が最大の荷物」を割り当てていくのが最適に思える。
ある箱に入れられる荷物はより大きい箱にも入れられるので、なるべく小さい箱に入れたい、というお気持ち
各値が小さいので愚直にシミュレートしても間に合うので、そのままやる。
クエリごとに使えない箱が出てくるが、愚直に取り除いても間に合う。
【感想】
Dで制約が緩いやるだけ問題は珍しいと思った
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<long long, long long>; constexpr char ln = '\n'; constexpr long long MOD = 1000000007; constexpr long long INF = 1000000000 + 100; constexpr long long LINF = 1000000000000000000 + 100; #define all(v) v.begin(), v.end() #define rep(i, n) for(int i=0;i<(n);i++) #define rept(i, j, n) for(int i=(j); i<(n); i++) #define rrep(i, n) for(int i=(n); i>=0; i--) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } int main(){ int N, M, Q; cin >> N >> M >> Q; vector<pll> nimotu(N); //value, weight rep(i, N){ ll w, v; cin >> w >> v; nimotu[i] = {v, w}; } sort(all(nimotu), greater<pll>()); vector<ll> X(M); rep(i, M)cin >> X[i]; vector<ll> ans; while(Q--){ int L, R; cin >> L >> R; L--; //[L, R) vector<ll> box; rep(i, M){ if(i<L or i>= R)box.push_back(X[i]); } sort(all(box)); ll res = 0; vector<int> used(N); rep(i, box.size()){ rep(j, N){ if(used[j])continue; if(nimotu[j].second <= box[i]){ res += nimotu[j].first; used[j] = true; break; } } } ans.push_back(res); } for(auto a:ans)cout << a << ln; }
ABC200-E Patisserie ABC 2
atcoder.jp
ケーキをパラメータの合計値でグループ分けする、という考察までは進んだが、そこで詰まった。
【問題】
1<=a,b,c<=Nである(a,b,c)の数列が合計値->各パラメータの昇順に並んでいる。K番目の(a,b,c)の値を出力せよ。
【典型ポイント】
辞書順Ｋ番目を求める問題は、各パラメータごとにグループ分けして考える(よくDPが使える)
【知らなかったこと】
一様の値を一定区間に連続して配る時は、DPだろうがimos法が使える
【解法1】
まず、Ｋ番目のa+b+cの合計値を知りたい。
これは、DP + imos法 で求められる。
dp[i][j]:先頭からi個のパラメータを決めたときの、パラメータの合計値がjである場合の数 とすると
遷移式：dp[i+1][j+(1~N)] += dp[i][j]
愚直に遷移するとO(N^2)かかってしまうので、一様の値を一定範囲に配ることに着目する。
imosで高速遷移を行うとdpテーブルの計算量がO(N)になって間に合う
K番目の合計値は, i=3から昇順にdp[3][i]をKから引いていき、次に引いた場合Kが0以下になる最初のiとなる。
これでKの合計値が求まった。
あとはa,b,cの値を順次確定させていく。
合計値を求めるのと同じようにa,bを昇順にチェックし、どのグループに属しているかを調べる。
【解法2】
立方体を書いてK番目の合計値を求める方法もある。（自分には使いこなせなさそう）
Nを制限しないとき、a+b+cの場合の数の増え方には規則性がある(等差数列っぽい)のだが、図にあらわすとわかりやすい。
#include <bits/stdc++.h> using namespace std; using ll = long long; using pll = pair<long long, long long>; constexpr char ln = '\n'; constexpr long long MOD = 1000000007; constexpr long long INF = 1000000000 + 100; constexpr long long LINF = 1000000000000000000 + 100; #define all(v) v.begin( ), v.end() #define rep(i,n) for(int i=0;i<(n);i++) #define rept(i, j, n) for(int i=(j); i<(n); i++) #define rrep(i, n) for(int i=(n); i>=0; i--) template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } //max(sum(a,b,c)) const int MAX_SUM = 1e6*3+100; ll dp[4][MAX_SUM]; int main(){ ll N, K; cin >> N >> K; //dp[i][j]:先頭からi番目までの数字を決定したときの、合計値がjである場合の数 dp[0][0] = 1; rep(i, 3){ rep(j, MAX_SUM){ if(dp[i][j]==0)continue; //imos 前処理 dp[i+1][j+1] += dp[i][j]; dp[i+1][j+N+1] -= dp[i][j]; } //imos 同一テーブル上でメモから値を導く rept(j,1, MAX_SUM){ dp[i+1][j] = dp[i+1][j] + dp[i+1][j-1]; } } int sum = -1; for(int i=3; i<=MAX_SUM; i++){ if(K <= dp[3][i]){ sum = i; break; } K -= dp[3][i]; } int ra = -1; for(int i=1; i<=N; i++){ if(K <= dp[2][sum-i]){ ra = i; break; } K -= dp[2][sum-i]; } int rb = -1; for(int i=1; i<=N; i++){ if(K <= dp[1][sum-ra-i]){ rb = i; break; } K -= dp[1][sum-ra-i]; } cout << ra << " " << rb << " " << sum-ra-rb << ln; }
ABC201-E Xor Distances
本番で解けず。重みを桁ごとに分解するという発想がなかった
【問題】
重み付き木が与えられる。
dist(i, j) = iからjへの最短パスに含まれる辺すべての重みのXOR
すべてのi ,j(i<j)についてdistの総和を求めよ
【忘れがちな知識】
総和は桁ごとに独立して足し合わせられる
例：123+789 = 1*10^2+7*10^2+2*10^1+8*10^1+3^10^0+9*10^0
【典型ポイント】
XOR => 桁ごとに考える
【方針】
愚直にdist(i,j)を全列挙としようとすると最低でもO(N^2)となり、全然間に合わない。
また、それぞれのdist(i, j)も高速に求める必要がある。
・2点間の最短パスを高速に求める
適当な根をrとして木を探索し、dist(r, i)を求める。
jこのとき、dist(i, j) = dist(r, i) ^ dist(r, j) となる(下図参照)
ので、任意のdist(i, j)を前計算O(N), 処理O(1)で求められる。
これで各distを高速に求めることはできたが、まだO(N^2)かかる。
・distを桁ごとに求める
dist(i, j)はXOR演算を繰り返すので、桁ごとに独立して考えることができる。
こうすると辺の重みとdist(i, j)の各桁は0か1の2通りになる。
各桁のdist(i, j)をdk(i, j)とすると
任意のi, j(i<j)を選んだ時、dk(i, j)が1になるのはdk(r,i) != dk(r, j)のときなので、
dk(i, j) = 1 と dk(r, i) != dk(r, j) が等しい。
よって、各桁においてdist(i, j) = 1 となる組み合わせの数は、1~nの各頂点において
count(dk=0) * count(dk=1)
となる。(2種類のボールの山から2個を選んだ時に色が異なる組み合わせの数と同じ)
