Tenka1 Programmer Contest 2018 D Crossing

beta.atcoder.jp

ゆるキャン△　１巻 (まんがタイムKRコミックス)

解法

下の図のように構成すればよい。
ただし N = k(k-1)/2となるようなkが存在しない場合にはNoを返す

コード

bool check[500][100005];
 
int main(){
    int N; cin >> N;
    int k;
    for(int i=1;i<=N+10;i++){
        int t = i * (i-1) / 2;
        if(t > N){
            cout << "No" << endl;
            return 0;
        }
        if(t == N){
            k = i;
            break;
        }
    }
 
    int s = 0;
    for(int i=0;i<k;i++){
        const int len = k-1-i;
        for(int j=s;j<s+len;j++){
            //cout << i << " " << j << endl;
            check[i][j] = true;
        }
 
        for(int j=0;j<len;j++){
            check[i+1+j][s+j] = true;
        }
        s = s + len;
    }
    cout << "Yes" << endl;
    cout << k << endl;
    for(int i=0;i<k;i++){
        int cnt = 0;
        for(int j=0;j<N;j++) if(check[i][j]) cnt++;
        cout << cnt;
        for(int j=0;j<N;j++){
            if(check[i][j]) cout << " " << j+1;
        }
        cout << endl;
    }
}