C++でsplit

最近、C/C++でもJavaのsplit()相当の標準関数があることを知った。

strtok()という関数。

以下のように使う。

view plainprint?

1. int main() {  
2.     char str[] = ":blue:red:yellow:black:";  
3.   
4.     char *p = strtok(str, ":");  
5.   
6.     while (p != NULL) {  
7.         printf("[%s]\n", p);  
8.         p = strtok(NULL, ":");  
9.     }  
10.   
11.     return 0;  
12. }  

int main() {
    char str[] = ":blue:red:yellow:black:";

    char *p = strtok(str, ":");

    while (p != NULL) {
        printf("[%s]\n", p);
        p = strtok(NULL, ":");
    }

    return 0;
}

　　char *p = strtok(分割対象文字列のアドレス, 分割文字);

のように使います。

但し、2回目以降は、

　　char *p = strtok(NULL, 分割文字);

とします。

　NULLを指定することで、前に検索し終わった部分の次の文字列から検索を再開します。ちょっと変な仕様ですが、クラスをサポートしていないCの名残のような感じがします。

stringに対して同じことをしたい場合は、c_str()メンバ関数で一旦(const char *)に変換してから上記関数を使うといいです。

ビットをカウントするアルゴリズム

最近、1であるビットをカウントする面白い方法を知った。4つほど例を示す。

1. 普通に全ビットをトラバースする
2. non-zero LSBを消してい
3. 半分ずつに畳みこむ
4. gccの標準関数を使う

以下にそれぞれソースを示す。今回は、32ビット長intに対してビットをカウントすることにする。

まず、普通にstraightforwardな方法で1のビット数を数える方法。

view plainprint?

1. int popcount1(int x) {  
2.  int ret = 0;  
3.   
4.  for (int i = 0; i < 32; i++)  
5.      ret += x >> i & 1;  
6.   
7.  return ret;  
8. }  

int popcount1(int x) {
 int ret = 0;

 for (int i = 0; i < 32; i++)
     ret += x >> i & 1;

 return ret;
}

速度を求められない普通の処理なら上でもいいかもしれないです。次に、non-zero LSBを潰していく方法。これはかなり賢いやり方だと思います。

view plainprint?

1. int popcount2(int x) {  
2.  int ret = 0;  
3.   
4.  while (x) {  
5.      x &= x-1;  
6.      ++ret;  
7.  }  
8.   
9.  return ret;  
10. }  

int popcount2(int x) {
 int ret = 0;

 while (x) {
     x &= x-1;
     ++ret;
 }

 return ret;
}

次に畳みこみながらビットを一か所に寄せて行くやり方。最初みたとき意味不明でした。。これも賢い。。

view plainprint?

1. int popcount3(int x) {  
2.  x = (x & 0x55555555) + (x >> 1 & 0x55555555);  
3.  x = (x & 0x33333333) + (x >> 2 & 0x33333333);  
4.  x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);  
5.  x = (x & 0x00FF00FF) + (x >> 8 & 0x00FF00FF);  
6.  x = (x & 0x0000FFFF) + (x >> 16 & 0x0000FFFF);  
7.   
8.  return x;  
9. }  

int popcount3(int x) {
 x = (x & 0x55555555) + (x >> 1 & 0x55555555);
 x = (x & 0x33333333) + (x >> 2 & 0x33333333);
 x = (x & 0x0F0F0F0F) + (x >> 4 & 0x0F0F0F0F);
 x = (x & 0x00FF00FF) + (x >> 8 & 0x00FF00FF);
 x = (x & 0x0000FFFF) + (x >> 16 & 0x0000FFFF);

 return x;
}

最後に、gccの標準関数。
　　unsigned int = __builtin_popcount(unsigned int);

はい、いろいろあります。じつは、1のstraightforwardなアルゴリズムは、32bit操作ではなく、毎回1右シフトさせて0になったらやめるというやり方をすれば、かなり速くなります。（私の環境では2.のアルゴリズムとほとんど変わりませんでした・・・・）

以下、10000000までの数値に対して、各関数をまわした場合の処理時間です。

Function Name		Elapsed Time[s]
popcount1		10.31
popcount2		0.65
popcount3		2.35
__builtin_popcount		0.84

popcount3は、ソース長いくせに余り速くないという悲しい結果になりました。いろいろな値が使用されているため、それをレジスタに登録するのに時間を食っているのではないかという考察をしました。

知ってると便利なSTL(7) bitset

C++のSTL紹介第７弾。

今日のは、かなり便利です。その名もbitset。

名前のとおり10進数を2進数に変換してくれます。

使い方は、 bitset<ビット長>(数値)とするだけ。

自分で作らなくても、c++標準関数に二進数変換機能があったんですねー@_@

以下、ビット演算でいろいろやってます。

基本的なものが多いですが、最後に書いてるn & -nは、なかなかマニアックです。（アルゴリズマーにとっては、常識の範疇？？）

n & -nでnのnon-zero LSBが取れます！

view plainprint?

1. #include <bitset>  
2.   
3. int main() {  
4.   
5.    int a = 20004;  
6.   
7.    // high 7 and 8 bits  
8.    int mask = 1 << 8 | 1 << 7;  
9.    cout << bitset<16>(a) << endl;  
10.    cout << bitset<16>(a | mask) << endl << endl;  
11.   
12.    // low 9 and 10 bits  
13.    mask = 1 << 9 | 1 << 10;  
14.    cout << bitset<16>(a) << endl;  
15.    cout << bitset<16>(a & ~mask) << endl << endl;  
16.   
17.    // flip 0 and 1 bits  
18.    mask = 1 << 0 | 1 << 1;  
19.    cout << bitset<16>(a) << endl;  
20.    cout << bitset<16>(a ^ mask) << endl << endl;  
21.   
22.    // the leaset significant non-zero bit  
23.    cout << bitset<16>(a) << endl;  
24.    cout << bitset<16>(-a) << endl;  
25.    cout << bitset<16>(a&-a) << endl;  
26.   
27.    return 0;  
28. }  

#include <bitset>

int main() {

   int a = 20004;

   // high 7 and 8 bits
   int mask = 1 << 8 | 1 << 7;
   cout << bitset<16>(a) << endl;
   cout << bitset<16>(a | mask) << endl << endl;

   // low 9 and 10 bits
   mask = 1 << 9 | 1 << 10;
   cout << bitset<16>(a) << endl;
   cout << bitset<16>(a & ~mask) << endl << endl;

   // flip 0 and 1 bits
   mask = 1 << 0 | 1 << 1;
   cout << bitset<16>(a) << endl;
   cout << bitset<16>(a ^ mask) << endl << endl;

   // the leaset significant non-zero bit
   cout << bitset<16>(a) << endl;
   cout << bitset<16>(-a) << endl;
   cout << bitset<16>(a&-a) << endl;

   return 0;
}

追記：

メンバ関数to_string()を使えば、対応するString型をえることができます。

string x = bitset<16>(a&-a).to_string();

のようにすればよいです。

関数ポインタをどう使うか

初めて、Cで関数ポインタを勉強したとき、

「は？？何これ？どこで使うの？」って感じでした。

今日、SRMで関数ポインタを使えそうな問題を見つけました。。

個人的な見解としては、関数ポインタを使うのは、配列などのコンテナに対して一括して処理を反映させたいときだと思います。

考えてみると、関数型言語の第一級関数を使ってやっていることを思い出せば良い気がします。

map、filter、reduceなど。

まー、何はともあれ例題を見てみましょう。以下のようなことをしたいとします。

view plainprint?

1. int ck1(int a, int b) {  
2.   return a;  
3. }  
4.   
5. int ck2 (int a, int b) {  
6.   return b;  
7. }  
8.   
9. int ck3(int a, int b) {  
10.   return a<b?a:b;  
11. }  
12.   
13. int ck4(int a, int b) {  
14.   return a<b?b:a;  
15. }  
16.   
17. int main() {  
18.   vector<int>A, B, wanted;  
19.   
20.   A.push_back(1);  
21.   A.push_back(2);  
22.   A.push_back(3);  
23.   A.push_back(4);  
24.   
25.   B.push_back(4);  
26.   B.push_back(3);  
27.   B.push_back(2);  
28.   B.push_back(1);  
29.   
30.   wanted.push_back(1);  
31.   wanted.push_back(2);  
32.   wanted.push_back(2);  
33.   wanted.push_back(1);  
34.   
35.   bool ck = true;  
36.   int sz = A.size();  
37.   
38.   // func1  
39.   REP(i, sz)  
40.       if (ck1(A[i], B[i]) != wanted[i])  
41.           ck = false;  
42.   if (ck)  
43.       cout << "ck1 holds" << endl;  
44.   
45.   // func2  
46.   ck = true;  
47.   REP(i, sz)  
48.       if (ck2(A[i], B[i]) != wanted[i])  
49.           ck = false;  
50.   if (ck)  
51.       cout << "ck2 holds" << endl;  
52.   
53.   // func3  
54.   ck = true;  
55.   REP(i, sz)  
56.       if (ck3(A[i], B[i]) != wanted[i])  
57.           ck = false;  
58.   if (ck)  
59.       cout << "ck3 holds" << endl;  
60.   
61.   // func4  
62.   ck = true;  
63.   REP(i, sz)  
64.       if (ck4(A[i], B[i]) != wanted[i])  
65.           ck = false;  
66.   if (ck)  
67.       cout << "ck3 holds" << endl;  
68. }  

int ck1(int a, int b) {
  return a;
}

int ck2 (int a, int b) {
  return b;
}

int ck3(int a, int b) {
  return a<b?a:b;
}

int ck4(int a, int b) {
  return a<b?b:a;
}

int main() {
  vector<int>A, B, wanted;

  A.push_back(1);
  A.push_back(2);
  A.push_back(3);
  A.push_back(4);

  B.push_back(4);
  B.push_back(3);
  B.push_back(2);
  B.push_back(1);

  wanted.push_back(1);
  wanted.push_back(2);
  wanted.push_back(2);
  wanted.push_back(1);

  bool ck = true;
  int sz = A.size();

  // func1
  REP(i, sz)
      if (ck1(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck1 holds" << endl;

  // func2
  ck = true;
  REP(i, sz)
      if (ck2(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck2 holds" << endl;

  // func3
  ck = true;
  REP(i, sz)
      if (ck3(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck3 holds" << endl;

  // func4
  ck = true;
  REP(i, sz)
      if (ck4(A[i], B[i]) != wanted[i])
          ck = false;
  if (ck)
      cout << "ck3 holds" << endl;
}

vector A, B, wantedのすべての要素が与えられた関数に対して条件を満たしているかどうかをしらべています。でも上のソースコードは明らかに冗長です。SRMのときは時間勝負だったので上のような実装をしました（汗）

関数ポインタを使って書き直してみます。

view plainprint?

1. bool check(vector<int>A, vector<int>B, vector<int>wanted, int (*func)(int, int)) {  
2.    int sz = A.size();  
3.   
4.    REP(i, sz)  
5.        if (func(A[i], B[i]) != wanted[i])  
6.            return false;  
7.   
8.    return true;  
9. }  
10.   
11. int main() {  
12.    vector<int>A, B, wanted;  
13.   
14.    A.push_back(1);  
15.    A.push_back(2);  
16.    A.push_back(3);  
17.    A.push_back(4);  
18.   
19.    B.push_back(4);  
20.    B.push_back(3);  
21.    B.push_back(2);  
22.    B.push_back(1);  
23.   
24.    wanted.push_back(1);  
25.    wanted.push_back(2);  
26.    wanted.push_back(2);  
27.    wanted.push_back(1);  
28.   
29.    if (check(A, B, wanted, ck1))  
30.        cout << "ck1 holds" << endl;  
31.    if (check(A, B, wanted, ck2))  
32.        cout << "ck2 holds" << endl;  
33.    if (check(A, B, wanted, ck3))  
34.        cout << "ck3 holds" << endl;  
35.    if (check(A, B, wanted, ck4))  
36.        cout << "ck4 holds" << endl;  
37. }  

bool check(vector<int>A, vector<int>B, vector<int>wanted, int (*func)(int, int)) {
   int sz = A.size();

   REP(i, sz)
       if (func(A[i], B[i]) != wanted[i])
           return false;

   return true;
}

int main() {
   vector<int>A, B, wanted;

   A.push_back(1);
   A.push_back(2);
   A.push_back(3);
   A.push_back(4);

   B.push_back(4);
   B.push_back(3);
   B.push_back(2);
   B.push_back(1);

   wanted.push_back(1);
   wanted.push_back(2);
   wanted.push_back(2);
   wanted.push_back(1);

   if (check(A, B, wanted, ck1))
       cout << "ck1 holds" << endl;
   if (check(A, B, wanted, ck2))
       cout << "ck2 holds" << endl;
   if (check(A, B, wanted, ck3))
       cout << "ck3 holds" << endl;
   if (check(A, B, wanted, ck4))
       cout << "ck4 holds" << endl;
}

だいぶすっきりしました。

関数4つまわしているのがちょっとカッコ悪いので、配列にしてみます。

関数ポインタも配列に格納することができます。

view plainprint?

1. int main() {  
2.     vector<int>A, B, wanted;  
3.   
4.     A.push_back(1);  
5.     A.push_back(2);  
6.     A.push_back(3);  
7.     A.push_back(4);  
8.   
9.     B.push_back(4);  
10.     B.push_back(3);  
11.     B.push_back(2);  
12.     B.push_back(1);  
13.   
14.     wanted.push_back(1);  
15.     wanted.push_back(2);  
16.     wanted.push_back(2);  
17.     wanted.push_back(1);  
18.   
19.     int (*funcs[4])(int, int) = {ck1, ck2, ck3, ck4};  
20.     string funcName[] = {"ck1", "ck2", "ck3", "ck4"};  
21.   
22.     REP(i, SIZE(funcs)) {  
23.         if (check(A, B, wanted, funcs[i]))  
24.             cout << funcName[i] << " holds" << endl;  
25.     }  
26.   
27. }  

int main() {
    vector<int>A, B, wanted;

    A.push_back(1);
    A.push_back(2);
    A.push_back(3);
    A.push_back(4);

    B.push_back(4);
    B.push_back(3);
    B.push_back(2);
    B.push_back(1);

    wanted.push_back(1);
    wanted.push_back(2);
    wanted.push_back(2);
    wanted.push_back(1);

    int (*funcs[4])(int, int) = {ck1, ck2, ck3, ck4};
    string funcName[] = {"ck1", "ck2", "ck3", "ck4"};

    REP(i, SIZE(funcs)) {
        if (check(A, B, wanted, funcs[i]))
            cout << funcName[i] << " holds" << endl;
    }

}

おー、結構きれいになりましたね。。

アルゴリズム競技のコンテストで、実装の勉強ができるなんて思ってませんでした。恐るべしTopCoder。。

知ってると便利なSTL(6) count

STL勉強シリーズ6回目。

今回はcountについて。その名の通り、コンテナに格納されている特定の要素の数を数えます。

使い方としては、以下の3つくらいでしょうか。

1. ベクトルの中に、目的の要素はいくつあるか数える
2. 文字列の中に、目的の文字はいくつあるか数える
3. 配列の中に、目的の要素はいくつあるか数える

それぞれ、サンプルソースを載せておきます。

view plainprint?

1. int main () {  
2.     vector<int> nums;  
3.   
4.     for (int i = 0; i < 100; i++)  
5.         nums.push_back(rand()%10);  
6.   
7.     for (int i = 0; i < 10; i++)  
8.         cout << count(nums.begin(), nums.end(), i) << endl;  
9.   
10.     return 0;  
11. }  

int main () {
    vector<int> nums;

    for (int i = 0; i < 100; i++)
        nums.push_back(rand()%10);

    for (int i = 0; i < 10; i++)
        cout << count(nums.begin(), nums.end(), i) << endl;

    return 0;
}

view plainprint?

1. int main () {  
2.     string name = "tanaka tarou";  
3.   
4.     cout << count(name.begin(), name.end(), 'a') << endl;  
5.   
6.     return 0;  
7. }  

int main () {
    string name = "tanaka tarou";

    cout << count(name.begin(), name.end(), 'a') << endl;

    return 0;
}

view plainprint?

1. int main () {  
2.     double x[] = {0.0, 0.1, 0.14, 0.0, 0.3, 0.6};  
3.     int sz = sizeof(x) / sizeof(double);  
4.   
5.     cout << count(x, x+sz, 0.0) << endl;  
6.   
7.     return 0;  
8. }  

int main () {
    double x[] = {0.0, 0.1, 0.14, 0.0, 0.3, 0.6};
    int sz = sizeof(x) / sizeof(double);

    cout << count(x, x+sz, 0.0) << endl;

    return 0;
}

PKU 250問クリア

昨年の夏からずっとやっているPKU。

ようやく、250問ACした。

今年の目標は300問達成だが、おそらくこのペースだと達成できそう。

最近解いた問題で面白かったのは、

Trie木を使った問題　 ： http://poj.org/problem?id=2001

オイラー路の問題　　 ： http://poj.org/problem?id=1300

でしょうか。

新しいデータ構造やアルゴリズムを学びました。

そろそろ、

• 最大フロー
• マッチング

あたりに手を出したいところ。

　あとは、そろそろTopCoder div.2を出たい。。多分出場回数を増やせば上がれるはず。codeforceはorange coderに上がりたいところ。。

Trie木による文字検索

最近、Trie木という面白いデータ構造を知った。

文字列を登録して、その文字が存在するかどうかを調べる場合、ハッシュやブルームフィルターなどが考えられる。

しかし、ハッシュは衝突が頻繁におこると最悪計算量がO(N)まで悪化する。（Nはキーの数。）

ブルームフィルターは高速に登録、判定ができるが、擬陽性があるため厳密なチェックに使うには抵抗がある。

Trie木は、論理上ハッシュと同等の速度で文字列処理ができ（実際はTrie木の方が速い）、ブルームフィルターのような偽検出もない。

ということで、Trie木を使いましょう。

Spaghetti sourceに実装があります。

http://www.prefield.com/algorithm/string/trie.html

短くてシンプルだけど、凡人の私には理解するのに少し時間がかかりました。。（汗）

自分でかいたソースは以下。

view plainprint?

1. class Trie {  
2. public:  
3.     Trie *next[26];  
4.   
5.     Trie () {  
6.         fill(next, next+26, (Trie *)0);  
7.     }  
8.   
9.     void insert(char *s) {  
10.         if (*s == '\0') return;  
11.         if (this->next[*s-'a'] == NULL)  
12.             this->next[*s-'a'] = new Trie();  
13.         this->next[*s-'a']->insert(s+1);  
14.     }  
15.   
16.     bool find(char *s) {  
17.         if (*s == '\0') return true;  
18.         if (this->next[*s-'a'] == NULL)  
19.             return false;  
20.         return this->next[*s-'a']->find(s+1);  
21.     }  
22. };  

class Trie {
public:
    Trie *next[26];

    Trie () {
        fill(next, next+26, (Trie *)0);
    }

    void insert(char *s) {
        if (*s == '\0') return;
        if (this->next[*s-'a'] == NULL)
            this->next[*s-'a'] = new Trie();
        this->next[*s-'a']->insert(s+1);
    }

    bool find(char *s) {
        if (*s == '\0') return true;
        if (this->next[*s-'a'] == NULL)
            return false;
        return this->next[*s-'a']->find(s+1);
    }
};

TopCoder Marathon Match Local Tester

Marathon Matchのローカルテスターを作った。

TopCoderのサーバーでテストすることは出来るのだが、

• 2時間に1回しかサーバーでテストできない。（Example testの場合は、15分に1回）
• queueに人が溜まっていると待たないといけない
• 採点されるテストケースは、Full Submit Testのテストケースより多い

の理由からローカルで自動テストスクリプトを作って走らせる人が多いようだ。

昨年のTCOで作ったはずだが、どこかに行ってしまったので今日作った。今度はどこかに行ってしまわないようにブログにあげておく。

テストを走らせる処理は、windowsのバッチスクリプト

テスト結果のパースはperlで書きました。

ローカルマシンよりTopcoderサーバーの方が断然早いのでTime Limitについては何らかの補正が必要か？？

view plainprint?

1. @ECHO OFF  
2.   
3. echo System Test Starts..  
4.   
5. :: set variables  
6. SET MAX_SEED=100  
7. SET SEED=0  
8. SET OUTPUT=%1.txt  
9.   
10. :: solve problems  
11. :LOOP  
12. echo Solving #%SEED% ....  
13. IF %SEED%==0 echo SEED = %SEED% > %OUTPUT%  
14. IF NOT %SEED%==0 echo SEED = %SEED% >> %OUTPUT%  
15.   
16. java -jar hogehogeVis.jar -exec "hogehoge.exe" -seed %SEED% -novis >> %OUTPUT%  
17.   
18. SET /A SEED=%SEED%+1  
19. IF %SEED%==%MAX_SEED% GOTO LOOPEND  
20. GOTO LOOP  
21.   
22. :LOOPEND  
23. echo System Test Ends!  
24. echo -----------------------  
25. echo [Overall Result]  
26. perl parse.pl %1  

@ECHO OFF

echo System Test Starts..

:: set variables
SET MAX_SEED=100
SET SEED=0
SET OUTPUT=%1.txt

:: solve problems
:LOOP
echo Solving #%SEED% ....
IF %SEED%==0 echo SEED = %SEED% > %OUTPUT%
IF NOT %SEED%==0 echo SEED = %SEED% >> %OUTPUT%

java -jar hogehogeVis.jar -exec "hogehoge.exe" -seed %SEED% -novis >> %OUTPUT%

SET /A SEED=%SEED%+1
IF %SEED%==%MAX_SEED% GOTO LOOPEND
GOTO LOOP

:LOOPEND
echo System Test Ends!
echo -----------------------
echo [Overall Result]
perl parse.pl %1

view plainprint?

1. open(INPUT, "<" . $ARGV[0] . ".txt");  
2.   
3. @list = <INPUT>;  
4.   
5. $pointSum = 0;  
6. $timeOver = 0;  
7.   
8. foreach $line( @list ) {  
9.     if ($line =~ /(^Time)/) {  
10.         $line =~ /([0-9\.]+)/;  
11.         $time = $1;  
12.         if ($time > 10) {  
13.             $timeOver++ ;  
14.         }  
15.     }  
16.     elsif ($line =~ /^Score/) {  
17.         $line =~ /([0-9\.]+)/;  
18.         $point = $1;  
19.          
20.         $pointSum += $point  
21.     }  
22. }  
23.   
24. print "Point: " . $pointSum . "\n";  
25. print "Time Over: " . $timeOver . "\n";  

open(INPUT, "<" . $ARGV[0] . ".txt");

@list = <INPUT>;

$pointSum = 0;
$timeOver = 0;

foreach $line( @list ) {
    if ($line =~ /(^Time)/) {
        $line =~ /([0-9\.]+)/;
        $time = $1;
        if ($time > 10) {
            $timeOver++ ;
        }
    }
    elsif ($line =~ /^Score/) {
        $line =~ /([0-9\.]+)/;
        $point = $1;
       
        $pointSum += $point
    }
}

print "Point: " . $pointSum . "\n";
print "Time Over: " . $timeOver . "\n";

MAX_SEEDは、TopCoder上のFull Submissionでは100、System Testでは1000くらいだと思う。

Haskell勉強記（5）

またまたまたHaskell。

今日はモナドについて書こうと思う。

1. モナドの概念
2. 物理的には（実体は）何なの？
3. 代表的なモナド

という切り口でモナドについてまとめてみる。

モナドの概念

　モナドでやりたいことは、”複数の演算をつなぐこと”である。具体的には、

• まず○○をして、そのあと××をしたい。（処理の順序付けをする）
• ○○をして、失敗したら××はしない。（Cのforループのbreakのような処理）

とかである。

　”参照透過性を保ちつつ、副作用を導入する”のがモナドという内容をよく見るが、これはモナドの概念とは異なる。上記は、IOモナドの機能であって、一般的なモナドの機能ではない。

物理的には（実体は）何なの？

　モナドとは、モナド型クラスのインスタンスである。モナド型クラスは、

• return
• >>=

のクラスメソッドをもっていて、この２つの演算は”モナド則”を満たす。

つまり、return、>>=が実装されていて、その実装がモナド則と呼ばれる法則を見てしていれば、それはモナド。

　難しい話は置いといて、モナドは一言でいうと”モナド型クラスが持つ機能を実装した型”のこと。

　演算子（>>=）の型は以下のとおり。

>>= :: m a -> (a -> m b) -> m b

①モナドの型に入ったaが与えられる。

②そこから、aを取り出して、aをbに変換。モナドで包む。

というイメージ。これは、入れ子のalistに対して関数lookupを適用する例を見ると分かりやすい。

代表的なモナド

　以下に代表的なモナドをあげる。

• Maybeモナド
• IOモナド
• リストモナド

　Maybeは、alistの検索など、データが存在するか、存在しないか分からない処理を格納する。

　IOは、putStrとかgetContentsとか。アクションとは、IOモナドの別名らしい。参照透明性を確保しつつ、副作用を持たせたい場合は、IOモナドが使われます。標準入出力の他にも乱数とかシステム日時取得など。

　リストモナドは、リストを扱うためのモナド。リストモナドの目的は、”適用するたびに値の数が増減する関数を連結すること。”

参考文献に分かりやすいサンプルコードがたくさん載ってるので、「モナドって何？」ていう最低レベルのことは理解できると思います。

参考文献：

『ふつうのHaskellプログラミング ふつうのプログラマのための関数型言語入門』

memset()の有効活用

前にも書いたが、memset()は初期化時に重宝する。

今日、ある問題を解いていたときに、3次元配列の初期化に遭遇した。

しかも、0ではなく、INF（比較的大きな数字）に初期化したい。

どうしたものか。。

　まず、やったのが、fill()。

view plainprint?

1. int main() {  
2.  int x[10][10][10];  
3.   
4.  fill(x, x+10, INF);  
5.  cout << x[0][0][0] << endl;  
6. }  

int main() {
 int x[10][10][10];

 fill(x, x+10, INF);
 cout << x[0][0][0] << endl;
}

ダメだった。なぜ。。3次元だけど、メモリは縦に連続して展開されるんじゃないの？？

同様にfill_n()も撃沈。

view plainprint?

1. int main() {  
2.   int x[10][10][10];  
3.   
4.   fill_n(x, 10*10*10, INF);  
5.   cout << x[0][0][0] << endl;  
6. }  

int main() {
  int x[10][10][10];

  fill_n(x, 10*10*10, INF);
  cout << x[0][0][0] << endl;
}

ま、マジか。。。

　仕方ないので、愚直にループを書く。

view plainprint?

1. int main() {  
2.  int x[10][10][10];  
3.   
4.  REP(i, 10) REP(j, 10) REP(k, 10) x[i][j][k] = INF;  
5.  cout << x[0][0][0] << endl;  
6. }  

int main() {
 int x[10][10][10];

 REP(i, 10) REP(j, 10) REP(k, 10) x[i][j][k] = INF;
 cout << x[0][0][0] << endl;
}

んー、ちょっとダサいなー。

ちょっと考えてmemset()で行けるのではと気付く。

memset()は2進数・byte単位で初期化するので、大きな数にセットしようとして、

view plainprint?

1. int main() {  
2.   int x[10][10][10];  
3.   
4.   memset(x, 0xFF, sizeof(x));  
5.   cout << x[0][0][0] << endl;  
6. }  

int main() {
  int x[10][10][10];

  memset(x, 0xFF, sizeof(x));
  cout << x[0][0][0] << endl;
}

とするのはNG。これでは、すべての要素が-1にセットされます。（2の補数ですね。）

大きい数なら、0x7Fがいいでしょう。

しかし、INF + INF < INT_MAX（アルゴリズムコンテストの問題を解いていると、こういう条件を満たしたいことがしばしばありますよね！）を満たす範囲でなるべく大きいINFにセットしたい場合は、

0x3Fが妥当でしょう。

view plainprint?

1. int main() {  
2.    int x[10][10][10];  
3.   
4.    memset(x, 0x3F, sizeof(x));  
5.    cout << x[0][0][0] << endl;  
6. }  

int main() {
   int x[10][10][10];

   memset(x, 0x3F, sizeof(x));
   cout << x[0][0][0] << endl;
}

ちなみに、上記の値は、十進数で”1061109567”です。

Haskell勉強記（4）

またまたHaskell。

今日のテーマは以下。

1. guard
2. case expression

これが使えれば、それっぽいHaskellのコードが書ける（気がする。）

まずは、guardから。

guardは、パターンマッチに似ていますが、パターンマッチとは異なり任意の形で関数のマッチングができます。以下にguardを利用したfizz buzzを書きます。

view plainprint?

1. main = putStr $ unlines $ map fizzBuzz [1..100]  
2.         where fizzBuzz x  
3.                    | x `mod` 3 == 0 && x `mod` 5 == 0 = "fizz buzz"  
4.                    | x `mod` 3 == 0                   = "fizz"  
5.                    | x `mod` 5 == 0                   = "buzz"  
6.                    | otherwise                           = show x  

main = putStr $ unlines $ map fizzBuzz [1..100]
        where fizzBuzz x
                   | x `mod` 3 == 0 && x `mod` 5 == 0 = "fizz buzz"
                   | x `mod` 3 == 0                   = "fizz"
                   | x `mod` 5 == 0                   = "buzz"
                   | otherwise                           = show x

|と=の間がguardです。ここに条件式を書きます。上から順に操作され、trueとなったら式が対応する評価されます。otherwiseは、Preludeで定義されている式で、その値Trueだそうです。

次にcase expression。guardを使うと任意の式でパターンマッチができますが、引数に対する条件式（上の場合はx）に対する条件式しか書けません。

case expressionを使用すると、引数を成形したものに対してマッチングをかけることができます。fizz buzzを書くと下のようになります。

view plainprint?

1. main = putStr $ unlines $ map fizzBuzz [1..100]  
2.         where fizzBuzz x = case [x `mod` 3, x `mod` 5] of  
3.                             [0, 0]      -> "fizz buzz"  
4.                             [0, _]    -> "fizz"  
5.                             [_, 0]    -> "buzz"  
6.                             otherwise -> show x  

main = putStr $ unlines $ map fizzBuzz [1..100]
        where fizzBuzz x = case [x `mod` 3, x `mod` 5] of
                            [0, 0]      -> "fizz buzz"
                            [0, _]    -> "fizz"
                            [_, 0]    -> "buzz"
                            otherwise -> show x

最後に、以上をふまえて、3の倍数と3が付く数字のときだけアホになる関数を書きましょう。

view plainprint?

1. main = putStr $ unlines $ map nabeatsu [1 .. 100]  
2.         where  hasThree x = any (== '3') $ show x  
3.                nabeatsu x  
4.                 | x `mod` 3 == 0     = "aho" ++ " (" ++ (show x) ++ ")"  
5.                 | hasThree x         = "aho" ++ " (" ++ (show x) ++ ")"  
6.                 | otherwise            = show x  

main = putStr $ unlines $ map nabeatsu [1 .. 100]
        where  hasThree x = any (== '3') $ show x
               nabeatsu x
                | x `mod` 3 == 0     = "aho" ++ " (" ++ (show x) ++ ")"
                | hasThree x         = "aho" ++ " (" ++ (show x) ++ ")"
                | otherwise            = show x

今日はここまで。

SRM 503（div2） 参戦記

[結果]

Easy ：　やるだけ。

Middle: 頭の柔らかさが必要な問題。greedyかDPだろって思いこんで突き進んだ結果解けず。

Hard : MST。やるだけ。本番は開かず。。。

[反省]

1. 固定概念は捨てる。greedyかDPだろって思いこんだのが敗因。
2. 全体像を考える前に、まず例外パターンは捨てる。middleでいきなり汎用的な解法を考えようとしたが、例外パターン（-1となるパターン）を始めに切り捨てておけば、それ以外の答えが{1, 2}のどちらかしかないというのに気付けたはず。プログラムで深いネストをしないためには、例外を一番最初にcontinueすればいいが、同じようにアルゴリズムを考える上でも例外は最初に排除すべき。例外を排除することで見えてくる規則性があるのだから。
3. 次回からはHardも開くようにしよう。今回みたいに簡単な問題もあるので。。

[Rating]

1088 -> 1061

次回こそdiv1に返り咲く！うまく行かなかった回からは学ぶべきものが多いはずなので、しっかり分析して次に活かす。後はひたすら練習。

Haskell勉強記（3）

またまたHaskell。書きすぎ！？

今日は、

1. function composition
2. where clause
3. cons

について。

　function compositionは、その名のとおり合成関数です。f, g, hという関数がある場合、

　　　　f (g(h(x)))

は、Haskellでは、

　　　　f $ g $ h x

と書けます。また、function compositionを使用すれば、

(f . g . h ) x

と書けます。使いどころとしては、mapの第一引数に合成関数を使用したい場合でしょう。

　次にwhere 節について。where節は、関数の中で有効なローカル変数、関数を定義します。

以上をふまえて、まず、sin (x^2)を計算するプログラムを書きます。

view plainprint?

1. main = print $ map (sin . sq) [1..10]  
2.       where sq x = x * x  

main = print $ map (sin . sq) [1..10]
      where sq x = x * x

まあ、そのままですね。。

最後に、consについて。consは":"（コロン）のことです。パターンマッチの説明のときに出てきました。

a : x

とすると、要素aをリストxの先頭に追加することができます。

例えば、リスト[1,2,3,4,5]は、

　1:2:3:4:5:[]

と書けるわけです。（最後に[]が必要なことに注意！）

では、最後に自前のzip関数を定義してみます。奇数リストと偶数リストを生成してzipしてみましょう。

view plainprint?

1. main = print $ myZip [1, 3 .. 10] [2,4 .. 10]  
2.      where myZip         [] [] = []  
3.            myZip (x:xs) (y:ys) = (x,y) : myZip xs ys  

main = print $ myZip [1, 3 .. 10] [2,4 .. 10]
     where myZip         [] [] = []
           myZip (x:xs) (y:ys) = (x,y) : myZip xs ys

今日はここまで。

Haskell勉強記（2）

今日もHaskell。

今日は、昨日の復習とlambda expressionについて。

まず、昨日の復習として、

• map
• filter
• reduce

を自分で実装してみます。これを実現するためには、

1. Pattern match
2. tuple

を使えばいいです。

view plainprint?

1. myReduce     f [] = 0  
2. myReduce f (x:xs) = f x (myReduce f xs)  
3.   
4. myMap f []     = []  
5. myMap f (x:xs) = [f x] ++ (myMap f xs)  
6.   
7. myFilter f []    = []  
8. myFilter f (x:xs) = if f x  
9.                    then [x] ++ (myFilter f xs)  
10.                    else myFilter f xs  

myReduce     f [] = 0
myReduce f (x:xs) = f x (myReduce f xs)

myMap f []     = []
myMap f (x:xs) = [f x] ++ (myMap f xs)

myFilter f []    = []
myFilter f (x:xs) = if f x
                   then [x] ++ (myFilter f xs)
                   else myFilter f xs

まぁこんな感じでしょう。

そして、上記自前関数の引数にlambda式を使ってみましょう。

Haskellでは、lambda expressionは"\"(バックスラッシュ)と"->"(ハイフンと大なり記号)を用いて表されます。

view plainprint?

1. a = [1 .. 10]  
2. main = do print $ myMap (\x -> x*x) a  
3.          print $ myFilter (\x -> x `mod` 2 /= 0) a  
4.          print $ myReduce (\x y -> x+y) a  

a = [1 .. 10]
main = do print $ myMap (\x -> x*x) a
         print $ myFilter (\x -> x `mod` 2 /= 0) a
         print $ myReduce (\x y -> x+y) a

なんか、意味不明な記号が多くて若干pe○lみたいで嫌ですが。。

今日はここまで。

Haskell勉強記（1）

最近Haskellを勉強しています。

これからこまめにHaskellを勉強して、学んだ内容を公開していきます。

今日の内容は、

1. pattern match
2. list match
3. concatenation

です。

例題として、quick sortを書いてみます。

view plainprint?

1. a = [31, 10, 19, 90, 100, 1, 3, 4]  
2. qsort [] = []  
3. qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)  
4. main = print $ qsort a  

a = [31, 10, 19, 90, 100, 1, 3, 4]
qsort [] = []
qsort (x:xs) = qsort (filter (<x) xs) ++ [x] ++ qsort (filter (>=x) xs)
main = print $ qsort a

qsortの定義が2つありますが、これはpattern matchと呼ばれています。

C++では、引数の型や型の数によって関数の挙動を変えることができます。（overload）

Haskellの場合は、引数の値に応じて関数の戻り値を変えることができます。

次に、(x: xs)という表現に注目。

Haskellでは、リストを先頭部分とそれ以外に分解して表現することができます。

xがリストの先頭要素、xsはそれ以外です。

これも、一種のpattern matchと考えることができます。

filterに関しては、一般的な関数言語の機能なので割愛。

最後に++演算について。

これは、concatenationです。リストを連結します。

Haskellだと、quick sortがかなりシンプルに書けますね！

今日はここまで。

バグを出さないプログラムテクニック（1）

よくあるバグの代表例は、

• 無限ループ
• out of bounds 系エラー

あたりだろう。

これらのバグは、ちょっとした事を実践することで回避することができる。

それは、whileループの禁止である。

whileループを使うと、

• やたらと処理が複雑になったり、
• 条件式が偽にならず無限ループになったり、

と悪いことばかり。

大抵のwhileループは、forループで書けるので、whileは禁止してしまってもいいかと思う。

（あと余談だが、ショートコーダーはwhileループは使わないらしい。）

例えば、この問題。

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

for文で書くと、綺麗に書けます。

whileで書くと、多分カオスになるでしょう。そしてバグが出るはず・・。

for文で書いたプログラムはこちら。

view plainprint?

1. vector<pair<int, int> >vec, ret;  
2. int main() {  
3.     int n, s, t;  
4.   
5.     scanf("%d", &n);  
6.     while (n--) {  
7.         scanf("%d %d", &s, &t);  
8.         vec.PB(MP(s,t));  
9.     }  
10.   
11.     sort(ALL(vec));  
12.     int pos = 0;  
13.     for (;pos < (int)vec.size(); pos++) {  
14.         int s = vec[pos].first;  
15.         int t = vec[pos].second;  
16.   
17.         for (; pos+1 < (int)vec.size() && vec[pos+1].first <= t; pos++)  
18.             t = max(t, vec[pos+1].second);  
19.   
20.         ret.PB(MP(s, t));  
21.     }  
22.   
23.     REP(i, ret.size())  
24.         printf("%d %d\n", ret[i].first, ret[i].second);  
25.   
26.     return 0;  
27. }  

vector<pair<int, int> >vec, ret;
int main() {
    int n, s, t;

    scanf("%d", &n);
    while (n--) {
        scanf("%d %d", &s, &t);
        vec.PB(MP(s,t));
    }

    sort(ALL(vec));
    int pos = 0;
    for (;pos < (int)vec.size(); pos++) {
        int s = vec[pos].first;
        int t = vec[pos].second;

        for (; pos+1 < (int)vec.size() && vec[pos+1].first <= t; pos++)
            t = max(t, vec[pos+1].second);

        ret.PB(MP(s, t));
    }

    REP(i, ret.size())
        printf("%d %d\n", ret[i].first, ret[i].second);

    return 0;
}

Being hooked on something makes you strong

I watched a TV drama entitled "aibou," which means buddy, co-worker or that kind of thing in Japanese, on this new year's day.

On the drama, a wife who had lost her son by a traffic accident, made explosive bombs and revenged on someone who killed her son.

On the drama, a detective, who solved the case, said "You think that an average house wife cannot make bombs, right? But one can do anything if s/he tries it all out."

And he continued, "She became really keen on studying about bomb. It made her proactive, outgoing and lively. Even though she stayed up late in the night -- 2 or 3 AM -- every day, she never looked sleepy. She looked cheerful every day."

あれ、何か。前置きが長くなった。

まー要約すると、最近仕事が忙しいことを言い訳にしてアルゴリズムの勉強をサボりがちだったけど、それは違うなと思いました。

本当に好きなこと、本当にやるべきことであれば、寝る時間を削ってでもやるべきだと。

そして、その方が活力的な生活が送れるはずだと信じています。

って、こんな精神論を書きたいわけじゃなかったのですが、

今日は、中国語の問題を解きました。

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

ちょっと文章が分かり難いですが、要は、

「mをn個以下に分割するパターンを求めよ。」

です。

分割数は、動的計画で解くのが定石。

分割数を知らない人はこのページを見よう！！

http://techtipshoge.blogspot.com/2011/01/blog-post_28.html

これくらいの規模ならDFSとかで解けそうですが、入力サイズが大きくなると動的計画じゃないと厳しそうです。。

view plainprint?

1. int dp[16][16];  
2.   
3. void init() {  
4.    REP(i, 16)  
5.        dp[i][0] = 0, dp[0][i] = 1;  
6.    dp[0][0] = 1;  
7.   
8.    FOR (i, 1, 16) FOR (j, 1, 16) {  
9.        if (i-j >= 0)  
10.            dp[i][j] = dp[i][j-1] + dp[i-j][j];  
11.        else  
12.            dp[i][j] = dp[i][j-1];  
13.    }  
14. }  
15.   
16. int main() {  
17.    int t, n, m;  
18.   
19.    init();  
20.    scanf("%d", &t);  
21.    REP(i, t) {  
22.        scanf("%d %d", &n, &m);  
23.        printf("%d\n", dp[n][m]);  
24.    }  
25.   
26.    return 0;  
27. }  

int dp[16][16];

void init() {
   REP(i, 16)
       dp[i][0] = 0, dp[0][i] = 1;
   dp[0][0] = 1;

   FOR (i, 1, 16) FOR (j, 1, 16) {
       if (i-j >= 0)
           dp[i][j] = dp[i][j-1] + dp[i-j][j];
       else
           dp[i][j] = dp[i][j-1];
   }
}

int main() {
   int t, n, m;

   init();
   scanf("%d", &t);
   REP(i, t) {
       scanf("%d %d", &n, &m);
       printf("%d\n", dp[n][m]);
   }

   return 0;
}

カントール集合

昨日、初めてフラクタルをプログラムで描画した。

実は、フラクタルは結構難しい。二次元の場合は正確かつ高度な実装能力が必要だ。

ただし、カントール集合は一次元なので簡単。

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

始点、終点を引数にして再帰関数で処理をすればOK。

カントール集合は、不可算集合の代表的な例らしい。

非加算集合とはその名の通り、『その要素に番号を割り振ることのできない集合』である。

なんじゃそりゃ！？って感じですね。

簡単に言うと、無限個の整数を使っても番号を割り振ることのできないくらい、濃度の濃い集合ということです。例えば、実数の集合も非加算集合です。

カントールさんは、この非加算集合の存在を数学的に示したそうです。

wikipedia（英語版）に、とても面白い内容がありました。

Cantor's diagonal argument（カントールの対角線論法）です。

http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument

要約すると、以下のような感じ。

0または、1のみから構成される無限長リストの集合を考える。

この無限長リストに番号をつけて、適当な要素列s_1、s_2、...を考える。

s₁ = (0, 0, 0, 0, 0, 0, 0, ...)

s₂ = (1, 1, 1, 1, 1, 1, 1, ...)

s₃ = (0, 1, 0, 1, 0, 1, 0, ...)

s₄ = (1, 0, 1, 0, 1, 0, 1, ...)

s₅ = (1, 1, 0, 1, 0, 1, 1, ...)

s₆ = (0, 0, 1, 1, 0, 1, 1, ...)

s₇ = (1, 0, 0, 0, 1, 0, 0, ...)

　　　...

とすると、対角成分（左上から右下にかけて）に移動しながら、通過した数字と異なる数字を選ぶ。

　　s₀ = (1, 0, 1, 1, 1, 0, 1, ...)

すると、このs₀は、どのsiとも異なる。

ここで面白いことに、

• s₀は集合sに含まれる。（1, 0からなるリストなので）
• 同時に、s₀は集合sに含まれれない。（上記のような操作をすれば、集合に含まれないようなリストを作成できる。）

の両方が成立する。

これは矛盾なので、

この無限長リストに番号をつけて、適当な要素列s_1、s_2、...を考える。

という操作は不可能だということが分かる。

よって、集合sはs_1、s_2、s_3、s₄は数えることはできない。

どういう頭の構造をしてたら、こんなこと考えつくんでしょうね・・。