Codeforces #840 : Div2 E. Node Pairs

割とすんなりだった回。
https://codeforces.com/contest/1763/problem/E

問題

有向グラフにおいて頂点対(u,v)がunidirectionalであるとは、u→vのパスはあってもv→uのパスは無いことを意味する。
有向グラフがP-reachableであるとは、互いに行き来可能な頂点対(u,v)かつu＜vである者がP個あることを意味する。

整数Pが与えられるので、P-reachableである最小頂点数と、その時のunidirectionalな頂点対の最大値を求めよ。

解法

f(n) := n-reachableとなる最小の頂点数
g(n) := n-reachableとなる最小の頂点数のグラフのうち、最大のunidirectionalな頂点対数

とする。完全グラフがいくつかあって、縮約するとそれらが1つのパスになるようにすることを考える。
k頂点の完全グラフがあるとk*(k-1)/2個のreachableな頂点対ができるので、

f(k*(k-1)/2) = k
g(k*(k-1)/2) = 0
から初めて、DPでf(n)とg(n)を埋めて行こう。

int P;

ll V[202020];
ll S[202020];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>P;
	FOR(i,201010) V[i]=1<<20;
	V[0]=S[0]=0;
	for(i=2;i*(i-1)/2<=P;i++) {
		for(x=0;x+i*(i-1)/2<=P;x++) {
			if(V[x]+i<V[x+i*(i-1)/2]) {
				V[x+i*(i-1)/2]=V[x]+i;
				S[x+i*(i-1)/2]=S[x]+V[x]*i;
			}
			else if(V[x]+i==V[x+i*(i-1)/2]) {
				chmax(S[x+i*(i-1)/2],S[x]+V[x]*i);
			}
		}
	}
	
	
	
	cout<<V[P]<<" "<<S[P]<<endl;
}

まとめ

コードも短い。