2014年5月29日木曜日

[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

2014年4月15日火曜日

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 は突破したいなぁ。

2014年4月8日火曜日

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 の支えになりますので。

2013年12月17日火曜日

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> を外して様子見な感じですが謎な状態です。

2013年11月22日金曜日

\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 つの挙動(特に前者)は無理して再現する必要はないだろうということで実装しないつもりでいます。

2013年9月26日木曜日

YAPC::Asia Tokyo 2013 参加メモ(二日目)

前稿に引き続き、聴講したトークの雑感を箇条書き的に。

Mojoliciousでつくる!Webアプリ入門 by Yusuke Wada

  • WAF 自作も楽しいけど、そこは本題じゃないんだからとりあえず WAF 使っとくのが良い、と。
  • ライブコーディングでさくっと作られてたのですごい簡単感が伝わってたと思います。
  • 「分けることで分かる」「少しづつやる(ことで俺スゲー感を持続)」俺スゲー感はモチベーション持続に有用ですよ、本当。新しいことやると楽しいんですよね。
  • CCF は WAF 使ってないんですが、特に model がきちっと分かれてないところは次の大改修前には手直ししたいという気になりました。

Programming AWS with Perl by Yasuhiro Horiuchi

  • with Perl 要素少なめ。
  • Python 製 AWS CLI が提供されてるので、Perl での自動処理用にはそれに対する wrapper AWS::CLIWrapper を使えば良いのではないかと、という感じですかね。
  • CLI と API 直叩きモジュールとどちらが良いという質問がありましたが、自動処理用には CLI 経由でいいでしょうけど、アプリ的にはモジュール使用なんじゃないですかね。

What's new in Carton & cpanm by Tatsuhiko Miyagawa

  • もちろん cpanm は使ってますけど Carton は使ってないんですよね。個人の趣味の領域だとそこまで必要性を感じないというか。
  • git URL 可になったのは patch 版指定とかできて嬉しい感じではあるんですけど、Dist::Zilla で github に置くと普通はインストール可にならないんで、その辺どうするのがいいのかな、と思ったりします。

GitHubでつくる、たのしい開発現場 by Hiroki OHTSUKA

  • どっちかっていうと精神よりというか、本来そういうことの方が重要だとは思うんですが、やっぱり具体的なツールとか Tips の方が分かりやすいんですよね。

可視化のためのPerl by Muddy Dixon

  • 可視化には Explanatory (ストーリー説明) と Exploratory (ストーリー探索) の 2 種類がある。
  • マイニング技術者はドメイン知識が少ない v.s. ドメイン専門家はマイニングの知識が少ないので可視化してドメイン専門家に見てもらおう、と。
  • DataCube の開発止まってるじゃんということで、Data::Cube をリリースされたとのことですが、「僕はこの手の処理はRでやります」という衝撃の結末からは、どうせこのモジュールも開発止まるんでしょ?、感が激しくします。

本当にあったレガシーな話 by Daisuke Maki

  • livedoor blog のモダン化について。モダン Perl 入門 増補改訂版 に書かれるそうです。題名は増補改訂版になっていますが 80% 変わっているとのこと。
  • 発表的にはとりあえず mod_perl dis だったと思っておけば大体合ってるんじゃないでしょうか。
  • とにかくログをとることがまず最初。設定切り替えには use constant による定数たたみ込み最適化の利用をすると良い。
  • 他色々あったんですが、$0 変えると ps で見たときに分かるというのは Tips は面白かったです。

スマフォアプリ開発を支える認証認可アーキテクチャ by Rieko Suzuki

  • 執筆記事の著者写真の時点でなんかもう色々と違う気がしましたが「糞アプリ」発言で逆に安心しました。

PhantomJSによる多岐にわたる広告枠の確実な表示テスト by Yusuke Yanbe

  • Selenium::Remote::Driver を使えば headless ブラウザである PhantomJS を操作できるのでそれを使ってテストするという話。

フルテストも50msで終わらせたい 〜 FreakOutの取り組み 〜

  • 最初にさすがに 50ms は無理ですとの潔いお言葉。
  • 一日目の soh335 さんの発表と結構被っていたとのこと。テスト用ユーティリティモジュールも用意されているそうです。
  • 実行順序に依存するテストを避けるために、テスト順序のシャッフルがおすすめとのこと。
  • File::Find, List::MoreUtils, Parallel::ForkManager, Net::OpenSSH, TAP::Harness といった CPAN モジュールを組み合わせて分散実行することで 2,000 秒 over → 180 秒に短縮。
  • CPAN モジュールの組み合わせというのがとても Perl らしくていいですね。
  • 「高速なテストは開発文化を変える」手元でやるより push した方が速いのでとりあえず push する文化に→コードが早期共有されてレビューも進み品質も向上。

LT

とりあえず分かる範囲でメモ。名前が分からない方とかもし抜けてたらすみません。

  • テストカバレッジについて http://coveralls.io/ というサービスがある。
  • DBIx::* の新しいモジュール。
  • makamaka さんの同人活動レポート。
  • HTTP から SMTP 送信ができる Haineko について。
  • Perl 入学式と近所の Perl Mongers のおかげで初心者でも「つぶやいてないでコード書け」というサービスができました!という話。いい LT だったと思います。
  • papix さんの Perl 入学式活動レポート。
  • kamipo さんの mysql-build の話。
  • もっとネタモジュールを!ということで netacpan.org できました。
  • kamadango さんのマイクロコミュニケーションの話。
  • tokuhirom さんの Test::Power っていうか HTTP::Body::Builder 作ったった。
  • mruby_nginx_module について。
  • pjf さんの method add_datapoint( Str: $goal!, Int:$timestamp) みたいに書ける Method::Signatures の紹介。
  • takesako さんの Perl クイズ。近藤嘉雪先生が優勝してました。チート級。識別子が 251 文字以下とかそんな制限あったんですね……

Keynote by Tomohiro Ikebe

  • 「Management and Perl culture」というタイトル。
  • マネージャーで画像検索するとリア充 マネージャーって管理するというより支える方じゃないの?
  • できるエンジニアにできるからマネージャーやれ、は最悪。とはいえチーム内のリーダーシップは必要。
  • 社内に対する広報(エンジニアの仕事が意味のある仕事だってことを伝える)ことも大事。
  • ……そんなに年が変わらないということにちょっとショックを受けました。

YAPC::Asia Tokyo 2013 クロージング by Daisuke Maki

  • 牧さん、櫛井さんのツートップによる YAPC::Asia はこれで終了、とのこと。後を継ぐ人が居ないとこれで終わり、ということなんでしょうか?
  • のべ参加者 1,000 人オーバー。うーむ、すごい。

まとめと余談

  • 今年の YAPC は Perl の話題が多いな、とかいう tweet を見ましたが、確かに Perl 寄りな感じで個人的には嬉しかったです。
  • 本当は今年発表できたらなーと朧気に思っていたのですが(Dist::Zilla の話とか)、Minilla と Milla のトークが応募されてるし、しかも Ricardo SIGNES ご本人来てるしってんで無理ゲーでしたね。LT できたらなーというネタは今年は余裕で間に合わなかったので来年に LT できたらなーと思っています。
  • 今回新しいノート PC (VAIO Pro 13)で参加しました。今まで一台のノート PC をどのシーンでも使い回す感じだったので 2kg 前半まで選択肢に入れていたのですが、重量というよりもバッテリーの持ちからこの手のイベントではちょっときついな、ということでモバイル用として購入。シートバッテリがなかったとしてもイベント中はもってそうでした。重量はあんまり気にしてなかったんですが実際に使ってみると、部屋の移動のときに横に抱えるのも楽だし AC アダプタもなくてそのまま運べるしで良かったと思います。