寝癖頭の解法

勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー

アルゴ式(beta版)の「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキューからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の2つで構成される、Web上で完結した学習コンテンツです。

C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー

僕が作成、提出したコードは、以下のとおりです。

Q1. 閉じた筒とボール (スタック)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q1. 閉じた筒とボール (スタック)
https://algo-method.com/tasks/886
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    /*~操作はじめ~
      A
      AB
      ABC
      AB
      ABX
      ABXY
      ABXYZ
      ABXY
    ~操作おわり~*/
    printf("A\nB\nX\nY\n");
    return 0;
}
Q2. 開いた筒とボール (キュー)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q2. 開いた筒とボール (キュー)
https://algo-method.com/tasks/885
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    /*~操作はじめ~
      A
      AB
      ABC
       BC
       BCX
       BCXY
       BCXYZ
        CXYZ
    ~操作おわり~*/
    printf("C\nX\nY\nZ\n");
    return 0;
}
Q3. キューを配列で実装

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q3. キューを配列で実装
https://algo-method.com/tasks/884
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n,q;
    cin>>n>>q;
    vector<ll> a(n,-1);
    ll head=0,tail=0;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            ll v;
            cin>>v;
            a[tail]=v;
            tail++;
            if(tail==n){
                tail=0;
            }
        }else{
            a[head]=-1;
            head++;
            if(head==n){
                head=0;
            }
        }
    }
    for(ll i=0;i<n;i++){
        cout<<a[i]<<endl;
    }
    return 0;
}
Q4. 逆ポーランド記法の計算

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q4. 逆ポーランド記法の計算
https://algo-method.com/tasks/883
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    string x;
    ll n;
    cin>>x>>n;
    vector<string> s(n);
    for(ll i=0;i<n;i++){
        cin>>s[i];
    }
    stack<ll> num;
    for(ll i=0;i<n;i++){
        string t=s[i];
        if(t=="+" || t=="-" || t=="*"){
            ll n2=num.top();
            num.pop();
            ll n1=num.top();
            num.pop();
            ll j;
            if(t=="+"){
                j=n1+n2;
            }else if(t=="-"){
                j=n1-n2;
            }else if(t=="*"){
                j=n1*n2;
            }
            num.push(j);
        }else{
            ll j=stoi(t);
            num.push(j);
        }
    }
    ll ans=num.top();
    cout<<x<<"="<<ans<<endl;
    return 0;
}
Q5. 括弧列の対応関係 (1)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q5. 括弧列の対応関係 (1)
https://algo-method.com/tasks/887
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    string s;
    cin>>n>>s;
    stack<ll> st;
    ll ans=-1;
    for(ll i=0;i<n;i++){
        if(s[i]=='('){
            st.push(i);
        }else{
            ll num=st.top();
            st.pop();
            if(num==0){
                ans=i;
            }
        }
    }
    cout<<ans<<endl;
    return 0;
}
Q6. 括弧列の対応関係 (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q6. 括弧列の対応関係 (2)
https://algo-method.com/tasks/890
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    string s;
    cin>>n>>s;
    stack<ll> st;
    vector<ll> v(n,-1);
    for(ll i=0;i<n;i++){
        if(s[i]=='('){
            st.push(i);
        }else{
            ll nu=st.top();
            st.pop();
            ll num=i;
            v[nu]=num;
            v[num]=nu;
        }
    }
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll k;
        cin>>k;
        cout<<v[k]<<endl;
    }
    return 0;
}
Q7. 括弧列の整合性判定

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q7. 括弧列の整合性判定
https://algo-method.com/tasks/888
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    string s;
    cin>>n>>s;
    stack<ll> st;
    for(ll i=0;i<n;i++){
        if(s[i]=='('){
            st.push(i);
        }else{
            if(st.size()==0){
                cout<<"No"<<endl;
                return 0;
            }
            st.pop();
        }
    }
    if(st.size()>0){
        cout<<"No"<<endl;
        return 0;
    }
    cout<<"Yes"<<endl;
    return 0;
}
Q8. スパン

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q8. スパン
https://algo-method.com/tasks/893
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n;
    cin>>n;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    stack<pair<ll,ll>> st;
    st.push(pair(0,0));
    for(ll i=1;i<n;i++){
        ll A=a[i];
        while(A<=st.top().first){
            st.pop();
        }
        ll ans=i-st.top().second;
        cout<<ans<<endl;
        st.push(pair(A,i));
    }
    return 0;
}
Q9. タスクスケジューリング (1)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q9. タスクスケジューリング (1)
https://algo-method.com/tasks/882
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll q;
    cin>>q;
    queue<string> que;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            string s;
            cin>>s;
            que.push(s);
        }else{
            cout<<que.front()<<endl;
            que.pop();
        }
    }
    return 0;
}
Q10. タスクスケジューリング (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q10. タスクスケジューリング (2)
https://algo-method.com/tasks/889
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll x,q;
    cin>>x>>q;
    queue<ll> que;
    ll sum=0;
    for(ll i=0;i<q;i++){
        ll num,t;
        cin>>num>>t;
        if(num==0){
            que.push(t+x);
        }else{
            while(que.size()>0 && que.front()<=t){
                que.pop();
                sum++;
            }
            cout<<sum<<endl;
        }
    }
    return 0;
}
Q11. シール貼り

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q11. シール貼り
https://algo-method.com/tasks/891
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n,l;
    cin>>n>>l;
    vector<ll> a(n);
    for(ll i=0;i<n;i++){
        cin>>a[i];
    }
    vector<ll> v(n,0);
    queue<ll> que;
    ll num=0;
    for(ll i=0;i<n;i++){
        v[i]=max(a[i]-num,0LL);
        que.push(v[i]);
        num+=v[i];
        if(que.size()>=l){
            num-=que.front();
            que.pop();
        }
    }
    ll ans=0;
    for(ll i=0;i<n;i++){
        ans+=v[i];
    }
    cout<<ans<<endl;
    return 0;
}
Q12. 幅優先探索

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」7章:スタックとキュー
Q12. 幅優先探索
https://algo-method.com/tasks/892
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
ll dx[4]={1,0,-1,0};
ll dy[4]={0,1,0,-1};
int main(void){
    ll h,w;
    cin>>h>>w;
    vector<string> s(h);
    for(ll i=0;i<h;i++){
        cin>>s[i];
    }
    ll sx=-1,sy=-1,gx=-1,gy=-1;
    for(ll x=0;x<h;x++){
        for(ll y=0;y<w;y++){
            if(s[x][y]=='S'){
                sx=x;
                sy=y;
            }
            if(s[x][y]=='G'){
                gx=x;
                gy=y;
            }
        }
    }
    vector<vector<ll>> vv(h,vector<ll>(w,-1));
    queue<pair<ll,ll>> que;
    vv[sx][sy]=0;
    que.push(make_pair(sx,sy));
    while(que.size()>0){
        auto [x,y]=que.front();
        que.pop();
        for(ll i=0;i<4;i++){
            ll nx=x+dx[i],ny=y+dy[i];
            if((0<=nx && nx<h) && (0<=ny && ny<w)){
                if(s[nx][ny]=='#'){
                    continue;
                }
                if(vv[nx][ny]!=-1){
                    continue;
                }
                vv[nx][ny]=vv[x][y]+1;
                que.push(make_pair(nx,ny));
            }
        }
    }
    cout<<vv[gx][gy]<<endl;
    return 0;
}

設問の出典は、情報科学をコツコツ積み立てて学習できるサービス「アルゴ式(beta版)」です。
algo-method.com