パスワードを忘れた? アカウント作成
223694 journal

Yak!の日記: Google Code Jam Round 1B A, B をあえて Boost 多用して解いてみた。

日記 by Yak!

1.43 で Range も拡張されたしかなり格好良く書けるんじゃね?とかふと思いついて書いてみたのだが少なくとも自分にはあまり格好良く書けなかった。今のところの結論としては「コンパイラ並に型導出できます」とか「山のようなコンパイルエラー、ご褒美です」とかいう人じゃない限りお勧めできない。っちゅーかそこまでするなら最初から関数型言語で書けよって気はする。

以下では #include, #define, using namespace, typedef 等を省いたコードを貼る。全体は codepad.org へのリンクで。

R1B-A File Fix-it。tokenized してから partial_sum でチェックが必要なディレクトリが作れるじゃん、というのがそもそも本項をやろうと思うに至った発想なのだが、そこからさらに連結ができないというのが痛い。ついでに tokenized から返ってくるのは value_type が string の Range ではなくて sub_match の Range なので partial_sum にそのまま渡せない。少なくとも GCC 4.3.4 の libstdc++ では partial_sum 内部で一度 __binary_op の戻り値を InputIterator::value_type 型の変数 __value に代入している。

          __value = __binary_op(__value, *__first);
          *++__result = __value;

結果 sub_match に代入しようとして失敗する。この一時的な __value への代入により不要な制約を持ち込んでいるだけのような気がするのだがどうなんだろうか。後 ssub_match = sub_match でもないというのも地味に詰まるポイントである。で、count_if のところでは単純に ref だけで渡すとコンパイルエラーになたので、function を経由することで回避した。

struct Check
{
    set<string> sExists;
    bool operator()(const string &s) {
        bool result = !sExists.count(s);
        sExists.insert(s);
        return result;
    }
};

int main(void)
{
    int num_problem;
    cin >> num_problem;
    foreach(int idx_problem,irange(0,num_problem)) {
        int result = 0;

        int n, m;
        Check check; check("");
        cin >> n >> m; cin.ignore();
        for(int i=0;i<n;++i) {
            string s;
            getline(cin, s);
            check(s);
        }
        for(int i=0;i<m;++i) {
            string s;
            getline(cin, s);
            vector<string> dirs;
// partial_sum in libstdc++ trys to assign value into InputIterator::value_type, in this case, sub_match
//    therefore, we transfrom it to just a string
// NOTE that type of sub_match is NOT ssub_match = sub_match<string::const_iterator> >
            partial_sum(s | tokenized("/", -1) | transformed(mem_fn(&sub_match<string::iterator>::str)), back_inserter(dirs), _1 + "/" + _2);
// the first element is empty string, therefore check("") is necessary.
// just passing ref(check) leads to an error "no match for call..."
            result += count_if(dirs, function<bool(const string&)>(ref(check)));
        }

        cout << "Case #" << idx_problem+1 << ": " << result << endl;
    }

    return 0;
}

R1B-B Picking Up Chicks。まず lambda が unsigned long long を認識してくれないところからスタートである。できるだけ自前で関数オブジェクトを書かないという個人的方針なので無理矢理 transformed とか transform_iterator とかを使って partial_sum さん無双とした。C++0x なら lambda でその場で関数オブジェクトを書く方が楽そうなので書き方も大分変わるかもしれない。それはともかく。accumulate にしろ <numeric> のアルゴリズムは地味にできる奴ばかりなので覚えておいて損はしない。今回割と普通の使い方だが関数オブジェクトを渡せるのでかなり適用範囲は広い。他に詰まったところとしては transform 系に (Boost の) lambda も mem_fn(OutputIterator に対する時のみ)もそのまま渡せないというところがまた厳しい。lambda の場合は、result_type が定義されていないとか言われる。result_of と lambda の sig テンプレートを橋渡ししてやるのが正道な気がするが面倒なので再度 function にお出まし願う。mem_fn の方は operator() としては const / 非 const のオーバーロードがあるのだが、result_type が const reference 固定なのでそのままでは出力側に使えない点の回避である。

// Currently, Boost lambda does not support long long and unsigned long long
namespace boost {
namespace lambda {
namespace detail {
    template <> struct promote_code<LL> { static const int value = 1000; };
    template <> struct promote_code<ULL> { static const int value = 2000; };
}
}
}

struct Temp
{
    int reached;
    int psum;
};

int main(void)
{
    int num_problem;
    cin >> num_problem;
    foreach(int idx_problem,irange(0,num_problem)) {

        ULL n,k,b,t;
        cin >> n >> k >> b >> t;
        vector<ULL> pos(n);
        foreach(ULL &temp, pos) { cin >> temp; }
        vector<ULL> vel(n);
        foreach(ULL &temp, vel) { cin >> temp; }

        if(k == 0) {
            cout << "Case #" << idx_problem+1 << ": " << 0 << endl;
            continue;
        }

        vector<Temp> temp(n);
// lambda does not support result_of, therefore we wrap it into function.
// mem_fn always have result_type with const reference, therefore we wrap it into function to force non-const result_type.
        boost::range::transform(pos, vel, make_transform_iterator(temp.begin(), function<int&(Temp&)>(boost::mem_fn(&Temp::reached))), _1 + _2 * t >= b);
        partial_sum(temp | reversed | transformed(function<int(Temp&)>(!bind(&Temp::reached, _1))), make_transform_iterator(temp.rbegin(), function<int&(Temp&)>(boost::mem_fn(&Temp::psum))));
        vector<int> psum;
        partial_sum(temp | reversed | filtered(boost::mem_fn(&Temp::reached)) | transformed(boost::mem_fn(&Temp::psum)), back_inserter(psum));

        if(psum.size() < k) {
            cout << "Case #" << idx_problem+1 << ": " << "IMPOSSIBLE" << endl;
        } else {
            cout << "Case #" << idx_problem+1 << ": " << psum[k-1] << endl;
        }
    }

    return 0;
}

仮に TopCoder でこんなコードがあったら速攻で解読諦めて閉じる系のコードだと思う。ほんと C++ は変態御用達である。自分は C++er 見習いだが。

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。
typodupeerror

日本発のオープンソースソフトウェアは42件 -- ある官僚

読み込み中...