SRM347

TopCoder の SRM に初めて参加しました。結果はこんな感じ。(部屋内で2位・DIV2で11位)
開始直後に友達から電話がくるというハプニングがありましたが、なんとか次回からDIV1でできるようです。わーい。
ちなみにタクシーの問題(1000pt)はさっぱりわかりませんでした。

一度 submit してしまうと、そのソースが Web で公開されてしまうみたいなので
あんまり汚いのを出すのは恥ずかしかったりします。でもソース整えてる時間ももったいないしなぁというジレンマ。あと汚い方がChallenge(他のコーダからのツッコミ)が飛んでくることが少ないのかなとか。

C++における関数型プログラミングのすすめ。

まぁ、そんなわけで、submitした後に書き直したいなーと思うことがあったりするのです。
例えばこのコード。

std::accumulate (Haskell の List.foldl, OCaml だと List.fold_left) を使うと次のように書き直せます。

#include <vector>
#include <string>
#include <sstream>
#include <algorithm>
#include <numeric>
using namespace std;

class mincost {
public:
  mincost(int x, int y): fpad(x), years(y) {}
  double operator()(const double acost, const string &s) {
    stringstream ss(s);
    int pcost, tax, eff;
    ss >> pcost >> tax >> eff;
    return min(acost, pcost + years * (fpad / eff + tax));
  }
private:
  double fpad;
  int years;
};

class CarBuyer {
public:
  double lowestCost(vector<string> cars, int fuelPrice,
                    int annualDistance, int years) {
    return  accumulate(cars.begin(), cars.end(), 
                       1e50, mincost(fuelPrice * annualDistance, years));
  }
};

まぁ、この例だと元のほうが読みやすいやん！ってなるのですが、少なくともループがあったところ（accumulateの呼出し元）を単純化することはできたということで。

for や while を使えばあらゆる処理が書けますが、逆にいろいろ書けすぎるのが困りものだったりします。2重ループぐらいならまだしも、5重6重のループになるとどのループで何をやっているんだかさっぱりわからなくなります。

ループをアルゴリズムで置き換えられれば、そこで何をやっているかが明確になり
（そのアルゴリズムが何を行うかを正確に知っている必要はある。remove系とか）ループ内部の処理を外に追い出せるのです。

一般に、コンテナの各要素から計算される値の最小値/最大値を求めたい場合は

  min = DEFAULT_MIN;
  for (i=c.begin(); i!= c.end(); ++i) {
    tmp = f(*i)
    if (min > tmp) min = tmp;
  }
  return min;

というコードを

  return accumulate(c.begin(), c.end(), DEFAULT_MIN, F);

と

  // f: elem_t -> ret_t
  // F: (ret_t * elem_t) -> ret_t
  ret_t F(ret_t m, elem_t e) {
    return min(m, f(e));
  }

というコードに分離できます。
関数ポインタを関数オブジェクトにして、インライン化できるようにしてやるとなお良し。

もちろん常に分離するのが良いわけではなく、場合によりけりです。
数百行もある関数が一つどんとあるのも、数行の関数が百個あるのも嫌なので、モジュールごとに上手に分割する必要があります。そのための手段のひとつとして覚えておくと良いんではないでしょうか。