AtCoder Beginner Contest 115
C - Christmas Eve
https://atcoder.jp/contests/abc115/tasks/abc115_c
方針
まず をソートし、 とします。 の隣り合った 個が選び方の候補となります。あとは各候補の を求め、その中の最小値を出力すればよいです。なお から始めて と選ぶとき、 となります。
ソースコード
#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
方針
の長さを 、が含む の数を とします。このときの漸化式から、との漸化式が次のようになることが分かります:
続いて求める値を とします。すると の漸化式から今度は次が成り立つことが分かるので、再帰的に計算していけば を求められます。
以下、 の漸化式を順に見て行きます:
-
- 左端が なのはのみで、他は必ず左端に が来ます。
-
- の左から 文字に含まれる の数は、 の左からに含まれるの数に等しくなります。
-
- ちょうど に含まれる の数なので、 に含まれる数 と右端の分1を足した、 になります。
-
- まず で 個の が含まれます。残り の左から 個に含まれる の数は、 です。
ソースコード
#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; }
メモ
- の漸化式の最後の場合分けを とするとWAになります(なりました)。これは再帰的に計算する中で となることがあるからです。具体的には のとき、一番最後の場合分けに分岐して が呼び出されます。例えば の場合、 が呼び出され、 です。