kmjp's blog

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

Codeforces #236 Div1 A. Searching for Graph

CF#236に参加。
本番ABCを解いたと思ったらBを凡ミスで落とす。とはいえディスク故障でだいぶレートを落としていたのでそこそこ回復。
http://codeforces.com/contest/403/problem/A

問題

数N,Pが与えられる。
N点と(2N+P)辺からなるグラフを作りたい。
この時、N点中任意のK点を選ぶと、それらの間の辺が2K+P以下になるようにしたい。
そのようなグラフを答えよ。

解法

  1. P分はまずは置いておいて、N点で2N辺を張る場合を考える。

すると点iと点(i+1)、点iと点(i+2)と各点から計4本の辺を張るようにすればよい。

後はまだ辺を張ってない場所に順次残りP本を割り当てればよい。

void solve() {
	int f,i,j,k,l,x,y;

	int N,T,P;
	cin>>T;
	while(T--) {
		int vis[24][24];
		ZERO(vis);
		cin>>N>>P;
		FOR(i,N) {
			j=i+2;
			if(j>N) j-=N;
			_P("%d %d\n",i+1,j);
			vis[i][j-1]=vis[j-1][i]=1;
			j=i+3;
			if(j>N) j-=N;
			_P("%d %d\n",i+1,j);
			vis[i][j-1]=vis[j-1][i]=1;
		}
		while(P--) {
			FOR(i,N) FOR(j,N) if(vis[i][j]==0 && i!=j) {
				vis[i][j]=vis[j][i]=1;
				_P("%d %d\n",i+1,j+1);
				goto out;
			}
			out:
			;
		}
	}

	_P("\n");
}

まとめ

いまいち何をしたかったのかわからない問題。

広告を非表示にする