こんなところを見ている人も居ないと思いますが、C++11 Advent Calendar および Boost Advent Calendar を機に http://yak-ex.blogspot.com/ を開設しました。プログラミング、ソフトウェア関連のネタは（どれだけ書くかはともかく）以降そっちに書くと思います。

とりあえず碧の軌跡クリアしたので雑多な感想など。

■総合

プレイ時間 123:15:34。寝落ちや放置も含んでると思いますが。獲得実績 34/56 2250pt。みーしぇのイベントだけ検索かけちゃいましたが他はノーヒント。結構頑張った方じゃないでしょうか。アニエス揃えられたのは嬉しかったですね。

なのですが感想というと、うーん。ラスト絵のところに空の軌跡の時のようにメッセージが出るんですが "Comletedly Finished" になってました。なんか違う。そぅ、クリア後の感想としてもなんか違うというかもっと良くできたんじゃないの？という気が。特に最後、単純に流れを見せられるだけなのはどうかと。同一世界観で話が続いていくのはともかくクロスベルの話としてはきちっとけりをつけてもらわないと。一旦エンドでその後プレイアブルにクロスベル解放してくれれば満足してたような気もします。

■ラストダンジョン

4つの「○の領域」を作る必要があったんでしょうか？作った割にあっさりしすぎかと。作るんだったらもっと各キャラクターの内面を掘り下げるべきだったような気がします。それこそ空の軌跡 the 3rd の扉みたいなものとか。中盤怒濤の展開でリーシャとシャーリィに因縁ができるわけですが双方ともサブキャラクターなわけでその後にもうちょっと何かが欲しかったと思います。リーシャの好感度が上がってるとイベントがあったのかもしれませんけど(エリィonlyプレイでした)。

もう一つ。Falcom さんはリアリティよりプレイアビリティを優先する、という方針なんじゃないかな、と思っています。ラストダンジョンでも途中でメルカバまで戻りやすくなってるというのはその顕れかな、と。ただメルカバ自体での移動までできるのはやり過ぎだったんじゃないでしょうか。せっかく突破イベントやってるくらいなんですからラストダンジョン入ったらもう戻れないくらいの方が緊張感があって良かったんじゃないかと思います。

後、最終盤の戦闘は相変わらず長かったですね。それも単純に長けりゃいいって思ってるわけじゃないですよね？とちょっと疑念を抱くような感じで。

■マスターアーツ

使いまくっておきながらなんですが、慈愛のルーンさんまじチート。防御系だと回数なのですぐ消えたりしてタイミングを計る必要がありますが継続効果があるというのが大きいですね。しかも終了して即時開始すれば HP50% 回復も選択可能です。ということで終盤の回復ポイント後の戦闘では使いまくってました。以前はアーツによる完全防御(アースウォールとかアダマスガード)は封じ手にしてたんですけどね。グラールスフィアとかは使ってましたが。まぁ何らかの手段を講じないと一撃死するのでもうしょうがないという感じです。

■その他

・誤字、脱字

これだけのテキスト量があれば誤字・脱字くらいあるでしょうが前作よりかなり気になりました。

・改善

「情報」で見えてる情報なのか色で分かるようになってたり、一部特殊クォーツが全体に効くようになってたり、インテリア揃えるとイベント発生したり細かい改善がされててプレイ当初感心してました。

Twitter 上で C++ STL の vector に関して評価順序不定ではまっているコードの例が流れていてそこから C 言語における(規格上の)落とし穴に行き着いたのでメモ。

// from http://www.jpcert.or.jp/sc-rules/c-exp35-c.html
#include <stdio.h>

struct X { char a[6]; };

struct X addressee(void) {
  struct X result = { "world" };
  return result;
}

int main(void) {
  printf("Hello, %s!\n", addressee().a);
  return 0;
}

上記コードは C++ では問題ないコードであるが、一方 C99 では未定義動作を含むコードである。理由はJPCERT のページに記述されているが、

一時オブジェクトの生存期間(という説明は C の規格上はされていないが)が次の副作用完了点までだと規定されているからである。この場合 printf 呼び出しの「前」が次の副作用完了点になる。

9899:1999 6.5.2.2 Function calls / 5
(snip) If an attempt is made to modify the result of a function call or to access it after the next sequence point, the behavior is undefined.

一方 C++ では full-expression の最後まで、と規定されているため printf 呼び出し「後」、となり問題がない。

14882:2003 12.2 Temporary objects / 3
(snip) Temporary objects are destroyed as the last step in evaluating the full-expression (1.9) that (lexically) contains the point where they were created. This is true even if that evaluation ends in throwing an exception.

この点は標準化委員会でも認識されている(Lifetime of temporaries)。この文書ではさらに嫌らしい例が挙げられていて

int f()
{
    return 'i';
}

int main()
{
    printf("%c%c!\n", salutation().a[0], f());
    return 0;
}

salutation() と a[0] の間に f() 呼び出しという副作用完了点が入るかもしれないというものである。

これに対して修正提案がされており(Extending the lifetime of temporary objects)、DIS(n1570) では以下のような少々無理矢理感がある記述となっている。

n1570 6.2.4 Storage durations of objects / 8
A non-lvalue expression with structure or union type, where the structure or union contains a member with array type (including, recursively, members of all contained structures and unions) refers to an object with automatic storage duration and temporary lifetime. Its lifetime begins when the expression is evaluated and its initial value is the value of the expression. Its lifetime ends when the evaluation of the containing full expression or full declarator ends. Any attempt to modify an object with temporary lifetime results in undefined behavior.

さて、もう一点補足しておくと、JPCERT のページでは gcc で -std=c99 オプションなしだと落ちるとの記述があるが実はこの問題のせいで落ちているわけではない(未定義動作であることに変わりはないが)。-Wallで出る警告も

eval.c:11: warning: format '%s' expects type 'char *', but argument 2 has type 'char[6]'

と書式指定文字列の不一致に対する警告である。これは配列がポインタに decay されずにそのまま配列として渡されているからだ(6 バイトスタックに積まれている)。この挙動は GCC マニュアルの 6.22 Non-Lvalue Arrays May Have Subscripts にも簡単に記述されている。C99 では右辺値の配列もポインタに decay されるが C89 では左辺値の配列のみに限定されている(らしい。C89 は規格を持っていないので引用できない)。ということで C99 に対応していないはずの VC ではコンパイルされないという挙動が正しいはずである。実際に Comeau C++ では C89/90 モードではコンパイルできずに(error: invalid use of non-lvalue array) C99 モードならばコンパイルできる。

ooo-o--- で 39pts 594 位。Round 2 は通過ならず。仕方ないというか大健闘と言っていい感じかと。初の T シャツゲットです、多分。とりあえず small 専業と割り切ったのはレベル相応で悪くない判断だったと思っています。B-large、C-large、D-small は解けても良かったかもと思わないでもないですが、バグ無しで思ったコードをさくっと書けないというコーディング力や、練習が足りないという点も含めてやっぱり実力がちょっと足りなかったと思います。なお、以下は Contest Analysis を読まない状態で書いています。

A. Airport Walkways

速度が遅いところから greedy に t 秒とっていけばいいだけ。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        UI x, s, r, t, n; cin >> x >> s >> r >> t >> n;
        vector<UI> len(n), speed(n);
        UI len0 = x;
        REP(i, n) {
            UI     b, e, w; cin >> b >> e >> w;
            len[i] = e - b;
            speed[i] = s + w;
            len0 -= len[i];
        }
        if(len0) {
            len.push_back(len0);
            speed.push_back(s);
        }
        vector<UI> index(len.size()); iota(RNG(index), 0);
        sort(RNG(index), [&](UI i1, UI i2) { return speed[i1] < speed[i2]; });
        double tt = t, result = 0;
        REP(i, index.size()) {
            UI ii = index[i];
            UI leni = len[ii], speedi = speed[ii];
//cerr << i << ':' << result << ':' << leni << ':' << speedi << endl;
            if(tt > 0) {
                double speed_ = speedi + (r - s);
                if(leni / speed_ >= tt) {
                    result += tt + (leni - tt * speed_) / speedi;
                    tt = 0;
                } else {
                    result += leni / speed_;
                    tt -= leni / speed_;
                }
            } else {
                result += double(leni)/speedi;
            }
        }

        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(12) << result << endl;
    }

    return 0;
}

B. Spinning Blade

small 専用で割り切ってループでぶん回しています。large は和の取り方を工夫するんだろうなぁと思いつつスキップ。ちゃんと復習しておきたい問題です。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI r, c, d; cin >> r >> c >> d;
        vector<vector<UI>> table(r, vector<UI>(c, d));
        for(auto &v1 : table) {
            string s; cin >> s;
            REP(i, c) {
                v1[i] += (s[i] - '0');
            }
        }
        UI k = min(r,c); bool flag = false;
        while(k >= 3) {
            REP(i, r-k+1) {
                REP(j, c-k+1) {
                    ULL sx = 0;
                    ULL sy = 0;
                    ULL sum = 0;
                    REP(ii, k) {
                        REP(jj, k) {
                            if((ii == 0 || ii == k - 1) && (jj == 0 || jj == k - 1)) continue;
                            sx += ii * table[i+ii][j+jj];
                            sy += jj * table[i+ii][j+jj];
                            sum += table[i+ii][j+jj];
                        }
                    }
//cerr << k << ':' << sx << ':' << sy << ':' << sum << endl;
                    if(2 * sx == (k-1)*sum && 2*sy == (k-1)*sum) {
                        flag = true;
                        break;
                    }
                }
                if(flag) break;
            }
            if(flag) break;
            --k;
        }

        if(k >= 3) {
            cout << "Case #" << casenum+1 << ": " << k << endl;
        } else {
            cout << "Case #" << casenum+1 << ": IMPOSSIBLE" << endl;
        }
    }

    return 0;
}

C. Expensive Dinner

small だけとはいえ、これが解けたのは嬉しかったですね。題意から費用そのものは単調非減少、その約数(通せる番号)の数も単調非減少になります。また最終的な費用は N 以下の全ての数字の最小公倍数になることが分かります。ということで最小回数の時はできるだけ早く最小公倍数までに増加(＝約数の数を増やす)させ最大回数の時はできるだけ遅く最小公倍数までに増加させればいいわけです。こう考えると最小回数の場合は、2^l、3^m、5^n、7^o、…(l、m、n、o、… は N 以下になる最大値)という順に通していけばいいことになります。つまり N 以下の素数の個数が回数になります。一方最大回数の場合は 1、2、2^2、…、2^l、3、3^2、…、3^m、… と通していけば 1 個ずつ素因数が増えるので最も遅い場合になります。以下のコードでは 1 ～ N まで愚直に回して指数の最大値を求めていますが、素数についてループを回して N 以下になる最大指数を求めるべきですね。

large については 10^12 が厳しい条件なわけですが、sqrt(N) より大きな素数の場合、指数が 1 となり最大回数の場合でも最小回数の場合でも 1 回としか数えられないので最大回数-最小回数を求める今回の場合は完全に無視できる、つまり sqrt(10^12) = 10^6 まで調べるだけで OK ということになります。@uwitenpen さんの tweet を見て初めて気付いたので時間中には思いつけなかったと思います。

template<typename T, typename OutputIterator>
inline T pshieve(T n, OutputIterator out) // type should be changable
{
    T count = 0;
    if(n<2) return count;
    *out++=2;
    ++count;
    std::vector<bool> v(n/2);
    const T nn1 = static_cast<T>(std::sqrt(n));
    const T nn = max(nn1, n/nn1);
    T i;
    for(i=3;i<=nn;i+=2) {
        if(v[i/2-1]==false) {
            *out++=i;
            ++count;
        }
        for(T j=i+i+i;j<=n;j+=i+i) {
            v[j/2-1]=true;
        }
    }
    for(;i<=n;i+=2) {
        if(v[i/2-1]==false) {
            *out++=i;
            ++count;
        }
    }
    return count;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    vector<ULL> primes;
    pshieve(1000ULL, back_inserter(primes));

    UI cases; cin >> cases;
    REP(casenum, cases) {

        ULL n; cin >> n;
        vector<ULL> counts(primes.size());
        REPV(ULL, i, n) {
            ULL ii = i+1;
            REPV(ULL, j, primes.size()) {
                ULL count = 0;
                while(ii % primes[j] == 0ULL) {
                    ii /= primes[j];
                    ++count;
                }
                if(counts[j] < count) counts[j] = count;
            }
        }
        ULL minimum = count_if(RNG(counts), [&](ULL v) { return v > 0; });
        ULL maximum = (n>1ULL?1ULL:0ULL) + accumulate(RNG(counts), 0ULL);

        cout << "Case #" << casenum+1 << ": " << maximum - minimum << endl;
    }

    return 0;
}

D. A.I. War

時間中に書いていたコードは BFS ですがデバッグしている途中で終わりました。色々と無駄が多く直したところで結局 TLE します(上のコード)。s.c[0] = true; の代わりに s.c[0] == true; と書いていたのがバグだったのですが、これ、警告が出ません。こういう場合、大抵は式の値を使っていないとかいう警告が出るのですが、vector<bool> のため値を参照するだけで色々と処理が発生しているので警告が出ないのだと思われます。vector<bool> さんはマジ鬼門。当初 bitset 使おうかとも思ったのですが使い慣れてないので逃げました。というか、36 だから 32 ビット超えてるし、と思ってしまったのですが unsigned long long は 64 ビットなので普通にビットフラグで持てるんですよね。さらに threaten な範囲は毎回調べる必要はない、というのを修正したのが下のコードでこれで small は通ります。

struct St
{
    vector<bool> c;
    vector<bool> t;
};
bool operator<(const St& s1, const St &s2)
{
    return s1.c < s2.c || s1.c == s2.c && s1.t < s2.t;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI p, w; cin >> p >> w;
        vector<vector<char> > mat(p, vector<char>(p, 0));
        REP(i, w) {
            int x, y; char c; cin >> x >> c >> y;
            mat[x][y] = mat[y][x] = 1;
        }

        set<St> st, st_;
        St s;
        s.c = vector<bool>(p, false);
        s.t = vector<bool>(p, false);
        s.c[0] = true;
        REP(i, p) {
            if(mat[0][i]) s.t[i] = true;
        }
        auto check = [&](const St& ss)->bool { return ss.t[1]; };
        st.insert(s);

        UI c = p, t = 0; bool flag = false; UI cur = 1;
        while(1) {
            if(cur > p) break;
//cerr << st.size() << endl;
            for(auto &v : st) {
                if(check(v)) {
                    flag = true;
                    if(c > cur || c == cur && count(RNG(v.t), true) > t) {
                        c = cur;
                        t = count(RNG(v.t), true);
                    }
                } else {
//cerr << "TH1" << endl;
                    REP(i, p) {
                        if(v.c[i] == false) continue;
//cerr << "TH2" << endl;
                        REP(j, p) {
                            if(mat[i][j] && v.c[j] == false) {
//cerr << "TH3" << endl;
                                St temp = { v.c, vector<bool>(p, false) };
                                temp.c[j] = true;
                                REP(ii, p) {
                                    if(temp.c[ii]) {
                                        REP(jj, p) {
                                            if(mat[ii][jj] && temp.c[jj] == false) {
                                                temp.t[jj] = true;
                                            }
                                        }
                                    }
                                }
                                st_.insert(temp);
                            }
                        }
                    }
                }
            }
            if(flag) break;
            swap(st, st_);
            ++cur;
        }

        cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
    }

    return 0;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI p, w; cin >> p >> w;
        vector<vector<char> > mat(p, vector<char>(p, 0));
        REP(i, w) {
            int x, y; char c; cin >> x >> c >> y;
            mat[x][y] = mat[y][x] = 1;
        }

        ULL checker = 0;
        REP(i, p) {
            if(mat[1][i]) checker |= (1ULL << i);
        }

        set<ULL> st, st_;
        ULL s = 1ULL;
        auto check = [&](ULL ss)->bool { return ss & checker; };
        auto th = [&](ULL ss)->UI {
            ULL t = 0; int count = 0;
            REP(i, p) {
                if(((ss >> i) & 1ULL) == 0) continue;
                REP(j, p) {
                    if(mat[i][j] && ((ss >> j) & 1ULL) == 0 && ((t >> j) & 1ULL) == 0) {
                        t |= (1ULL << j);
                        ++count;
                    }
                }
            }
            return count;
        };
        st.insert(s);

        UI c = p, t = 0; bool flag = false; UI cur = 1;
        while(1) {
            if(cur > p) break;
//cerr << st.size() << endl;
            for(auto &v : st) {
                if(check(v)) {
                    flag = true;
                    if(c > cur || c == cur && th(v) > t) {
                        c = cur;
                        t = th(v);
                    }
                } else {
//cerr << "TH1" << endl;
                    REP(i, p) {
                        if(((v >> i) & 1ULL) == 0) continue;
//cerr << "TH2" << endl;
                        REP(j, p) {
                            if(mat[i][j] && ((v >> j) & 1ULL) == 0) {
//cerr << "TH3" << endl;
                                ULL temp = v;
                                temp |= (1ULL << j);
                                st_.insert(temp);
                            }
                        }
                    }
                }
            }
            if(flag) break;
            swap(st, st_);
            ++cur;
        }

        cout << "Case #" << casenum+1 << ": " << c-1 << ' ' << t << endl;
    }

    return 0;
}

まとめ

2008 は Round2 661 位で通過、Round3 885 位、2009 は Round1 で落ち、2010 は Round2 1005 位と評価に困る所ではありますが 2008 はまぐれとするとちょっとずつ向上という言い方もできるかもしれません。反省的には、毎回コーディング力と練習が足りない、ばっかり言っている気がしますが、事実だからしょうがないというか。

テンプレ

// Using C++0x mode in g++ 4.6.0

#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/
// I used 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

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 boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

きっと誰かやってるだろうと思いつつ書いてみたら案の定 @iorate さんが直近で同様の事をやっているわけだが折角なので晒してみる。

https://gist.github.com/1000596

動作確認したのは g++ 4.3.4 と g++ 4.6.0。VC10 は Variadic templates が使えないのでパス。@iorate さんのを見ればどこ直せば対応できるかは分かるけど。違いとしては一応 CV 修飾子(要素の型だけでなく tuple 自体についてる場合についても)と参照型について手当をしているけど、参照型については C++0x で reference to reference が大丈夫になったので何も考えずに tuple_element<I, tuple_type> & で大丈夫かもしれない(左辺値参照の範囲では)。

こういうのを自分で書いてみるというのもやっぱり勉強になって、型のテスト用に MPL 使ったけどメタ関数周りが色々と理解が足りなかったのを再認識した。さらに基本中の基本だろうけど、const tuple<int&> な t があったとして get<0>(t) の型は const int& ではなく int& だというのも再認識。

int n;
struct A {
  int &r;
  int *p;
};
const A a = { n, &n };

が有った時に a.r = 5; が可能というのと同じで、一瞬あれ？っと思うのだが *(a.p) = 5; が可能であることと同じである。つまり、ポインタ自体が const なのであって指している先が const ではない。参照は指し先が変えられないので最初から const みたいなものではあるが。

なんとか R1B 枠で通過しました。

R1A Problem A. FreeCell Statistics

数学。結構悩んでました。辿りついた考え方は次の通り。その日の勝利数/その日の試合数=PD/100⇔100×その日の勝利数=PD×その日の試合数となるのでPD×その日の試合数は100=2^2*5^2の倍数になる必要があります。PD と 100 の公約数を調べてその数で 100 を割ってやるとその日の試合数の最低値 nn が出ます。これが n より大きい場合、条件を満たすことは不可能です。なお↓のコードだと PD = 0 のケースを特別扱いしていませんがたまたまうまく行っているだけ(ちゃんと nn = 1 になります)でそこまで考えていたわけではないです。次にその日の試合数が nn だった場合のその日の勝利数 w を求めています。PG = 100 の場合、全て勝利である必要があり、PG = 0 の場合、勝利数 0 である必要があります。PG が 0 でも 100 でもない場合、PG / 100 の分母・分子にものすごく大きい数をかけてやれば (w + k) / (nn + l) (但し 0 ≦ k ≦ l, k はその日以外の勝利数、l はその日以外の試合数) で k, l を適当に設定して合わせることが必ずできます。ということで判断しているのですが、実際には w を求めなくても、PD = 0 か PD = 100 で判断すればいいだけですね。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        ULL n, pd, pg; cin >> n >> pd >> pg;
        string s;

        if(pd == 0) {
            if(pg != 100) s = "Possible";
            else s = "Broken";
        } else {
            ULL d2 = 0, d5 = 0, pd_ = pd;
            if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
            if(pd_ % 2 == 0) { ++d2; pd_ /= 2; }
            if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }
            if(pd_ % 5 == 0) { ++d5; pd_ /= 5; }

            ULL nn = 1 * (d2 == 2 ? 1 : d2 == 1 ? 2 : 4) * (d5 == 2 ? 1 : d5 == 1 ? 5 : 25);
//cerr << "nn: " << nn << endl;
            if(nn > n) {
                s = "Broken";
            } else {
                ULL w = pd * nn / 100;
//cerr << "w: " << w << endl;
                if(w != 0 && pg == 0) s = "Broken";
                else {
                    if(w != nn && pg == 100) { s = "Broken"; }
                    else { s = "Possible"; }
                }
            }
        }

        cout << "Case #" << casenum+1 << ": " << s << endl;
    }

    return 0;
}

R1A Problem B. The Killer Word

シミュレーション的に実装しようとしてごりごり書いていてぎりぎりの時間くらいでコンパイルが通るようにはなったのですがロジックが間違っていました。文字候補リスト上で最後に確定される単語を返すように書いていて、明らかに使われない文字候補はスキップしてポイントが入らない、という点が抜けていました。全単語についてポイントを計算して最大値になる単語を返すよう修正すると通りました。Large についても手元の環境では 4 分くらいで実行できています。

実装的にはデータ構造をどうしようかで multimap とふらついたりして時間をロスしてしまいました。基本的には区別できない単語群を set として持って区別できるようになったら分割していく、1 つになったらそこで終了、という処理になっています。contest analysis で記述されているのもこれと同じような方法のようですね。Union-find の逆、みたいなイメージなのですがこれを効率的に実装できるデータ構造とかあるんでしょうか？各単語10文字以下なので単語中の各文字の使用位置をビットフラグで持って高速化しています。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {
        UL n,m; cin >> n >> m;
        vector<string> dic(n); for(auto &v : dic) { cin >> v; }
        vector<vector<UL>> len(10);
        REP(i, n) {
            len[dic[i].size()-1].push_back(i);
        }
        vector<vector<UL>> pos(n, vector<UL>(26));
        REP(i, n) {
            REP(j, 26) {
                UL temp = 0;
                REP(k, dic[i].size()) {
                    if(dic[i][k] == 'a' + j) temp |=  (1U << k);
                }
                pos[i][j] = temp;
            }
        }

        vector<string> result;
        REP(i, m) {
            string l; cin >> l;
            vector<UL> temp(n); iota(RNG(temp), 0);
            set<UL> candidate(RNG(temp));
            map<UL, UL> group, newgroup;

            UL gidx = 0;
            for(auto &v1 : len) {
                for(auto &v2 : v1) {
                    group.insert(make_pair(v2, gidx));
                }
                ++gidx;
            }

            vector<UL> points(n);
            for(auto &ch : l) {
                map<pair<UL, UL>, set<UL> > check;
                vector<UL> gflag(gidx);
                for(auto &v : candidate) {
//cerr << v << ':' << group[v] << ':' << pos[v][ch - 'a'] << endl;
                    check[make_pair(group[v], pos[v][ch - 'a'])].insert(v);
                    gflag[group[v]] |= pos[v][ch - 'a'] != 0;
                }
                for(auto &v : candidate) {
                    if(gflag[group[v]] && pos[v][ch - 'a'] == 0) ++points[v];
                }
                gidx = 0;
                set<UL> removed;
                for(auto &v : check) {
                    if(v.second.size() == 1) {
                        removed.insert(*v.second.begin());
                    } else {
                        for(auto &v2 : v.second) {
                            newgroup.insert(make_pair(v2, gidx));
                        }
                        ++gidx;
                    }
                }
                for(auto &v : removed) { candidate.erase(v); }
                swap(group, newgroup); newgroup.clear();
            }
            result.push_back(dic[max_element(RNG(points)) - points.begin()]);
        }

        cout << "Case #" << casenum+1 << ':';
        REP(i, m) {
            cout << ' ' << result[i];
        }
        cout << endl;
    }

    return 0;
}

R1A Problem C. Pseudominion

未着手

R1A まとめ

Qualification がゆるゆるだったのでその流れで行くのかと思ったらいきなり頬はったかれたかのような感じでした。コンディション的に寝不足でへろへろのひどい状態で、B のコード書いてる間に訳が分からなくなることもしばしば。最終的には A-Small、A-Large の 20 pts 1257 位で通過ならず。ただ B の基本方針は外れておらずボーダー的にも近いところではあったので R1B で通過できるんじゃないかな、という希望は残りました。

R1B Problem A. RPI

やるだけ。OWP が正しく解釈できたかどうかにかかっている気がします。ある意味英語ゲー。Large にしても計算量的に問題になるところもないでしょう。R1A 出た人の中にはこれでいいのか、と深読みしちゃった人も居るんじゃないでしょうか。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UL n; cin >> n;
        vector<string> table(n); for(auto &v : table) { cin >> v; }
        vector<long double> wp(n), owp(n), oowp(n);
        REP(i, n) {
            int num = 0, won = 0;
            REP(j, n) {
                if(table[i][j] == '1') {
                    ++num; ++won;
                    int num2 = 0, won2 = 0;
                    REP(k, n) {
                        if(i != k) {
                            if(table[k][j] == '0') { ++num2; ++won2; }
                            else if(table[k][j] == '1') { ++num2; }
                        }
                    }
                    owp[i] += (long double)won2/num2;
                }else if(table[i][j] == '0') {
                    ++num;
                    int num2 = 0, won2 = 0;
                    REP(k, n) {
                        if(i != k) {
                            if(table[k][j] == '0') { ++num2; ++won2; }
                            else if(table[k][j] == '1') { ++num2; }
                        }
                    }
                    owp[i] += (long double)won2/num2;
                }
            }
            wp[i] = (long double)won/num;
            owp[i] /= num;
        }
        REP(i, n) {
            int num = 0;
            REP(j, n) {
                if(table[i][j] != '.') {
                    ++num;
                    oowp[i] += owp[j];
                }
            }
            oowp[i] /= num;
        }

        cout << "Case #" << casenum+1 << ":" << endl;
        REP(i, n) {
            cout << fixed << setprecision(12) << 0.25*wp[i]+0.5*owp[i]+0.25*oowp[i] << endl;
        }
    }

    return 0;
}

R1B Problem B. Revenge of the Hot Dogs

これも結構考えてました。当初はある位置での点の個数を n として必要な幅は (n-1)*d。左右に振り分けてこれがぶつからないグループに分けてグループ毎に計算すればいける？みたいなことを考えていましたが玉突き的にぶつかっていくケースがあるので独立に計算できないことに気づき考え込んでしまいました。で降ってきたのが光円錐のイメージ(光である必要は全然ないのですが)。速度は 1m/s で決まっているのである時刻 t のとき、ある位置を起点にした点群が移動可能な範囲は決まってしまいます。逆にこの範囲内なら自由に移動可能です。基本的にはこれが (n-1)*d の幅を持てばいいわけです。隣とぶつかるケースがあるのでその分だけ移動可能な範囲を制限してやるとある時刻 t で条件を満たすか判定できます。ということで二分探索で解くことが可能です。これに気付いた時にはキターって感じになりました。

実際には B-Large に落ちました。提出しようとするときに絶対誤差だけ見てループを回していて無限ループしていたのを相対誤差も見るようにして(8分以内に)直して提出したのですがそれでも落ちました。原因は check() の中の wall の初期値です。二分探索の初期値を大きくした分、この初期値も絶対値的に大きな値に変更する必要がありました。意味的には -inf なので -numeric_limits::max() にしておくべきだったかもしれません。浮動小数点に対する numeric_limits の意味ってどうだったっけ？というのがあって即値で書いてしまいました。

題意を満たすだけなら絶対誤差と相対誤差の両方が閾値を越えている(r - l > diff && (r -l) / r > diff)間 回せばいいのですが、出力結果的に切りが悪い数値が出るので固定回数回す分も入れた形になっています。こうするぐらいなら単に固定回数回してしまえばいいでしょうけど。

bool check(long double time, vector<LL> &pos, vector<LL> &num, UI d)
{
    long double wall = -1.0e+20;
    REP(i, pos.size()) {
        if(pos[i] + time - max(wall, pos[i] - time) < (num[i]-1) * d) return false;
        wall = max(wall, pos[i] - time) + num[i] * d;
    }
    return true;
}

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI cases; cin >> cases;
    REP(casenum, cases) {

        UI c, d; cin >> c >> d;
        vector<LL> pos(c);
        vector<LL> num(c);
        REP(i, c) {
            cin >> pos[i] >> num[i];
        }
        const long double diff = 0.000000001;
        long double l = 0, r = 1.0e+13, cent;
        int i = 0;
        while(r - l > diff && ++i < 1000) {
            cent = (l+r)/2;
//            cerr << l << ' ' << cent << ' ' << r << endl;
            if(check(cent, pos, num, d)) {
                r = cent;
            } else {
                l = cent;
            }
        }

        cout << "Case #" << casenum+1 << ": " << fixed << setprecision(8) << cent << endl;
    }

    return 0;
}

R1B Problem C. House of Kittens

分割された各部屋の最小頂点数が答えになる、というのまでは当たりづけ。ただしこれもすぐに OK という話ではなくて隣接している部屋で共有するのは 2 点のみ、隣接している部屋を辿って同じ部屋に再び戻ってくることはない(言い換えると双対グラフが閉路を持たず木になっている)ため色の塗り分けを(双対グラフの葉側で)調整できて 4 頂点なのに 3 色でしか塗れない、といった状態が発生しないから、とまで考えての結果です。実は双対グラフどうこうも後付けで最初からそう考えられていれば多角形内部に点がないから双対グラフに閉路なくて当然だよね、という話でした。

で、各部屋をどうやって確認しようかということで自前で頑張ってコードを書こうかとしたのですがそこではたと気づきました。「これ、Google Code Jam じゃん」　そう、外部ライブラリが使用可能なわけです。ということで Boost Graph を確認すると正にそういう目的の関数 planar_face_traversal() がありました。これを使って色数を出力するところまではできたのですが、色分けまでできませんでした。planar embedding とか知らなかったので最初から BGL 使おうとしても辿り着けなかった可能性は高いです。しかも色塗りのコードで色々と思い違いをして試行錯誤しました。以下のコードでは双対グラフ(前述のように木になる)上を辿りつつ、最初は出来る限り色を使いつつ全色使った後は辺の両端が異なる色になるようにして塗っています。結局 contest analysis の方法に辿り着いた、という形でしょうか。

template<typename Graph>
struct dual_graph_visitor : public planar_face_traversal_visitor
{
    typedef typename graph_traits<Graph>::vertex_descriptor Vertex;
    typedef typename graph_traits<Graph>::edge_descriptor Edge;

    void begin_face() {
        vertices.push_back(vector<Vertex>());
        edges.push_back(vector<Edge>());
    }
    void end_face() { }

    void next_vertex(Vertex v)
    {
        vertices.back().push_back(v);
    }
    void next_edge(Edge e)
    {
        edges.back().push_back(e);
        links[e].push_back(edges.size()-1);
    }

    vector<vector<Vertex>> vertices;
    vector<vector<Edge>> edges;
    map<Edge, vector<UI>> links;
};

template<typename T>
T absdiff(T a, T b) { return a > b ? a - b : b - a; }

int main(void)
{
    ios_base::sync_with_stdio(false);

    typedef adjacency_list
        < vecS,
          vecS,
          undirectedS,
          property<vertex_index_t, int>,
          property<edge_index_t, int>
        >
        graph;
    typedef graph_traits<graph>::vertex_descriptor Vertex;
    typedef graph_traits<graph>::vertex_iterator VIterator;
    typedef graph_traits<graph>::edge_descriptor Edge;

    UI cases; cin >> cases;
    REP(casenum, cases) {
        int n, m; cin >> n >> m;

        vector<int> u(m), v(m);
        for(auto &val : u) { cin >> val; --val; }
        for(auto &val : v) { cin >> val; --val; }

        graph g(n);
        REP(i, m) {
            add_edge(u[i], v[i], g);
        }
        REP(i, n) {
            add_edge(i, (i+1)% n, g);
        }

        property_map<graph, edge_index_t>::type e_index = get(edge_index, g);
        graph_traits<graph>::edges_size_type edge_count = 0;
        graph_traits<graph>::edge_iterator ei, ei_end;
        for(tie(ei, ei_end) = edges(g); ei != ei_end; ++ei)
            put(e_index, *ei, edge_count++);

        typedef std::vector< Edge > vec_t;
        std::vector<vec_t> embedding(num_vertices(g));
        int idx = 0;
        VIterator vi, vi_end;
        for(tie(vi, vi_end) = vertices(g); vi != vi_end; ++vi) {
            auto p = out_edges(*vi, g);
            embedding[idx].assign(p.first, p.second);
            sort(RNG(embedding[idx]), [&](Edge e1, Edge e2) { return target(e1, g) < target(e2, g); });
            ++idx;
        }

        dual_graph_visitor<graph> v_vis;
        planar_face_traversal(g, &embedding[0], v_vis);

        auto it = find_if(RNG(v_vis.vertices), [&](vector<Vertex> &v) { return v.size() == n; });
        if(it == v_vis.vertices.end()) cerr << "Not found" << endl;
        for(auto &v : v_vis.edges[it - v_vis.vertices.begin()]) {
            v_vis.links[v].push_back(0); // 0 is dummy
        }
        for(auto it = v_vis.links.begin(); it != v_vis.links.end();) {
            if(it->second.size() == 3) {
                v_vis.links.erase(it++);
            } else ++it;
        }
        v_vis.edges.erase(v_vis.edges.begin() + (it - v_vis.vertices.begin()));
        v_vis.vertices.erase(it);

        vector<UI> sizes(v_vis.vertices.size());
        transform(RNG(v_vis.vertices), sizes.begin(), [](vector<Vertex>&s) { return s.size(); });
        int colors = *min_element(RNG(sizes));

        vector<int> color(n);
        vector<bool> visited(v_vis.edges.size());

        function<void(UI)> traverse = [&](UI face) {
            if(visited[face]) return;
            visited[face] = true;
            vector<bool> used(colors);
            auto colorize = [&](Vertex v, int idx) {
                if(color[v] != 0) return;
                REP(j, colors) {
                    if(!used[j]) {
                        color[v] = j+1;
                        used[j] = true;
                        break;
                    }
                }
                if(color[v] == 0) {
                    int vn = v_vis.vertices[face].size();
                    int c1 = color[v_vis.vertices[face][(idx+1)%vn]];
                    int c2 = color[v_vis.vertices[face][(idx+vn-1)%vn]];
                    if(c1 > c2) swap(c1, c2);
                    color[v] = c2 <= 2 ? c2 + 1 : c1 <= 1 ? 2 : 1;
                }
            };
            for(auto vertex : v_vis.vertices[face]) {
                if(color[vertex] != 0) used[color[vertex]-1] = true;
            }
         REP(i, v_vis.vertices[face].size()) {
              colorize(v_vis.vertices[face][i], i);
         }
            for(auto edge : v_vis.edges[face]) {
                if(v_vis.links.count(edge)) {
                    if(v_vis.links[edge][0] == face) {
                        traverse(v_vis.links[edge][1]);
                    } else {
                        traverse(v_vis.links[edge][0]);
                    }
                }
            }
        };
        traverse(0);

        cout << "Case #" << casenum+1 << ": " << colors << endl;
        REP(i, n) {
            if(i != 0) cout << ' ';
            cout << color[i];
        }
        cout << endl;
    }

    return 0;
}

R1B まとめ

A-Small、A-Large、B-Small の 35 pts で 828 位。B-Large も取っておきたかったところではありますが教訓を得た上で通過できたのでまぁ良しとしましょう。あれ？と引っかかったところを安易にスルーしない、といったところでしょうか。後、グラフ関連は弱いのでもう少し BGL を確認しておきたいです。

まとめ

なかなか C++0x ぽいコードが書けないですね。特に誘惑に負けて REP マクロを導入してしまったため余計にそちらに頼ってしまう感じです。Range-based for もそれなりに使えることは使えるんですが REP マクロの単純明快さには勝てないというか。型名無かったら自動的に auto とかにならないですかね。後、要素だけではなくて添字も欲しいケースが結構あるので。アダプタを噛ませるべきなのかもしれませんが。後、auto func = [&](...) {...} や function<...> func = [&](...) {...} はヘルパ関数作成用に結構有用なイディオムだと思うので今後とも使える時には使いそうです。

テンプレ

#include <iostream>
#include <sstream>

#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 <functional>

#include <cmath>

// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/properties.hpp>
#include <boost/graph/graph_traits.hpp>
#include <boost/property_map/property_map.hpp>
#include <boost/ref.hpp>
#include <boost/graph/planar_face_traversal.hpp>
#include <boost/graph/boyer_myrvold_planar_test.hpp>

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;
using namespace boost;

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

5/14(土)の Boost.勉強会 #5 名古屋で発表してきました。ぶっちゃけ GC 本勉強会の LT を入れてすら発表 2 回目という状況だったのですが、cpp_akira さんのプレッシャーに背中を押して頂いて手を挙げました。Boost.勉強会でそれも Spirit テーマとか無謀だろうという感じでしたがまぁなんとか。

「春のlock free祭り」 (kumagi)

Lock-free。Java だと標準ライブラリに入ってる事もあって憧れですね。なんせ C++ にはマルチスレッドについてさえ規定がありませんでしたから。C++0x で Concurrency 周りが超強化され <atomic> も入る事で portable に lock-free 　が書ける事になりある意味タイムリーとも言える訳ですが。うーん、やっぱり難しいですね。全然理解できていないのはともかく、話を聞いているのは面白いのですがやっぱりこの辺の実装は専門家に任せないと駄目だなぁという意を強くしました。ということで誰か書いてください。

「Boostで線形代数(再)入門」 (wof_moriguchi)

今のところあまり線形代数に関わらない感じではあるのですが。ただ多元連立一次方程式については結局その問題に帰着される問題も多い訳でさくっと書けるに超した事はないかも。

「Frama-Cによるソースコード検証」 (mzp)

うん、まぁ @mzp さんですね、うん。良く分かりませんが今は亡き Concept さんが居れば axiom とかと連携して良い感じになっていたかもしれません。

簡単のために端折ったのかもしれませんが min の仕様が返値が引数 x,y 以下、だけってのがちょっと気になりました。LE だけでも LE(x, \result) || LE(y, \result) で x か y のいずれかあるいは両方と等しいって規定できますよね？直接言えよって話ですが。

「C(C++)による左再帰を許すPEG」 (eldesh)

発表タイトルが告知された時から「ぐぁぁ」って感じでした。なぜなら発表では明示してなかったような気もしますが Spirit は PEG だからです。ネタ被りっていうかもっと高度じゃないですか－、やだー、みたいな。もちろん大変興味深く聞けました。

なお、Spirit は PEG で、かつ、Packrat parser を使っていません。なので左再帰は無限ループします(当日の朝に一応確認)。 ただ左再帰は文法を書き直せばいいですし計算量的に最悪指数時間と言っても無限先読みが可能という特徴から来ているものですので先読みがなければそれ程大きな影響はないはずです、多分。例えば axpdf--.spi なんかは先読みを使わずに書けています。

「Boost.Pythonの有能性」 (fate_fox)

高校生ですよ、高校生。競技コーディングもそうですけど最近の高校生ぱねぇ。

後、さらっと color f0 の助け船を出した yOU_aND_i さん、かっけぇ。

第一スクリプト言語が Perl なのでちょっと使うには敷居が高いですね。Python 以外にも対応させようという Language Binding というプロジェクトがあったはずなのですが完全に止まっちゃってますね。

「Boost.statechart / Boost.MSM」 (PG_kura)

衝撃のデモｗ DSEL がキモイのは、もうしょうがない気がします。基本無理矢理だし。でもきもいと言われた記法は eUML っぽいですが、UML のステートチャート図の記法が「イベント[ガード]/アクション」なので「まんまやん」って話ですよ。そうすると source + event [guard] / action == target ってのもそんなに変な感じはしません。…毒されてるんでしょうか。

「C++0x総復習」 (wraith13)

170 ページもある超大資料。carries_dependency ってのは知らなかったです。というか Concurrency 周りは良く分かってないので誰かエロイ人纏めてくれないでしょうか。まぁそれ以外にも FDIS 眺めてると結構知らない変更とかあったりします。ぶっちゃけ to_string() とか stoi() とかも知りませんでした。

「OpenCVを使った画像処理」 (miyabiarts)

やりたいんですけどね、OpenCV。本を買うだけはする自分のこと、OpenCV 本もあります。完全に積読ですが。GIL については BGL で adjacency_list とかと visitor だけがある状態みたいなイメージだと思うのでその上で走るアルゴリズムとかがないとなかなか使うメリットが見いだせないよな、という気はします。

「非実用的 Boost.Spirit.Qi 入門」 (yak_ex)

何の因果かトリになってしまいました(手を上げるのが遅かっただけ)。ネタの方向性的に Spirit に真面目に取り組んでる人ほど不興を買うような発表をしてしまったような気がします。発表が終わった後、酷評されてたらどうしようとか思いながら #boostjp 見に行ったのですが 3.3MB で全て持って行ってしまってたような。ちなみにエラー 3.3MB は本当に極端なケースです。ついでに言えば着目すべきエラーを一つ決めてしまえば後どんだけ出ようが大した問題ではありません。

反省点としてはそもそもの発表の位置づけでしょうか。Spirit で行くぜ→Tutorial あるじゃん→マニアックな方向も入れよう→非現実的、という思考回路だったのですが結局マニアックな方向を纏めきれませんでした。いっそ拡張性のところをばっさり割愛しようかとも思ったのですが(時間的にも)、せっかく書いたんだしということでスライドに残した上でスキップにしてしまいました。「Tutorila あるじゃん」に対する対応としては、カバーしきれていない落とし穴(Skipper周り)とか、いっそのこと Spirit エラーメッセージの傾向と対策とか、そういう実用方面を目指せばより有意義な発表ができたと思います。それだけの経験が貯まってなかったのも事実ですが。

ネタ的には「アーサー・C++・クラーク」とかも拾って頂いたようで無いセンス絞ったのが報われたような気がします。でも座席表で「へんたい」と書かれたのは想定外。違うよ。ボクはへんたいじゃないよ。仮にへんたいだとしてもへんたいという名の C++er 見習いだよ。

全体

Boost どころか C++ も関係ない発表が多いってどういうことなの？って感じですが、まぁ、Boost(に興味を持つような人が興味を持つようなことの)勉強会、ということにしておけば問題ないですね！　Spirit における Packrat parser の実装可能性についてはちょっと考えてみたいところです。また、Boost.勉強会に限らず何らかの発表ができればいいなぁと思います。

一応 GCJ は毎回書いてるようなので今回も書いてみます。一応無事全問正解でした。のんびり書いてたんであんまり意味はないですが。今回は C++0x で書いてみよう、というコンセプトで書いてます。共通分テンプレートは最後にあります。何となくマクロ使わない派だったのですが RNG だけ入れてしまいました。

Problem A. Bot Trust

まぁ、シミュレーションですね。そしてのっけから 0x 不要なコードです。珍しく読み取りながら計算してるコードで書きました。割と A 面倒みたいなコメントも見かけましたが結構きれいに書けたんじゃないでしょうか。ちなみに small 提出しようとしたら Case #x: の形式が違うって言われて慌てて時間内に修正して submit したりもしました。

inline UI absdiff(UI a, UI b) { return a > b ? a - b : b - a; }

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI t; cin >> t;
    for(UI i=0;i<t;++i) {
        UI p[2] = { 1, 1 }, t[2] = { 0, 0 };
        UI cur = 0, prev = 0;

        UI n; cin >> n;
        for(UI j=0;j<n;++j) {
            char c; UI r; cin >> c >> r; cur = c == 'B' ? 0 : 1;
            t[cur] = max(t[prev] + 1, t[cur] + absdiff(p[cur], r) + 1);
            p[cur] = r; prev = cur;
        }
        cout << "Case #" << i+1 << ": " << t[cur] << endl;
    }
    return 0;
}

B. Magicka

これもまぁシミュレーションですね。とりあえず clear の意図がいまいちはっきりせず質問しましたが read more carefully みたいなこと言われました。言われるだろうとは思いましたが。他にも質問した人が居るようで問題文も途中で修正されたようです。コード的には素直に for ループで回せばいいのにあえて boost::irange とか使っちゃいました。カウンタ変数も使ってないのに(そういう警告も出ます)。C++0x だというなら unordered_set, unordered_map を使っても良かったかもしれません。後は、今回不要だったっぽいですが element list 中の base element の数をカウントしておいて毎回 list 舐めるのを回避してるくらい。そのせいもあってやたら長くなっちゃってますけど。

// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

int main(void)
{
    ios_base::sync_with_stdio(false);

    vector<char> be = { 'Q', 'W', 'E', 'R', 'A', 'S', 'D', 'F' };
    map<char, int> rbe;
    for(auto i : IR(0U,be.size())) {
        rbe.insert(make_pair(be[i], i));
    }

    UI t; cin >> t;
    for(UI i=0;i<t;++i) {
        map<pair<char, char>, char> comb;
        UI c; cin >> c;
        for(auto j : IR(0U,c)) {
            string s; cin >> s;
            comb.insert(make_pair(make_pair(s[0],s[1]), s[2]));
            comb.insert(make_pair(make_pair(s[1],s[0]), s[2]));
        }
        multimap<char, char> opposed;
        UI d; cin >> d;
        for(auto j : IR(0U,d)) {
            string s; cin >> s;
            opposed.insert(make_pair(s[0],s[1]));
            opposed.insert(make_pair(s[1],s[0]));
        }
        UI n; cin >> n;
        string s; cin >> s;

//        for(auto val: comb) { cerr << val.first.first << ',' << val.first.second << ':' << val.second << endl; }
//        for(auto val: opposed) { cerr << val.first << ':' << val.second << endl; }

        string result;
        vector<int> count(be.size());
        for(auto ch:s) {
//cerr << result << ':' << ch << endl;
            if(!result.empty()) {
                if(comb.count(make_pair(result.back(), ch))) {
                    char nch = comb[make_pair(result.back(), ch)];
                    --count[rbe[result.back()]];
                    result.back() = nch;
                } else {
                    bool cleared = false;
//for(auto vv: count) { cerr << vv; } cerr << endl;
                    for(auto check: boost::make_iterator_range(opposed.equal_range(ch))) {
                        if(count[rbe[check.second]]) {
                            result.clear();
                            fill(RNG(count), 0);
                            cleared = true;
                            break;
                        }
                    }
                    if(!cleared) {
                        result.push_back(ch);
                        ++count[rbe[result.back()]];
                    }
                }
            } else {
                result.push_back(ch);
                ++count[rbe[result.back()]];
            }
        }

        cout << "Case #" << i+1 << ": [";
        bool flag = false;
        for(auto v:result) { if(flag) cout << ", "; cout << v; flag = true; }
        cout << ']' << endl;
    }

    return 0;
}

Problem C. Candy Splitting

今回、C++0x を使ったのはこのために有ったんだ！そんな問題(嘘)。Patrick は xor 計算しているので xor で総和とって 0 以外なら NO、そうでなければ(通常の和で)総和とったものから最小値を引けば OK。accumulate の初期値も make_tuple にして 戻り値を auto で受けるとさらに格好いい気がします、なんとなく。ここまで来ると lambda の引数の型指定も省略したくなってきますね。

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI t; cin >> t;
    for(UI i=0;i<t;++i) {

        UI n; cin >> n;
        vector<UI> v(n); for(auto &val:v){cin>>val;}
        tuple<UI, UI, UI> tup(0, 0, v[0]); // xorsum, sum, min
        tup = accumulate(RNG(v), tup, [](tuple<UI,UI,UI> t, UI n) {
            return make_tuple(get<0>(t) ^ n, get<1>(t) + n, min(get<2>(t), n));
        });
        cout << "Case #" << i+1 << ": ";
        if(get<0>(tup) != 0) {
            cout << "NO" << endl;
        } else {
            cout << get<1>(tup) - get<2>(tup) << endl;
        }
    }

    return 0;
}

Problem D. GoroSort

さて今回最大の鬼門。そもそも submit 数も少なくかつ small 正答率も少ない問題です。自分も本戦とかだと解けていないと思います。後付けで調べた用語も入れて自分の対処を説明すると、状態を置換とみなして、長さ n の巡回置換について期待値が n (n≧2)であることを計算で n=6 まで確かめた形になります。巡回置換(感覚的には「ばらばら」と表記される状態)の時には全部シャッフルが最良だろうという仮定の下で、ですが。n=3 の時は順列を書き下して 1,2,3 なら OK、一箇所だけ一致する 1,3,2、3,2,1、2,1,3 なら(exampleの説明と同様)後 2 回、2,3,1、3,1,2 ならもう一度やり直し。結果、期待値 a は a = 1/3! * 1 + 3/3! * (1 + 2) + 2/3! * (1 + a) と表され計算すると a = 3 になります。n=4 も書き下して計算すると期待値 4 になってひょっとしてと思い、n=5 はさすがに全部は書き下せなかったので、

• 5 箇所同じ場合
• 4 箇所だけ同じ場合(実際には無い)
• 3 箇所だけ同じ場合
• 2 箇所だけ同じ場合
• 1 箇所だけ同じ場合
  • 残りが長さ2の巡回置換(swap)2つの場合
  • 残りが長さ4の巡回置換の場合

として場合分け。実際にはこの辺までは巡回置換、のような発想はありませんでした。今回時間があるので n=6 でやろうとして k 箇所だけ同じ場合の数え方が思いつかず、(正確な用語としては脳内にはありませんでしたが)巡回置換という考え方に辿り着きました。

• 長さ1の巡回置換6個の場合
• 長さ1の巡回置換4個と長さ2の巡回置換1個の場合
• 長さ1の巡回置換2個と長さ2の巡回置換2個の場合
• 長さ2の巡回置換3個の場合
• …

という感じで場合分けして計算。長さ n の巡回置換の数は (n-1)! になります。円順列ってやつですね。これで計算して 6 になったのでこれは行くしかないな、と。ちなみに、n=5 辺りの計算でぴったり 5 になって正直感動してました。こういう考え方だったのでコードも無駄に素な巡回置換の積に分解して長さ 1 以外のものの長さを足す、という風になっています。実際には一致していない箇所を数えることに帰着されてしまうのですが。なお、巡回置換ではなく一致していない箇所の個数、をベースにして式を立てる場合だとその場合の数については Wikipedia の完全順列の項や、Wolfram Mathworld の Subfactorial、Partial Derangement の項にあるようです。

// Boost library can be retrieved from http://www.boost.org/
// I uses 1.46.1

#include <boost/range/irange.hpp>
#include <boost/range/iterator_range.hpp>

template<class Integer>
inline boost::iterator_range< boost::range_detail::integer_iterator<Integer> >
IR(Integer first, Integer  last)
{ return boost::irange(first, last); }

int main(void)
{
    ios_base::sync_with_stdio(false);

    UI t; cin >> t;
    for(UI i=0;i<t;++i) {
        UI n; cin >> n;
        vector<UI> v(n); for(auto &val:v){cin>>val;--val;}
        vector<char> flag(n);
        UI result = 0;
        for(auto idx : IR(0U,n)) {
            if(!flag[idx]) {
                flag[idx] = 1;
                UI count = 1, idx_ = v[idx];
                while(!flag[idx_]) {
                    flag[idx_] = 1; idx_ = v[idx_]; ++count;
                }
                if(count>1) result += count;
            }
        }
        cout << "Case #" << i+1 << ": " << result << endl;
    }

    return 0;
}

共通テンプレート

#include <iostream>
#include <sstream>

#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>

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()

using namespace std;

nagoya313 さんの記事「Boostのfusionとspiritやばい」で Boost.Spirit.Qi を使ってカンマ区切りのデータを Fusion シーケンスに突っ込む例が紹介されている。これはこれで簡潔なのだがせっかく構造体を Fusion にアダプトしていてメンバの型情報がとれるはずなのに parse() に渡すルールのところでもメンバの型情報を指定しなければならないのが悲しい感じである。どうせならルールを自動生成したいところだ。

実は Boost.Spirit.Qi にはそんなニーズに応えられる機能が存在する。auto_ パーサーである。auto_ パーサーがどういうものかは本家ドキュメントか faith_and_brave さんの記事「qi::auto_で簡易パース」を参照してもらうとして、Fusion シーケンスを属性として渡した場合には、各要素に対する auto_ パーサーを >> で連結したものがシーケンスに対応するパーサーとなる。これが単純に >> で連結したものではなく、>> ',' >> で連結したものになればカンマ区切りデータ用のパーサーが得られることになる。

そのままでも十分変態的な Spirit だが拡張性が非常に高いところも変態的である。当然ながら auto_ パーサーの挙動もカスタマイズ可能だ。これは create_parser という customization point で実現できる。customization point とは特殊化することで Spirit の挙動をカスタマイズできるテンプレートだと思えば良い。create_parser の概要は以下の通りである(ref. 本家ドキュメント)。

template <typename T, typename Enable>
struct create_parser
{
    typedef <unspecified> type;
    static type const& call();
};

T 型の属性を渡した際に返すパーサーの型を type とし、実際に返すための関数が call()、Enable は SFINAE を使って有効か無効かを切り替えるためのもので Spirit の customization point には大抵ついている。基本的にはこの create_parser を T が Fusion シーケンスの場合に対して特殊化してやればよいことになる(ただしデフォルトでは std::string に対しても実装がないのでその分も特殊化が必要である)。

ここで実際の実装を見る前にデフォルトの実装を見てみよう。

    ///////////////////////////////////////////////////////////////////////////
    // Fusion sequences
    template <typename Sequence>
    struct meta_create_sequence
    {
        // create a mpl sequence from the given fusion sequence
        typedef typename mpl::fold<
            typename fusion::result_of::as_vector<Sequence>::type
          , mpl::vector<>, mpl::push_back<mpl::_, mpl::_>
        >::type sequence_type;

        typedef make_nary_proto_expr<
            sequence_type, proto::tag::shift_right, qi::domain
        > make_proto_expr;

        typedef typename make_proto_expr::type type;

        static type call()
        {
            return make_proto_expr::call();
        }
    };

Fusion シーケンスを vector に変換しその結果に対して mpl::fold で push_back を適用する。得られるのは Fusion シーケンスと同じ要素型を持つ mpl::vector である。make_nary_proto_expr は mpl::vector の各要素型に対して create_parser 相当を呼び出しそれらを指定した演算子で連結する。この場合、shift_right ＝ 右シフト、つまり >> である。つまり mpl::vector<A, B, C> に対しては parserA >> parserB >> parserC が返ってくることになる。

これを元に >> ',' >> で連結するにはどうしたらいいか？普通に考えれば make_nary_proto_expr を修正するべきだろうが解析が面倒そうだったので今回は make_nary_proto_expr をそのまま利用することにした。make_nary_proto_expr の結果が parserA >> ',' >> parserB >> ',' >> parserC になれば良いのだから mpl::vector<A, 何か, B, 何か, C> を渡してやれば良い。ここで何かとは create_parser で ',' が返ってくる型である。以上の考え方を元にして実装したのがこのコードだ。10 行目で定義している csv_separator が「何か」である。特殊化した create_parser は 30 行目以降にある。15 行目からの is_fusion_sequence_but_not_proto_expr は Fusion シーケンスに対してだけ create_parser を特殊化するためのものだ。Enabler として 61 行目で使用している。44 行目からは std::string 用の create_parser 特殊化、59 行目からが問題の Fusion シーケンス用の特殊化である。66 行目の fold で単純に要素を push_back するだけではなくさらに csv_separator も push_back している。結果として要素と csv_separator が交互に並んだものが sequence_type_ として得られる。これだけだと末尾に余計な csv_separator が付くため、要素数が 0 でなければ pop_back している(70 行目)。後はデフォルト実装と同様である。これだけ用意しておけば 123 行目のように auto_ に対して Fusion シーケンスを渡してやるだけでそれに適したカンマ区切りのパーサーが得られる。ちなみに 88 行目、101 行目のように BOOST_FUSION_DEFINE_STRUCT によって構造体定義と BOOST_FUSION_ADAPT_STRUCT を同時にできる。

Boost Spirit Qi の rule と Skipper についてちょっと戦った結果のメモ。

Boost Spirit Qi の Parser コンセプトに従う p は

p.parse(f, l, context, skip, attr)

の形の式が有効でなければならない。基本的に parse は以下のように定義されているので任意の型の Skipper を受け取れるはずである。

template <typename Context, typename Skipper, typename Attribute>
bool parse(Iterator& first, Iterator const& last
  , Context& context, Skipper const& skipper
  , Attribute& attr) const;

が、rule (grammer も)は宣言時に Skipper の型を指定しなければならない。これは右辺の式を boost::function で保存しているからだ。

template <//snip...
>
struct rule
      : // snip...
{
// snip...
    typedef function<
        bool(Iterator& first, Iterator const& last
          , context_type& context
          , skipper_type const& skipper
        )>
    function_type;
// snip...
    template <typename Context, typename Skipper
      , typename Attribute, typename Params>
    bool parse(Iterator& first, Iterator const& last
      , Context& caller_context, Skipper const& skipper
      , Attribute& attr, Params const& params) const
    {
        if (f)
        {
// snip...
            if (f(first, last, context, skipper))
            {
// snip...
    }
    function_type f;
// snip...

正確には parse() の呼び出し自体ではなくその内部の f の呼び出しの時点で型に関するエラー(変換不能だったりマッチする関数がない)が発生する。この辺りの挙動について書かれたのが Boost Spirit の Tutorial にある以下の記述のはずなのだが、

rule<Iterator> r;

(snip) This rule cannot be used with phrase_parse. It can only be used with the parse function

rule<std::string::iterator, space_type> r;

This type of rule can be used for both phrase_parse and parse.

実のところこれは誤りである(むしろ逆だ)。どちらかというと rule は指定された Skipper しか受け取れないと考えた方が良い。実際には次のような挙動になる(以下、OK はコンパイル可能で BAD はコンパイル不可能とする)。

#include <boost/spirit/include/qi.hpp>
#include <string>

int main()
{
    namespace qi = boost::spirit::qi;

    std::string str;
    typedef std::string::iterator Iterator;
    Iterator first = str.begin(), last = str.end();

    qi::rule<Iterator, qi::space_type> rule_with_skip, rule_with_skip2;
    qi::rule<Iterator> rule_without_skip, rule_without_skip2;

    rule_with_skip    = qi::int_;
    rule_without_skip = qi::int_;

    phrase_parse(first, last, rule_with_skip,    qi::space);
    phrase_parse(first, last, rule_without_skip, qi::space); // OK
//  phrase_parse(first, last, rule_with_skip,    qi::cntrl); // BAD
    phrase_parse(first, last, rule_without_skip, qi::cntrl); // OK
//  parse       (first, last, rule_with_skip);               // BAD
    parse       (first, last, rule_without_skip);

//  snip..

    return 0;
}

あれ？ Skipper なしの rule に対して適当な Skipper を指定した phrase_parse() が呼べてるじゃんと思うかもしれないがこちらの方が例外だと考えた方が良いだろう。Skipper なしは実際には boost::spirit::unused_type を Skipper に指定したことと同じになる。そして boost::spirit::unused_type は boost::fusion::unused_type と同じであり、以下の変換コンストラクタが定義されているため任意の型から型変換可能である。

namespace boost { namespace fusion
{
    struct unused_type
    { // snip..

        template <typename T>
        unused_type(T const&)
        {
        }
// snip..
}}

ということで適当な Skipper を渡しても勝手に boost::spirit::unused_type に変換されて受け取れてしまうのだ。ただし pre-skip が行われるだけで rule の右辺には Skipper は引き継がれない。なお Reference 側にはこの挙動自体は書かれている。

さて、長かったがまだもう少し気をつける部分がある。Boost Spirit では skip, no_skip, lexme ディレクティブにより Skipper の有無を途中で切り替えることができる（今回の話上は lexme は no_skip と同じと思えばよい）。基本的な考え方は rule の左辺の Skipper 指定が右辺に引き渡されることに注意して「rule は指定された Skipper しか受けとれない」に従えばいいので次のような結果になる。

    rule_with_skip2    = rule_with_skip >> rule_without_skip; // OK
//  rule_without_skip2 = rule_with_skip >> rule_without_skip; // BAD
    rule_with_skip2    = rule_with_skip >> qi::no_skip[rule_without_skip]; // OK
    rule_without_skip2 = qi::skip(qi::space)[rule_with_skip] >> rule_without_skip; // OK

つまり必要な時には skip で Skipper を指定するよう調節してやらなければならないということだ。no_skip は無くても通る。

最後に引数無しの skip についても少しだけ注意があるので触れておこう。

    rule_with_skip2    = qi::no_skip[qi::skip[rule_with_skip]]; // OK
    rule_with_skip2    = qi::no_skip[rule_without_skip2];
//  rule_without_skip2 = qi::skip[rule_with_skip];              // BAD
    rule_without_skip2 = qi::skip(qi::space)[rule_with_skip];   // OK

引数無しの skip は no_skip で一度無指定になった Skipper を復元する。従って一番上の例では qi::space が復元されるのでコンパイルできる。しかしこの効果は Skipper 無指定の rule を経由すると消えてしまい skip を付けても Skipper 無指定と同じ状態になってしまう。これは戻すべき Skipper の型を静的に判断しているためだ。一度 unused_type に変換(この場合は変換コンストラクタによるものではなく upcast)されてしまうと元に戻せなくなり unused_type つまり無指定と同じになってしまう。この場合には明示的に Skipper を指定してやる必要がある。

以上を把握すれば Skipper の有無によるエラーは回避できるだろう。実に誰得な記事であったと言えるが、これも PDF の仕様が複雑なのがいけないのだ。