[C++][Google CodeJam] C++20 rangeでGCJ2019 R2-Aを解く

5年空いた更新でのっけから言い訳で始まりますが、C++20どころかC++14から周回遅れ状態で突っ込みどころが多々あるかと思いますがそれ相応にお願いします。

さて2008年以降毎年参加しているGoogle CodeJamですが、最新のC++で頑張る(特に時間に余裕のあるQualification Roundでは)という裏目的は2018年にコンテストシステムがローカル実行からリモート実行へ変更されて以降難しくなってしまいました(2019年ではgcc-6.3.0で-std=c++14になっています)。ということでC++欲が高まっているところにGCJ R2-Aが割ときれいに書けた＆cmcstl2を見つけた(遅い)ということでC++20 rangeで書いてみたものです。

該当の問題はNew Elements: Part 1。実装した解法はanalysisに書いてあるのと同じだと思います。競技時間中に書いていたものをC++20 rangeを使って書き直したものが↓でwandboxによる実行結果がこれです。

#include "cmcstl2/include/meta/meta_fwd.hpp" // force to use meta in cmcstl2
#include "cmcstl2/include/meta/meta.hpp" // same as above
#include <experimental/ranges/ranges>
#include <experimental/ranges/iterator>
#include <experimental/ranges/algorithm>
#include <vector>
#include <set>
#include <iostream>
#include <utility>
#include <cstdint>

namespace ranges = std::experimental::ranges;

// for ADL for operator>>
struct vec2 : std::pair<int,int> { using std::pair<int,int>::pair; };
inline std::istream& operator>>(std::istream& is, vec2& p) { return is >> p.first >> p.second; }
inline constexpr vec2 operator-(const vec2 &v1, const vec2 &v2) { return { v1.first - v2.first, v1.second - v2.second }; }
inline constexpr vec2 operator-(const vec2 &v1) { return { -v1.first, -v1.second }; }
inline constexpr auto ratio_less = [](const std::pair<int,int> &v1, const std::pair<int,int> &v2){
    return static_cast<std::int64_t>(v1.second) * v2.first > static_cast<std::int64_t>(v1.first) * v2.second;
};

// from http://ericniebler.com/2018/12/05/standard-ranges/
inline constexpr auto for_each = [] <ranges::Range R, ranges::Iterator I = ranges::iterator_t<R>, ranges::IndirectUnaryInvocable<I> Fun>
                                    (R&& r, Fun fun) /* requires ranges::Range<ranges::indirect_result_t<Fun, I>> */ {
    return std::forward<R>(r) | ranges::view::transform(std::move(fun)) | ranges::view::join;
};
inline constexpr auto all_pairs = [](int N) {
    return for_each(ranges::iota_view(0, N), [=](int n){ return ranges::view::transform(ranges::iota_view(n+1, N), [=](int m){ return std::make_pair(n, m); }); });
};
inline constexpr auto all_pairs_r = [](auto &&r){
    return for_each(
        ranges::iota_view(ranges::begin(r), ranges::end(r)) | ranges::view::transform([e=ranges::end(r)](auto it){return ranges::subrange(it, e);}),
        [](auto &&rr){
            return ranges::view::transform(rr.next(), [pp1=ranges::begin(rr)](auto p2){ return std::make_pair(*pp1, p2); });
        }
    );
};

int main()
{
    int P; std::cin >> P;
    ranges::for_each(ranges::iota_view(1, P+1), [&](int p){
        int N; std::cin >> N;
        std::vector<vec2> v(N);
        // At least, ranges::copy_n can't be used because input iterator is incremented for a result value
        // see also http://www.open-std.org/jtc1/sc22/wg21/docs/lwg-active.html#2471
        std::copy_n(ranges::istream_iterator<vec2>(std::cin), N, ranges::begin(v));
#if 1
        auto r = all_pairs_r(v) | ranges::view::transform([](auto p){ return p.first - p.second; })
                                | ranges::view::filter([](auto p){ return p.first * p.second < 0; })
                                | ranges::view::transform([](auto p){ return p.first > 0 ? p : -p; })
                                | ranges::view::common;
#else
        auto r = all_pairs(N) | ranges::view::transform([&v](auto p){ return v[p.first] - v[p.second]; })
                              | ranges::view::filter([](auto p){ return p.first * p.second < 0; })
                              | ranges::view::transform([](auto p){ return p.first > 0 ? p : -p; })
                              | ranges::view::common;
#endif
        // Use deduction guide (gcc8 required for libstdc++ part)
        std::set s(ranges::begin(r), ranges::end(r), ratio_less);
        std::cout << "Case #" << p << ": " << s.size() + 1 << std::endl;
    });
    return 0;
}

以下簡単な説明。

最初の2行とコンパイルオプション-I/opt/wandboxはwandboxだとcmcstl2内のmetaとrange-v3のmetaが衝突するのでその回避用です。まず必要なヘッダを#includeして適当にnamespace aliasを作成。vec2を定義しているのはiostream用のoperator>>がADLで引っ掛けられるようにするためです(std::pairのままだとstd名前空間内にoperator>>を定義しないとADLで引っ掛けられないが未定義動作になる)。using部分はinheriting constructorsです。このvec2に対して、iostream用operator>>、減算、単項マイナス、有理数として見た場合の比較関数(の符号手抜き版)を定義します。比較関数は32bit環境向けに64ビット変数へのキャストを入れています。

for_eachはRangeの神様 Eric Niebler 氏の記事からぱくってきたものです。Constraint lambdaがとてもえぐいですがシグネチャとしては明確になっていると思います(でもあまり書きたいとは思えない)。コメントアウトしてあるrequires部分はtrailing requires-clauseとしてここにかけるはずなのですがgcc-9.1.0では通りませんでした(HEADだとコンパイラが落ちる)。

このfor_eachを利用して、N未満の2整数の組のrangeを生成するall_pairsと、渡されたrange中の2要素の組のrangeを生成するall_pairs_rを定義しています。all_pairs_rについてはとりあえず動いてるように見えますが書いた当人がまじで動いてるのこれ？状態です。

最初の ranges::for_each にはあまり意味はなく、せっかくだら for なくそうというだけでしかありません。

最初にデータ数を読みだしてきてstd::copy_nを使ってstd::cinからvec2の列を読みだしてきます。このとき少なくともranges::copy_nだと意図通り動作しません。ranges::copy_nはstd::copy_nと違い入力側のiteratorについても処理後の値を返り値で返すのですがいわゆるone-past-endの値になっています。一方でistream_iteratorはインクリメント時に次のデータを読みだしてくるのでN個コピーするときにはN+1個読みだされた状態になってしまいます(実質1個分捨てられる)。実際にはstd::copy_nについても現状は明確な記載がなくlwg-2471がOpenになっていますが既知の実装ではN-1回インクリメントになっているようです。

次がメインの処理で、all_pairs起点の場合、N未満の2整数の組を生成→これを添え字としたときのvec2列の要素間の差を生成→firstとsecondの積が負になる場合(＝傾きが負になる場合)のみに限定→first(分母)が正になるように正規化しています。all_pairs_r起点の場合には添え字の組ではなく最初から要素の組が生成されています。最後のranges::view::commonは次にsetのコンストラクタ(Iteratorの組を引数にとるもの)に渡すためにbeginとendが同じ型になるようにしています。これを有理数としてみた場合のsetに突っ込んで独立な傾きの数を求めて+1して終了です。setではクラステンプレートのテンプレート引数推論で型引数を省略しています。ranges::to: A function to convert any range to a containerが入れば

auto s = all_pairs_r(v) | ... | ranges::to<std::set>(ratio_less);

みたいに書けるようになるかもしれません(多分)。Input Range Adaptorsも加えて

auto v = ranges::istream_view<vec2>(std::cin) | ranges::view::take(N) | ranges::to<std::vector>;

とでも書けるともっといいと思いますが、copy_nの時と同じ話になってしまいます。せっかく無限Rangeが表現できるようになったので++時には入力を読まない版ができればいいのかもしれません。

どうでしょうか。もちろんこの処理なら普通に書いてもよっぽどシンプルですがまるでアルゴリズムの教科書に書いてあるかのごとく処理内容・意図が簡潔・明確に示されている感じがしないでしょうか。C++11以降とそれより前でC++は大きく変わっているわけですが、Conceptが入ることもありC++20はそれ以上に大きな変革になりそうです。