Codeforces Round #633 (Div. 2) - 接着剤の精進日記

A. Filling Diamonds

問題文

正の整数nが与えられる
図の左側の図形を移動、回転させて右側の図に敷き詰めることを考える
この時、その敷き詰め方の個数を数えよ

解法

難しくないですか・・・？
実は、どこかを縦に置くと残りは一意に定まる
そのため、縦に置く場合の数はn通りあるのでnを出力する
提出コード

void solve(){
    int n;
    cin >> n;
    cout << n << endl;
}

B. Sorted Adjacent Differences

問題文

n個の要素からなる数列aが与えられる
$|a_1 - a_2| \leq |a_2 - a_3| \leq ... \leq |a_{n-1} - a_n|$ を満たすように数列を並べかえたものを出力せよ
これを満たす数列の並べ方は必ず存在する

解法

数列をソートし、左端と右端を交互に取っていけば必ず達成できる
何故か実装バグらせてしまったのでdequeを使いました…
端から取っていくと単調減少になっているのでreverseして出力する

提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());
    deque<int> dq;
    REP(i,n) dq.push_back(a[i]);
    int parity = 0;
    vector<int> ans;
    while(!dq.empty()){
        if(parity & 1){
            ans.push_back(dq.back());
            dq.pop_back();
        }
        else{
            ans.push_back(dq.front());
            dq.pop_front();
        }
        parity = 1 - parity;
    }
    reverse(ans.begin(), ans.end());
    REP(i,n) cout << ans[i] << " ";
    cout << endl;
}

C. Powered Addition

問題文

長さnの数列aが与えられる
x秒目に次の操作を行える
1. 任意のインデックス $i_1, i_2, ... , i_k$ を選びそれぞれの要素を $a_{i_j} = a_{i_j} + 2^{x-1}$ に更新する
ただし、インデックスを一つも選ばなくても良い
このような操作を行った時、数列aが広義単調増加列にするための最小の秒数を答えよ

解法

こどふぉによくあるやつ
前から貪欲に変更していけばいい
今見ている要素に加算する必要がある場合を考える
一つ前の要素の差を2進数で考えるとその表し方は一意になる
そのため、一つ前の要素と同じにするのが最適となる
そのような最小の秒数は差の2進数の先頭bitを見ればいいので数列全体でのこのmaxが答え
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> a(n);
    REP(i,n) cin >> a[i];
    
    int ma = 0;
    for(int i=1;i<n;i++){
        if(a[i-1] <= a[i]) continue;
        ll sa = a[i-1] - a[i];
        for(int i=40;i>=0;i--){
            if(sa >> i & 1){
                chmax(ma, i + 1);
                break;
            }
        }
        a[i] = a[i-1];
    }
    cout << ma << endl;
}