アルゴ式（beta版）の「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リストからの出典です。
algo-method.com
アルゴ式とは...
>・プログラミングや情報科学をコツコツ学べる「教科書」
>・学んだ内容をゲーム感覚で大量に実践できる「練習問題」
>の２つで構成される、Web上で完結した学習コンテンツです。
C++による「さまざまなデータ構造 (#毎日アルゴ式)」4章:連結リスト
僕が作成、提出したコードは、以下のとおりです。
Q1. 連結リスト
/* 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)
/* 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. キュー
/* 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. デック
/* 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. ブロックつなぎ
/* 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)
/* 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. マラソン
/* 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. マス目からの脱出ゲーム
/* 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
