## 2014年11月30日日曜日

### 大きな数の最初の10桁を求める

logを使うとうまく出来そうだ。ということでやってみた。
とりあえず2のべき乗の上10桁を求めてみた。

プログラム
```#include <iostream>
#include <cmath>

using namespace std;

const double EPS = 1e-6;

// return the first 10 digits of 2^k
long long calc(int k) {
double x = k * log(2);
int d = x / log(10);
x -= d * log(10);
x += 9 * log(10);
return exp(x) + EPS;
}

int main(int argc, char **argv) {

cout << calc(1000) << endl;
cout << calc(10000) << endl;
cout << calc(100000) << endl;

return 0;
}
```

プログラムの実行結果。

1071508607
1995063116
9990020930

Pythonで2^kを実際に計算して検算してみた。正しく計算出来ていた。
```\$ python -c "print str(2**1000)[:10]"
1071508607
\$ python -c "print str(2**10000)[:10]"
1995063116
\$ python -c "print str(2**100000)[:10]"
9990020930
```

## 2014年11月29日土曜日

### Graphvizで二分探索木を描画する

Graphvizという便利なツールがあることを知った。
AT&T研究所が開発したオープンソースのグラフ描画ツールである。とりあえず動かして遊んでみようということで、二分探索木を描画してみた。

インストール
Ubuntuマシンにインストール。
```\$ sudo apt-get install graphviz
```

まず、20個の乱数を二分探索木に格納する。
その後、Graphvizに読み込ませるDOT言語のスクリプトをdump関数で出力する。
```#include <iostream>
#include <cstdlib>

using namespace std;

struct node {
int x;
node *lch, *rch;

node (int x) : x(x), lch(NULL), rch(NULL) {}
};

node *insert(node *v, int x) {
if (v == NULL)
return new node(x);
if (x < v->x)
v->lch = insert(v->lch, x);
if (x > v->x)
v->rch = insert(v->rch, x);
return v;
}

void dump(node *v, node *par = NULL) {
if (v == NULL)
return;

if (par == NULL) {
cout << "digraph G{" << endl;
cout << "  graph [ordering=\"out\"];" << endl;
}
else {
cout << "  " << par->x << " -> " << v->x;
if (v->x > par->x)
cout << " [style = dotted]";
cout << ";" << endl;
}

dump(v->lch, v);
dump(v->rch, v);

if (par == NULL)
cout << "}" << endl;
}

int main(int argc, char **argv) {

srand(time(NULL));
node *root = NULL;

for (int i = 0; i < 20; i++)
root = insert(root, rand() % 100);

dump(root);

return 0;
}
```

```\$ g++ bst.cpp -o bst
\$ ./bst >sample.dot
\$ dot -Tpng sample.dot -o sample.png
\$ xdg-open sample.png
```

すると、以下の画像が表示される。実戦が左の子への辺、破線が右の子への辺である。

これで木の回転をして遊んだり、平衡二分木を自分で実装したり、などなどするときに動作確認がしやすくなる。

## 2014年11月27日木曜日

### 商社は何をやっているのか

商社は何をやっているのか？どうやって儲けているのか？

ここまでは前から知っていた。いまいち分かっていなかったのは商社の存在意義。メーカーが直接売ればいいじゃん。なんか商社って楽して儲けてるだけで何の価値も創造していないような・・と思っていた。

いいモノを作れば売れるというわけではない

そこで登場するのが商社。商社は持ち前の営業力でモノを上手に宣伝し、顧客に売り込む。もちろん現代においては、ITを駆使した顧客分析、商品分析なども行う。今はこういう商品が人気だから、今度はこういう商品を開発しましょう！というように商品企画に関与することもある。

つまり商社はメーカーが作ったいいモノを世の中により広く流通させるために営業力の面からサポートを行う仲介業者みたいなイメージ。これが分かったとき、商社は楽して儲けているだけというイメージは完全に無くなった。

モノは買い手にすぐ届くわけではない
モノを買いたい人が見つかったらそれで終わりというわけではない。
モノを顧客の元に届けなければならない。そのためには配送ルートが必要だ。それからモノを格納しておく倉庫も必要だ。何をいつどれだけ作ればいいかを考える生産計画も必要だ。

こういう物流まわりも商社がやっている。メーカーが作ったモノを営業して売り込み、顧客のもとに届けるまで面倒をみる。これが商社。商品の総合プロデューサーという感じだろうか。

### Optimal Strategy for Grundy's Game

I learned about "Grundy's Game." This game is played by two players as follows:

1. The game starts with a single heap of objects.
2. The first player chooses a heap and splits the heap into two heaps of different sizes.
3. The second player does the same thing as 2.
4. Repeat 2. and 3. The player who cannot make a proper move loses.

For example, let's say the size of an initial heap is 9.

The first player splits a heap into (4, 5).
The second player splits the second heap into (2, 3), making the heap sizes (4, 2, 3).
The first player splits the first heap into (2, 2), making the heap sizes (2, 2, 2, 3).
The second player splits the last heap into (1, 2), which is the only allowed move here, making the heap sizes  (2, 2, 2, 1, 2).

Now there are no proper moves available.
You cannot split a heap of the size 1.
And You cannot split a heap of the size 2 into two heaps of different sizes.
Therefore the second players wins in the example.

Umm, sounds like a good way to kill time. You can play with some coins.

I wrote a program that returns the optimal strategy for this game. As you can guess from the name of this game, I used Grundy numbers. Just run the program, input the heap sizes, like, 10 or 5 10 20 or whatever. That's it.
```#include <iostream>
#include <vector>
#include <set>
#include <sstream>

using namespace std;

const int MAX_V = 1000;
int g[MAX_V + 1];

void init() {
for (int i = 2; i <= MAX_V; i++) {
set<int> s;
for (int j = 1; 2 * j < i; j++) {
s.insert(g[j] ^ g[i-j]);
}
while (s.count(g[i]))
++g[i];
}
}

void solve(vector<int> &a) {

int sum = 0;
for (int i = 0; i < a.size(); i++)
sum ^= g[a[i]];

for (int i = 0; i < a.size(); i++) {
sum ^= g[a[i]];

for (int j = 1; 2 * j < a[i]; j++) {
if (!(sum ^ g[j] ^ g[a[i] - j])) {

for (int k = 0; k < a.size(); k++) {
if (k == i)
cout << j << " " << (a[i] - j) << " ";
else
cout << a[k] << " ";
}
cout << endl;

return;
}
}

sum ^= g[a[i]];
}

cout << "Uncle." << endl;
}

int main(int argc, char **argv) {

init();

for (string line; getline(cin, line), line != "bye"; ) {

istringstream iss(line);
vector<int> a;

int n;
while (iss >> n)
a.push_back(n);

solve(a);

}

return 0;
}
```