見出し画像
Photo by pav

#9 - 文系出身エンジニアが競プロをやる

funai(pav)

こんばんは、GW2日目です（既に3日目に突入しました）。
俺はGWに特に予定がないので（関東ITSやその他宿が取れなかった）、勉強しつつ体を休めています。

前回の投稿では初コンテストである、ABC125について書きました。

累積GCDがツイッターのトレンドになっていたのが記憶に新しいですね。


さて、今回はStackとQueueについて学習したので書いていきます。
自分でアルゴリズムを実装するつもりがつい便利なライブラリを使ってしまったりもしたのですが、読み進めて理解（本当か？）しているのでまあ良いでしょう。

ALDS1_3_A: Stack

問題文

逆ポーランド記法は、演算子をオペランドの後に記述する数式やプログラムを記述する記法です。例えば、一般的な中間記法で記述された数式 (1+2)*(5+4) は、逆ポーランド記法では 1 2 + 5 4 + * と記述されます。逆ポーランド記法では、中間記法で必要とした括弧が不要である、というメリットがあります。

逆ポーランド記法で与えられた数式の計算結果を出力してください。

数式・プログラムの記法の一つで演算子（+-*/など）を被演算子（数値）の後に書く記法のことです。

# 1 + 2の事を表現している
1 2 +

入力

１つの数式が１行に与えられます。連続するシンボル（オペランドあるいは演算子）は１つの空白で区切られて与えられます。

出力

計算結果を１行に出力してください。

制約

・2 ≤ 式に含まれるオペランドの数 ≤ 100
・1 ≤ 式に含まれる演算子の数 ≤ 99
・演算子は +、-、* のみを含み、１つのオペランドは106 以下の正の整数
・-1 × 109 ≤ 計算途中の値 ≤ 109

解答（コード）

#include <stack>
#include <string>
#include <cstdlib>
#include <cstdio>

using namespace std;

int main() {
    char s[100];
    stack<int> St;
    int l, r;
    while (scanf("%s", &s) != EOF) {
        switch (s[0]) {
            case '+':
                l = St.top();St.pop();
                r = St.top();St.pop();
                St.push(l + r);
                break;
            case '-':
                l = St.top();St.pop();
                r = St.top();St.pop();
                St.push(r - l);
                break;
            case '*':
                l = St.top();St.pop();
                r = St.top();St.pop();
                St.push(l * r);
                break;
            default:
                St.push(atoi(s));
                break;
        }
    }

    printf("%d\n", St.top());

    return 0;
}

stackライブラリを使います。
被演算子であれば、stackの中に放り込み演算子が来たら計算をして再度stackへと放り込みます。
今回の制約では + or - or * が被演算子として与えられるため、特定が容易でした。

ちょっと困ったのは、EOFの扱いです。
入出力の終わりを特定する方法がわからなかったので、一応指定の参考書の解説・解答に従う形にしましたがそもそもEOFなのか不明です。

（わかる人いたら教えてください…）
軽く調べたんですが、納得いくような答えに出会えず。


入力の終端取れてるのか確かめる術もなかったです（正確には正しく動かすのが面倒でした）。
いずれにしても無事パスしたので、次の問題へ進みます。

ALDS1_3_B: Queue

皆大好き（本当にそうか？）なQueueです。普段RedisやAWS SQSなどに触れていて馴染みが深いです。

問題文

名前 namei と必要な処理時間 timei を持つ n 個のプロセスが順番に一列に並んでいます。ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。各プロセスは最大 q ms（これをクオンタムと呼びます）だけ処理が実行されます。q ms だけ処理を行っても、まだそのプロセスが完了しなければ、そのプロセスは列の最後尾に移動し、CPU は次のプロセスに割り当てられます。

入力

入力の形式は以下の通りです。

n q
name1 time1
name2 time2
...
namen timen
最初の行に、プロセス数を表す整数 n とクオンタムを表す整数 q が１つの空白区切りで与えられます。

続く n 行で、各プロセスの情報が順番に与えられます。文字列 namei と整数 timei は１つの空白で区切られています。

出力

プロセスが完了した順に、各プロセスの名前と終了時刻を空白で区切って１行に出力してください。

制約

・1 ≤ n ≤ 100,000
・1 ≤ q ≤ 1,000
・1 ≤ timei ≤ 50,000
・1 ≤ 文字列 namei の長さ ≤ 10
・1 ≤ timei の合計 ≤ 1,000,000

解答（コード）

#include <string>
#include <queue>
#include <iostream>

using namespace std;

struct P {
    string name;
    int req;
};

int main() {
    queue<P> que;
    int n, q;
    cin >> n >> q;
    P p[n], pp;
    for (int i = 0; i < n; i++) {
        cin >> p[i].name >> p[i].req;
        que.push(p[i]);
    }

    int timer = 0;
    while (!que.empty()) {
        pp = que.front();
        if (pp.req > q) {
            pp.req -= q;
            timer += q;
            que.pop();
            que.push(pp);
        } else {
            timer += pp.req;

            cout << que.front().name << " " << timer << endl;
            que.pop();
        }
    }

    return 0;
}

完全に構造体を理解しているので、Processを表現する構造体を作ってからそいつらをQueueへと差し込んでいきます。
これらが全て空になるまでぶん回してあげます。
取り出す処理は1つにもできたなーとか思いました。無事パス。

いやー、よかった。

おわりに

次回は連結リストについて書く予定ですが、平行してABCの過去問を解き始めたのでそちらを掲載する可能性もあります。

余談ですが、自宅・会社共にMac Book Pro 15インチを使っており端末が重いので持ち歩くのが大変辛いです。そのため、プロコンだけでもiPadでやりたいなーという気持ちが高まったので、 AWS Cloud9の設定をしてみることにしたのでした。

結果から言うと、実用に即す状態ではなかったのですが一応書いておきます（大して時間かけてないので、sshで行う形で整備すればいけると思います）。


今回やったのは、AWSコンソールにiPadからログインして、ブラウザでcloud9を使うってだけです。iPad版のGoogle Chromeだとサードパーティクッキーの設定が詳細にできず開く事さえままなりませんでした。

Safariで行うようにします。iPadの設定から、以下をオフにしてURLへとアクセスすると無事開けるはずです。

実用に耐えるようになったらまた試そう…（それとは別にAWS Cloud9はめっちゃ便利でした）。

皆も使ってみてね。


面白ければシェアをお願いします！ twitterのフォローとブログの購読も！ blog: www.pavlog.tokyo twitter: https://twitter.com/_pavlog