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