AtCoder Beginner Contest 364

A - Glutton Takahashi

O(N)
シミュレートしましょう。
"sweet"が２回連続で続いた時に、料理を食べ終わっていないなら"No"になります。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

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

    int cnt = 0;
    for(int i=1; i<=N; i++){
        string s;
        cin >> s;

        if(s == "sweet"){
            cnt++;
        }else{
            cnt = 0;
        }

        if(cnt >= 2){
            if(i==N) cout << "Yes" << endl;
            else cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl; 

    return 0;
} 

このコードは綺麗でないですね。
A問題を綺麗に解くのに技術、知識が必要でセンスが出ます。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N;
    cin >> N;
    vector<string> S(N);
    rep(i, N) cin >> S[i];
 
    for(int i=0; i<N-2; i++){
        if(S[i] == "sweet" && S[i+1] == "sweet"){
            cout << "No" << endl;
            return 0;
        }
    }
    cout << "Yes" << endl; 

    return 0;
} 

このコードのが良いです。

B - Grid Walk

O(N)
シミュレートしましょう。
スタート地点からXの文字列に従って移動させます。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }



int main() {
    int H, W, si, sj;
    cin >> H >> W;
    cin >> si >> sj;

    si--;
    sj--;

    vector<string> HW(H);
    for(int i=0; i<H; i++){
        cin >> HW[i];
    }
    string X;
    cin >> X;
    for(int i=0; i<X.size(); i++){
        int ni = si;
        int nj = sj;
        if(X[i] == 'L') nj--;
        if(X[i] == 'R') nj++;
        if(X[i] == 'U') ni--;
        if(X[i] == 'D') ni++;

        if(0 <= nj && nj < W && 0 <= ni && ni < H && HW[ni][nj] == '.'){
            si = ni;
            sj = nj;
        }
    }
    cout << si+1 << ' ' << sj+1 << endl;

    return 0;
} 

C - Minimum Glutton

O(N)
最適解を繰り返し行う問題です。
A、Bを降順に並び替えます。
AとBをそれぞれ大きい値から加算していき、XとYの値を超えたインデックスを探索します。
探索した２つインデックスを比較して、小さい値が答えになります。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    vector<ll> A(N), B(N);
    rep(i, N) cin >> A[i];
    rep(i, N) cin >> B[i];

    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
    reverse(A.begin(), A.end());
    reverse(B.begin(), B.end());

    ll ASum = 0, BSum = 0;
    rep(i, N){
        ASum += A[i];
        BSum += B[i];

        if(ASum > X || BSum > Y){
            cout << i + 1 << endl;
            return 0;
        }
    }
    cout << N << endl;

    return 0;
} 

D - K-th Nearest

O(QlogNlogNlogN)
二分探索への理解が深くないと解けない問題です。
復習していて良問だと感じました。

数直線上にa_iの点があります。
b_iの点から距離がk_i番目の距離を求めよ。

i	0	1	2	3
a	-3	-1	5	6

b_i = -2
k_i = 3
の時、３番目に近い点はA_2になります。
距離は7です。

この問題は、この距離7を求めたいです。
距離7を変数Xとして扱うと二分探索で求めることができそうです。

left = b_i - X
right = b_i + X + 1

leftの距離以上になる最初の点A_iを求めます。
rightの距離以上になる最初の点A_iを求めます。
これも二分探索で求めることができそうです。
right - leftがK_i以上になる最小の距離を求めると答えになります。

right - left >= K_i

なぜK_i以上なのか。
b_iから同じ距離に２つの点があるとき、b_iからXの距離以内の点の数がK_i個以内にならない可能性があります。

C++

#include <bits/stdc++.h>
 
#define rep(i,n) for(int i=0; i<(n); ++i)
#define repx(i,x,n) for(int i=x; i<(n); ++i)
#define fixed_setprecision(n) fixed << setprecision((n))
#define execution_time(ti) printf("Execution Time: %.4lf sec\n", 1.0 * (clock() - ti) / CLOCKS_PER_SEC);
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9
 
using namespace std;
using ll = long long;
using P = pair<int,int>;
template<class T> inline bool chmax(T& a, T b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b){ if(a>b){ a=b; return 1; } return 0; }

int main() {
    int N, Q;
    cin >> N >> Q;
    vector<int> a(N);
    rep(i, N) cin >> a[i];
    sort(a.begin(), a.end());
    vector<int> b(Q), k(Q);
    rep(i, Q) cin >> b[i] >> k[i];

    rep(i, Q){
        int ng = -1;
        int ok = 2e8;
        while(abs(ok-ng)>1){
            int mid = (ok + ng) / 2;
            int l = lower_bound(a.begin(), a.end(), b[i] - mid) - a.begin();
            int r = upper_bound(a.begin(), a.end(), b[i] + mid) - a.begin();
            if(r-l >= k[i]){
                ok = mid;
            }else{
                ng = mid;
            }
        }
        cout << ok << endl;
    }

    return 0;
}