気付いてしまえばあとは楽。
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; } }
まとめ
最初いろいろ乱択とか考えたけど、終わってみればシンプルな解法だった。