Codeforces Round #714 (Div. 2) A, B

A. Array and Peaks

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n, k;
        cin >> n >> k;
        int c = ceil((n-2)*1.0/2);
        if(k > c){
            cout << -1 << "\n";
            continue;
        }
        int rn = n-k;
        int i;
        int v;
        vector<int> ans(n, 0);
        i = 1;
        v = n;
        while(k--){
            ans[i] = v;
            v--;
            i += 2;
        }
        i = -1;
        v = 1;
        while(rn){
            i++;
            if(ans[i]) continue;
            ans[i] = v;
            v++;
            rn--;
        }
        for(int x : ans) cout << x << " ";
        cout << "\n";
    }
    return 0;
}

1 부터 n-1 번째 자리 중에 ai-1 < ai 와 ai > ai+1 조건을 만족하는 수 c 는 최대 ⌈(n-2)/2⌉ 개 존재한다. k 값이 c 보다 작거나 같은 경우에만 1 부터 n-1 번째 자리에 제일 큰 수부터 한 칸씩 띄워가며 k 개를 놓고 빈칸을 나머지 수 들로 채워주면 된다.

B. AND Sequences

C++

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(0), cin.tie(0)
#define all(c) c.begin(), c.end()
#define INF 1e9
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

ll mod = 1e9+7;

ll fact(ll n, ll r){
    if(n == 0) return 1;
    ll ret = n;
    for(int i = 1; i < r; i++){
        ret *= n-i;
        ret %= mod;
    }
    return ret;
}

int main(){
    fastio;
    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        vector<int> a(n);
        int m = INF;
        for(int i = 0; i < n; i++){
            cin >> a[i];
            m = min(m, a[i]);
        }
        int c = count(all(a), m);
        bool valid = false;
        for(int i = 0; i < n; i++){
            if((a[i]&m) != m) valid = true;
        }
        if(valid){
            cout << 0 << "\n";
            continue;
        }
        ll ans;
        ll o = fact(c, 2);
        ll i = fact(n-2, n-2);
        ans = o*i;
        ans %= mod;
        cout << ans << "\n";
    }
    return 0;
}

제일 작은 값이 좌우에 올 때 good 이 된다는 조건을 찾았다. 단 제일 작은 값과 나머지 모든 값을 AND 연산한 결과가 모두 제일 작은 값이 되어야만 good 이 될 수 있다. 제일 작은 값의 개수를 c 라고 하면 양 끝에 배치하는 경우의 수는 _cP₂, 양 끝을 제외한 수들을 배치하는 경우는 (n-2)! 으로 두개의 곱이 정답이다.

후기

적게 틀리고 조금 더 빨리 b 번을 풀었으면 그린을 찍을 수 있었을텐데 아쉽다.