結果

問題 No.3030 Kruskal-Katona
コンテスト
ユーザー TKTYI
提出日時 2025-02-21 21:41:43
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 31 ms / 2,000 ms
コード長 915 bytes
コンパイル時間 3,581 ms
コンパイル使用メモリ 282,096 KB
実行使用メモリ 35,072 KB
最終ジャッジ日時 2025-02-21 21:41:53
合計ジャッジ時間 5,455 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> pii;
int main(){
	cin.tie(0)->sync_with_stdio(0);
	cin.exceptions(cin.failbit);
	ll N,i;cin>>N>>i;
	if(i==1){cout<<N<<endl;return 0;}
	if(i==2){
		ll m=2;
		while((m+1)*m/2<=N)m++;
		if(N!=m*(m-1)/2)cout<<m<<" "<<N-(m-1)*m/2<<endl;
		else cout<<m<<endl;
		return 0;
	}
	vector<vector<ll>>binom(2010,vector<ll>(2010));
	binom[0][0]=1;
	rep(i,0,2009)rep(j,0,i+1){
		binom[i+1][j]+=binom[i][j];
		binom[i+1][j+1]+=binom[i][j];
		binom[i+1][j]=min(N+100,binom[i+1][j]);
		binom[i+1][j+1]=min(N+100,binom[i+1][j+1]);
	}
	vector<int>ans;
	while(N){
		int m=i;
		while(binom[m][i]<=N)m++;
		m--;
		ans.emplace_back(m);
		N-=binom[m][i];
		i--;
	}
	rep(i,0,sz(ans))cout<<ans[i]<<(i==sz(ans)-1?"\n":" ");
}
0