Hatena::ブログ(Diary)

名古屋313の日記

2014-01-29 久々の出向だん

戻り値auto

| 03:25

今更󠄁ですけど戾り値のautoつて飜譯單位分󠄁けると利かないんですね。

// hoge.h
auto hoge();

// hoge.cc
auto hoge() {
  return 0;
}

// main.cc
#include "hoge.h"

int main() {
  auto h = hoge(); // 怒られる!
}

まあ良く考へたらさうですよね...。

福岡けん福岡けん 2014/04/26 15:21 そうですか?

わかりました。


http://openwiki.pixub.com/

naohiro19naohiro19 2015/08/28 22:41 Visual Studio 2015からしか使えません。

naohiro19naohiro19 2015/08/28 22:41 Visual Studio 2015からしか使えません。

2013-12-13 早起き()

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

| 04:16

前󠄁回PaizaとはI/Oゲーである - 名古屋313の日記にて、野田さんの案件が如何にI/Oゲーであるかを暴き出した訣ですが、最速󠄁記錄である0.01秒の壁は越えられずにゐました。流石にI/O關聯でもう手を付けられる所󠄁は殘つてゐないと思つたので、かうなるともうアルゴリズムを見直すしかないですね。

で、まあ次󠄁に重いのがソートなのは分つてゐたんですけど、色々なページperlで頑張って新人女子を助けた。 #paizahack_01 - blog.aklaswad.com佐祐理ブログ: 続 C# は高級アセンブラtwitterの檢索を見るとどうもバケットソートなるものが良いみたいな空󠄁氣を受信し、まあ屹度速󠄁いソートがあるんだらうとぐぐつてみたらありました404 Not Found。このページは私でも理解出來たので、早速󠄁この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秒出たので氣にしない事に...。

2013-12-12 The インクリメンツ再び

operator +の自動生成のconstexpr化は詰んでなかつた

| 02:07

operator +の自動生成のconstexpr化は多分詰んでる - 名古屋313の日記で詰んでるたとされてゐたoperator +の自動生成󠄁のconstexpr化󠄁ですが、C++14仕樣になつたら別に詰んでゐませんでした。

template <typename T>
struct addable {
  friend constexpr T operator +(const T &lhs, const T &rhs) {
    return T(lhs) += rhs;
  }
};

struct hoge : private addable<hoge> {
  constexpr explicit hoge(int x) : x_{x} {}
  
  constexpr hoge &operator +=(const hoge &rhs) {
    // かう書けば宜しい
    x_ += rhs.x_;
    return *this;
  }
  
  int x_;
};

#include <iostream>

int main() {
  constexpr auto a = hoge{313};
  constexpr auto b = hoge{211};
  constexpr auto c = a + b;

 auto d = hoge{311};
  d += c;

  std::cout << d.x_ << std::endl;
}

大勝󠄁利ですね。

2013-12-06 野田さんとの戲れ

PaizaとはI/Oゲーである

| 01:55

一部界隈で話題になつてゐる「新人女子プログラマの書いたコードを直すだけの簡単なお仕事です!|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秒を出してゐるらしいのですよね。一體どんなコードなんでせうか、氣になるところです。

2013-12-04 フィーバーがしたい

clangは麻雀が作りやすい

| 13:36

clangは素晴󠄀らしい事に識別子に日本語が使󠄁へるので、英語弱󠄁者󠄁の私が識別子名で惱む事がないのです。

牌の型の定義も簡單で、可讀性も屹度高い筈です。

enum 牌種 {
  一, 九,
  , , , , , , , , ,
  1, 2, 3, 4, 5, 6, 7, 8, 9,
  東, 南, 西, 北,
  白, 發, 中
};

因みに萬子の中がないのはサンマのせいです。

で、手牌がこんな感じに表現出來ます。

const std::vector<牌種> 手牌 = {一, 九, , , 1, 9, 東, 南, 西, 北, 白, 發, 中};

よくある麻󠄁雀の手牌表記に近󠄁附きました。

ただ日本語識別子だと型名と變數名がわりかし被り易いやうな氣がします。アルファベット書きだと先頭の大文󠄁字小文󠄁字で區󠄁別し易いんですがね。まああんまりこんな事やる人はゐないでせうから、命名規約的なものもさつぱりないでせうし...。