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

ゆとりーなの日記

日記的な事を書いて行くと思はれる

PaizaとはI/Oゲーである

一部界隈で話題になつてゐる「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!|paizaオンラインハッカソンVol.1」に、アルゴリズム弱󠄁者󠄁の私も挑戰してみました。
で、取敢ずこんなコードで挑む訣です。

#include <algorithm>
#include <iostream>
#include <vector>

typedef std::vector<int>::const_iterator c_it_t;

int check(c_it_t begin, c_it_t end, int price_max) {
    int price = 0;
    const c_it_t b = std::upper_bound(begin, end,
                                      price_max, std::greater<int>());
    if (b != end) {
	for (c_it_t it = b; it != end - 1; ++it) {
            const c_it_t it2 = std::lower_bound(it + 1, end,
                                                price_max - *it,
                                                std::greater<int>());
            if (it2 != end && price < *it + *it2) {
                price = *it + *it2;
                if (price == price_max) {
                   return price;
                }
            }
        }
    }
    return price;
}

int main() {
    int num;
    int day;
    std::cin >> num >> day;
    std::vector<int> items;
    items.reserve(num);
    for (int i = 0; i < num; ++i) {
        int price;
        std::cin >> price;
        items.push_back(price);
    }
    std::sort(items.begin(), items.end(), std::greater<int>());
    for (int i = 0; i < day; ++i) {
        int price;
        std::cin >> price;
        std::cout << check(items.begin(), items.end(), price) << std::endl;
    }
    return 0;
}

アルゴリズムは適󠄁當で、降󠄁順にソートしてから條件に當嵌る奴だけ只管二分󠄁探索して良い答へを見つけて、一致があつたら拔ける、とかそんな事をやつてるだけです。二分󠄁探索が自力で書けないゆとりでもC++にはSTLがゐるので安心です。lower/upper_bound萬歲!で、結果がこちらnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。case3で0.48秒です。
しかし明らかにもつと速󠄁い人がゐるのはTLから明らかだつたので改良に走ります。まづ目をつけるのはiostreamが遲いと云ふ噂です。そこでかねてから聞いてゐたiostream高速󠄁化󠄁のおまじなひをつけてみます。

int main() {
    int num;
    int day;
    std::cin.tie(0); // coutとcinの結び附きを解除
    std::ios::sync_with_stdio(false); // Cのstdioとの同期をしない
    std::cin >> num >> day;
    std::vector<int> items;
    items.reserve(num);
    for (int i = 0; i < num; ++i) {
        int price;
        std::cin >> price;
        items.push_back(price);
    }
    std::sort(items.begin(), items.end(), std::greater<int>());
    for (int i = 0; i < day; ++i) {
        int price;
        std::cin >> price;
        std::cout << check(items.begin(), items.end(), price) << '\n'; // フラッシュを毎回しない
    }
    return 0;
}

これだけで一氣に速󠄁くなりましたnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。case3で0.13秒です。因みにどうも競技界隈ではiostreamを使󠄁ふならこの手をやるのは常識みたいな感じらしいです。
C言語の一般的なI/O版

int main() {
    int num;
    int day;
    std::scanf("%d %d", &num, &day);
    std::vector<int> items(num);
    for (int i = 0; i < num; ++i) {
        std::scanf("%d", &items[i]);
    }
    std::sort(items.begin(), items.end(), std::greater<int>());
    for (int i = 0; i < day; ++i) {
        int price;
        std::scanf("%d", &price);
        std::printf("%d\n", check(items.begin(), items.end(), price));
    }
    return 0;
}

nagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1だつたので、なんと大勝󠄁利を收めてゐます。(case3で0.14秒、但し實行機󠄁會に依つて動作時間にバラつきがあるらしいので誤󠄁差の可能性も否定出來ない?)
續いてiostreamの數値變換は遲かつた記憶があつたので、getlineしてatoiすると云ふのもやつてみました。

int main() {
    int num;
    int day;
    char str[8];
    std::cin.tie(0);
    std::ios::sync_with_stdio(false);
    std::cin >> num >> day;
    std::vector<int> items;
    items.reserve(num);
    std::cin.getline(str, sizeof(str));
    for (int i = 0; i < num; ++i) {
        std::cin.getline(str, sizeof(str));
        items.push_back(std::atoi(str));
    }
    std::sort(items.begin(), items.end(), std::greater<int>());
    for (int i = 0; i < day; ++i) {
        std::cin.getline(str, sizeof(str));
        std::cout << check(items.begin(), items.end(), std::atoi(str)) << '\n';
    }
    return 0;
}

これでややC言語つぽくなつた代はりにほんのちよびつとだけ速󠄁くなつたものの、まだ最速󠄁には遠󠄁く及びませんnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。case3で0.11秒です。
で、twitterをみてたらC#で參戰してゐた@haxeさんが佐祐理ブログ: C# は高級アセンブラにてI/O呼び出しを削󠄁ると良いと書いてあつたので、あまりやりたくなかつたのですがメモリに一度に讀んで自前󠄁で數値パースと云ふ力技をやる事にしました。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>

typedef const int *c_it_t;

int check(c_it_t begin, c_it_t end, int price_max) {
    int price = 0;
    const c_it_t b = std::upper_bound(begin, end,
                                      price_max, std::greater<int>());
    if (b != end) {
	for (c_it_t it = b; it != end - 1; ++it) {
            const c_it_t it2 = std::lower_bound(it + 1, end,
                                                price_max - *it,
                                                std::greater<int>());
            if (it2 != end && price < *it + *it2) {
                price = *it + *it2;
                if (price == price_max) {
                   return price;
                }
            }
        }
    }
    return price;
}

int main() {
    int num = 0;
    int day = 0;
    // 條件から恐らく使はれるであらう最大メモリを確保(計算間違つてたら恥づい...)
    char * const data = static_cast<char *>(std::malloc(4002412));
    char *it = data;
    const int len = std::fread(data, 1, 4002412, stdin);
    for (; *it != ' '; ++it) {
        num = num * 10 + (*it - '0');
    }
    ++it;
    for (; *it != 0x0a; ++it) {
        day = day * 10 + (*it - '0');
    }
    ++it;
    int * const items = static_cast<int *>(std::malloc(sizeof(int) * (num + day)));
    for (int i = 0; it < data + len; ++it) {
        if (*it == 0x0a) {
      	    ++i;
        } else {
            items[i] = items[i] * 10 + (*it - '0');
        }
    }
    std::free(data);
    std::sort(items, items + num, std::greater<int>());
    for (int i = 0; i < day; ++i) {
        std::printf("%d\n", check(items, items + num, items[num + i]));
    }
    std::free(items);
    return 0;
}

ここまで來たら殆どC言語ですが大分󠄁速󠄁くなりましたnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。辛うじてSTLを使󠄁つてゐるとは言へ、生ポインタにmallocと、C言語に塗れています。これでcase3が0.05秒です。
なんだかんだでI/Oゲーだつたつてのが何となくお解り頂けたかと思ひます。アルゴリズムはそのままでもこれだけ變はるのですから、殆ど如何に入力を速󠄁くするかのゲームなのです。
因みに私はここまでが限界でしたが巷では0.01秒を出してゐるらしいのですよね。一體どんなコードなんでせうか、氣になるところです。