[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はそれ以上に大きな変革になりそうです。

[C++] next_combination() 書いてみた

C++ 標準ライブラリの <algorithm> には next_permutation() という関数があります。辞書順で順列を列挙してくれる大変便利な関数で競プロ関連でお世話になったことのある人も結構いるのではないかと思います。順列があるなら組み合わせはないの？ということで next_combination() で検索をかけると nyama++ さんの 全ての組み合わせを作る【C++】 - Programming Magic という記事が引っかかります(他の検索結果からも結構参照されているようです)。この記事のリンクで指し先が消失しているものがありますが、内容自体は ISO C++ 標準化委員会(JTC1/SC22/WG21) に提案されているペーパー n2639 Algorithms for permutations and combinations, with and without repetitions です(実装は Reference implementation のところ)。next_pertial_permutation() (next_permutation() が n! の列挙なら、これは nPr を列挙する) の実装が

template <class BidirectionalIterator>
bool next_partial_permutation(BidirectionalIterator first, BidirectionalIterator middle, BidirectionalIterator last)
{
  reverse(middle, last);
  return next_permutation(first , last);
}

というのも私的に感動ポイントですが、next_combination() は確かに訳が分かりません。ってことで一度自分で書いてみたところ最終的にほぼ同様のアルゴリズムとなり理解が進みましたので解説記事っぽいものを書いてみようと思います。なお図としては全ての要素が1ずつ異なるようなイメージで書いていますが、値が跳んでいてもいいですし重複があっても問題ないはずです。

まず最初に意味不明と書かれていた prev_combination() について。処理上何かと便利なので [first, middle), [middle, last) がソートされている、という前提を置いておきます。このとき、[first, middle) に対して next_combination() した場合の例は以下のようになります。

見ての通り、[middle, last) に対しては prev_combination() になっています(両方の領域がソート済み、かつ、辞書式順序で列挙なのでこうなる)。ということで先の前提の下で next_combination() が正しく実装できれば他方の領域に対して next_combination() をかけてやれば元々の領域に対する prev_combination() になります。

さて、では本論のコードについて。さすがに真っ白の状態だと書けないので n2639 で参考文献として挙げられている Knuth 先生の The Art of Computer Programming. Volume 4, Fascicle 3 GeneratingAll Combinations and Partitions を見ると（※立ち読み。分冊が一冊になったら買います、多分）確かに列挙アルゴリズムが記述されてはいますが添字の列挙としてのアルゴリズムであって実際に要素の並び替えを行う next_permutation() 風の next_combination() の場合だとそのままでは使えなさそうです。そうすると指針としては、汎用的な方法として挙げられている「最も右端の増加可能な要素を見つけて増加、以降の要素は設定可能な最小値を設定していく」になります。これを実装してみましょう。

まずは「最も右端の増加可能な要素」を見つける必要があります。右端(middle - 1)が最大値でない場合はそこが増加可能です。では右端ではない部分が「最も右端の増加可能な要素」となる場合を考えてみましょう。この時その要素(*targetとしておきます)の右側には、右端(*(middle-1))が最大値となる状態で連続して昇順に要素が並んでいることになります。さもなくば、より右側の要素が増加可能になるからです。[middle, last) もソート済であることと合わせると、*target < *(last-1) となる最も右端の target を見つければいいことになります。これが存在しない場合には列挙終了です。

次に、*target をどの値に変更すれば良いかを考えましょう。target の右側が最大値から連続で詰まっているので、[target, middle) の間の値は考慮する必要がありません(target から middle まで埋めるには要素が足りない)。ということで、[middle, last) のうちで *target より大きくなる最小値に設定すれば良いことになります(next とします)。*target < *(last-1) なので [middle, last) で必ず見つかります。

では、[target+1, middle) (と [next, last) をどのように埋めれば良いでしょうか？ これまでの条件から [target, middle) [next, last) 近傍の順序は下図上段のようになっています。[target, middle) はできるだけ最小になるように設定すること、[middle, last) もソートされている必要があることを考えると最終結果は下図下段のようになっている必要があります。これは target と next を iter_swap した後、[target+1, middle), [next+1, last) が一つの領域だとみなして、next+1 が先頭となるように rotate() することに他なりません。

というのをコードにまとめると以下のようになります。C++er な人には言うまでもないとは思いますが、わざわざ !(a < b) みたいな書き方になってるのは operator< のみ使用にしたかったからです。なお、rotate() は en.cppreference.com の参考実装(Forward Iterator 向けですが)に分割2領域用にちょっとだけ修正したものです。

// possible implementation introduced at http://en.cppreference.com/w/cpp/algorithm/rotate with slight modification to handle parted ranges
template<typename FI>
void parted_rotate(FI first1, FI last1, FI first2, FI last2)
{
 if(first1 == last1 || first2 == last2) return;
 FI next = first2;
 while (first1 != next) {
  std::iter_swap(first1++, next++);
  if(first1 == last1) first1 = first2;
  if (next == last2) {
   next = first2;
  } else if (first1 == first2) {
   first2 = next;
  }
 }
}

template<typename BI>
bool next_combination_imp(BI first1, BI last1, BI first2, BI last2)
{
 if(first1 == last1 || first2 == last2) return false;
 auto target = last1; --target;
 auto last_elem = last2; --last_elem;
 // find right-most incrementable element: target
 while(target != first1 && !(*target < *last_elem)) --target;
 if(target == first1 && !(*target < *last_elem)) {
  parted_rotate(first1, last1, first2, last2);
  return false;
 }
 // find the next value to be incremented: *next
 auto next = first2;
 while(!(*target < *next)) ++next;
 std::iter_swap(target++, next++);
 parted_rotate(target, last1, next, last2);
 return true;
}

// INVARIANT: is_sorted(first, mid) && is_sorted(mid, last)
template<typename BI>
inline bool next_combination(BI first, BI mid, BI last)
{
 return next_combination_imp(first, mid, mid, last);
}

// INVARIANT: is_sorted(first, mid) && is_sorted(mid, last)
template<typename BI>
inline bool prev_combination(BI first, BI mid, BI last)
{
 return next_combination_imp(mid, last, first, mid);
}

基本的に n2639 とほぼ同じことをするコードです。nyama++ さんの記事で②③となっているところが実は合わせて rotate() だったわけです。

reverse(first, mid);
reverse(mid, last);
reverse(first, last);

という reverse() 3連打の rotate() 実装を 2 領域対応にした形が②③になります。後の違いは、false を返す時に先に return する(rotate() が 2 ヶ所になる)か、1ヶ所で rotate() するかくらいですね。

ついでなので、計算量(iter_swap の呼び出し回数)について実際に計数させてみたところ、2nCn 列挙時での 1 next_combination() 辺りの平均 iter_swap() 回数は 1.7 くらいに収束しそうな感じです。 もちろん組み合わせの数自体が指数関数的に増えるので全体的にはすぐに苦しくなるのですが、かなり悪くない数字に感じます。

#n,r,the number of iter_swap,the number of combinations,average iter_swap per one next_combination() call
2,1,2,2,1
4,2,8,6,1.33333
6,3,30,20,1.5
8,4,112,70,1.6
10,5,414,252,1.64286
12,6,1540,924,1.66667
14,7,5754,3432,1.67657
16,8,21656,12870,1.68267
18,9,81994,48620,1.68643
20,10,312068,184756,1.68908
22,11,1192954,705432,1.6911
24,12,4577356,2704156,1.69271
26,13,17619034,10400600,1.69404
28,14,68003992,40116600,1.69516
30,15,263097002,155117520,1.69611
32,16,1019997844,601080390,1.69694
34,17,3961678122,2333606220,1.69766
36,18,15412309480,9075135300,1.6983
38,19,60046904394,35345263800,1.69887
40,20,234252753696,137846528820,1.69937

TopCoder Open 2014 Algorithm Round 1A

システム不調ということで開始できず1週延期になった TCO R1A ですが、今回は System test に問題ってことで今のところ暫定結果でしかないものの、珍しく 1A で通過できたっぽいです。大体 1C 通過なんですけどね。またテンプレからです。今回から TopCoder も C++11 使用ですが吟味が足りない感じ。提出時には適当に削ってから提出してます。

#include <iomanip>
#include <iostream>
#include <sstream>

#include <iterator>

#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>

#include <string>

#include <map>
#include <set>
#include <queue>
#include <stack>

#include <tuple>
#include <initializer_list>

#include <cmath>
#include <cassert>

typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned int UI;

#define MP make_pair
#define RNG(v) (v).begin(), (v).end()
#define RRNG(v) (v).rbegin(), (v).rend()
struct irange {
    struct irit {
        int value;
        operator int&() { return value; }
        int operator *() { return value; }
    };
    irit begin() const { return { first }; }
    irit end() const { return { last }; }
    int first, last;
};
inline irange IR(int first, int last) { assert(first <= last); return { first, last }; }
template<typename T> struct rpq { typedef std::priority_queue<T, std::vector<T>, std::greater<T> > type; };

using namespace std;

class $CLASSNAME$ {

    public: $RETURNTYPE$ $METHODNAME$($METHODPARAMS$) {
        return $DUMMYRETURN$;
    }

};

GCJ と基本変わりませんが、TopCoder では boost が使えないので IR() だけ似非 range クラスでごまかしています。早いところ range 標準で入ってくれないですかね……。

250. EllysSortingTrimmer

まず最初に問題の意味を取り違えました。複数回使えるをすっ飛ばしてコード書いて実行して例の結果見てから「ふぁ？」ってなりました。それはともかく。1回のソートで L 文字ソートできる訳ですが、結果を引き継ごうとしてずらして実行する時には最大 L-1 文字しか引き継げないわけで右から順に1つづつずらしていったら最終的には先頭文字と先頭以外で最小の L-1 文字からなる文字列のソートになります。

class EllysSortingTrimmer {
    public: string getMin(string S, int L) {
        sort(S.begin() + 1, S.end());
        sort(S.begin(), S.begin() + L);
        return S.substr(0, L);
    }
};

500. EllysScrabble

左側から可能な範囲内で一番小さな値を探して詰めていきますが、可能な範囲の左端に未使用の文字が残っていて次に可能な範囲から外れてしまう場合はそれ使うしかないので強制的に選択します。'~' は使用済みフラグです。string のコンストラクタの引数順序間違えたり、min_element の終端指定で +1 忘れたりしましたがまぁどうにか。結構 C++ らしいコードで書けた気がしています。

class EllysScrabble {
    public: string getMin(string letters, int maxDistance) {
        string result(letters.size(), ' ');
        for(int i : IR(0, letters.size())) {
            if(i >= maxDistance && letters[i - maxDistance] != '~') {
                result[i] = letters[i - maxDistance];
                letters[i - maxDistance] = '~';
            } else {
                auto it = min_element(letters.begin() + max(0, i - maxDistance), letters.begin() + min<int>(letters.size(), i + maxDistance + 1));
                result[i] = *it;
                *it = '~';
            }
        }
        return result;
    }
};

1000. EllysLamps

いつも 1000 出せない感じですが、Example は通ったので記念半分で提出しました。……正直に言えば、休憩時間に駄目だってのに気付くまでは結構テンション高かったです。結局 Challenge されましたがちゃんと気付くもんですね。まぁ YYYNY で駄目なので Challenge する側の方は簡単かもしれませんが。

実例を紙に書きながら Y が残ってしまって駄目な場合はどうなるのか考えたところ、2スイッチの場合は↓の場合だけ2スイッチが独立で変更できません(縦横転置してます)。この場合、NY か YN だとどちらか 1 つは残ってしまいます。これで Example を確認したところ最後の例だけ数字が合いません。

A|AB
B|AB

ぱっと見 YYY と連続しているところが臭そうということでここで 3 スイッチでも書き下してみたところ例えば↓なんかだとYYYで1個残ってしまいます。

A|AB
B|ABC
C|  C

ということでとりあえず書いたのが以下のコードです。

class EllysLamps { // 間違ってます
    public: int getMin(string lamps) {
        int result = 0;
        for(int i: IR(0, lamps.size() - 1)) {
            if(lamps[i] != ' ' && lamps[i] != lamps[i+1]) {
                ++result; lamps[i] = lamps[i+1] = ' ';
            }
        }
        if(lamps.size() >= 3) {
            for(int i: IR(0, lamps.size() - 2)) {
                if(lamps[i] == 'Y' && lamps[i] == lamps[i+1] && lamps[i+1] == lamps[i+2]) {
                    ++result; lamps[i] = lamps[i+1] = lamps[i+2] = ' ';
                }
            }
        }
        return result;
    }
};

先に一通り YN/NY を消してしまってから YYY を調べていますが同じループ内で調べていれば実は通っていたようです。それで良いことが言えていないのであまり意味はないですが。足りないのはこれらのパターンだけでいいのかと、取り方が左から greedy でいいのか、でしょうか。greedy の方は NY, YYY, YN は（これらだけであれば）被っても 1 文字だけで内包もされないのでできるだけ片方に寄せた方がたくさんとれる、でいいかもしれません。これらのパターンだけでいいのかはうーん、2+2とかに分解した場合にその境界を超えるところがあっても高々左右1スイッチしか広がらなくて境界内では逆に独立性があがる、みたいな。あるいは結局これらの最小パターンに帰着できる、ということになるんでしょうか。はっきりこれだと言えない感じです。

まとめ

今回珍しく簡潔に書けちゃったもので、Challenge 中に他の人のコード見てると「なんでこんなややこしいの」って感じになってしまいました。Challenge するには気力が足りなくなってる感じです。今回たまたま R1A で通ってしまいましたが、どう考えてもリハビリが足りない感じなので Parallel Round にはできるだけ参加したいと思っています。

Google Code Jam 2014 Qualification Round

今年も GCJ に参加しているわけですが、無事、Qualification Round は突破した模様です。一応全完。今回も C++11 で書こう、は有効の状態です。あまり活用してないですが。まず最初にテンプレ。

// gcc version 4.8.2 with -std=c++11
 
#include <iostream>
#include <sstream>
#include <iomanip>
 
#include <iterator>
 
#include <algorithm>
#include <numeric>
#include <utility>
#include <limits>
 
#include <string>
 
#include <vector>
#include <deque>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>
#include <queue>
#include <stack>
 
#include <tuple>
#include <initializer_list>
 
#include <cmath>
 
// Boost library can be retrieved from http://www.boost.org/
// 1.52 is used
 
#pragma GCC diagnostic ignored "-Wconversion"
#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>
#pragma GCC diagnostic warning "-Wconversion"
 
typedef unsigned long long ULL;
typedef long long LL;
typedef unsigned long UL;
typedef unsigned int UI;
typedef unsigned short US;
typedef unsigned char UC;
 
#define RNG(v) (v).begin(), (v).end()
#define REP(v, e) for(UI v = 0U; v < e; ++v)
#define REP_(v, s, e) for(UI v = s; v < e; ++v)
#define REPV(v, e) for(v = 0; v < e; ++v)
#define REPV_(v, s, e) for(v = s; v < e; ++v)
 
using namespace std;
 
template<class Integer>
inline auto
IR(Integer first, Integer  last) -> decltype(boost::irange(first, last))
{ return boost::irange(first, last); }
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        cout << "Case #" << casenum+1 << ": " << endl;
    }
 
    return 0;
}

Range-based for loop 用に IR() を作ってます。元々 REP マクロ(というかマクロ全般)があまり好きではないので基本 Range-based for loop 使用ですが元々のテンプレで使っていた部分から外すほど修正もしていない感じです。では、以下各問題について。

Problem A. Magic Trick

やるだけ。わざわざ set 2 つ作って set 演算してますが、1 つだけ作っといてもう一方は読み込みながら判定、の方が無駄が少ないですね。後、サイズ既知の vector の場合は for(auto &val : v) { cin >> v; } でさくっと読み込めますけどこれくらい簡単に set とかも読み込みたい感じ。inserter みたいな感じでラッパ作ればいけそうではありますが。

set<int> read()
{
    set<int> t;
    int ans; cin >> ans;
    for(int i : IR(1,5)) {
        int n;
        if(i != ans) {
            for(int j: IR(0,4)) { cin >> n; }
        } else {
            for(int j: IR(0,4)) { cin >> n; t.insert(n); }
        }
    }
    return t;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        set<int> s1 = read();
        set<int> s2 = read();
        set<int> sr;
        set_intersection(RNG(s1), RNG(s2), inserter(sr, sr.end()));
        if(sr.size() > 1) {
            cout << "Case #" << casenum+1 << ": " << "Bad magician!" << endl;
        } else if(sr.size() == 0) {
            cout << "Case #" << casenum+1 << ": " << "Volunteer cheated!" << endl;
        } else {
            cout << "Case #" << casenum+1 << ": " << *sr.begin() << endl;
        }
    }
 
    return 0;
}

Problem B. Cookie Clicker Alpha

ループで回した場合のループ回数を確認するのが面倒だったのでへたれて不等式を解いて一撃にしてしまいました。$$ X/{2+(n+1)F} ≤ C/{2+(n+1)F} + X/{2+(n+2)F} $$ n と n+1 で立式すればよかったんですが、なぜか n+1 と n+2 で立ててしまったので微妙にずれた感じです。一応、累積誤差を考えて数が小さい方から加算するようにしていますが気にしなくても良かったかも。

int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin << cases;
    REP(casenum, cases) {
        long double C, F, X; cin << C << F << X;
        int thr = floor((F*X - 2*C - F*C)/(F*C));
        long double result = 0;
        if(thr <= 0) {
            result += X / (2+(thr+1)*F);
            for(int i : IR(0, thr+1)) {
                result += C / (2 + (thr-i)*F);
            }
        } else {
            result = X / 2;
        }
        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(7) << result << endl;
    }
 
    return 0;
}

Problem C. Minesweeper Master

Cookie Clicker には Orteil does not endorse and has no involvement with Google Code Jam. と書いてあるのに Minesweeper には Microsoft Windows への言及があるのに同様の文言がなかったのは何か意味があるのでしょうか。

DP で解いた人も居るようですが、場合わけでやりました。書いてる時には（コピペ分も多いので）そんなに長く書いたつもりはなかったのですが、結果としては結構長いですね。

全体を貫く考え方としては、（1行、あるいは1列の場合でなければ）空きマスが最低2行あるいは2列繋がっていないと広がらない、です。また、c は必ず左上にしています（一般性を失わない）。最初の場合分けとしては、1行の場合、1列の場合、2行の場合、2列の場合、それ以外（3行3列以上）の場合で分けています。行・列を転置してしまえば場合わけは少なくなりますが、転置するのも面倒なんでコピペベースでいいや、という駄目な手抜きです。

1行あるいは1列の場合は、impossible は無しで右端あるいは下端から詰めるだけ。

2行あるいは2列の場合は爆弾が奇数の場合は基本 impossible ですが、1 マスだけ残っている場合は OK。OK の場合は右端あるいは下端から詰めるだけです。

最後、3行3列以上の場合は、さらに場合わけしています。最低2行あるいは2列必要ということから考えると、1) M ≦ (R-2)*(C-2) の場合は、左端および上端2列分を開けておいて右下から詰めていけば良い 2) R*C-M < 9 の場合、R*C-M = 2, 3, 5, 7 の場合 impossible、それ以外の場合は左上の状態は R*C-M の値に合わせて決め打ち、で良いことが分かります。最後、R*C-M ≧ 9 の場合ですが、空きマス8個分は確定、(2,2) の位置で偶奇を調整して、後は右2列を下から1行(2マス)づつ、上2行を右から1列(2マス)づつ埋めていけば良いことになります。

Short input については全入力パターンが (1+2+3+4+5)^2 = 225 通り、制約の数字から全パターンが入力になってそうってことでローカルで全入力作っといて目視で確認してから subumit してます。時間に余裕のある Qualification Round ならではって感じですね。

void c1(int R, int M)
{
    cout << "c" << endl;
    for(int i: IR(0, R - M - 1)) cout << "." << endl;
    for(int i: IR(0, M)) cout << "*" << endl;
}
 
void r1(int C, int M)
{
    cout << "c";
    for(int i: IR(0, C - M - 1)) cout << ".";
    for(int i: IR(0, M)) cout << "*";
    cout << endl;
}
 
void c2(int R, int M)
{
    if(2*R-M == 1) {
        cout << "c*\n";
        for(int i: IR(0, R - 1)) cout << "**" << endl;
    } else if(M % 2 || 2*R-M == 2) {
        cout << "Impossible" << endl;
    } else {
        cout << "c.\n";
        for(int i: IR(0, R - M/2 - 1)) cout << ".." << endl;
        for(int i: IR(0, M/2)) cout << "**" << endl;
    }
}
 
void r2(int C, int M)
{
    if(2*C-M == 1) {
        cout << "c";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
        cout << "*";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
    } else if(M % 2 || 2*C-M == 2) {
        cout << "Impossible" << endl;
    } else {
        cout << "c";
        for(int i: IR(0, C - M/2 - 1)) cout << ".";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
        cout << ".";
        for(int i: IR(0, C - M/2 - 1)) cout << ".";
        for(int i: IR(0, M/2)) cout << "*";
        cout << endl;
    }
}
 
char result[50][50];
void gen(int R, int C, int M)
{
    for(int i: IR(0,R)) { for(int j: IR(0,C)) { result[i][j] = '*'; } }
    if(R*C - M == 1) { // nothing to do
    } else if(R*C - M == 4) {
        result[0][0] = result[0][1] = result[1][0] = result[1][1] = '.';
    } else if(R*C - M == 6) {
        result[0][0] = result[0][1] = result[1][0] = result[1][1] = result[2][0] = result[2][1] = '.';
    } else if(R*C - M == 8) {
        for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
        result[2][2] = '*';
    } else if(R*C - M < 9) {
        cout << "Impossible" << endl;
        return;
    } else if(M <= (R-2)*(C-2)) {
        for(int i: IR(0,2)) { for(int j: IR(0,C)) { result[i][j] = '.'; } }
        for(int i: IR(0,R)) { for(int j: IR(0,2)) { result[i][j] = '.'; } }
        int MM = (R-2)*(C-2);
        for(int i: IR(2, R)) {
            if(M == MM) break;
            for(int j: IR(2,C)) {
                result[i][j] = '.'; --MM;
                if(M == MM) break;
            }
        }
    } else {
        for(int i: IR(0,3)) { for(int j: IR(0,3)) { result[i][j] = '.'; } }
        int MM = R*C - 9;
        if(((R*C-M) % 2) == 0) {
            result[2][2] = '*'; ++MM;
        }
        for(int i: IR(3, R)) {
            if(M == MM) break;
            for(int j: IR(0, 2)) {
                result[i][j] = '.';
            }
            MM-=2;
        }
        for(int i: IR(3, C)) {
            if(M == MM) break;
            for(int j: IR(0, 2)) {
                result[j][i] = '.';
            }
            MM-=2;
        }
    }
    result[0][0] = 'c';
    for(int i: IR(0,R)) { for(int j: IR(0,C)) { cout << result[i][j]; } cout << endl; }
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        int R, C, M; cin >> R >> C >> M;
        cout << "Case #" << casenum+1 << ":" << endl;
        if(R == 1) { r1(C, M); }
        else if(C == 1) { c1(R, M); }
        else if(R == 2) { r2(C, M); }
        else if(C == 2) { c2(R, M); }
        else { gen(R, C, M); }
    }
 
    return 0;
}

Problem D. Deceitful War

War について Ken の戦略は Naomi の戦略に依らないということなので順序は気にしなくとも良いはず。ということで、Ken としては勝つときには最小の余力(Naomi の値以上で最小のものを出す)で勝ち、負けるときは最小で出すという自然な戦略で良いはずです。では、Deceitful War ではどうなのかといことで、とりあえず最初にできるだけ強いカードを捨てさせて（相手の最大に自分の最小をぶつける）、後は先後逆転で計算する形で書いたら結果が合いません（この時点でなんで先後逆転で計算しようと思ったのか細かいことを忘れちゃってます）。入力例の最後をソートして眺めると、勝ちようがない最小の1枚だけ捨てて後は Naomi が全て勝ってるんですよね。ってことで捨てる枚数でループさせて最大値を取る、で一応結果は合うのですが……。ここで天啓。「あれ？相手のカードも戦略も全部分かってるんだから相手の出すカード全部操作できるんじゃね？」これで先後逆転で一発計算すればいいや、となりました。実際には submit 時点では宣言した値と勝敗が異なってはいけないという条件を忘れていたので考えが足りなかったのですが、Ken の最大値より大きな値を言い続ければ最小から出てくるのでそこで勝ち続けて、勝てなくなるところからは最小値より小さな値を言い続ければやっぱり小さい方から出てきてそこで負ければよい、となるので問題ないことになります(仮に本当にこのまま実際にに人間相手にやったら普通ばれるでしょうけれども)。

int calc_war(const set<double> &naomi, set<double> ken)
{
    int ret = 0;
    for(double i : naomi) {
        auto it = ken.upper_bound(i);
        if(it != ken.end()) {
            ken.erase(it);
        } else {
            ken.erase(ken.begin());
            ++ret;
        }
    }
    return ret;
}
 
int main(void)
{
    ios_base::sync_with_stdio(false);
 
    UI cases; cin >> cases;
    REP(casenum, cases) {
        set<double> naomi, ken;
        int N; cin >> N;
        for(int i: IR(0, N)) { double t; cin >> t; naomi.insert(t); }
        for(int i: IR(0, N)) { double t; cin >> t; ken.insert(t); }
        size_t result_war = calc_war(naomi, ken);
        size_t result_dwar = naomi.size() - calc_war(ken, naomi);;
        cout << "Case #" << casenum+1 << ": " << result_dwar << ' ' << result_war << endl;
    }
 
    return 0;
}

まとめ

TopCoder Open より Google Code Jam の方が相性がいい感じなのですが、なかでも Qualification Round は時間を気にせずに考えたり書けるんで一番楽しいです。本戦考えるとあんまり良くない参加方法ではありますが。今年もどこまでいけるか分かりませんが、Round1 は突破したいなぁ。

EclipseCoder C++ プラグインの拡張

競技プログラミング界の雄 TopCoder では競技環境でプラグインの使用が可能ですが、それを利用して Eclipse 上でコーディングできるようにしてしまおうというのが EclipseCoder です。実際便利ではあるのですが、C++ でやっている場合に特に面倒なのが以下 2 点です。

1. 例えば、Windows 上で VC++ が入っている状態だけど Cygwin GCC を使いたい場合などに、毎回ツールチェインの設定が必要だったりする(環境依存)。
2. C++11 有効にしたりオプション変えるのも毎回設定が必要。

ということで、これらの設定が可能なように C++ プラグインを修正しました。GitHub のリリースページから net.fornwall.eclipsecoder.ccsupport_0.2.5y1.zip をダウンロード、中の net.fornwall.eclipsecoder.ccsupport_0.2.5.jar で Eclipse インストール先フォルダの同名ファイルを上書きしてください。Window -> Preferences -> EclipseCoder -> C++ の設定下側に、コンボボックスが 2 つ増えています。上がツールチェインの設定、下が設定のコピー元プロジェクトです。

設定コピー元プロジェクトについては EclipseCoder で作成されたプロジェクトを元にした方が無難なので、まずはツールチェインについては自分の使用するものを選び(選択必須)、プロジェクトについては空白にしておきます。この状態でいつものように TopCoder に接続、Practice にでも入って問題を開くと新規プロジェクトが作成されます。この時、特に必須ではありませんが作成されたプロジェクトを設定コピー元プロジェクトだと分かるようリネームしておいてもいいかもしれません。このプロジェクトで EclipseCoder でのプロジェクト作成時に適用しておきたい設定を適当に変更します。例えば (Cygwin GCC で) C++11 有効にする場合だと↓の感じになります。

これで再度 Window -> Preferences -> EclipseCoder -> C++ を開いて、今度は下側のコンボボックスで先ほど設定を変更したプロジェクトを選びます。上側コンボボックスで選択しているツールチェインと整合していなかったりすると OK 時にメッセージが表示されて適用できません。SRM 615 Div2 250 で作成したプロジェクトを設定コピー元プロジェクトにした場合、↓のようになります。

後は、普通に問題を開いていくと先ほどの設定コピー元プロジェクトの設定内容が反映されているはずです。注意点として、設定を取得する際にはプロジェクトがオープンされている必要があるため、設定コピー元プロジェクトは必要があればオープンされます。そしてプラグイン側ではクローズしません。毎回オープン・クローズ繰り返すのもどうかな、と思ったのでこういう仕様になっています。

よろしければ使ってみてください。とりあえずしばらくして問題がなさそうであれば upstream に pullreq を出すつもりです。実のところ 1. については pullreq がすでに upstream にマージ済みでリリースバージョンまで更新されているのですが、にも関わらずサイトでリリースされていません。作者さんが忘れているだけなんじゃないかな、という気もしますが、pullreq 出したときに「Java 初心者なんでチェックしてね」みたいなことを書いてしまったので確認するのもなんだかなと思っているうちに 1 年が経ってしまいました。

なお、本プラグインを使用したせいで Eclipse が落ちて rating 下がった等、いかなる結果についても責任を負いかねますのでその辺は承知の上でお願いします。【追記】もし使用されてる方がいらっしゃいましたら「問題なく動いてるよ」でも良いのでコメントを付けて頂けると嬉しいです。pullreq の支えになりますので。

main() のすり替え in C++

[2013/12/18] ptr_umain 経由の呼び出しで引数を付けていなかった点を修正。

ある種のライブラリの場合、main() の呼び出し前に処理をしておきたい場合があります。ものすごく真っ当な方法で言うならスタートアップルーチンを書くべきところではありますが、その場合、ライブラリを使う側でもオプション指定が必要になったりしてちょっと面倒になります。こういう時に、ライブラリ側で main() を定義してしまいユーザーコード側では

// main.h
#define main _umain
#ifdef __cplusplus
extern "C" int _umain(int argc, char **argv);
#else
extern int _umain(); // No specification for parameters in C
#endif

// main.c
#include "main.h"
int main(int argc, char **argv) { /* ... */ } // replaced with _umain

のようにヘッダを読み込ませることによって main() をすり替えてしまい、ライブラリ側の main() からすり替えた _umain() を呼び出す、といったことが行われる場合があります。例えば SDL (http://www.libsdl.org/) なんかはこれを使っているようです。

が、問題が一つ。main() は引数が固定されていません。実用的には、以下の3種類くらいあると考えてよいでしょう。

int main(void);
int main(int argc, char **argv);
int main(int argc, char **argv, char **envp);

C の場合、これでもそんなに問題になりません。すり替え用マクロが有効であるとして、上記コードのように extern int _umain(); としておけば、C 言語では引数に関しては指定がない扱いであり、かつ可変引数関数を実現する C の呼び出し規約上、上記いずれの定義であっても _umain(argc, argc, envp); と呼び出してしまえば、普通の処理系ならまず問題なく動作するはずです。

が、C++ の場合、プロトタイプ宣言が必須であり、また、関数の型チェックが必ず行われます。つまり main() がどの形式で定義されていたかによって呼び分ける必要が出てくるわけです。前述の SDL では main() の型を int main(int, char**) に限定することで回避しているようです。最初から特定ライブラリを使う前提であればそれでもいいのですが、今作成中のライブラリ(UTF-8 Win32 API)は後付けの形での利用を想定しているので限定はちょっとつらいです。

要はユーザーがどの形式で main() を定義したか判別する方法があればいいわけです。そこで(処理系依存ですが) GCC の weak symbol と alias を使用してみました。

int _umain_stub()
{
 return 0;
}

// for C
extern "C" int _umain(...) __attribute__((weak, alias("_Z11_umain_stubv")));
// for C++
extern int _umain() __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc) __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc, char ** argv) __attribute__((weak, alias("_Z11_umain_stubv")));
extern int _umain(int argc, char ** argv, char **envp) __attribute__((weak, alias("_Z11_umain_stubv")));

static int(*ptr_umain)(...)                   = static_cast<int(*)(...)>(_umain);
static int(*ptr_umain0)()                     = static_cast<int(*)()>(_umain);
static int(*ptr_umain1)(int)                  = static_cast<int(*)(int)>(_umain);
static int(*ptr_umain2)(int, char**)          = static_cast<int(*)(int, char**)>(_umain);
static int(*ptr_umain3)(int, char**, char**)  = static_cast<int(*)(int, char**, char**)>(_umain);

template<typename T>
static inline bool is_target(T t)
{
 return t != reinterpret_cast<T>(_umain_stub);
}

int main(int argc, char **argv, char **envp)
{
 if(is_target(ptr_umain))  return ptr_umain(argc, argv, envp);
 if(is_target(ptr_umain0)) return ptr_umain0();
 if(is_target(ptr_umain1)) return ptr_umain1(argc);
 if(is_target(ptr_umain2)) return ptr_umain2(argc, argv);
 if(is_target(ptr_umain3)) return ptr_umain3(argc, argv, envp);
 return -1; // Not reached if main() is user-defined
}

通常、同名の関数定義がある場合、多重定義エラーになります。weak symbol を使うと、他に同名の定義がない場合だけ有効になる定義を作ることができます。デフォルト実装の定義を作っておいて、場合によってはより高速な実装に差し替えることも可能、みたいな使い方が典型的なユースケースです。alias はある関数を別の関数の別名として定義できる機能です。上記コードでは C/C++ の _umain() 系を全て _umain_stub(void) の別名かつ weak symbol としています。ユーザーがある形式の main() を定義した場合、マクロで _umain() にすり替えられていずれかの weak symbol が上書きされます。結果として _umain_stub(void) と値(アドレス)が変わるため、それを is_target() で判別して呼び分けているわけです。

で、話が済んでいれば幸せだったのですが、なぜか StrawberryPerl 5.18.1.1 32bit 中の GCC を使って、↑ main() のあるソースファイルで #include <iostream> や #include <cstdio> すると関数ポインタの値がずれます。Cygwin の i686-w64-ming32-g++ だと問題ありません。両方とも GCC-4.7.3 なんですが。例えば実際のアドレスが、
__Z7_umain_v (ユーザー定義の _umain(void)) -> 0x401560
__Z11_umain_stubv (_umain_stub(void)) -> 0x40195e
である場合に、バイナリ中で参照されるアドレスがそれぞれ、0x40117e, 0x40157c だったりします。両方とも 0x3e2 だけずれています。バグなのか設定がおかしいのかちょっと分かりませんがとりあえず以下のようなコードで無理やり補正すると一応動作はします。ユーザー定義の _umain() と _umain_stub(void) の 2 種類があるだけで、かつ、ユーザー定義は 1 つだけ存在するはず、という前提で多数派が実際には _umain_stub(void) であるとみなしてその差を補正しています。

template<typename T>
static inline unsigned long get_offset(T t)
{
 return reinterpret_cast<unsigned long>(_umain_stub) - reinterpret_cast<unsigned long>(t);
}

template<typename T>
static inline void add_offset(T& t, unsigned long offset)
{
 t = reinterpret_cast<T>(reinterpret_cast<unsigned long>(t) + offset);
}

void fix_fptr()
{
 std::map<unsigned long, int> counter;
 ++counter[get_offset(ptr_umain)];
 ++counter[get_offset(ptr_umain0)];
 ++counter[get_offset(ptr_umain1)];
 ++counter[get_offset(ptr_umain2)];
 ++counter[get_offset(ptr_umain3)];
// assert(counter.size() == 2);
 unsigned long offset = counter.begin()->second > (++(counter.begin()))->second ? counter.begin()->first : (++(counter.begin()))->first;
 add_offset(ptr_umain, offset);
 add_offset(ptr_umain0, offset);
 add_offset(ptr_umain1, offset);
 add_offset(ptr_umain2, offset);
 add_offset(ptr_umain3, offset);
}

ちょっとどうだかなという感じではあるので、とりあえず、#include <iostream> や #include <cstdio> を外して様子見な感じですが謎な状態です。

\L と \U と Perl

Perl スクリプトに文字列を渡すのに

count -t '\t'

のような感じでエスケープを使いたいけれど、Perl コアでそのものの機能は提供されていないということで String-Unescape というモジュールを作成中です。もちろん eval 使えば済むのは分かってるんですけど、文字列 eval はなるたけ避けたいということで。その中でぶつかった(自分的には)驚きの Perl 仕様について書いてみます。

ダブルクウォート内で \Q と \E で囲った範囲の英数アンダーバー以外をエスケープできる(quotemeta がかかる)というのは Perl 使いではそれなりに知られた事実だと思います。

say "\Q[|]\E";
# \[\|\+\]

同様に範囲で効く変換として \L, \U も存在は知っているという方も多いでしょう(最近は \F と言うのもあります)。で、これらは重ねることができると perldoc perlop には書いてあります。

\L, \U, \F, and \Q can stack, in which case you need one \E for each. For example:

 say"This \Qquoting \ubusiness \Uhere isn't quite\E done yet,\E is it?";
# This quoting\ Business\ HERE\ ISN\'T\ QUITE\ done\ yet\, is it?

さて、では問題です。以下はどのように出力されるでしょうか。

say "\Q[A\U[a\L[A\E[a\E[A\E";

正解は \[A\[A\[a\[a[A です。この時点で「は？」って感じですが、続いて第 2 問。

say "\U[a\Q[a\L[A\E[a\E[a\E";

正解は [A\[A[a[a[a です。もう訳がわからないという感じですが、真っ当に追っかける気を無くすコードを感覚で読み取ったところ、\U 中の \L や \L 中の \U があると、その前の \U, \L まで(途中に \Q とかがあればそれも)無効になった後で、新しく \L, \U が有効になるようです。\L や \U が一回しか有効にならないように \E が適宜補われると考えると分かりやすいかもしれません。

say "\Q[A\U[a\L[A\E[a\E[A\E";
say "\Q[A\U[a\E\L[A\E[a\E[A\E"; # 直前の \U が無効
# \[A\[A\[a\[a[A
# \[A\[A\[a\[a[A

say "\U[a\Q[a\L[A\E[a\E[a\E";
say "\U[a\Q[a\E\E\L[A\E[a\E[a\E"; # \U\Q が無効
# [A\[A[a[a[a
# [A\[A[a[a[a

\L...\U...\E...\E ってやっても外側の \L しか効かないから無駄じゃねーか、という意図であろうというのは推測できますが、個人的には「いや、書かれたとおりに実行しろよ」と言いたくなる挙動です。

もう一つ、エスケープ関連でお節介じゃないの？という機能として、\L\u と \U\l をそれぞれ \u\L と \l\U に置き換えるというものがあります。

say "\L\uaAA\E \U\lAaa\E";
# Aaa aAA

\u してから \L したら結局 \L だけじゃねーかってのは分かりますが、「勝手に書き換えるな、警告出せ」と思うわけです。

ちょっと気を利かせたつもりで全体として訳が分からなくなる、というのはある意味とても Perl らしいという気もしますが。元々 String-Unescape は Perl の処理と一致させることを目指そうと思っていたわけですが、この 2 つの挙動(特に前者)は無理して再現する必要はないだろうということで実装しないつもりでいます。