AtCoder Beginner Contest 364 復習

作成日時:2024/07/28

program

AtCoder

C++

ホームへ戻る

https://atcoder.jp/contests/abc364

ABC364に参加しました。

A-Glutton Takahashi

問題要約

甘い料理と塩辛い料理が出てくるが、甘い料理を2つ連続で食べるとその後の料理が食べられない。

全ての料理を食べることができるか答える。

注意：最後の2つが甘い料理でも全て食べたことにはなる。

▼

入力形式

$N\\ S_1\\ S_2\\ \vdots\\ S_N$

解答要約

素直に甘い料理が連続している回数を数える

▼

コード

language: c++

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;

int main(){
    //N:料理の数
    ll N;
    cin >> N;

    //count:連続でsweetが出た回数
    ll count = 0;
    for(ll i=0;i<N;i++){
        if(count >= 2){
            //前回までで、連続で甘い料理を食べた回数が2回以上の場合、今回の料理を食べられない
            cout << "No" << endl;
            return 0;
        }
        //s:今回の料理の味
        string s;
        cin >> s;
        if(s == "sweet"){
            //甘い料理の場合、countをインクリメント
            count++;
        }else{
            count = 0;
        }
    }
    //全ての料理を食べ終わった場合、Yes
    cout << "Yes" << endl;
    return 0;
}

B- Grid Walk

問題要約

空きマスと壁がある迷路がある

スタート位置の座標とそこからの移動指示(上下左右)が与えられる。

指示に従って移動(移動できない場合は留まる)した場合、最終的にどの位置にいるか出力

▼

入力形式

$H\quad W\\ S_i\quad S_j\\ C_{1,1}C_{1,2}...C_{1,W}\\ C_{2,1}C_{2,2}...C_{2,W}\\ \vdots\\ C_{H,1}C_{H,2}...C_{H,W}\\ X$

解答要約

素直に指示に従い、順にマスを移動する

▼

コード

language: c++

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;

int main(){
    //H:高さ、W:幅
    ll H,W;
    cin >> H >> W;

    //(Si,Sj):現在地
    //Si:上からi番目,Sj:左からj番目
    ll Si,Sj;
    cin >> Si >> Sj;
    //0-indexedに変換
    Si--; Sj--;

    //S:迷路
    vector<string> S(H);
    for(ll i=0;i<H;i++){
        cin >> S[i];
    }

    //X:移動する方向の指示
    string X;
    cin >> X;
    for(char now: X){
        //now:今の指示
        switch(now){
            case 'L':
                //左に移動できる場合、左に移動
                if(Sj > 0 && S[Si][Sj-1] != '#'){
                    Sj--;
                }
                break;
            case 'R':
                //右に移動できる場合、右に移動
                if(Sj < W-1 && S[Si][Sj+1] != '#'){
                    Sj++;
                }
                break;
            case 'U':
                //上に移動できる場合、上に移動
                if(Si > 0 && S[Si-1][Sj] != '#'){
                    Si--;
                }
                break;  
            case 'D':
                //下に移動できる場合、下に移動
                if(Si < H-1 && S[Si+1][Sj] != '#'){
                    Si++;
                }
                break;
        }
    }

    //1-indexedに変換して移動後の位置を出力
    cout << Si+1 << " " << Sj+1 << endl;
}

C-Minimum Glutton

問題要約

$N個$ の料理と、その $甘さA_i$ 、 $しょっぱさB_i$ が与えられる

食べれる限界値は $甘さがX$ 、 $しょっぱさがY$ 。これを超えると次の料理は食べれない

食べる料理数の最小値

▼

入力形式

$N\quad X\quad Y\\ A_1\quad A_2\quad ...\quad A_N\\ B_1\quad B_2\quad ...\quad B_N$

解答要約

最小値を求めれば良いから、甘いものかしょっぱいもののどちらかを集中的に食べれば良い

甘いものを食べるなら甘い順に、しょっぱいものを食べるならしょっぱい順に食べれば早く限界が来る

▼

コード

language: c++

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;

int main(){
    //N:料理の数、X:甘さの上限、Y:しょっぱさの上限
    ll N,X,Y;
    cin >> N >> X >> Y;

    //N個の料理の　A:甘さ、B:しょっぱさ
    vector<ll> A(N),B(N);
    for(ll i=0;i<N;i++){
        cin >> A[i];
    }
    for(ll i=0;i<N;i++){
        cin >> B[i];
    }

    //甘さの降順、しょっぱさの降順にソート
    sort(A.rbegin(),A.rend());
    sort(B.rbegin(),B.rend());

    //sumA:甘さの合計、sumB:しょっぱさの合計
    ll sumA=0,sumB=0;
    for(ll i=0;i<N;i++){
        //甘い順、しょっぱい順にそれぞれ料理を食べた場合をシミュレートし、どちらかの限界(X,Y)を超えた時、食べた料理の数を出力
        sumA += A[i];
        sumB += B[i];
        if(sumA > X || sumB > Y){
            cout << i+1 << endl;
            return 0;
        }
    }
    //限界を超えなかった場合、全ての料理を食べたことになる
    cout << N << endl;
}

D-K-thNearest

問題要約

数直線上に複数の点( $a_1,a_2,...,a_N$ )がある

クエリ： $点b_i$ から $k_i番目$ に近い点との距離を出力

注意：点( $a_1,a_2,...,a_N$ )には同じ位置の点もある

▼

入力形式

$N\quad Q\\ a_1\quad a_2\quad ...\quad a_N\\ b_1\quad k_1\\ b_2\quad k_2\\ \vdots\\ b_Q\quad k_Q$

解答要約

点( $a_1,a_2,...,a_N$ )をソートする

各クエリに対し、 $点b_i$ と最も近い $点a_j$ を2分探索で見つける

$点b_i$ と距離が $1〜k_i番目$ に近い点の候補は $a_{j-k_i+1}〜a_{j+k_i-1}$ のうちの連続する $長さk_i$ の部分列になる

▼

コード

language: c++

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;

int main(){
    //N:点A[i]の数
    //Q:クエリの数
    ll N,Q;
    cin >> N >> Q;

    //A:点A[i]の座標の配列
    vector<ll> A(N);
    for(ll i=0;i<N;i++){
        cin >> A[i];
    }
    //Aを昇順にソート
    sort(A.begin(),A.end());

    for(ll i=0;i<Q;i++){
        //各クエリを処理する

        //b:点bの座標
        //k:bからk番目に近い点A[i]を考える
        ll b,k;
        cin >> b >> k;

        //2分探索でb以下でindexが最大のA[i]を求める
        //A[l] <= b < A[l+1]となるlを求める
        ll l=-1,r=N,mid=(l+r)/2;
        while(l+1 < r){
            mid = (l+r)/2;
            if(A[mid] <= b){
                l = mid;
            }else{
                r = mid;
            }
        }
        if(l+1<N && abs(b-A[l]) > abs(A[l+1]-b)){
            //A[l] <= b < A[l+1]であるため、A[l]とA[l+1]のうちbに近い方を選ぶ
            l = l+1;
        }

        ll d1=1e9,d2=1e9;
        for(ll j=max(0LL,l-k+1);j<l+k;j++){
            //A[l]を含む連続したk個の点A[i]を考える

            //A[L]からA[R]について考える
            ll L,R;
            L = j;
            R = L+k-1;
            if(R >= N){
                break;
            }

            //A[L]からA[R]のうちbから最も遠い点とbの距離を求める
            d2 = max(abs(A[L]-b),abs(A[R]-b));
            if(d2 <= d1){
                d1 = d2;
            }else{
                //d2が更新されなかった時、A[L]からA[R]がbから近い順にk個集めた点の集合となる
                break;
            }
        }
        cout << d1 << endl;
    }
}

E-Maximum Glutton

問題要約

$N個$ の料理がある

$料理i$ の甘さは $A_i$ 、しょっぱさは $B_i$

食べた料理の甘さの合計が $X$ を超えるか、しょっぱさの合計が $Y$ を超えるとそれ以上の料理を食べられない

食べられる料理の数の最大値を答える

▼

入力形式

$N\quad X\quad Y\\ A_1\quad B_1\\ A_2\quad B_2\\ \vdots\\ A_N\quad B_N$

解答要約

DP(動的計画法)で解く

公式解説そのまま

▼

コード

language: c++

#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long ll;

int main(){
    //N:料理の数、X:甘さの上限、Y:しょっぱさの上限
    ll N,X,Y;
    cin >> N >> X >> Y;

    //N個の料理の　A:甘さ、B:しょっぱさ
    vector<ll> A(N),B(N);
    for(ll i=0;i<N;i++){
        cin >> A[i] >> B[i];
    }

    //dp[i][j][k]：i番目(0-indexed)までの料理のうちj個を選んで、甘さがkであるもののうち最小のしょっぱさ
    vector<vector<vector<ll>>> dp(N+1,vector<vector<ll>>(N+1,vector<ll>(X+1,1e9)));
    dp[0][0][0] = 0;
    for(ll i=0;i<N;i++){
        for(ll j=0;j<=i;j++){
            for(ll k=0;k<=X;k++){
                dp[i+1][j][k] = min(dp[i+1][j][k],dp[i][j][k]);
                if(k+A[i] <= X){
                    dp[i+1][j+1][k+A[i]] = min(dp[i+1][j+1][k+A[i]],dp[i][j][k]+B[i]);
                }
            }
        }
    }

    for(ll i=N;i>=0;i--){
        for(ll j=0;j<=X;j++){
            if(dp[N][i][j] <= Y){
                cout << min(i+1,N) << endl;
                return 0;
            }
        }
    }
}

🙇

今週はここまで

F-Range Connect MST

G-Last Major City

一番上へ