寝癖頭の解法

小学生の目線から、勉強中の覚え書きを投稿、更新していきます。

アルゴ式(beta版): C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト

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

C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト

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

Q1. 連結リスト

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q1. 連結リスト
https://algo-method.com/tasks/844
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* next;
    string str;
    Node(const string& str=""):next(NULL),str(str){}
};
Node* nil;
void init(void){
    nil=new Node();
    nil->next=nil;
}
void insert(Node* v){
    v->next=nil->next;
    nil->next=v;
}
int main(void){
    init();
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            string s;
            cin>>s;
            Node* v=new Node(s);
            insert(v);
        }else{
            ll k;
            cin>>k;
            Node* v=nil;
            for(ll j=0;j<k;j++){
                v=v->next;
                if(v==nil){
                    break;
                }
                cout<<v->str<<" ";
            }
            cout<<endl;
        }
    }
    return 0;
}
Q2. スタック (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q2. スタック (2)
https://algo-method.com/tasks/845
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* next;
    string str;
    Node(const string& str=""):next(NULL),str(str){}
};
Node* nil;
void init(void){
    nil=new Node();
    nil->next=nil;
}
void insert(Node* v){
    v->next=nil->next;
    nil->next=v;
}
string erase(void){
    Node* front=nil->next;
    if(front==nil){
        return "Error";
    }else{
        string ret=front->str;
        nil->next=front->next;
        delete front;
        return ret;
    }
}
int main(void){
    init();
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            string s;
            cin>>s;
            Node* v=new Node(s);
            insert(v);
        }else{
            cout<<erase()<<endl;
        }
    }
    return 0;
}
Q3. キュー

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q3. キュー
https://algo-method.com/tasks/846
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* next;
    Node* prev;
    string str;
    Node(const string& str=""):next(NULL),str(str){}
};
Node* nil;
void init(void){
    nil=new Node();
    nil->next=nil;
    nil->prev=nil;
}
void PushHead(Node* v){
    v->next=nil->next;
    v->prev=nil;
    nil->next=v;
    (v->next)->prev=v;
}
string PopTail(void){
    Node* tail=nil->prev;
    if(tail==nil){
        return "Error";
    }else{
        string ret=tail->str;
        nil->prev=tail->prev;
        (nil->prev)->next=nil;
        delete tail;
        return ret;
    }
}
int main(void){
    init();
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            string s;
            cin>>s;
            Node* v=new Node(s);
            PushHead(v);
        }else{
            cout<<PopTail()<<endl;
        }
    }
    return 0;
}
Q4. デック

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q4. デック
https://algo-method.com/tasks/847
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
struct Node{
    Node* next;
    Node* prev;
    string str;
    Node(const string& str=""):next(NULL),str(str){}
};
Node* nil;
void init(void){
    nil=new Node();
    nil->next=nil;
    nil->prev=nil;
}
void PushHead(Node* v){
    v->next=nil->next;
    v->prev=nil;
    nil->next=v;
    (v->next)->prev=v;
}
void PushTail(Node* v){
    v->next=nil;
    v->prev=nil->prev;
    nil->prev=v;
    (v->prev)->next=v;
}
string PopHead(void){
    Node* head=nil->next;
    if(head==nil){
        return "Error";
    }else{
        string ret=head->str;
        nil->next=head->next;
        (nil->next)->prev=nil;
        delete head;
        return ret;
    }
}
string PopTail(void){
    Node* tail=nil->prev;
    if(tail==nil){
        return "Error";
    }else{
        string ret=tail->str;
        nil->prev=tail->prev;
        (nil->prev)->next=nil;
        delete tail;
        return ret;
    }
}
int main(void){
    init();
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            string s;
            cin>>s;
            Node* v=new Node(s);
            PushHead(v);
        }else if(num==1){
            string s;
            cin>>s;
            Node* v=new Node(s);
            PushTail(v);
        }else if(num==2){
            cout<<PopHead()<<endl;
        }else{
            cout<<PopTail()<<endl;
        }
    }
    return 0;
}
Q5. ブロックつなぎ

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q5. ブロックつなぎ
https://algo-method.com/tasks/848
提出コードの解答例
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> next(N,-1),back(N,-1);
    for(ll i=0;i<Q;i++){
        ll num;
        cin>>num;
        if(num==0){
            ll p,q;
            cin>>p>>q;
            if(next[p]==-1 && back[q]==-1){
                cout<<"Yes"<<endl;
                next[p]=q;
                back[q]=p;
            }else{
                cout<<"Error"<<endl;
            }
        }else{
            ll r;
            cin>>r;
            if(next[r]!=-1){
                back[next[r]]=back[r];
            }
            if(back[r]!=-1){
                next[back[r]]=next[r];
            }
            next[r]=back[r]=-1;
        }
    }
    return 0;
}
Q6. ままこだて (2)

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q6. ままこだて (2)
https://algo-method.com/tasks/850
提出コードの解答例
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> next(n+1,0),prev(n+1,0);
    for(ll i=1;i<=n;i++){
        next[i]=i+1;
        if(i==n){
            next[i]=1;
        }
        prev[i]=i-1;
        if(i==1){
            prev[i]=n;
        }
    }
    ll out=1;
    for(ll i=0;i<n-1;i++){
        prev[next[out]]=prev[out];
        next[prev[out]]=next[out];
        out=next[next[out]];
    }
    cout<<out<<endl;
    return 0;
}
Q7. マラソン

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q7. マラソン
https://algo-method.com/tasks/849
提出コードの解答例
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];
    }
    vector<ll> next(n,-1),back(n,-1);
    for(ll i=0;i<n;i++){
        if(i!=0){
            next[a[i]]=a[i-1];
        }
        if(i!=n-1){
            back[a[i]]=a[i+1];
        }
    }
    ll q;
    cin>>q;
    for(ll i=0;i<q;i++){
        ll num;
        cin>>num;
        if(num==0){
            ll v;
            cin>>v;
            if(next[v]==-1){
                cout<<"Error"<<endl;
            }else{
                ll numb=next[v];
                cout<<numb<<endl;
                if(next[numb]!=-1){
                    back[next[numb]]=v;
                }
                if(back[v]!=-1){
                    next[back[v]]=numb;
                }
                next[v]=next[numb];
                back[numb]=back[v];
                back[v]=numb;
                next[numb]=v;
            }
        }else{
            ll v;
            cin>>v;
            if(next[v]!=-1){
                back[next[v]]=back[v];
            }
            if(back[v]!=-1){
                next[back[v]]=next[v];
            }
            next[v]=back[v]=-1;
        }
    }
    return 0;
}
Q8. マス目からの脱出ゲーム

algo-method.com

/*
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
Q8. マス目からの脱出ゲーム
https://algo-method.com/tasks/851
提出コードの解答例
https://neguse-atama.hatenablog.com
*/
#include<bits/stdc++.h>
using namespace std;
using ll=long long;
int main(void){
    ll n,k;
    string s;
    cin>>n>>k>>s;
    vector<ll> right(n,-1),left(n,-1);
    for(ll i=0;i<n;i++){
        if(i!=0){
            left[i]=i-1;
        }
        if(i!=n-1){
            right[i]=i+1;
        }
    }
    ll direct=1,i=k,ans=0;
    while(1){
        right[left[i]]=right[i];
        left[right[i]]=left[i];
        if(s[i]=='>'){
            direct=1;
        }
        if(s[i]=='<'){
            direct=-1;
        }
        ll num;
        if(direct==1){
            num=right[i];
        }else if(direct==-1){
            num=left[i];
        }
        ans+=abs(i-num);
        i=num;
        if(i==0 || i==n-1){
            break;
        }
    }
    cout<<ans<<endl;
    return 0;
}

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