読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

yukicoder : No.466 ジオラマ

構築ゲーは苦手。
http://yukicoder.me/problems/no/466

問題

パラメータA,B,C,Dが与えられる。
以下の条件を満たすグラフを作成可能なら、その例を示せ。

  • 0~(N-1)番のN頂点M辺からなる有向グラフである。
  • MはD以下である。
  • 0番の頂点から有向辺をたどり到達可能な頂点はA個
  • 1番の頂点から有向辺をたどり到達可能な頂点はB個
  • 0番、1番の頂点から有向辺をたどり、どちらからも到達可能な頂点はC個
  • 0番、1番の頂点から有向辺をたどり、どちらからも到達不可能な頂点はない

解法

到達可能な頂点数を満たす最少辺のグラフを作ろう。
以下A,B,Cの関係によりグラフの形状が変わる。

  • A==B==Cの場合:
    • A==B==C==1なら解なし。
    • A==B==C>1の場合、A個の頂点で閉路を作ればよい。
  • A==CまたはB==Cの場合
    • 以下A==C、B>Cの場合を示す。B個の頂点を1列に並べて端から順に有向辺で結ぶ。最初の頂点を1番、末尾から数えてA個目の頂点を0番にすればよい。
  • C==0の場合
    • 0番に(A-1)個、1番に(B-1)個の頂点をぶら下げればよい。
  • それ以外(A>C、B>C、C!=0)
    • まずC個の頂点を1列につなげる。0番、1番の頂点からその根元の頂点に辺を張る。
    • あとは残り、0番からつながる(A-(C+1))個の頂点を追加し、1番からつながる(B-(C+1))個の頂点を追加すればよい。
int A,B,C,D;

vector<pair<int,int>> V;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B>>C>>D;
	if(A==C && B==C) {
		if(A==1) return _P("-1\n");
		FOR(i,A) V.push_back({i,(i+1)%A});
	}
	else if(A==C) {
		x=1,y=2;
		FOR(i,B-A-1) V.push_back({x,y}),x=y++;
		V.push_back({x,0});
		x=0;
		FOR(i,A-1) V.push_back({x,y}),x=y++;
	}
	else if(B==C) {
		x=0,y=2;
		FOR(i,A-B-1) V.push_back({x,y}),x=y++;
		V.push_back({x,1});
		x=1;
		FOR(i,B-1) V.push_back({x,y}),x=y++;
	}
	else if(C==0) {
		x=2;
		FOR(i,A-1) V.push_back({0,x++});
		FOR(i,B-1) V.push_back({1,x++});
	}
	else {
		V.push_back({0,2});
		V.push_back({1,2});
		x=2,y=3;
		FOR(i,C-1) V.push_back({x,y}),x=y++;
		x=y;
		FOR(i,A-(C+1)) V.push_back({0,x++});
		FOR(i,B-(C+1)) V.push_back({1,x++});
	}
	
	if(V.size()>D) _P("-1\n");
	else {
		int ma=1;
		FORR(v,V) ma=max(ma,max(v.first,v.second));
		_P("%d %d\n",ma+1,V.size());
		FORR(v,V) _P("%d %d\n",v.first,v.second);
	}
}

まとめ

なぜジオラマというタイトルにしたんだろう…。

広告を非表示にする