自前のクラスでsortをする

自前のクラスでsortをするとき、自前のクラスにてオペレータ<を定義してあげないといけない。

なぜならsortは、オペレータ<を用いてソートを行うからである。

ということで、見本を。

例の如く、PKUからの出題。今回は、2376 Cleaning Shiftsという問題。あーこんな問題TopCoderでもあったなー。ソートしてgreedyで解きます。

ソースはこんな感じ。

view plainprint?

1. class Shift {  
2. public:  
3. int s;  
4. int e;  
5. Shift(int s, int e) {  
6. this->s = s;  
7. this->e = e;  
8. }  
9. bool operator<(const Shift &shift) const {  
10. return this->s < shift.s;  
11. }  
12. };  
13.   
14. int main() {  
15. int N, T;  
16. cin >> N >> T;  
17.   
18. int s, e;  
19. vector<Shift> cows;  
20. REP(i, N) {  
21. cin >> s >> e;  
22. cows.PB(Shift(s,e));  
23. }  
24. SORT(cows);  
25.   
26. int p = 0;  
27. int up = 0;  
28. int ret = 0;  
29. while(p < N) {  
30. int max = -1;  
31. for (;p < N; p++) {  
32. if (cows[p].s > up + 1)  
33. break;  
34. max = MAX(max, cows[p].e);  
35. }  
36. if (max == -1)  
37. break;  
38. ret++;  
39. up = max;  
40. if (up == T)  
41. break;  
42. }  
43. printf("%d\n", (up == T) ? ret : -1);  
44. return 0;  
45. }  

class Shift {
public:
int s;
int e;
Shift(int s, int e) {
this->s = s;
this->e = e;
}
bool operator<(const Shift &shift) const {
return this->s < shift.s;
}
};

int main() {
int N, T;
cin >> N >> T;

int s, e;
vector<Shift> cows;
REP(i, N) {
cin >> s >> e;
cows.PB(Shift(s,e));
}
SORT(cows);

int p = 0;
int up = 0;
int ret = 0;
while(p < N) {
int max = -1;
for (;p < N; p++) {
if (cows[p].s > up + 1)
break;
max = MAX(max, cows[p].e);
}
if (max == -1)
break;
ret++;
up = max;
if (up == T)
break;
}
printf("%d\n", (up == T) ? ret : -1);
return 0;
}

Shiftというクラスでオペレータを定義していますね。このようにクラスの中で<を定義してあげないとsortは使えません。

ここで注意しないといけないのはconstってちゃんと書かないといけない（※引数部と関数部に２ヵ所書かないとダメです。）ということです。constを書かないとoperatorとして認識してくれないようで、コンパイラエラーになってしまいます。

じゃ、constって2つあるけどどう違うの？

引数のconstは引数の値を関数内で変更しないっていう意味です。引数が、参照渡しになっているため、関数内で値を書きかえることができるんですね。。値が変えられると困るのでconstって書いています。

では、そもそも何故引数は、参照渡しなの？んーいい質問です。プリミティブ型（int, doubleなど基本的な型）の場合は、関数に値をするのが基本ですが、構造体やクラスを渡すときはポインタ渡しや参照渡しを行います。これはメモリ量を節約するためです。（クラスそのものを渡すより、クラスのアドレスを渡した方がメモリが節約できますよね！）

で、まー大体こんな風に使い分けるのが基本です。

	引数を変更するとき	引数を変更しないとき
プリマティブ型	値渡し	値渡し
構造体、クラス	ポインタ渡し	参照渡し（constを付けます。）

で、関数についているconst。これは、メンバ関数内でオブジェクトのメンバ変数を変更しないということを意味しています。さらに、constがついた関数からはconstがついていない関数を呼び出すことができません。（呼び出せてしまうと、constじゃない関数の中で値を変えることができてしまい、constの意味がなくなりますね。）

つまり、このconstは、大小を比較する際に、自分のメンバ変数を変えることを禁止しているんですね。

ということで、まとめると、

• 変数部のconstは、比較相手のメンバ変数の値が変わるのを防ぐ。
• 関数部のconstは、自身のメンバ変数の値が変わるのを防ぐ。

っていう意味ですね。確かに、大小比較するんだから、値が変わらないことを担保するのは当然と言えば当然。

四捨五入をしよう。

C言語、またはC++で四捨五入をするときどういったコードを書きますか？

無知な私はこんなヘタレコードを書きました。

view plainprint?

1. int main() {  
2.  double x;  
3.  int ret;  
4.   
5.  scanf("%lf", &x);  
6.  ret = ((int)(x * 10) % 10 >= 5) ? (int)(x + 1) : (int)(x);  
7.  printf("ret=%d\n", ret);  
8.   
9.  return 0;  
10. }  

int main() {
 double x;
 int ret;

 scanf("%lf", &x);
 ret = ((int)(x * 10) % 10 >= 5) ? (int)(x + 1) : (int)(x);
 printf("ret=%d\n", ret);

 return 0;
}

あーー、もう穴があったら入りたい。

これで行けますね。

view plainprint?

1. int main() {  
2.  double x;  
3.  int ret;  
4.   
5.  scanf("%lf", &x);  
6.  ret = (int)(x + 0.5);  
7.  printf("ret=%d\n", ret);  
8.   
9.  return 0;  
10. }  

int main() {
 double x;
 int ret;

 scanf("%lf", &x);
 ret = (int)(x + 0.5);
 printf("ret=%d\n", ret);

 return 0;
}

0.5足してintにキャスト、これで四捨五入できます。

はい、今日は以上。

Invincible Macros for C++(3) : My Conclusion

After time-consuming research and hands-on experience, I've finally reached the conclusion.

This is "the best macros" I could come up with.

Of course seems like there exist plenty of rooms for improvement, but this is the best for now.

How does it feel like to you?

Please notice that "using namespace" phrase comes before the "typedef" part.

It is because you should explicitly write the namespace name before you use vectors.

Without this notation, you'd end up with compiler error.

It was not until I learned the fact that I found it was mistake to think typedef of "containers in STL" was impossible.

So write "using namespace std" before the "typedef" part.

(日本語)

C++のための最強のマクロ集（3）

長い長い研究と手探りの経験の結果、ついに結論に達した。

これが考えつく限り最強のマクロだ！

もちろん、改良の余地はあるが、今のところこれがベストである。

どうですかねー？？

ここで、"using namespace"っていうフレーズが"typedef"の前にあることに気付いて下さい。

これは、vectorを使用する前に、名前空間を明示的に指定しないといけないからです。

この表記をつけなかったら、コンパイルエラーになります。

この事実に気付くまで、STLのコンテナのtypedefは不可能なんだと思いこんでいました（笑）

だから"using namespace std"って"typedef"の前にちゃんと書きましょう！

view plainprint?

1. #include <algorithm>  
2. #include <iostream>  
3. #include <limits.h>  
4. #include <list>  
5. #include <map>  
6. #include <math.h>  
7. #include <queue>  
8. #include <set>  
9. #include <sstream>  
10. #include <stdio.h>  
11. #include <string>  
12. #include <string.h>  
13. #include <vector>  
14.   
15. using namespace std;  
16.   
17. #define REP(i, n) for(int i=0; i<(int)(n); i++)  
18. #define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)  
19. #define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)  
20. #define MAX(a,b) ((a) > (b) ? (a) : (b))  
21. #define MIN(a,b) ((a) < (b) ? (a) : (b))  
22. #define ABS(x) ((x) < 0 ? - (x) : (x))  
23. #define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))  
24. #define SORT(c) sort((c).begin(),(c).end())  
25. #define PB push_back  
26. #define DISP(x) cout << #x << " : " << x << endl  
27.   
28. typedef vector<int> VI;  
29. typedef vector<VI> VVI;  
30. typedef vector<string> VS;  
31. typedef long long int LL;  
32.   
33. const double PI = acos(-1.0);  

#include <algorithm>
#include <iostream>
#include <limits.h>
#include <list>
#include <map>
#include <math.h>
#include <queue>
#include <set>
#include <sstream>
#include <stdio.h>
#include <string>
#include <string.h>
#include <vector>

using namespace std;

#define REP(i, n) for(int i=0; i<(int)(n); i++)
#define FOR(i, s, e) for (int i = (int)(s); i < (int)(e); i++)
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define MAX(a,b) ((a) > (b) ? (a) : (b))
#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define ABS(x) ((x) < 0 ? - (x) : (x))
#define SIZE(buff) (sizeof(buff)/sizeof(buff[0]))
#define SORT(c) sort((c).begin(),(c).end())
#define PB push_back
#define DISP(x) cout << #x << " : " << x << endl

typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef long long int LL;

const double PI = acos(-1.0);

int型の除算の結合法則に注意

結合法則に思わぬ落とし穴があることを発見した。（多分、基本ですが・・・）

まずは、この問題を見て下さい。PKUの問題です。

http://acm.pku.edu.cn/JudgeOnline/problem?id=3619

この問題に対して、最初にsubmitした回答がこれ。

撃沈。

view plainprint?

1. int main() {  
2. int N, K;  
3. scanf("%d %d", &N, &K);  
4.   
5. int s, t, r;  
6. while(K) {  
7. scanf("%d %d %d", &s, &t, &r);  
8. int ret = 0;  
9. while (ret * s < N)  
10. ++ret;  
11. printf("%d\n", ret + r*(ret - 1)/t);  
12. --K;  
13. }  
14.   
15. return 0;  
16. }  

int main() {
int N, K;
scanf("%d %d", &N, &K);

int s, t, r;
while(K) {
scanf("%d %d %d", &s, &t, &r);
int ret = 0;
while (ret * s < N)
++ret;
printf("%d\n", ret + r*(ret - 1)/t);
--K;
}

return 0;
}

結構悩んだ後で、気付いたのはここ。

11行目のところ。

計算したかったのは、

しかし、私が求めたかった値を厳密に数学的に記すならば、

である。ここで注意すべきは、

の結合法則は成立するが、int型で小数点以下を切り捨てしている場合は、ソース上では単なる乗算と除算だが数学的にはfloorという演算が入っているため、同様の結合法則が成り立たないということだ。

ここを見落としてしまうと、上の例でr = 3, ret = 11, t =3のとき

を期待して、r * (ret - 1) / tなんてやってしまうと、

と計算されてしまうことになる。。

つまり、思惑通りの演算をするためには、11行をr * (ret-1) /t ではなく、(ret - 1) / t * r にしなければいけなかったのだ。。。

まあかなり基本だけど、ハマってしまうと意外と抜けられない感じなので気をつけましょう。。

インタビュワーとして学んだこと

暫く、会社でインタビュワーのようなことをやっていた。

詳細はconfidentialなので紹介できないが、社内から複数の人間をピックアップし、彼らの過去の経験をインタビューするというもの。

今まで、面接を受ける立場の人間だった私が、面接をするのである。。
かわいい女の子だったら喜んだり、いかついおっさんだったら凹んだり、いろいろあった。

違う、違う、上の灰色の部分は無視して下さい。

今日整理して置きたかったのは、インタビュワーを経験して初めて分かったことだ。
まず、気付いたのが、話の上手い下手は正直そんなにない。ということだ。内容自体の善し悪しも個人差はそんなにない。

それでは、何が取材協力者の印象の良し悪しを決めたか。。
それは、「話の一貫性」と「聞き手の意思をくみ取った話をしているか」ということだ。

まず、一つ目。これは言わずもがな。
入社試験のときも、よく言われますね。話は一貫性を持ちなさい。って。
まあその通りだ。一貫性のない話をする人の話し方の特徴に気付いた。

「○○○なんです。」
「あ、あと△△なんです。」
「あ、でも××なんです。」

と継ぎ接ぎ的に話を進めていく。おそらくたくさん喋らないといけないと思ってくれてるのだろう。（インタビュワーとしてはたくさん喋って情報をくれるのは嬉しいですけど。。）しかし、こういう話し方をする人はたいてい最初に行ったことと最後に言ったことが矛盾している。
そして、聞き手側に最後に残ってしまう印象は「あれ？？？言ってること矛盾してる。結局何が言いたいんだろう・・」
そう、この場合、最初の「○○○なんです。」で話を終えておけば良いのである。そもそも”長く話さないといけない”っていうのも間違いだと思う。ビジネスの場では、simply and conciselyが基本だ。

そして二つ目。これは、相手が何を聞きたいのかを考えて答えを返しているかいないのかである。
例えば、こう言う感じ。

「この出来事の後、あなたの考え方は変わりましたか？」

この質問に対して、何と、7割の人は、「変わりました。」と答えて口を閉ざしてしまう。。
これには、正直ショックを覚えた。。。（しかし、もし自分が逆に取材協力者だったら、自分も彼らと同じだったと思う。）
そのあと、暫く沈黙があり、「具体的にどう変わりましたか?」と聞いてようやく、どう変わったのかを話してくれる。

これは、例えるとこんな感じだ。あなたは、道に迷ってしまった。駅までの道のりが分からない。そこで、通りがかりの人に勇気を出して尋ねた。
「あの、すいません。駅までどうやったら行けるか知ってますか？」
「はい。」



「・・・・・・」



「・・・・・・」


「・・・・・・」


「え、えっとどうやっていくか説明してもらってもいいですか？？」

話を戻そう。「考え方は変わりましたか？」という質問は、closed questionだが、実質的にopen questionである。「変わった。」ということを前提にして、本当に聞きたいのは「どう変わったか」ということである。

このpractically open question（勝手に名前付けた笑）に対して、きちんと「どう変わったか」まで話してくれる人は、よい印象を残すと思う。
そして、インタビュワーはこう思う。あ、この人は、日頃から話すときは、ただ質問に答えるのではなくて相手が聞きたいことを意識しながら質問に答えるんだな。と。

日常の仕事の上でも、

• 質問に答えるときは相手が何を意図しているのか意識すること
• そして逆に、相手に何かを尋ねる時は、何故その質問をするのか、その質問の答えを知って「何をしたいのか」または「相手に何をして欲しいのか。」を伝えることが大切だと思う。

と、プログラマーとして入社したものの、とても貴重な体験をすることが出来たので、忘れないようにここに記録を残しておきます。。

初めてのGoogle API

最近、どうやら、ウェブの世界ではAPIが蔓延っているということを知った。

Google, Yahoo, twitter, Skypeなど各社が自社製品を開発した際に使用した基本的な機能を無償でAPIとして一般開発者に提供しているようだ。

ということで、今日は、Google APIにチャレンジしようと思う。

題材として選んだのは、Google Chart API。

パラメータをあるURLにGETで送信すれば、グラフや図などが取り出せるというもの。

HTMLのイメージタグのsrc属性に上記URLを指定すれば、そのグラフや図を自身のウェブページに埋め込むことができる。

まー、とりあえずやってみましょう。

はい。これのソースはこんな感じです。出たな！余分三兄弟！

view plainprint?

1. <img src="http://chart.apis.google.com/chart?cht=p3&chd=t:30,30,40&chs=250x100&chl=糖分|脂肪|塩分" alt="sample1" width="250" height="150" />  

<img src="http://chart.apis.google.com/chart?cht=p3&chd=t:30,30,40&chs=250x100&chl=糖分|脂肪|塩分" alt="sample1" width="250" height="150" />

簡単ですね。

さらに、このAPI、隠し玉を持ってました！！！

ななななんと、Latexのコマンドで数式を入力できるのですーー。＠＿＠

では、早速、今日知った数式を書いてみます。

うむ。なかなか良い感じ。適切なサイズの指定（HTMLのheight, width属性）にちょっと迷ったけど何も書かなければデフォルトで自動設定してくれるのかな。。良い感じのサイズになりました。

ちなみに上の式は素数定理と呼ばれます。

は、2からxまでの自然数の中に現れる素数の数です。xまでの素数の数は上式で近似できるそうです。目から鱗ですね！！

ちなみに素数定理の式のソースコードはこんな感じ。

view plainprint?

1. <img src="http://chart.apis.google.com/chart?cht=tx&chs=1x0&chf=bg,s,FFFFFF&chco=000000&chl=\pi(x)%20\sim%20\frac{x}{\ln(x)}" />  

<img src="http://chart.apis.google.com/chart?cht=tx&chs=1x0&chf=bg,s,FFFFFF&chco=000000&chl=\pi(x)%20\sim%20\frac{x}{\ln(x)}" />

FFFFFFのところは数式表示部分の背景色（この場合は白）を指定しています。また、000000のところは数式の文字色（この場合は黒）です。この値をいじれば、数式に色が付けられるということですね。例えば、こんな感じ。

ちなみに、GETでパラメータを渡すので空白やプラス記号はASCIIコードに置き換えて送信する必要があるようです。具体的には、空白は、「%20」、プラス記号は「%2b」としてあげましょう。

上の相加相乗平均の式は、

view plainprint?

1. <img src="http://chart.apis.google.com/chart?cht=tx&chs=1x0&chf=bg,s,FFCCCC&chco=FF0000&chl=\frac{(a%2bb)}{2}%20\geq%20\sqrt{ab}" />  

<img src="http://chart.apis.google.com/chart?cht=tx&chs=1x0&chf=bg,s,FFCCCC&chco=FF0000&chl=\frac{(a%2bb)}{2}%20\geq%20\sqrt{ab}" />

としています。空白とプラス記号は16進数のASCIIコードで渡しているところに注目です！！

いや、実は数式をbloggerで表示させる方法探してたんだよね。丁度よかった。

さてさて、他にもいろいろできそう。以下のサイトにGoogle Chart APIで使用できるチャート一覧が記載されています。

http://code.google.com/intl/ja/apis/chart/docs/gallery/chart_gall.html

あと、Latexコマンドを知らない人は、こちらのサイトがお勧めです。

http://www1.kiy.jp/~yoka/LaTeX/latex.html

ではでは、今日はこの辺で！

泥遊びをする子供の問題

今日は少し趣向を変えて、頭の体操をしようと思う。

以下の問題を考えて欲しい。

**********************************************************************************

泥遊びをしている子供が3人いる。3人とも顔に泥が付いている。

そこへ大人がやって来て、こう言った。「君たちの中に少なくとも1人は顔に泥が付いてる。早く洗って来なさい。」

さて、この後子供たちはどうするでしょう？

**********************************************************************************

ちょっと難しいかもしれないので、まずは、単純化のため子供が2人の場合を考えてみよう。（何事も一番単純な例で考えてみるのは良い習慣だと思う。）

A君はB君の顔を見てこう思うだろう。「あ、B君の顔泥付いてる。はははー。」

一方B君はこう思う。「あ、A君の顔に泥付いてる、早く洗い行けよなー。。」

そして、2人とも暫く動かない。。

ここで、A君は気付く。

「あれ、なんでB君顔洗いにいかないんだろう。。僕の顔に泥が付いてなかったら、自分（B君のこと）に泥が付いてるって気付いてすぐに洗いに行くはずだよな。。すぐに行かないってことは、やべっ。。おれの顔にも泥が付いてるんだ！！」

B君も然り。

そこで、2人は一斉に顔の泥を洗いに行く。（ただし、これはA君とB君の頭の回転の速さが同じであることが前提な気が・・・。ま、これは本筋とは違うので突っ込まないで下さい。おそらく僕がきちんとした問題の定義を知らないだけです。。）

では、子供が3人の時はどうなる？

A君は、B君とC君の顔を見て「泥が付いてるのはB君とC君だな。もしくは、3人全員の顔に泥が付いてるのかも。」と思う。

しかし、B君とC君が顔を洗いに行かないのを見て不思議に思う。

「もし、僕の顔に泥が付いていないのであれば、B君とC君はお互いの顔を見合ってこう思うはず。B君：『何故、Cのやつ顔洗いに行かないんだ。あ、おれの顔に泥が付いてるからだ。』C君も同様。そして、B君とC君は一斉に顔を洗いに行くはずである。（※）でも、それが起きないってことは、僕の顔に泥が付いていないっていう仮定が正しくないんだ。やべっ、顔洗いに行こ！」

そして、A君は、顔を洗いに行く。B君及びC君も、A君と同じ考察をして顔を洗いに行く。

よって答えは”みんなお互いの顔を暫く見た後、一斉に顔を洗いに行く。”

上記（※）の部分からn人の場合の問題が、n-1人の場合の問題に帰着できるのは明らかだろう。

よって、子供の数が4人、5人、6人・・・・に増えた場合も同様に考えることができる。

さてさて、この問題のポイントは3つあると思う。

1. 「問題の簡素化」 まずは、子供が2人の場合を考えることで展望が開ける。
2. 「場合分け」それぞれの子供の思考を、「顔に泥が付いているのは、自分以外」か「自分も含めた全員か」の2パターンに場合分けする。
3. 「一般化」　上記の場合分けにより、サイズnの問題がサイズn-1の問題に帰着出来ることに気付く。

今回取り上げた問題意外でも、上記3つの思考は問題解決においてとても重要なファクターである。こういう頭の体操もたまには良いかも知れない。

怒涛の4AC★

PKUハマりすぎ。。笑

今日は4問解いた。。

出力フォーマットの形式ミスと、define入れ損ねてコンパイルエラーになった凡ミスを除けば4連続一発AC。

まー簡単な問題しかやってないんだけど（笑）

でも、ランキングを確認すると、Top10%入りが目前に迫ってきた。。やっぱTopCoderと違ってやればやるほどランキングが上がるというのは良いモチベーションになるみたいだ。

今日やった問題で、どうやら自分の苦手分野が分かってきた。

こういうのは得意。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2291

与えられた複数のロープを使って持ちあげられる荷物の重量の最大値を返せ。但し、ロープには均等に重さがかかるとする。それぞれのロープは荷物にくくりつけても、つけなくてもよい。

こういうのが苦手。

http://acm.pku.edu.cn/JudgeOnline/problem?id=1595

1からNまでの素数をリスト化する。リストのサイズが偶数個の場合は、C*2個、奇数の場合はC*2-1個リストの中央部分から抽出せよ。

簡単に言うと数学チックなのは得意だけど、配列の添え字の微妙な感覚(-1するべきか、しないべきかなど)が苦手みたい。。

Topcoderでは、1595みたいな問題に苦戦する。

まー慣れなんだろうけど。。。こういう問題いっぱい解いた方がいいのかな。。

衝撃の事実！cin, coutは遅かった。。

衝撃の事実が発覚した。。

c++のcin, coutは遅いようだ。。（これ常識なの？？）

pkuを解いていて、たまに

｢テストケースが非常に多いので、scanfの使用をお勧めします。｣

みたいな文言を見ていたので何だろうと思っていたら、どうやらcinとscanfにはスピードに差があるよう。。。

同じようにcoutとprintfにも処理速度に差があるようだ。。

自分のローカルマシンで試してみたところ、

同様の処理をするのに、coutの方が1.5 - 2.0倍程度(表示行数100,000-1,000,000の場合)の時間を要していた。。

考えられる理由は以下の２つ。

①cin/coutはオーバーロード関数であるため、引数に応じてどのプロトタイプを使用するか決定しないといけない。scanf/printfはオーバーロードされていないため、このオーバーヘッドがない。

②scanf/printfはプログラマーが読み取る型をソース内で指定するのに対して、cin/coutは型の解釈を実行時に行わなければならない。

らしい。。

参考: http://www.daniweb.com/forums/thread40450.html

醜い争いが繰り広げられているので心臓の弱い方は上のURLにアクセスしないで下さい(笑)

とりあえず、今日の教訓は、コンテスト系の処理速度が求められる場面では、

｢cin, cout より scanf, printfを使え！！｣っていうことでした。

（でも、出力の場合は処理速度もさることながら、桁数指定とかが断然printfの方が楽ですよね。。。）

二分探索をやってみよう！

昨日PKUにて、解き方の方針は立ったがどうしようか・・という場面に遭遇した。

簡単にいうとこんな感じ。

1 - 50,000までの数の中で、ある条件を満たす数の最大値はいくらか？？数が小さければ小さいほど条件を余裕をもって満たせることは明らか。。

じゃー、1-50,000までインクリメントしてやってみるか。。。

いや、待て。そんなんじゃ時間足りない気がする。条件を満たすかどうか調べるの結構時間使いそうだし。じゃあどうしよう・・・

そこで閃いた。

①まず、25,000で試してみよう。

②25,000で条件を満たすのなら、今度は25,000 - 50,000までの探索をしよう。満たさないなら0-25,000まで探索しよう。

①②の操作で探索範囲が1/2になった。同じことを逐次10回やれば探索範囲は大体1/1000くらいになるな。20回やれば1/1,000,000くらいにできるな。。

単純にインクリメントした場合は、最悪50,000個の数を調べないといけないけど、この範囲を1/2に狭めていく方法を使えば、最悪でも16回以下くらいで探索ができるな！！

ん・・何かこれ、もしかしてBinary Searchとか言うやつじゃないのか。

ググってみると、ありました。Binary Search(二分探索)。そうそうこれこれ。。

早速ちょっと試しに簡単な例題を作って練習してみました。

例題

単調増加関数fがある。ある自然数nが与えられた時、f(x) > nとなる最小の自然数xを求めなさい。

ここで、f(x) = (int)log(x) + (int)sqrt(x) + 1とする。

単純な線形探索とBinary Searchで実行速度を比べてみよう。

ソースはこんな感じ。

view plainprint?

1. using namespace std;  
2.   
3. int func(int n) {  
4.   
5.     return (int) log(n) + (int)sqrt(n) +  1;  
6. }  
7.   
8. int main() {  
9.     int target = 7777;  
10.     int i = 0;  
11.   
12.     // Linear Search  
13.     while (1) {  
14.         if (func(i) > target)  
15.             break;  
16.         i++;  
17.     }  
18.     cout << i << endl;  
19.   
20.     // Binary Search  
21.     int left = 0;  
22.     int right = INT_MAX;  
23.     i = left + (right - left) / 2;  
24.     while (1) {  
25.         if (func(i) > target && func(i - 1) <= target)  
26.             break;  
27.   
28.         if (func(i) > target)  
29.             right = i;  
30.         else  
31.             left = i;  
32.         i = left + (right - left) / 2;  
33.     }  
34.     cout << i << endl;  
35. }  

using namespace std;

int func(int n) {

    return (int) log(n) + (int)sqrt(n) +  1;
}

int main() {
    int target = 7777;
    int i = 0;

    // Linear Search
    while (1) {
        if (func(i) > target)
            break;
        i++;
    }
    cout << i << endl;

    // Binary Search
    int left = 0;
    int right = INT_MAX;
    i = left + (right - left) / 2;
    while (1) {
        if (func(i) > target && func(i - 1) <= target)
            break;

        if (func(i) > target)
            right = i;
        else
            left = i;
        i = left + (right - left) / 2;
    }
    cout << i << endl;
}

ちなみに x= 60,217,600だが、探索にかかった時間は
Linear Searchの場合は、12.347秒。Binary Searchの場合は、0.000000011秒（笑）。

全然違います。

他にもBSはいろいろな使い道がありそうです。

DPと並んでアルゴリズムコンテストでは必須アイテムの一つと言えるでしょう。

ちなみにこれが昨日遭遇したBinary Searchを使って解くPKUの問題。興味のある人はチャレンジしてみて下さい！僕も実装はまだです。。。

この夏、PKUが熱い！！

先日始めたPKU!

中々熱いYo! PKU!

You の順位付くYo!!

あれ・・・・

なんかラップ調に。。。

ちょっと、疲れてるのかな。。

とにかく、PKUが熱いです！！なんと解いた問題数に応じて順位が付くじゃありませんか！！

今のところ、42813位（177050中）くらい。

PKUをお勧めする理由は3つあります。（｢3つあります。｣はうちの会社の社員の口癖（笑）彼らは何でも3つあるみたいです。。）

①いつでも解ける。

　Topcoderと違っていつでも解けます。

②時間制限がない。

　時間制限がなく、単純に解けた問題数で順位が付くみたいです。

③問題が豊富である。

　Topcoderにはないような問題があります。例えば、多倍長整数の演算や、STLを使用するとそのオーバーヘッドにより解けない問題（TopCoderはSTLの使用が基本ですよね。。）など。。問題量が豊富なので、問題の難易度も豊富です。自分のレベルにあった問題を探して解けばかなりレベルアップができます。

とりあえず目指すは、Top1%のプログラマーですかね！

300問くらい解けば、1%に入れるみたい。。。毎日1問ペースでやれば、1年後には、

｢あ、おれ、世界のプログラマーTop1%に入るんだよね！｣

って言えます（笑）

300問解ければ、TopCoderでも黄色くらいにはなれるかな・・・

PKUを始めてみた！

PKUを始めた。。

PKUは、北京大学がストックしているプログラミングコンテストの過去問題集である。

世界中で開催されたプログラミングコンテストの過去問がのっているのでなかなか勉強になる。

しかも、PKUを問題の種類別に（探索/動的計画/貪欲法など）カテゴライズしてくれているサイトがあったり、最重要問題をピックアップしてくれていたりするサイトがあるので、自分の弱点を重点的に補強することが可能である。

問題自体は、登録なしでも見れるが、submitしてソースコードの正当性を確認するためには、PKUのサイトに登録しなければならない。。（まーでも、ちょっとした情報入れるだけなんで30秒くらいで出来ます。）

使ってみた感想は、Google Code Jamに似ている気がする。フォーマッティングされたinputを読み取り、outputを指定のフォーマットで出力する。。

とりあえず、今日は、最近勉強しているDPを解いてみた。

問題は、これ。

http://acm.pku.edu.cn/JudgeOnline/problem?id=2192

比較的簡単な問題だった。。

普通にコーディングすると最悪計算量がO(2^(n+m))になってしまう典型的なクラスNPの問題。。

ちょっと工夫すれば、O(n*m)で解けます。。。（ここで、n, mはそれぞれ文字列A,Bの長さとする。）

今回は、｢PKUってのがありますよ｣って紹介だったので、ソースは掲載しませんが（手抜きですいません。。）、2次元のマトリックスが頭の中に浮かんで、左下からスタートして、上に行くか、右に行くか、を逐次選びながら進んで、一番右上にゴールしたときに・・・・みたいなイメージが頭の中に浮かぶといいです。。

DP知らない人からすると、何で文字列の問題が、経路問題みたいになるんだろう？？？って感じだと思いますが。。そういう人は、是非ともDPの勉強をお勧めします。。

お勧めのサイトはこれ。

http://www.itmedia.co.jp/enterprise/articles/1003/06/news002.html

知ってると便利なSTL(1) set

今日、こんな場面に出くわした。。

複数の自然数（ダブりあり）からなる入力を一意な集合で整理したい。。。

例えばこんな感じ。。

{1,2,3,4,1,2} -> {1,2,3,4}

最初こんなことしてしまった（笑）

view plainprint?

1. int main(void) {  
2. int input[] = { 1, 3, 4, 3, 2, 7, 5, 8, 8, 10, 2, 4, 1 };  
3. VI myVec;  
4.   
5. int pre = 0;  
6. forf(i, SIZE(input)) {  
7.  bool in = false;  
8.  foreach(itr, myVec) {  
9.   if (*itr == input[i]) {  
10.    in = true;  
11.    break;  
12.   }  
13.  }  
14.  if (!in)  
15.   myVec.pb(input[i]);  
16. }  
17. foreach(itr, myVec)  
18.  cout << *itr << endl;  
19. }  

int main(void) {
int input[] = { 1, 3, 4, 3, 2, 7, 5, 8, 8, 10, 2, 4, 1 };
VI myVec;

int pre = 0;
forf(i, SIZE(input)) {
 bool in = false;
 foreach(itr, myVec) {
  if (*itr == input[i]) {
   in = true;
   break;
  }
 }
 if (!in)
  myVec.pb(input[i]);
}
foreach(itr, myVec)
 cout << *itr << endl;
}

ヘタレ過ぎる・・・・

STLでsetという便利なものがあることを発見。

これを使うと一意な要素しか入力しないらしい。

setを使って書くとこんな感じ。。

view plainprint?

1. int main(void) {  
2. int input[] = {1,3,4,3,2,7,5,8,8,10,2,4,1};  
3.   
4. set<int> mySet;  
5. forf(i, SIZE(input))  
6.  mySet.insert(input[i]);  
7.   
8. foreach(itr, mySet)  
9.  cout << *itr << endl;  
10. }  

int main(void) {
int input[] = {1,3,4,3,2,7,5,8,8,10,2,4,1};

set<int> mySet;
forf(i, SIZE(input))
 mySet.insert(input[i]);

foreach(itr, mySet)
 cout << *itr << endl;
}

若干、C++に見えない気がしますが、C++です（笑）

便利なマクロ使ってます。

このset意外と使う場面は多そうだ。