逆ポーランド方式, ラウンドロビンスケジューリング, 双方向連結リスト, Areas on the Cross-Section Diagram

ALDS1_3_A

逆ポーランド方式

計算の仕方を誤って理解してました。
配列に用意した計算式を先頭から順番にスタックに追加していきます。
演算子が出現した際、スタックから要素を２つ取り出して計算し、再度スタックに計算結果を追加します。
最後の要素は答えになります。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;

vector<string> split(string s, char c){

    vector<string> elem;
    string item;

    for(char ch: s){
        if(ch == c){
            if(!item.empty()) elem.push_back(item);
            item.clear();
        }else{
            item += ch;
        }
    }

    if(!item.empty()) elem.push_back(item);

    return elem;
}

class MyStack{
    public:
    int marray[1000]={0};
    int size=0;
    MyStack(){
    }

    int top(){
        return marray[size-1];
    }

    void pop(){
        marray[size]=0;
        size-=1;
    }

    void push(int p){
        marray[size]=p;
        size+=1;
    }
};

int main(int argc, const char * argv[]) {
    string s;
    getline(cin, s);

    vector<string> vec = split(s, ' ');

    int cnt=0;
    MyStack st;
    while(vec.size() > cnt){
        string tmp = vec[cnt];

        if(tmp=="+" || tmp=="-" || tmp=="*" || tmp=="/"){
            int a = st.top();
            st.pop();
            int b = st.top();
            st.pop();

            if(tmp == "+") st.push(b + a);
            else if(tmp == "-") st.push(b - a);
            else if(tmp == "*") st.push(b * a);
            else if(tmp == "/") st.push(b / a);
        }else{
            st.push(stoi(tmp));
        }
        cnt++;
    }

    cout << st.top() << endl;

    return 0;
}

ALDS1_3_B

ラウンドロビンスケジューリング

先頭の要素から処理を行う。
まだ処理が完了していないならキューの最後に追加を行う。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

class MyQueue{
public:
    int mhead=0;
    int mtail=0;
    int msize=0;
    pair<string, int> marray[100000];

    MyQueue(){}

    void push(pair<string, int> p){
        marray[mtail] = p;
        msize++;
        mtail++;
        if(mtail>=100000) mtail=0;
    }

    void pop(){
        msize-=1;
        mhead++;
        if(mhead>=100000) mhead=0;
    }

    int size(){
        return msize;
    }

    pair<string, int> front(){
        return marray[mhead];
    }
};

int main(int argc, const char * argv[]) {

    int n, q;
    cin >> n >> q;

    MyQueue que;
    rep(i, n){
        string name;
        int time;
        cin >> name >> time;
        que.push(pair<string, int>(name, time));
    }

    int time=0;
    while(que.size()>0){
        pair<string, int> p = que.front();
        que.pop();

        if(p.second - q > 0){
            p.second -= q;
            que.push(p);
            time+=q;
        }else{
            time+=p.second;
            cout << p.first << ' ' << time << endl;
        }
    }

    return 0;
}

ALDS1_3_C

双方向連結リスト

「Node* mdummy=NULL;」がポイントです。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

class MyList{
public:
    class Node{
    public:
        int mvalue=0;
        Node* mprev=NULL;
        Node* mnext=NULL;
        Node(){}
        Node(int x, Node* prev, Node* next){
            mvalue=x;
            mprev = prev;
            mnext = next;
        }
    };
    Node* mdummy=NULL;

    MyList(){
        mdummy = new Node();
        mdummy->mprev = mdummy;
        mdummy->mnext = mdummy;
    }
    ~MyList(){}

    void Insert(int x){
        Node* newNode = new Node(x, mdummy, mdummy->mnext);
        mdummy->mnext->mprev = newNode;
        mdummy->mnext = newNode;
    }

    void Delete(int x){
        for(Node* p = mdummy->mnext; p != mdummy; p = p->mnext){
            int xx = p->mvalue;
            if(xx==x){
                p->mprev->mnext = p->mnext;
                p->mnext->mprev = p->mprev;
                delete p;
                return;
            }
        }

    }

    void DeleteFirst(){
        Node* tmp = mdummy->mnext;
        mdummy->mnext = mdummy->mnext->mnext;
        mdummy->mnext->mprev = mdummy;
        delete tmp;
    }

    void DeleteLast(){
        Node* tmp = mdummy->mprev;
        mdummy->mprev = mdummy->mprev->mprev;
        mdummy->mprev->mnext = mdummy;
        delete tmp;
    }

    void Show(){
        for(Node* p = mdummy->mnext; p != mdummy; p = p->mnext){
            if(p->mnext == mdummy) cout << p->mvalue << endl;
            else cout << p->mvalue << " ";
        }
    }

    void Clear(){
        for(Node* p = mdummy->mnext; p != mdummy;){
            Node* pp = p;
            p = p->mnext;
            delete pp;
        }
    }
};

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;

    MyList mylist;
    pair<string,int> p;
    rep(i, n){
        cin >> p.first;

        if(p.first == "insert"){
            cin >> p.second;
            mylist.Insert(p.second);
        }
        if(p.first == "delete"){
            cin >> p.second;
            mylist.Delete(p.second);
        }
        if(p.first == "deleteFirst") mylist.DeleteFirst();
        if(p.first == "deleteLast") mylist.DeleteLast();
    }

    mylist.Show();
    return 0;
}

ALDS1_3_D

Areas on the Cross-Section Diagram

面積は横方向で計算を行う。

C++

#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>

#define rep(i,n) for(int i=0; i<(n); ++i)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    string s;
    getline(cin, s);

    stack<int> side;
    stack<pair<int,int>> area;
    rep(i, s.length()){
        if(s[i] == '\\'){
            side.push(i);
        }
        if(s[i] == '/'){
            if(side.size()==0) continue;

            int w = side.top();
            side.pop();

            if(area.size()>0 && area.top().first >= w){
                int x = 0;
                int a = 0;
                while(area.size()>0 && area.top().first >= w){
                    pair<int,int> p = area.top();
                    area.pop();
                    x = p.first;
                    a += p.second;
                }
                area.push(pair<int,int>(x, i-w + a));
            }else{
                area.push(pair<int,int>(w, i-w));
            }
        }
    }

    int ans=0;
    vector<int> vec;
    while(area.size()>0){
        pair<int,int> p = area.top();
        area.pop();
        vec.push_back(p.second);
        ans+=p.second;
    }

    cout << ans << endl;
    if(vec.size()>0) cout << vec.size() << ' ';
    else cout << vec.size() << endl;
    for(int i=(int)vec.size()-1; i>=0; i--){
        if(i==0) cout << vec[i] << endl;
        else cout << vec[i] << ' ';
    }

    return 0;
}