kmjp's blog

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

yukicoder : No.1831 Parasol

気付いてしまえばあとは楽。
https://yukicoder.me/problems/no/1831

問題

正整数Nが与えられる。
i=1~(2N-1)に対し、iがi個ずつある整数のmultisetがある。
ここから、数値を抜き出し、以下のsetをできるだけ多く作りたい。

  • 各setはN要素で、その値はいずれも異なる
  • まったく同じsetは高々2個しかない

最大何個のsetを構築できるか。

解法

multisetに整数は全部はN(2N-1)個あるが、これらを全部使いN要素のsetを(2N-1)個作ることができる。
iと(2N-1-i)を組み合わせ、それらがN個の行列に分かれるようにしよう。
その際iの偶奇により、i個が先頭i個のsetに入るか、後半i個のsetに入れるか互い違いに詰め込んでいく。
イメージとしてはN=4の時こんな感じ。こうすると、同じsetは高々2個しか登場しない。

1537
6537
6537
6547
6547
6247
6247
int N,M;

vector<int> V[600];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	M=2*N-1;
	int cur=0;
	for(i=1;i<=N-1;i++) {
		FOR(x,i) {
			if(i%2) V[x].push_back(i);
			else V[M-1-x].push_back(i);
		}
	}
	for(i=N;i<=2*N-2;i++) {
		FOR(x,i) {
			if(i%2) V[x].push_back(i);
			else V[M-1-x].push_back(i);
		}
	}
	FOR(i,M) V[i].push_back(M);
	
	cout<<M<<endl;
	FOR(i,M) {
		FORR(s,V[i]) cout<<s<<" ";
		cout<<endl;
	}
	
}

まとめ

最初いろいろ乱択とか考えたけど、終わってみればシンプルな解法だった。