AtCoder Regular Contest 098 F - Donation

AtCoder 競技プログラミング

なんかDPについて少しだけお気持ちがわかった気になったよ。

問題

F - Donation

にゃっほい

これは日本語のeducationalがわかりやすかったです(seica視点)。

思いっきり解説を見たので実際に解くときにどうゆう流れで行くべきかを考えていくわけですが。

基本的には最初っからDPをにらむべきっぽいですね。

まあ、どこからスタートするべきか、どうゆう移動をするべきか等、全探索が必要そうなにおいがあるので。

ではDPをするとしたときに何が必要かというと「状態」と「状態遷移」になるのでそれに相当するものを探すと解法のようなものが見つかると。

操作を逆から見るというのはかなり定番ですね、ある程度の難易度帯になると操作を変形するというのも多くなってきますね。

最近だとARC096のSweet Alchemyでしょうか。あれに関してはすぐにDの制約が煩わしくなるので変換がしやすいですが、こっちは扱いずらいと思いつつもなかなかすぐには思いつかなそうですね。操作を逆から見たいと思うと初めて妥当な言いかえができる感じ。(seica視点)

見つけるべき大事なポイントが

  • (操作を逆から見たときに)ある点に初めて訪れた際には必ずB_vもらうべきで、一度訪れた点は何度も通ってよくなる。

というものでしょうか。これが飲み込めると一気に理解が進みますね。

UnionFindをつかった木の構築について少々手こずりましたね、こうゆう定番のデータ構造やアルゴリズムを利用しつつやりたいことを行う処理はむつかしい、ちゃんとした理解が必要になりますね。

今回はDPの遷移をどうするか、という問題でした。コードが思ったよりあっさりしてビックリ。

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG_MODE
	#define DBG(n) n;
#else
	#define DBG(n) ;
#endif
#define REP(i,n) for(ll (i) = (0);(i) < (n);++i)
#define rep(i,s,g) for(ll (i) = (s);(i) < (g);++i)
#define rrep(i,s,g) for(ll (i) = (s);i >= (g);--(i))
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
#define SHOW1d(v,n) {for(int WWW = 0;WWW < (n);WWW++)cerr << v[WWW] << ' ';cerr << endl << endl;}
#define SHOW2d(v,i,j) {for(int aaa = 0;aaa < i;aaa++){for(int bbb = 0;bbb < j;bbb++)cerr << v[aaa][bbb] << ' ';cerr << endl;}cerr << endl;}
#define ALL(v) v.begin(),v.end()
#define Decimal fixed<<setprecision(20)
#define INF 1000000000
#define LLINF 1000000000000000000LL
#define MOD 1000000007

typedef long long ll;
typedef pair<ll,ll> P;

struct UF
{
	vector<int> par; // 親のインデックスを記憶する配列
	vector<int> sz; // サイズを記憶する。
	vector<int> rank;
	// 初期化
	UF(int n):par(n),sz(n),rank(n){
		for(int i = 0; i < n; i++){
			par[i] = i;sz[i] = 1;rank[i] = 0;
		}
	}
	// 親を求める
	int find(int x) {
		if (par[x] == x) return x;
		else return par[x] = find(par[x]);
	}
	// xとyの属する集合を併合
	void unite(int x, int y) {
		x = find(x); y = find(y);
		if (x == y) return;
		if(rank[x] < rank[y]){
			par[x] = y;
			sz[y] += sz[x];
		}
		else{
			par[y] = x;
			sz[x] += sz[y];
			if(rank[x] == rank[y])rank[x]++;
		}
	}
	// xとyが同じ集合ならtrue
	bool same(int x, int y) { return find(x) == find(y); }
	// 素の集合のサイズを求める
	int size(int n){return sz[find(n)];}
};

ll n,m;
ll a[111111];
ll b[111111];
ll c[111111];
vector<pair<ll,pair<ll,ll>>> edge;
vector<vector<int>> v(111111);

ll dfs(ll node){
	ll ret = LLINF;
	ll tmp_sum = b[node];
	vector<ll> seica(v[node].size());
	REP(i,v[node].size()){
		seica[i] = max(dfs(v[node][i]),c[node]);
		tmp_sum += b[v[node][i]];
	}
	REP(i,v[node].size()){
		ret = min(ret,seica[i]+tmp_sum-b[v[node][i]]);
	}
	
	ret = min(ret,c[node]+tmp_sum);
	
	b[node] = tmp_sum;
	return ret;
}

int main(){
		
	cin >> n >> m;
	ll ma = -1;
	ll node;
	REP(i,n){
		cin >> a[i] >> b[i];
		c[i] = max(0LL,a[i] - b[i]);
		if(ma < c[i]){ma = c[i],node = i;}
	}
	REP(i,m){
		int x,y;cin >> x >> y;
		x--;y--;
		edge.PB(MP(max(c[x],c[y]),MP(x,y)));
	}
	
	sort(ALL(edge));
	
	UF uf(n);
	
	REP(i,m){
		ll A = edge[i].SE.FI;
		ll B = edge[i].SE.SE;
		if(uf.same(A,B))continue;
		if(c[A] < c[B]){
			v[B].PB(uf.find(A));
			uf.par[uf.find(A)] = B;
		}
		else{
			v[A].PB(uf.find(B));
			uf.par[uf.find(B)] = A;
		}
		uf.unite(A,B);
	}
	
	cout << dfs(node) << endl;
		
	return 0;
}