読者です 読者をやめる 読者になる 読者になる

Gobble up pudding

プログラミングの記事がメインのブログです。

MENU

AOJ(Aizu Online Judge)やってみた

スポンサードリンク

f:id:fa11enprince:20150730082309j:plain
競技プログラミングでAOJやってみました。
最初よくわからんかったのですが、
ここも自動で提出したコードを即時にチェックしてくれる
いいところです!
なぜか人間がチェックするものだとずっと勘違いしていました(笑)
他の人の回答も手軽に見れるところも良いです!オヌヌメです。
そんなわけで手始めにバブルソートやってみました。
バブルソートやるだろ最初なら!!
ってことで最初提出。
Presentation Errorと出る。
うーん…………。
どうも余計なスペースとか入ってるとダメらしい。
気づくのに3分もかかったぞ!!
includeとか使ってないもの入っているのは競技プログラミング仕様です。
ここもpaizaと一緒で標準入力を受け取らないとダメらしい。
そこがめんどくさい……。
ちなみにでっかい方から後ろに持ってく方式にしたけど、
小さい方から前に持ってく方が普通かも。まあいいや。
やったのはこのレッスン
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ALDS1_2_A

入力

5
5 3 2 4 1

バブルソート(C++11)

#include <iostream>
#include <iterator>
#include <sstream>
#include <string>

#include <set>
#include <list>
#include <unordered_map>
#include <vector>
#include <stack>
#include <queue>

#include <algorithm>
#include <utility>

using namespace std;

// C++11系の標準関数でのg++のバグ対策と
// split系の関数を作成
namespace patch
{
    template <typename T>
    string to_string(const T &n)
    {
        ostringstream stm;
        stm << n;
        return stm.str();
    }
    int stoi(const string &str)
    {
        int ret;
        istringstream stm(str);
        stm >> ret;
        if (stm.fail())
        {
            throw -1;
        }
        return ret; 
    }
    vector<string> split(const string &str)
    {
        istringstream stm(str);
        vector<string> ret;
        copy(istream_iterator<string>(stm),
            istream_iterator<string>(),
            back_inserter(ret));
        return ret;
    }
    vector<string> split(const string &str, char delim)
    {
        istringstream stm(str);
        vector<string> ret;
        string buf;
        while (getline(stm, buf, delim))
        {
            ret.push_back(buf);
        }
        return ret;
    }
}

int bubbleSort(vector<int> &vs)
{
    int end = vs.size();
    if (end == 1)
    {
        return 0;
    }
    int cnt = 0;
    for (int j = 0; j < end - 1; ++j)
    {
        for (int i = 0; i < end - j - 1; ++i)
        {
            if (vs[i] > vs[i+1])
            {
                swap(vs[i], vs[i+1]);
                ++cnt;
            }
        }
    } 
    return cnt;
}

// bubble sort
int main()
{
    ios::sync_with_stdio(false);

    // --- 標準入力読込開始 ---
    // line 1
    string s1;
    getline(cin, s1);
    int n = patch::stoi(s1);

    // line 2
    vector<int> vs(n);
    vector<string> ss;
    string s2;
    getline(cin, s2);
    ss = patch::split(s2);
    for (int n = 0, sz = ss.size(); n < sz; ++n)
    {
        vs[n] = patch::stoi(ss[n]);
    }
    // --- 標準入力読込終了 ---

    // バブルソート実行
    int cnt = bubbleSort(vs);
    
    bool isFirst = true;  // 無駄なスペースがあるとダメらしいので
    for (int n : vs)
    {
        //cout << n << " ";   // ふぁっ?! Presentation Error??!
        if (isFirst)          // こうやるしかないぽ
        {
            cout << n;
            isFirst = false;  // 仕方ねぇ
        }
        else
        {
            cout << " " << n;
        }
    }
    cout << "\n";
    cout << cnt << "\n";
    
    return 0;
}