ビット演算集大成の問題！？

ビット演算集大成の良問をPOJで見つけたので紹介。

実は、自分でも似たような問題を考えていてTopCoderに問題投稿しようかな・・と思ってましたが、似たような問題は既にありました。。

しかも、2次元バージョンでよりトリッキーな感じ。。

問題はこちら。

http://poj.org/problem?id=2965

簡単に日本語訳すると、

4*4マスに+と-の文字列がある。

（i, j）マスを選択すると、(i,j)マスが

+の場合は、-に

-の場合は、+に

反転変換できる。但し、(i,j)マスを選択すると、i行のマス及びj行のマスの値もすべて反転してしまう。

すべての文字を-にするためには、最低何回のマスを選択しないといけないか？

またそのときに選択するマスを列挙せよ。

んー、これ系の問題はメジャーなんですかね。。TopCoderでも似たような問題ありました。

ビット演算を使うと解けますが、実はこの問題はビット演算の使いどころが２種類あります。

①組み合わせをビットで表現する

②状態および処理をビット演算で計算し、処理を高速化

①は、どのマスを選択するかを0, 1のビットで表すという意味。

②は、4*4マスの状態を16bitのビットで保持します。さらに、あるマスを選択した場合の処理をXORを用いて実現します。

以下ソース。

int main() {
    int ch[16];
    REP(i,16) {
        ch[i] = 0;
        REP(k, 16)
            if (k/4 == i/4 || k%4 == i%4)
                ch[i] |= 1<<k;
    }

    string in;
    int ref = 0;

    REP(i, 4) {
        cin >> in;
        REP(j, 4)
            if (in[j] == '+')
                ref |= 1<<(4*i+j);
    }

    int ret = INF, bcomb = -1;
    REP(comb, 1<<16) {
        int ref_t = ref, cnt=0;
        REP(i, 16)
            if (comb >> i & 1)
                ref_t ^= ch[i], ++cnt;

        if (!ref_t && ret > cnt)
            ret = cnt, bcomb = comb;
    }
    cout << ret << endl;
    REP(i, 16)
        if (bcomb >> i & 1)
            cout << i/4+1 << " " << i%4+1 << endl;

    return 0;
}

クロージャとは何か？(2)

前回に引き続き、クロージャについて。

前回のブログで、クロージャとは”汎用的な機能を持つ関数の機能を何らかの変数で固定して使うような仕組み”と説明しました。

実際に例を見て、クロージャとは何かを更に詳しく調べてみます。

1,2,3, ...., n

という数列の和を求める関数を書いてみます。

def seriesSum(n):
  ret = 0
  for x in range(1, n+1):
      ret += x
  return ret

久々のPython。。

では、次に、

1, 4, 9, ...., n^2

という数列の和を求める関数を書いてみましょう。

def seriesSum(n):
  ret = 0
  for x in range(1, n+1):
      ret += x*x
  return ret

じゃあ、一般的に

f(1), f(2), ..., f(n)

という数列の和を求める関数は書けないものでしょうか？

クロージャを使えば書けます。

こんな感じ。

def genSeriesSum(_f):
  func = _f
  def seriesSum(n):
      ret = 0
      for x in range(1, n+1):
          ret += func(x)
      return ret
  return seriesSum

使うときは、どうするのでしょうか？

例えば、fはx -> x^2の写像とする場合は以下のようにして使います。

def square(x):
  return x*x

squareSum = genSeriesSum(square)
print squareSum(10)

では、説明してみます。

まず、genSeriesSum()について。

この関数は、

まず、関数オブジェクト_fを受け取ります。

そのあと、変数funcに_fを代入しています。

そして、関数内で定義された関数seriesSum()を関数オブジェクトとして返します。

ここでポイントは、seriesSum()の中のfuncという変数は、_fという値に固定されているということです。

つまり、genSeriesSum()は、機能を固定した（funcを_fにした）関数seriesSum()を生成するような関数であると言えます。

そう、これです。

「機能を固定した関数を生成する関数」

これが、クロージャです。

クロージャを使うと、こんなことも出来ます。

関数の微分値を求める関数。

def genDeriverable(_f, _dx):
  f = _f
  dx = _dx
  def deriverable(x):
      return (f(x + dx) - f(x)) / dx

  return deriverable

どうでしょうか？

クロージャ、すごいです。

個人的には、クロージャとは、関数ファクトリーという感覚を覚えました。

私の認識が間違ってたら、是非是非指摘してくださいーー。

クロージャとは何か？(1)

最近よく耳にするクロージャ。

JavaやC++の最新バージョンがクロージャをサポートするとか、しないとか。。

で、結局、クロージャって何なの？

いろいろ調べてみましたが、「なるほど！」と思わせるサイトがいくつかあったので、それを読んで得た知識を紹介します。（間違いなどありましたらご指摘ください。）

wikiをみると、以下のような解説があります。

In computer science, a closure is a first-class function with free variables that are bound in the lexical environment.　Such a function is said to be "closed over" its free variables. A closure is defined within the scope of its free variables, and the extent of those variables is at least as long as the lifetime of the closure itself.

日本語訳。（間違いあるかも。。）

クロージャとは自由変数を持つ第一級関数である。そして、その自由変数はそのスコープにおいて境界となる。このような関数はその自由変数に包括されたと言われる。

クロージャはその自由変数のスコープによって定義され、それらの変数の有効期限は、クロージャそのもののライフタイムと同じ程度である。

これだけ見ても？？な感じですが、具体的な例を見るとその意味が分かります。

クロージャの例や便利な使い方（pythonでの使用例）は次回紹介するとして、今回は、クロージャのポイントをまとめます。

①変数を持ち、かつ、オブジェクトのように扱うことのできる関数である。

②自由変数によってその機能がclosed（固定）される。

③自由変数は、クロージャそのものが存在している間は、記憶され続ける。

どうやら、汎用的な機能を持つ関数の機能を何らかの変数で固定して使うような仕組みを”クロージャ”と呼ぶのではないでしょうか？

逆に言うと、異なる変数で"closed"してあげると、異なる機能を持った関数を簡単に作成することができるということにもなります。

続きを読む..

包除原理とその実装

日曜のSRM、no-contestとは。。悲しすぎる。。

本番は解けなかったHardの問題。包除原理を使うことは分かっていたけど、実装が間に合わなかった。

今日は、簡単な包除原理の復習。英語では、Inclusion-exclusion principle.

そのまんま。

この原理を用いると、集合A1, A2, A3, ... Anがあるときに、すべての集合の和集合の要素数を求めることができます。

一番簡単な例で、A1とA2の2つしか集合が無い場合を考えます。これは簡単。

|A1| + |A2| - |A1 and A2|

ですね。ここで、|x|は集合xの要素数です。

じゃ、A1, A2, A3と集合が3つになったら？？

これはベン図を書いて、少し考えると分かります。

|A1| + |A2| + |A3| - |A1 and A2| - |A1 and A3| - |A2 and A3| + |A1 and A2 and A3|

です。

じゃあ、集合がn個あるときは？を説明したのがInclusion-exclusion principleです。

いろいろ解説サイトがありますが、wikiの説明が1番分かりやすいです。

http://en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle

証明も載ってます。

それでは、実装してみましょう。POJの問題を解いてみます。

ぱっと見簡単そうですが、入力値が10^9のときも時間内で解くためには、工夫が必要です。包除原理を使って解いてみます。

http://poj.org/problem?id=2407

set<int> primes;

void fact(int n) {
 FOR (i, 2, n) {
     if (n % i == 0) {
         primes.insert(i);
         n /= i;
         i = 1;
     }
 }
 if (n > 1) primes.insert(n);
}

int solve(int n, int bit, VI &vec) {
 int on = 0, mul = 1;

 REP(i, 32)
     if (bit >> i & 1)
         ++on, mul*= vec[i];

 return (on % 2 ? 1 : -1) * n / mul;
}

int main() {
 int n;

 while (cin >> n, n) {
     primes.clear();
     fact(n);

     int ret = 0;

     vector<int>vec(ALL(primes));
     REP(bit, 1<<vec.size()) {
         if (!bit) continue;
         ret += solve(n-1, bit, vec);
     }
     cout << n-1-ret << endl;
 }

 return 0;
}

部分集合をビット演算を使って実装するのがポイントでしょうか～。

2^n - 1パターンの部分集合を考えないといけないので、nが大きい場合は何らかの工夫が必要なようです。数学的アルゴリズムの世界は奥が深い。。

C++でParse

POJで見つけた良問。

難しくはないけど、C/C++で如何に文字列をparseするかが練習できる良い問題です。

あと、無駄なキャスト（upper cast）はしないとか、scanfやcinとgetsの使い分けとか学べます。

取りあえず、問題とソースを見てください。

もっときれいなコードが書ける人は随時募集！（たくさんいそう。。）

問題：

http://poj.org/problem?id=2501

ソース：

char input[256];
int main() {
   int h, m, s, v = 0;
   double x = .0;
   double t0 = .0, t1 = .0;

   while (gets(input)) {
       stringstream ss(input);
       string s1 = "", s2 = "";

       ss >> s1 >> s2;
       sscanf(s1.c_str(), "%02d:%02d:%02d", &h, &m, &s);

       t1 = h + m/60.0 + s/3600.0;
       x += (t1 - t0) * v;
       t0 = t1;

       if (s2 != "")
           sscanf(s2.c_str(), "%d", &v);
       else
           printf("%02d:%02d:%02d %.2lf km\n", h, m, s, x);
   }
   return 0;
}

末尾再帰について

ちょっと夜更かしして末尾再帰について勉強。。

下の解説がかなり分かりやすいです。

In traditional recursion, the typical model is that you perform your recursive calls first, and then you take the return value of the recursive call and calculate the result. In this manner, you don't get the result of your calculation until you have returned from every recursive call.

In tail recursion, you perform your calculations first, and then you execute the recursive call, passing the results of your current step to the next recursive step. This results in the last statement being in the form of "(return (recursive-function params))" (I think that's the syntax for Lisp). Basically, the return value of any given recursive step is the same as the return value of the next recursive call.

The consequence of this is that once you are ready to perform your next recursive step, you don't need the current stack frame any more. This allows for some optimization. In fact, with an appropriately written compiler, you should never have a stack overflow snicker with a tail recursive call. Simply reuse the current stack frame for the next recursive step. I'm pretty sure Lisp does this.

ざっくり日本語で言うと、

1. 普通に再帰を書くと、再帰して呼び出した結果を利用して、値を計算するという流れになる。
2. 末尾再帰では、一番最後に自身を再帰する。最初に計算をして、その値を呼び出し先に伝えるという手法を取る。
3. 末尾再帰を用いると、現在使用しているスタック構造をそのまま再帰呼び出し先で再利用することができ、スタックの節約ができる。

3.は末尾再帰の最適化と呼ばれているそうです。実際は、再帰が繰り返しループに置換されるみたい。末尾再帰の恩恵を受けるには、この最適化機能が使用する言語で提供されているかどうかが肝になるみたい。

とりあえず、言葉の説明はこの程度にしておいて、いつものようにサンプルコードを。

int factorial(int n) {
  if (!n)
      return 1;
  return n * factorial(n-1);
}

上のコードは階乗を求めるソースです。普通は、上のように書くでしょう。。

これは、factorial(n-1)の値を求めて、それにnをかけてreturnするという形になっています。つまり再帰呼び出しの結果を用いて計算を実施したのち、returnという形です。

計算されるイメージはこんな感じ。

factorial(5)

5*factorial(4)

5*(4*factorial(3))

5*(4*(3*factorial(2)))

5*(4*(3*(2*factorial(1))))

5*(4*(3*(2*1)))

これに対して、末尾再帰。

int factorial2(int n, int acc=1) {
   if (!n)
       return acc;
   return factorial2(n-1, n*acc);
}

かるく衝撃を覚えるほどのソースコードです。returnするときには、現在の関数のスタックは必要じゃなくなってますね。。ちょっと動的計画を彷彿とさせるような感じですが。。

この場合の計算イメージはこんな感じです。

factorial2(5,1)

factorial2(4,5)

factorial2(3,20)

factorial2(2,60)

factorial2(1,120)

factorial2(0,120)

末尾再帰の場合は、最後に呼び出された関数の戻り値が答えになります。それぞれの関数は自分の役割を終えたら、後は呼び出し先に任せるよ。ってイメージです。

逆に普通の再帰の場合は、最初に呼ばれた関数の戻り値が答えになります。

それぞれの関数は、自分の仕事を部下に任せるんですが、部下が仕事を終えるのをずっと待っていなくてはなりません。一番上の関数は、部下の部下の部下の・・・・部下の仕事が終って、自分のところまで結果が戻ってくるのを待たないといけないわけですね。。これは大変。（面倒くさそう。。日本のソフト開発の主流であるウォータフォールモデルみたい。。）

残念ながら、私が使用しているC++環境では末尾再帰の最適化はサポートされていないようです。末尾再帰を使って書いた関数（総和を求める関数）でもスタックオーバーを起こしました。。

引用サイト：　http://stackoverflow.com/questions/33923/what-is-tail-recursion

Emacs 入門（２）

前回に引き続き、emacs入門。

今回は、

①ソースコード作成

②コンパイル

③実行

をemacs上でやる方法について整理します。

①ソースコード作成

これは、簡単。

コマンドラインから、「emacs ファイル名」を実行すれば、指定されたファイル名でファイルを編集できます。

保存は、「C-x s」

閉じるは、「C-x C-c」

です。「saveのs」と「closeのc」ですね。

②コンパイル

emacs上でコンパイルができます。

「M-x compile」

と打つと、コンパイルのコマンドを入力できます。makefileがあれば、「make -k」と入力しましょう。

③実行

なんと、実行もemacs上で出来ます。ここまで出来ると単なるエディタではなくて統合開発環境に近い気がします。デバッガも起動できるみたいです。

とりあえず、実行は、「M-x shell」とすればよいです。

すると、コマンドラインが現れます。そこで、いつもやってるように、「./exeファイル名」とすれば実行できます。（emacs画面に表示されるコマンドライン上では、lsやgrepなどのコマンドも使えます。）

プログラミング実行の後、ソースコードに戻りたければ、「バッファ」（※参考サイト参照のこと）を切り替えればよいです。

「C-x b」とすると、ウィンドウに表示されるバッファを変更できます。

参考サイト

バッファとは？　http://cns-guide.sfc.keio.ac.jp/2000/4/2/1.html

Emacs 入門

最近（昨日から）、emacsを始めた。

大学１年生のときさわったことがあったが、当時の私はコンピュータアレルギーだったため、意味が全く分からず挫折。。

とりあえず、これだけ使えれば何とかなりそうなコマンドをまとめてみる。

C-は「ctrl」キーを押しながら

M-は「alt」キーを押しながら

という意味。

①C-x C-c 　　 ファイルを閉じる

②C-x C-s 　 ファイルを保存する

③M-x compile コンパイルを実行する

④C-x 2 画面を上と下に２分割する

⑤C-x 3 画面を左と右に２分割する

⑥C-x 1 分割をやめて、フォーカスのある画面だけを開く

⑦C-x o 画面分割時に他の画面にフォーカスを移す

⑧C-k １行削除する

取りあえず、これだけあれば何とかなるだろう。。コピペとかも必要そうだが。。

あと、.emacsというファイルにて初期設定ができるらしい。

このファイルがなければ、自分のホームディレクトリに作ればいいみたい。

とりあえず、下の２つを設定してみた。

①C/C++の予約語に色を付ける

②C/C++のインデントはタブ４つ分にする

以下、設定ファイル。

(global-font-lock-mode t)

(setq-default indent-tabs-mode nil)

(setq-default tab-width 4)

(add-hook 'c-mode-common-hook

'(lambda ()

(c-set-style "k&r")

(setq indent-tabs-mode t)

(setq c-basic-offset 4)

))

(setq auto-mode-alist

(append

'(("\\.c$" . c-mode))

'(("\\.h$" . c-mode))

'(("\\.cpp$" . c++-mode))

auto-mode-alist))

いろいろな距離概念

日常生活で距離というと、「ユークリッド距離」のことを指す。

他にもいろいろと距離があるので、代表的な3つの距離をまとめてみる。

1. ユークリッド距離
2. マンハッタン距離
3. チェビシェフ距離

まずは、「ユークリッド距離」について。

n次元空間中の2点x, yのユークリッド距離は次のように表される。

これは、ベクトル空間でいう距離や３次元空間における一般的な距離と同じである。

次に、マンハッタン距離。

同じく2点x,yの距離を式で表すとこんなかんじ。

これは、マンハッタンのようなブロックで区画されたまちにおいて、北に○ブロック、西に×ブロック移動した言われた場合に、移動しなければいけないブロックの数を表す。

最後に、チェビシェフ距離。

同じく式で。

これは、あんまり日常生活では使われない。

斜めに移動するという概念を縦横に移動するのと同じと考えた距離概念である。

たとえば、チェスでルークは斜め方向に4移動する場合、縦横二回にわけてそれぞれ4マス移動しなければならない。（マンハッタン距離=4+4=8）

これに対して、クイーンなら一気に斜めに移動できる。（チェビシェフ距離=4）

最後に、それぞれの距離概念において、原点から等距離にある点を結んだ場合にできる線を下図に示す。

赤：チェビシェフ距離

青：ユークリッド距離

緑：マンハッタン距離

である。

ビットDPにチャレンジ

今日は、最近よく解いているビットDPについて。

その名のとおりビット演算を用いた動的計画法。

一番分かりやすい例として循環セールスマン問題を考えます。

セールスマンが、営業所を出発し、n個の都市をまわり、営業所に帰ってくる。

n個の都市を最適な順番でまわったとき、どれくらい時間がかかるか？

以下、n個の都市をa,b,c,・・として考えます。

まず、簡単に思いつく解法は全件探索。

a,b,c,d,・・・

a,b,d,c,・・・

a,c,b,d,・・・

・・・・・

とpermutationで探索すると答えはでます。しかし、階乗オーダーとなるため、現実的ではありません。

ここで、

”ある都市から営業所に戻るまでの最短距離は、それまでにどの都市を訪問したかに依存するが、その都市をどの順番で回ったかには依存しない”

ということに気付けばDPが適用できます。

つまり、これまでに辿った経路が

a,b,c,dだろうが、

b,c,a,dだろうが、

c,a,b,dだろうが、

これから先のdから営業所までの最短距離は同じです。

これは、俗に言う「Principle of Optimality」ってやつですね。これでDPが適用できます。

あとは、どの都市を回ったかを覚えておけばいいのですが、これをビットを使って記憶します。

これで、ビットDPの完成です。

例題を解いてみましょう。

http://poj.org/problem?id=2907

typedef pair<int, int>point;
point beeper[12];
int network[12][12];
int dp[12][1<<12];
int n;

void tsp(int p, int bit) {
   if (bit+1 == 1<<n+1)
       return;

   REP(i, n+1) {
       if (bit >> i & 1) continue;
       int mask = bit | (1 << i);
       if (!i && mask != (1<<n+1)-1) continue;

       if (dp[i][mask] > dp[p][bit] + network[p][i]) {
           dp[i][mask] = dp[p][bit] + network[p][i];
           tsp(i, mask);
       }
   }
}


int main() {
   int sc, xsize, ysize;
   int x, y;

   cin >> sc;
   while (sc--) {
       cin >> xsize >> ysize;
       cin >> x >> y;
       beeper[0] = point(--x, --y);
       cin >> n;

       REP(i, n) {
           cin >> x >> y;
           beeper[i+1] = point(--x, --y);
       }

       REP(i, n+1)REP(j, n+1)
           network[i][j] = ABS(beeper[i].first - beeper[j].first)
               + ABS(beeper[i].second - beeper[j].second);

       REP(i,n+1)REP(j, 1<<n+1)
           dp[i][j] = INF;
       dp[0][0] = 0;
       tsp(0, 0);

       cout << "The shortest path has length " << dp[0][(1<<n+1)-1] << endl;
   }

   return 0;
}

tspの部分は、最後に0に戻ってくるような形にしたくて、ちょっとスパゲッティ気味です。。

よく考えると、以下のコードでOKです。。。

void tsp(int p, int bit) {
    REP(i, n+1) {
        if (bit >> i & 1) continue;
        int mask = bit | (1 << i);
        if (dp[i][mask] > dp[p][bit] + network[p][i]) {
            dp[i][mask] = dp[p][bit] + network[p][i];
            tsp(i, mask);
        }
    }
}

注意）但し、ビットDPでも指数オーダーなので、この方法で解けるのはnが小さい場合のみ。