kmjp's blog

競技プログラミング参加記です

K4PC : F - タイトル未定(Untitled)

その他コンテスト

この解法は自力では思い浮かばないなぁ。
http://k4pc.contest.atcoder.jp/tasks/k4pc_f

問題

１次元の数直線上にN個の点がある。
各点P[i]は座標X[i]にある。

各点P[i]において、満たすべき条件K[i]、D[i]が与えられる。
それは、自分自身を含め、X[i]からK[i]番目に近い点がX[i]から距離D[i]にあることである。

上記条件を満たすため、頂点を追加することができる。
10^5以下の頂点追加で条件を満たせるなら、追加する座標を答えよ。
10^5より多くの頂点を追加することで条件を満たせるなら、"too many"と答えよ。
どう追加しても条件を満たせない場合、"impossible"と返せ。

解法

自力で解けないので、Editorialを見て回答。

座標－∞からxまでの間にある頂点の数をS[x]とする。
各点P[i]は以下の両方の条件を満たさなければならない。

  • 距離D[i]未満の点はK[i]個未満。すなわちS[X[i]+D[i]-1]-S[X[i]-D[i]] ＜ K[i]
  • 距離D[i]以下の点はK[i]個以上。すなわちS[X[i]+D[i]]-S[X[i]-D[i]-1] ≧ K[i]

両者を式変形すると、以下の２式が求められる。

  • S[X[i]+D[i]-1] ≦ S[X[i]-D[i]] + (K[i]-1)
  • S[X[i]-D[i]-1] ≦ S[X[i]+D[i]] + (-K[i])

また、最初にあるN頂点のうち、座標xにある頂点数をQ[x]とすると、以下の式が得られる。

  • S[x-1] ≦ S[x] + (-Q[x])

この形の不等式は、グラフの最小コスト問題に落とし込むことができる。
よって各S[x]に相当する頂点を作り、上記不等式における定数項をコストとしたグラフを作る。

S[x]はすべてのxについて考慮する必要はない。
S[x]のうち、値が変化しうる場所は下記の通りであるので、座標圧縮の要領でこれらの点だけS[x]を求めればよい。

  • S[X[i]]
  • S[X[i]+D[i]-1]
  • S[X[i]+D[i]]
  • S[X[i]-D[i]-1]
  • S[X[i]-D[i]]

初期位置をS[∞]とし、(コストに負の値を含むので)Bellman-Ford法を適用するとS[-∞]のコストを得られる。

S[-∞]に至る経路がない場合、条件を満たせないので"impossible"である。

  • S[-∞]が条件を満たすのに必要な点の個数なので、-S[-∞]-Nが10^5より大きいなら、10^5個より多くの頂点を追加する必要があるので、"too many"である。
  • S[-∞]-Nが10^5以下なら、S[x]の値が変化する点が頂点がおかれた点なので、元のN個分を除いた追加すべき頂点の座標を得ることができる。
int N;
ll X[100001],K[100001],D[1000001];
map<ll,int> M;
vector<ll> V;
vector<int> num;

template<int MV> class Bellman_Ford {
public:
	int NV;
	ll cost[MV];
	vector<pair<int,ll> > E[MV];
	
	void add_edge(int from,int to,ll cost){ E[from].push_back(make_pair(to,cost));}
	bool calc(int start,int NV) {
		int i,j,k;
		FOR(i,NV) cost[i]=1LL<<61;
		cost[start]=0;
		FOR(i,NV) {
			bool up=false;
			FOR(j,NV) FOR(k,E[j].size()) {
				if(cost[E[j][k].first]>cost[j]+E[j][k].second) {
					cost[E[j][k].first]=cost[j]+E[j][k].second;
					up=true;
				}
			}
			if(!up) return true;
		}
		return false;
	}
};

Bellman_Ford<500010> bf;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	M[1LL<<40]=M[-1LL<<40]=0;
	FOR(i,N) {
		cin>>X[i]>>K[i]>>D[i];
		M[X[i]]=M[X[i]+D[i]]=M[X[i]+D[i]-1]=M[X[i]-D[i]]=M[X[i]-D[i]-1]=0;
	}
	
	ITR(it,M) it->second=V.size(), V.push_back(it->first), num.push_back(0);
	FOR(i,N) num[M[X[i]]]++;
	
	
	for(i=1;i<V.size();i++) bf.add_edge(i,i-1,-num[i]);
	FOR(i,N) bf.add_edge(M[X[i]-D[i]],M[X[i]+D[i]-1],K[i]-1);
	FOR(i,N) bf.add_edge(M[X[i]+D[i]],M[X[i]-D[i]-1],-K[i]);
	if(!bf.calc(V.size()-1,V.size())) return _P("impossible\n");
	if((-bf.cost[0])-N>100000) return _P("too many\n");
	vector<ll> VV;
	for(i=1;i<V.size();i++) {
		x=bf.cost[i]-bf.cost[i-1]-num[i];
		while(x--) VV.push_back(V[i]);
	}
	_P("%d\n",VV.size());
	FOR(i,VV.size()) {
		if(i!=0) _P(" ");
		_P("%lld",VV[i]);
	}
	if(VV.size()) _P("\n");
	
}

まとめ

不等式をグラフに落とせることをすっかり忘れていた。
さらにBellman-Fordのライブラリを持っていなかったので、どのみち自力回答は無理だった。
しかし勉強になったな。