競プロやります。

競プロを頑張るブログです。

AtCoder Beginner Contest 115

C - Christmas Eve

https://atcoder.jp/contests/abc115/tasks/abc115_c

方針

まず  \{h_n\} をソートし、  \{h_n^{\prime}\} とします。 \{h_n^{\prime}\} の隣り合った  K 個が選び方の候補となります。あとは各候補の  h_{max} - h_{min} を求め、その中の最小値を出力すればよいです。なお  h_i^{\prime} から始めて  h_i^{\prime}, h_{i+1}^{\prime}, \dots, h_{i+K-1}^{\prime} と選ぶとき、 h_{max} = h_{i+K-1}^{\prime}, h_{min}^{\prime} = h_i となります。

ソースコード

#include <bits/stdc++.h>
using namespace std;

int main(){
    int N, K;  cin >> N >> K;
    vector<int> h(N);
    for(int i=0; i<N; i++) cin >> h[i];

    sort(h.begin(), h.end());
    int ans = h[N-1];
    for(int i=0; i<N-K+1; i++){
        int dh = h[i+K-1] - h[i];
        if(dh < ans) ans = dh;
    }

    cout << ans << endl;
}

D - Christmas

https://atcoder.jp/contests/abc115/tasks/abc115_d

方針

 L_N の長さを  l_N L_Nが含む  P の数を  p_N とします。このとき L_Nの漸化式から、 l_N p_Nの漸化式が次のようになることが分かります:
   \begin{align}
l_N &= 2l_{N-1} + 3&(l_0 = 1) \\
p_N &= 2p_{N-1} + 1&(p_0 = 0)
\end{align}

続いて求める値を  f(N, X)とします。すると  L_N の漸化式から今度は次が成り立つことが分かるので、再帰的に計算していけば  f(N,X) を求められます。
   f(N, X) = \begin{cases}
                                   1 & (N=0) \\
                                   0 & (N \geq 1 \text{かつ} X = 1)  \\
                                   f(N-1, X-1) & ( 1 < X \leq l_{N-1} + 1) \\
                                   p_{N-1} + 1 & (X = l_{N-1} + 2) \\
                                   p_{N-1} + f(N-1, X- l_{N-1} - 2) & (l_{N-1} + 2 < X)
\end{cases}

以下、 f(N,X) の漸化式を順に見て行きます:

  •  X=1
    • 左端が  P なのは L_0のみで、他は必ず左端に  B が来ます。
  •  1 < X \leq l_{N-1} + 1
    •  BL_{N-1} の左から X 文字に含まれる  P の数は、 L_{N-1} の左から X-1に含まれる Pの数に等しくなります。
  •  X = l_{N-1} + 2
    • ちょうど BL_{N-1}P に含まれる  P の数なので、 L_{N-1} に含まれる数  p_{N-1} と右端の分1を足した、 p_{N-1} + 1 になります。
  •  l_{N-1} + 2 < X
    • まず BL_{N-1}P p_{N-1} + 1 個の  P が含まれます。残り  L_{N-1}B の左から  X - (l_{N-1} - 2) 個に含まれる  P の数は、 f(N-1, X-(l_{N-1} + 2)) です。

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
vector<ll> l, p;

ll f(int N, ll X){
    ll ret = 0;
    if(N == 0) ret = 1;
    else if(X == 1) ret = 0;
    else if(1 < X && X <= l[N-1] + 1){
        ret = f(N-1,X-1);
    }else if(X == l[N-1] + 2){
        ret = p[N-1] + 1;
    }else if(l[N-1] + 2 < X){
        ret = p[N-1] + 1 + f(N-1, X-l[N-1]-2);
    }
    return ret;
}

int main(){
    int N;  ll X;
    cin >> N >> X;

    l = vector<ll>(N+1, 0);
    p = vector<ll>(N+1, 0);
    l[0] = 1;  p[0] = 1;
    for(int i=0; i<N; i++){
        l[i+1] = 2*l[i] + 3;
        p[i+1] = 2*p[i] + 1;
    }
    cout << f(N, X) << endl;
}

メモ

  •  f(N,X)の漸化式の最後の場合分けを  l_{N-1} + 2 < X \leq 2l_{N-1} + 3 = l_N とするとWAになります(なりました)。これは再帰的に計算する中で X > l_N となることがあるからです。具体的には  f(N, X = l_N) のとき、一番最後の場合分けに分岐して  f(N-1, X-l_{N-1} - 2) = f(N-1, l_{N-1} + 1) が呼び出されます。例えば  f(N=2, X=13) の場合、 f(N-1, X- l_{N-1} - 2) = f(N=1, X=6) が呼び出され、 X = 6  > l_1 = 5 です。