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

ゆとりーなの日記

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

Paiza、そのI/Oゲーを越えて

前󠄁回PaizaとはI/Oゲーである - 名古屋313の日記にて、野田さんの案件が如何にI/Oゲーであるかを暴き出した訣ですが、最速󠄁記錄である0.01秒の壁は越えられずにゐました。流石にI/O關聯でもう手を付けられる所󠄁は殘つてゐないと思つたので、かうなるともうアルゴリズムを見直すしかないですね。
で、まあ次󠄁に重いのがソートなのは分つてゐたんですけど、色々なページperlで頑張って新人女子を助けた。 #paizahack_01 - blog.aklaswad.com佐祐理ブログ: 続 C# は高級アセンブラtwitterの檢索を見るとどうもバケットソートなるものが良いみたいな空󠄁氣を受信し、まあ屹度速󠄁いソートがあるんだらうとぐぐつてみたらありました分布数えソート(最高速のソート)。このページは私でも理解出來たので、早速󠄁このdist_sortなるものを實裝します。

#include <unistd.h>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <iostream>
#include <vector>

typedef const int *c_it_t;
typedef int *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;
}

// 分布數へソート
void dist_sort(it_t begin, it_t end) {
  int tmp[1000001] = {0};
  for (it_t it = begin; it != end; ++it) {
    ++tmp[*it];
  }
  for (int i = 1000000; i >= 0 && begin != end; --i) {
    for (int j = 0; j < tmp[i]; ++j) {
      *(begin++) = i;
    }
  }
}

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);
    dist_sort(items, items + num);
    for (int i = 0; i < day; ++i) {
        std::printf("%d\n", check(items, items + num, items[num + i]));
    }
    std::free(items);


    return 0;
}

std::sortをこれで置換へて挑戰した結果がこれですnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。case3が0.02秒です。惜しいですね。(因みにヘッダでの惡さの跡が垣間見えるのはシステムコールを呼ばうとした時の消󠄁し忘れです。因みに殆ど效果の程󠄁はありませんでしたとさ。他にも前囘のを使ひ囘したので今迄氣附かなかつたんですけど、vectorやらcinを使つてた時の名殘のヘッダもあつて、かう云ふのが殘つてるとバイナリサイズに影響󠄃が出たりするので要󠄁注󠄁意󠄁なんですよね...。)
このコードで無駄な所󠄁は割󠄀りとすぐ見つかります。最初に商品價格を價格配列に讀まずにヒストグラム配列に讀めば、多少はコピー囘數が減らせるでせう。で、これを元に折角なので構󠄁造󠄁化󠄁()とヘッダの整理を施したしたコードがこちら。

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <functional>

typedef const int *c_it_t;
typedef int *it_t;
const std::size_t price_max = 1000000;
const std::size_t input_len_max = 4002412;

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;
}

char *read_input(std::size_t &len) {
    char * const data = static_cast<char *>(std::malloc(input_len_max));
    len = std::fread(data, 1, input_len_max, stdin);
    return data;
}

int get_num(char *&it) {
    int num = 0;
    for (; *it != ' '; ++it) {
      num = num * 10 + (*it - '0');
    }
    ++it;
    return num;
}

int get_day(char *&it) {
    int day = 0;
    for (; *it != 0x0a; ++it) {
      day = day * 10 + (*it - '0');
    }
    ++it;
    return day;
}

void make_hist(char *&it, int (&hist)[price_max + 1], int num) {
    int tmp = 0;
    for (int i = 0; i < num; ++it) {
        if (*it == 0x0a) {
            ++hist[tmp];
            tmp = 0;
            ++i;
        } else {
            tmp = tmp * 10 + (*it - '0');
        }
    }
}

int *get_days(char *&it, int day, const char *data, int len) {
    int * const days = static_cast<int *>(std::malloc(sizeof(int) * (day)));
    for (int i = 0; it < data + len; ++it) {
        if (*it == 0x0a) {
            ++i;
        } else {
            days[i] =days[i] * 10 + (*it - '0');
        }
    }
    return days;
}

void dist_sort(it_t begin, it_t end, const int (&hist)[price_max + 1]) {
  // 今思ふと外側のループの終了條件はbegin != end丈で良い氣もする
  for (int i = price_max; i >= 0 && begin != end; --i) {
    for (int j = 0; j < hist[i]; ++j) {
      *(begin++) = i;
    }
  }
}

int main() {
    std::size_t len;
    char * const data = read_input(len);
    char *it = data;
    const int num = get_num(it);
    const int day = get_day(it);
    int hist[price_max + 1] = {0};
    make_hist(it, hist, num);
    int *days = get_days(it, day, data, len);
    std::free(data);
    int *items = static_cast<int *>(std::malloc(sizeof(int) * (num)));
    dist_sort(items, items + num, hist);
    for (int i = 0; i < day; ++i) {
        std::printf("%d\n", check(items, items + num, days[i]));
    }
    std::free(days);
    std::free(items);
    return 0;
}

結果がこちらですnagoya313さんの採点結果[100点 CTOに昇進しました!]|paizaオンラインハッカソンVol.1。念願のオール0.01秒。漸く大勝󠄁利に漕ぎ着けました。
しかしエントリ書くに邊り細々調󠄁整して割󠄀と何囘も提出したので、C++受驗數の中何%を私が囘したのかを考へると...(ry。
追󠄁記:
より短く0.01秒を出してゐる所󠄁を發見しましたpaiza POH ec-campaign #paizahack_01 - Qiita。こちらも今思ふと確かにmallocは生配列で良かつたのでは感ありますね...。まあ0.01秒出たので氣にしない事に...。