SRM 525 DIV2 950 MagicalSquare

DPで解く問題。どのような状態を保持するかが悩ましかった。最初、dp[r][i][j][k]としてr行目まで見たときに、各カラムが先頭からi, j, k文字まで埋まっている場合のパターン数を保持するようにした。しかしよく考えると、kはi, jが決まれば一意にきまるので、dp[r][i][j]とした。

　計算量は、(行数 4) * (カラムの埋まっている文字 50^2) * (現在注目している行の文字の分割パターン 50^2) * (文字列比較 50)であやしかったけど、投げてみる。TLE。ループの中にbreakを入れて枝狩りをしてみる。Accept。

　んー、通ったものの、計算量はもう一段階落ちると思う。文字列の比較をハッシュとか使ってやればいいのかなー。Editorialに期待します。

long long int dp[4][51][51];

class MagicalSquare {
public:
    long long int getCount(vector<string> rowStrings, vector<string> columnStrings) {
        memset(dp, 0, sizeof(dp));

        vector<string> rows(4);
        rows[0] = "";
        REP(i, rowStrings.size()) rows[i+1] = rowStrings[i];

        dp[0][0][0] = 1;
        int rLen[4];
        int cLen[3];

        REP(i, 4) rLen[i] = rows[i].length();
        REP(i, 3) cLen[i] = columnStrings[i].length();

        if (rLen[1] + rLen[2] + rLen[3] != cLen[0] + cLen[1] + cLen[2])
            return 0;

        int s = 0;
        REP (r, 3) {
            s += rLen[r];
            REP (i, cLen[0]+1) REP(j, cLen[1]+1) {
                if (!dp[r][i][j]) continue;

                int k = s - i - j;

                REP(p, rLen[r+1]+1) {
                    string s1 = rows[r+1].substr(0, p);
                    if (columnStrings[0].substr(i, s1.length()) != s1) break;

                    FOR (q, p, rLen[r+1]+1) {
                        string s2 = rows[r+1].substr(p, q-p);
                        string s3 = rows[r+1].substr(q);

                        if (columnStrings[1].substr(j, s2.length()) != s2) break;
                        if (columnStrings[2].substr(k, s3.length()) != s3) continue;

                        dp[r+1][i+s1.length()][j+s2.length()] += dp[r][i][j];
                    }
                }
            }
        }

        return dp[3][cLen[0]][cLen[1]];
    }
};

SRM 525 DIV1 250 dropcoins

完敗(^O^)／

どうせ探索問題だろうとおもったのが、すべての敗因でした。このやり方知ってるのに出て来なかったのは悔しい。ばか、もうほんとばか。

int cnt[31][31];
class DropCoins {
public:
    int getMinimum(vector<string> board, int K) {
        int r = board.size();
        int c = board[0].length();

        int ret = INF;
        memset(cnt, 0, sizeof(cnt));
        FOR (i, 1, r+1) FOR (j, 1, c+1) {
            cnt[i][j] = cnt[i-1][j] + cnt[i][j-1] - cnt[i-1][j-1] + (board[i-1][j-1] == 'o');
        }

        FOR (i, 1, r+1) FOR (j, 1, c+1) FOR (it, i, r+1) FOR (jt, j, c+1) {
            int x = cnt[it][jt] + cnt[i-1][j-1] - cnt[it][j-1] - cnt[i-1][jt];

            if (x == K) {
                int ans = (i-1)+(j-1)
                        + (r-it)+(c-jt)
                        + min(i-1, r-it)
                        + min(j-1, c-jt);
                ret = min(ret, ans);
            }
        }

        if (ret == INF) return -1;
        return ret;
    }
};

C++の関数オブジェクト

前から気になっていたのですが、C++にgreater<int>というものがあります。例えば、vector<int> xsを降順にソートしたい場合に

sort(xs.begin(), xs.end(), greater<int>());

のようにして使います。また、priority_queue<int>のデータ構造でtopに最小のものがくるようにしたい場合、

priority_queue<int, vector<int>, greater<int> >que;

のようにします。

　ここで気になることがあります。sort()の場合は、greater<int>()と括弧つきで使用して、priority_queueの場合は括弧なしで使用しています。この違いは一体・・？そもそもこれは関数なのか、関数ポインタなのか？

ということで調べてみました。

http://www.geocities.jp/ky_webid/cpp/library/015.html

　これは、関数オブジェクト（ファンクタ）と呼ばれるらしいです。operator()がオーバーロードされていてオブジェクトを通常の関数と同様の方法で呼び出し可能にする仕組みらしいです。ということでgreater<int>()は以下のように使うことができます。

cout << greater<int>()(3,1) << endl;        // true
cout << greater<int>()(1,2) << endl;        // false
cout << greater<int>()(-1,-1) << endl;      // false

または、こんなかんじ。こっちの書き方がオブジェクトを関数のように使ってるというのが分かりやすいかも。

greater<int> g;

cout << g(3,1) << endl;        // true
cout << g(1,2) << endl;        // false
cout << g(-1,-1) << endl;      // false

　でも何だかもやもやしています。これって何が嬉しいんだろう。関数ポインタと一緒じゃ。。ということでまた調べてみました。

http://d.hatena.ne.jp/pknight/20090818/1250584515#c

　関数ポインタと比べたときの関数オブジェクトの利点は以下の2つだそうです。

• コンパイラがインライン展開しやすい
• メンバ変数を持てるので状態を持った関数を作れる

　なるほど。。2つ目の利点が面白そうで、これってクロージャとかジェネレータとかがつくれるってことなんじゃ？と思って書いてみました。

　まず、クロージャ的なやつ（実行時に入力された数値によって挙動の異なる関数を生成したように見せかける）。

template <typename T>
class Closure {
    T pw;

public:
    T operator() (T x) {
        T ret = 1;
        for (int i = 0; i < pw; i++)
            ret *= x;

        return ret;
    }

    Closure(T pw) {
        this->pw = pw;
    }
};

int main() {
    int n, m;

    cin >> n >> m;
    Closure<int> f(n), g(m);

    cout << f(10) << endl;           // 10^n
    cout << g(10) << endl;           // 10^m

    return 0;
}

　次に、ジェネレータ的なやつ（フィボナッチ数列生成器）。

class Gen {
    int a, b;

public:
    int operator() () {
        int tmp = a;

        a = b;
        b += tmp;

        return tmp;
    }

    Gen() {
        a = 1;
        b = 1;
    }
};

int main() {
    Gen gen;

    for (int i = 0; i < 30; i++)
        cout << gen() << endl;

    return 0;
}

なんかここまでくると、関数型言語みたいなことができそうじゃなイカ！？と思ってfunction composition的なものを書いてみます。最初templateをプレースホルダーのように使って書いてみました。

template <typename _T, typename _OuterFunction, typename _InnerFunction>
class Composite {
public:
    _T operator() (_T __x) {
        _OuterFunction __g = _OuterFunction();
        _InnerFunction __f = _InnerFunction();
        return __g(__f(__x));
    }
};

template <typename _T>
class dbl {
public:
    _T operator() (_T __x) {
        return 2*__x;
    }
};

template <typename _T>
class succ {
public:
    _T operator() (_T __x) {
        return __x + 1;
    }
};

int main() {
    Composite<int, succ<int>, dbl<int> > comp1;
    Composite<int, dbl<int>, succ<int> > comp2;

    cout << comp1(10) << endl;     // ((+1).(*2)) 10
    cout << comp2(10) << endl;     // ((*2).(+1)) 10

    return 0;
}

そのあと、動的に渡すような形で書けないかなーと試行錯誤して以下のようなものを書きました。

template <typename _T, typename _OuterFunction, typename _InnerFunction>
_T composite(_OuterFunction __f, _InnerFunction __g, _T __x) {
    return __f(__g(__x));
}

template <typename _T>
class dbl {
public:
    _T operator() (_T __x) {
        return 2*__x;
    }
};

template <typename _T>
class succ {
public:
    _T operator() (_T __x) {
        return __x + 1;
    }
};

int main() {
    cout << composite(succ<int>(), dbl<int>(), 10) << endl;    // ((+1).(*2)) 10
    cout << composite(dbl<int>(), succ<int>(), 10) << endl;    // ((*2).(+1)) 10

    return 0;
}

　書いた後、気付いたのですが、compositionの上のバージョンはpriority_queueと同様、下のバージョンはsort()と同様の書き方になっていました。こうやって見ると、priority_queueの場合は関数オブジェクトのクラスを、sort()の場合は関数オブジェクトのインスタンスを渡しているということに気付きます。たしかに、priority_queue<>の<>内で指定するものは"型"、sort()の引数で渡すのは実体を持った"値、または、インスタンス"であることを考えると、どっちに括弧付けないどっちに付けないのかってのは納得できます。実際にSTLのライブラリのソースを読んでみると、priority_queueの場合、第三引数で渡す_Compare（greater<int>に対応するもの）は"型"として使われていて、こういう使い方は関数ポインタだと書きづらいのかなと思いました。

木構造のメモリ確保

トライ木を使って以下の問題にトライしたところ、TLEを食らいました。

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

　最初に書いたコードはこれです。トライ木を構築して、語尾にあたる節点が子を持っていたらエラーとします。このエラー検出と同時に動的確保したメモリを解放しています。

struct Trie {
    bool tail;
    Trie *next[10];
    Trie() {
        tail = false;
        fill(next, next+10, (Trie*)0);
    }
};

Trie *find(char *t, Trie *r) {
    for (int i = 0; t[i]; ++i) {
        int c = t[i]-'0';
        if (!r->next[c]) r->next[c] = new Trie;
        r = r->next[c];
    }
    r->tail = true;
    return r;
}

bool validate(Trie *r) {
    bool hasCld = false;
    bool ret = true;
    for (int i = 0; i < 10; i++) {
        if (r->next[i]) {
            hasCld = true;
            ret &= validate(r->next[i]);
        }
    }

    if (r->tail && hasCld)
        ret = false;

    delete r;
    return ret;
}

int main() {
    int t, n;
    char num[12];

    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        Trie *rt = new Trie;
        REP(i, n) {
            scanf("%s", num);
            find(num, rt);
        }

        if (validate(rt))
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

　なんとか高速化する方法はないかと調べていたら、komiyamさんの日記におもしろいアイディアがあったので、参考にさせていただきました。毎回メモリを動的確保するのではなく、予め必要な分だけ静的領域に確保しておき、節点を生成するときは予め確保しておいたメモリのアドレスを渡すという方法です。これにより、メモリの確保/解放に係るオーバーヘッドがなくなります。また、メモリの解放をせずにすむために枝狩りができます。私の最初のソースでは、エラーを検出してもトライ木全体をトラバースしていました。これはメモリを解放するためです。メモリの解放がいらなくなると、エラーを検出した時点で探索をやめることができます。

struct Trie {
    bool tail;
    Trie *next[10];
    Trie() {
        tail = false;
        fill(next, next+10, (Trie*)0);
    }
};

Trie nodes[100000];
int ptr;

Trie *find(char *t, Trie *r) {
    for (int i = 0; t[i]; ++i) {
        int c = t[i]-'0';
        if (!r->next[c]) {
            nodes[++ptr] = Trie();
            r->next[c] = nodes + ptr;
        }
        r = r->next[c];
    }
    r->tail = true;
    return r;
}

bool validate(Trie *r) {
    for (int i = 0; i < 10; i++) {
        if (r->next[i]) {
            if (r->tail)
                return false;
            if (!validate(r->next[i]))
                return false;
        }
    }
    return true;
}

int main() {
    int t, n;
    char num[12];

    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        ptr = 0;

        nodes[ptr] = Trie();
        Trie *rt = &nodes[ptr];
        REP(i, n) {
            scanf("%s", num);
            find(num, rt);
        }

        if (validate(rt))
            puts("YES");
        else
            puts("NO");
    }

    return 0;
}

　以上がメイントピックですが、3点ほどちょっとしたTipsを書いておきます。

[C++のstructについて]

　C++のstructはCの構造体とは違います。C++の場合はstruct内にメンバ関数を持つことができます。classの場合アクセス修飾子を省略するとprivateになりますが、structの場合はpublicになるそうです。

http://www2s.biglobe.ne.jp/~ragnarok/program/cpp/struct.htm

[文字から数値への変換]

'0'　- '9'のcharを0 - 9のintに変換するとき、komiyamさんはおもしろいやり方をしています。

c & 15

でchar -> intに変換されます。確かに、'0'は16進数だと0x30なので、0x0fでマスクしてあげるとintに変換できます。

[ローカル変数のdelete]

最初、rootの接点だけローカル変数で宣言していて、validateでメモリ解放するとクラッシュしました。当然っちゃ当然ですがスタックに積まれた変数をdeleteしようとすると予期せぬ結果が発生します。再帰的処理で一括してメモリ解放するときなどに、ある特別なデータだけスタック変数だったとか結構ありそうな落とし穴なので注意。

http://stackoverflow.com/questions/441831/c-calling-delete-on-variable-allocated-on-the-stack

SRM 524 DIV2 1000 multipleswithlimit

modular arithmeticの絡んだ数論チックな問題（好きなタイプの問題）。余り毎にメモ化しておけばいいのはすぐ気付いたけど、最初のsubmissionでは、dp[2][10000]みたいにして、rolling table/flying tableを使って解いて、TLE。前回新しく更新されたところだけをpick upすればいいので、priority_queueを利用したダイクストラ法のようなやり方をすればいいのに気付く。これでAC。

（追記）editorial読んだら、queueでいいっぽい。最初に埋まったやつがbestになるから、確かにqueueでOK。

typedef pair<int, pair<string, int> >  ISI;
string dp[10000];

class MultiplesWithLimit {
    string format(string x) {
        if (x.length() < 9)
            return x;

        char ret[512];
        sprintf(ret, "%s...%s(%d digits)", x.substr(0, 3).c_str(), x.substr(x.length()-3).c_str(), x.length());

        return ret;
    }

    bool contain(vector<int> vec, int n) {
        REP(i, vec.size())
            if (vec[i] == n)
                return true;

        return false;
    }

public:
    string minMultiples(int N, vector<int> forbiddenDigits) {
        vector<int> nums;

        REP(i, 10) {
            if (!contain(forbiddenDigits, i))
                nums.push_back(i);
        }

        priority_queue<ISI, vector<ISI>, greater<ISI> > Q;
        Q.push(MP(0, MP("", 0)));
        string ret = "";

        REP(i, 10000) dp[i] = "";
        while (!Q.empty()) {
            string str = Q.top().second.first;
            int rm = Q.top().second.second;

            Q.pop();
            if (rm == 0 && str != "") {
                ret = str;
                break;
            }
            if (dp[rm].length() < str.length() ||
                (dp[rm].length() == str.length() && dp[rm] < str))
                continue;

            REP(i, nums.size()) {
                int rm_t = (10 * rm + nums[i]) % N;
                string str_t = str + (char)(nums[i] + '0');

                if (str_t == "0") continue;
                if (dp[rm_t] == "" ||
                    str_t.length() < dp[rm_t].length() ||
                    (str_t.length() == dp[rm_t].length() && str_t < dp[rm_t])
                ) {
                    dp[rm_t] = str_t;
                    Q.push(MP(str_t.length(), MP(str_t, rm_t)));
                }
            }
        }

        if (ret == "")
            return "IMPOSSIBLE";

        return format(ret);
    }
};

SRM 523 DIV2 1000 smallbricks31

　On top of the basement of size 1*1*w, we like to construct a building object using three types of bricks, whose sizes are 1*1*1, 1*1*2, 1*1*3, respectively. The height of the building is at most h. How many different type of buildings could you construct under some constraints? -- A concise summery is like that.

At first glance, I was like, "Umm, this is a simple bit DP problem." But it took me longer to implement the idea than I thought. Guess I have to solve this level of problem within 30 minutes to be a yellow coder. Just need more practices!!

const LL MOD = 1000000007LL;

LL dp[10+1][1<<10];
LL ptr[1<<10][1<<10];

void init(int x, int y, int b) {
    if ((1<<b) > x) return;

    init(x, y, b+1);
    if (x >> b & 1) {
        init(x, y | 1<<b, b+1);
        ++ptr[x][y | 1<<b] %= MOD;
    }
    if ((x >> b & 1) && (x >> (b+1) & 1)) {
        init(x, y | 3<<b, b+2);
        ++ptr[x][y | 3<<b] %= MOD;
    }
    if ((x >> b & 1) && (x >> (b+2) & 1)) {
        init(x, y | 7<<b, b+3);
        ++ptr[x][y | 7<<b] %= MOD;
    }
}

class SmallBricks31 {
public:
    int countWays(int w, int h) {
        memset(dp, 0, sizeof(dp));
        memset(ptr, 0, sizeof(ptr));

        REP(i, 1<<10) {
            if (i > 0) {
                int b = 0;
                while (!(i & 1<<b))
                    ++b;
                init(i, 0, b);
            }
        }

        dp[0][(1<<w)-1] = 1;
        REP(i, h) REP(j, 1<<w) {
            if (!dp[i][j]) continue;

            REP(k, 1<<w) {
                if (ptr[j][k]) {
                    LL tmp = dp[i][j] * ptr[j][k] % MOD;
                    dp[i+1][k] = (dp[i+1][k] + tmp) % MOD;
                }
            }
        }

        LL ret = 0;
        FOR (i, 1, h+1) REP(j, 1<<w) ret = (ret + dp[i][j]) % MOD;

        return ++ret % MOD;
    }
};

サーバー奮闘記（17） Hadoopインストール

"stone setting" by angela7dreams

　Hadoop（最新安定ver 0.20.203）試してみました。Pseudo-Distributedモードでexampleをいくつか動かしてみました。ほとんど公式ホームページにあるとおりにやればOKですが、いくつかひっかかったところがあったので、メモしておきます。

[SSHのオプション]

SSHのポートをデフォルトの22以外にしている場合は設定ファイルにsshのオプションを設定。

（例：ポート1234の場合）

conf/hadoop-env.sh に以下追記。

export HADOOP_SSH_OPTS="-p 1234"

[Webインターフェース]

NameNode、JobTrackerのステータス確認用のwebインターフェース

http://localhost:50070/

http://localhost:50030/

があって、プラスα的な機能かなと勝手に思い込んでいたら、このページを開かないとhdfsがきちんと機能しないらしい。

[データ保存領域の設定]

Ubuntuだと再起動後に、dfsのテンポラリーディレクトリに保存したファイルが消えてしまいます。保存先をデフォルトのtmpから変更してあげればOKです。

conf/core-site.xmlに以下の設定を追記。

<property>
    <name>hadoop.tmp.dir</name>
    <value>/home/kenji/hadoop-data</value>
    <description>hadoopのデータ保存領域</description>
</property>

[example実行]

bin/hadoop jar hadoop-examples-0.20.203.0.jar xxxx

とする。xxxxは実行したいサンプル。

wordcountを実行したい場合は、

bin/hadoop jar hadoop-examples-0.20.203.0.jar wordcount input output

のようにする。

サーバー奮闘記（16） SSHのRSA鍵設定、rm、emacsの設定など

vps初めて半年くらい経ちました。当初借りたは良いけど、何をしたらいいのか分からない状態でしたが、適当にwebサービスを作ったりしてまあまあ活用できている気がします。最近気に成っていたことがいくつかあったので、まとめて片づけました。

1. SSHのRSA鍵設定
2. aliasでrmをrm -i にする
3. emacsのバックアップファイルを作成しないようにする

　まず1。プレインテキストでユーザー情報とかパスワード流すのやばいだろう。。（※訂正：teratermのオプションにプレインテキストって書いてあったので平文で流れているのかと思いましたが、mojavy先生曰くsshではすべての通信が暗号化されているため、プレインテキストでパスワードが流れるなんてことは無いそうです。）vpsで誰かがtcpdumpとかしてたら漏れ漏れじゃないですか@_@　と前々から思っていて、いつの間にか忘れていて、セキュリティの読み物見ていたら思い出して、即実行しました。

　http://d.hatena.ne.jp/elwoodblues/20070620/1182330984

を参考にしました。

　上のサイトにあるようにローカルで鍵ペアを作成して、サーバーに公開鍵を送るようにしましょう。サーバーで作って、秘密鍵をローカルに転送とかやってたら本末転倒なので。

　あと、SSH認証を使いますっていうのをtera termの初期設定ファイルに保存しておくとログインがらくです。「設定」 -> 「SSH認証」 と進み、

1. 「ユーザ名」にユーザ名を入力
2. 「RSA/DSA鍵を使う」にチェック
3. 「秘密鍵」項目で秘密鍵のファイルを選択
4. 「OK」ボタン押下

とし、「設定」 -> 「設定の保存」を選んで、INIファイルに設定を保存します。

　2. はtypoでrm *とかやったら泣けるなーと思ってその予防策。

~/.bashrcに以下追記。

alias rm='rm -i'

　3. は、毎回チルダから始まるバックアップファイルを作っているのがemacsだと分かったので作らないように設定。

~/.emacsに以下の設定追記。

(setq make-backup-files nil)

ヨセフス数（Josephus Number）の求め方

ヨセフスの問題（Josephus problem）という有名問題があります。これの一般解を求める式があるらしいので調べてみました。

　以下では、円を組む人の数をn、スキップ数をkとします。本来は、n番目（つまり最後に）処刑される人の番号を求めればよいのですが、より汎用的にs番目に処刑される人の位置を求めることにします。

　ここのページにあるように、以下のソースコードでs番目に処刑される人の位置がわかります。

int josephus(int n, int k, int s) {
    int ret = k * s;

    while (ret > n)
        ret = ((ret - n) * k - 1) / (k - 1);

    return ret;
}

　えーーっと、よくわかりません。ということで、何故上のコードで答えがでるのか考えてみました。（結構がんばりました（汗）。）

まずは、正の整数xに対して、f_k: x -> (x * k - 1) / (k - 1)という写像が何をするのか考えます。

k = 2のとき

f_2(1) = 1

f_2(2) = 3

f_2(3) = 5

f_2(4) = 7

・・・・・

k = 3のとき

f_3(1) = 1

f_3(2) = 2

f_3(3) = 4

f_3(4) = 5

f_3(5) = 7

・・・・・

ふーむ、どうやらf_kは、自然数からなる点列(1,2,3,...)からkの倍数を取り除くような効果があるようです。本当か？ちょっと数学的に考えてみます。

f_k(x) = (k * x - 1) / (k - 1)なので、f_k(1) = (k*1 - 1) / (k - 1) = 1です。

f_k(2) = (k*2 - 1) / (k - 1) はコンピュータの整数演算では2ですが、数学上は、2余り1です。

同様に、

f_k(3) = 3余り2

f_k(4) = 4余り3

・・・・

f_k(k) = k余り(k-1)

です。f(k)は(k-1)余ってますが、(k-1)で割るのでこの余りは消えて商が1増えます。ということで、f(k) = k+1となります。これで、(1,2,3,.....k)という点列が(1,2,3,....,k-1, k+1)となりました。さらに続きを調べるために、g_k(x) = (k * x - 1) を (k-1)で割った余りが0になる場所を調べます。

g_k(1) = 0 (mod (k-1))

g_k(k) = 0 (mod (k-1))

g_k(2*k-1) = 0 (mod (k-1))

・・・・

なので、y = 1 + i * (k-1), i = 0,1,2,3,...なる正の整数yに対してg_k(y) = 0 (mod (k-1))となります。先の例で正の整数の点列からkが除去されることを確認しました。2*k-1という場所は本来2*kがある場所です。（kが無くなってるから1引かれる）。ここで同様に商の繰り上がりがおこることから、2*kは点列から除去されます。同様に3*k-2に対応する3*kも除去されます。以降同様にして、kの倍数がすべて除去されるというわけです。

　ここまでで、写像f_kがkの倍数だけを除いた整数点列を生成できることが分かりました。ソースコードを見ると、まず

ret = k * s;

としているので、retは、(1,2,3...n)の点列を拡張して、(1,2,3,....,n,n+1,n+2,....... k*s)にしたものを考えていることが分かります。ここから逆算して、k*sが区間[1,n]の整数のどれに対応しているかをみていこうというわけです。(ret - n)でnからはみ出ている分が分かります。このはみ出ている部分に対して、写像f_kを適用することで、retは消えたものを除いて数えた場合にそれがあるべき場所へとマッピングされます。これをret <= nになるまで繰り返しているというわけです。ちょっと説明足らずな感じなので、表で示します。n = 5, k = 3, s = 5とした場合、

k*s	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
k*s - n	-	-	-	-	-	1	2	3	4	5	6	7	8	9	10
f_k(k*s - n)	-	-	-	-	-	1	2	4	5	7	8	10	11	13	14

となります。例えば、処刑される順番は、k*s = 3, 6, 9, 12, 15の順です。それぞれ見て行きます。

1番目に処刑される人は、3番目の人です。

2番目に処刑されるのは、6ですが、これはnより大きいので、もともといる位置に変換します。表のf_k(k*s - n)を見ると1なので、1番目の人です。

3番目に処刑されるのは、9ですが、これも同様に対応位置に変換して5になります。

4番目に処刑されるのは、12 -> 10 -> 7 -> 2と変換されるので、2番目の人です。

同様に、最後に処刑されるのは、15 -> 14 -> 13 -> 11 -> 8 -> 4で4番目の人です。

ということで、(3, 1, 5, 2, 4)の順で処刑されるということです。4の位置に居れば助かりますね！

アセンブラを出力して遊ぶ

簡単なプログラムをアセンブラで出力して、スタックの動きを追ってみます。簡単なプログラムですが、結構面白いです。環境は、Ubuntu、gcc 4.4.3です。

　まず、Cのソースコード（test.c）。

#include <stdio.h>

main()
{
  int i, j, k;

  i = 1;
  j = 2;
  k = i + j;
  printf("%d %d %d\n", i, j, k);
}

　そして、アセンブラ（test.s）。

$ gcc -S test.c

でアセンブラのコードを出力できます。

    .file    "test.c"
    .section    .rodata
.LC0:
    .string    "%d %d %d\n"
    .text
.globl main
    .type    main, @function
main:
    pushl    %ebp
    movl    %esp, %ebp
    andl    $-16, %esp
    subl    $32, %esp
    movl    $1, 28(%esp)
    movl    $2, 24(%esp)
    movl    24(%esp), %eax
    movl    28(%esp), %edx
    leal    (%edx,%eax), %eax
    movl    %eax, 20(%esp)
    movl    $.LC0, %eax
    movl    20(%esp), %edx
    movl    %edx, 12(%esp)
    movl    24(%esp), %edx
    movl    %edx, 8(%esp)
    movl    28(%esp), %edx
    movl    %edx, 4(%esp)
    movl    %eax, (%esp)
    call    printf
    leave
    ret
    .size    main, .-main
    .ident    "GCC: (Ubuntu 4.4.3-4ubuntu5) 4.4.3"
    .section    .note.GNU-stack,"",@progbits

　いろいろ分かることがあります。

　まず、スタックのアドレスが番地の大きい方から小さいほうへと広がっているところです。これはx86マシンでは共通だと昔聞いたことがあります。

　それから、andl $-16, %esp があるので、16byteのaddress alignmentを使っているようです。FFFFFFF0でマスキングして16の倍数になる次の数をスタックポインタに代入しています。これだとベースポインタとスタックポインタの整合性があわないようにみえるんですけど、結局ベースポインタ使ってないし、リターンする時ベースポインタをスタックポインタに戻す処理も省略されてるので別にいいような気もします。

　意外だったのは、スタック内の変数にスタックポインタからの差分でアクセスしているところです。スタックポインタは実行時に移動するから、ベースポインタからの差分で変数にアクセスするのが普通かと思いましたが、そうでもないみたいです。

　あと、最後にprintfの可変長引数のところの仕組みがおもしろいです。第一引数の%dが3つあるんで、第一引数をpopしたあと、3回popすればいいんですねー。当然といえば当然ですが、実際コード上でみるとちょっとした感動がありました。printfがcallされるときのstackの状態は下のようになっています。

素数とは宇宙の創造主が人間に与えた暗号である

"On the trail" by Mr eNil

最近、素数に関するNHKのドキュメンタリーを見た。それそれは、もう、感動でした。宇宙の神秘、数学の美に魅せられました。元ネタは、『魔性の難問 ～リーマン予想・天才たちの闘い～』です。要約を書きます。

　まず、素数とは何か？それ自身と1以外に約数を持たない正の整数のことです。2,3,5,7,11,13....と無限に続きます。この素数列の並びはランダムに見えます。しかし、2人の有名な数学者が素数と自然界においてとても重要な数を結びつけました。レオンハルト・オイラーは、素数と円周率πの間に以下の関係を見出しました。

まったくランダムに見える素数に関する式を無限個掛けあわせると、なんと世界で最も美しい数πがでてくるのです。これによって、オイラーは素数と円や球体が何らかの関係を持っていることを発見しました。

　それから、カール・フリードリヒ・ガウスは、ある正数xまでに現れる素数の数は以下の式で近似できることを発見しました。いわゆる素数定理ってやつですね。

ln()は自然対数で、その底はeです。eは、カタツムリの渦巻き、台風、銀河なのどの自然界で多くみられる螺旋形状と関連のある数字です。

　オイラーとガウスの手によって、ランダムな素数が数のキングおよびクイーンと関連付けられました。そして、素数と自然界には何らかの関係があるのではと考えられるようになったのです。その考えはベルンハント・リーマンによって『何らかの関係がある』から以下のような数学的な問題へと変換されました。

ゼータ関数

の非自明な零点は一直線上に並ぶ。

ゼータ関数が零になるようなx（複素数）を複素平面上にプロットすると、なんとそれが一直線上に並ぶというのです。衝撃的ですね！

　上記のリーマン予想は、現在証明されておらず、N ≓　NP予想などと同様にミレニアム懸賞問題の一つです。今まで、ジョン・ナッシュやアラン・チューリングといった偉大な数学者、暗号科学者たちがその証明を試みましたが、失敗に終わっています。

　時は流れて、違ったアプローチでリーマン予想にチャレンジする数学者が現れました。ヒュー・モンゴメリーは、直線状にならぶ零点の間隔に興味をもちました。そして、たまたま出会った物理学者フリーマン・ダイソンに零点の間隔の式を見せた時に、ダイソンは言いました。「それはすごい！その式はウランなどの原子核のエネルギーレベルの間隔を表す式と同じような形をしている！」

素数と量子力学の世界、まったく異なる分野が一つになった瞬間でした。

　この発見を機に、多くの物理学者がゼータ関数の零点と同じ間隔をもった原子を探すようになりました。すると今度は、非可換幾何学というまったく異なる学問を研究しているアラン・コンヌが閃いたのです。「モンゴメリーの発見を発端として、物理学者たちは素数と関連をもつ空間をさがしている。そして、その空間とは非可換幾何学と完璧に一致する空間である。」当時、非可換幾何学は、量子力学を書き変え森羅万象の原理を説明する究極の法則『万物の理論』の基礎になると期待されていた学問でした。宇宙の創生と素数が繋がっていることを示す非常に興味深い話です！

　ある数学者はいいます。

「非可換幾何学を使って素数の謎がとかれるとき、森羅万象を説明する万物の理論--いわば創造主による宇宙の設計図--も明らかになるだろう。」と。

Google Developer Day Japan 2011

　『Webの世界はすさまじい速度で進化してきた。次世代のWebがどのようなものになるのか私は分からない。しかし確かなことがある。次世代の新しいWebはこの部屋にいる技術者たちによって作られだろう。そして未来のビジネスはあなた方がつくった新しい仕組みのうえで展開される。』

　―先日、Google Developer Day 2011が横浜で開催されました。Googleの製品へ高い貢献をしているDeveloper、およびDevQuizで高得点を取り招待状をゲットしたエンジニア、約2000人が一同に会しました。

　Google Developer Dayは午前の部と午後の部に大きく分かれていて、午前はKeynote Speech、午後は複数のSessionが同時進行するという形で構成されていました。主に、

• Android
• Chrome
• App Engine
• HTML5
• Google+

などの技術の最新動向が発表されました。また、技術者同士が会話をしたり、Googleのエンジニアとコミュニケーションを取ったりできるような工夫が施されており、とても楽しいイベントでした。私自身も、缶バッジ交換のおかげでゲーム業界のエンジニアの人とお話することができ非常にいい経験となりました。

　特に私の印象に残ったのは以下の3点です。

1. ScalabilityとAgility
2. Googleマインド
3. エンジニアとしての社会貢献

　1. 『これからのWebのサービスにおいて重要なものは、どうスケールするか、そして如何に柔軟な開発スタイルを取り入れていくかだ。』特に、アジャイル開発の重要性に関しては、Googleの東日本大震災に対する取り組みの中でも語られました。

　アジャイル開発を行うためには、プロトタイピング力を持ったエンジニアの存在が絶対条件だと思います。しかし、浮かんだアイディアをすぐに実装できるエンジニアは日本には決定的に少ないように感じます。これはそもそも、日本のシステム業界（とりわけSIer業界?）が要件定義/設計/開発/テスト/保守のように縦割りになっていることが原因じゃないかと。。要件定義はできるけど、fizzbuzzも書けないエンジニア。開発はできるけど要件がまったく分からないエンジニア。アジャイル開発を取り入れるためには、まずこのあたりの体質を変えていく必要があるのかなと思いました。

　2. これは、単純にいいな～と（羨ましいなと）。。会社のスローガンって見栄えだけ綺麗で中身が伴っていないことがしばしばありますが、Googleが大切にしているという以下の三箇条は本物だなと感じました。

• なにごともエンジニアありき
• 百聞は一デモに如かず
• 日本で「イケる！」と思ったら、世界のみんなも同感するかも

　3. 「Googleのクライシスレスポンス」というSessionで、東日本大震災に対するGoogleの取り組みが語られました。『すべてが自動化された完璧なシステムを届ける必要はない。途中に人の手が入っていてもかまわない。』『当初、被災地の人達が欲していたのは、スマートフォン上で起動するアプリでもクラウド上で動作するアプリでもなかった。エクセルやアクセスといったごく単純な技術だった。』

　技術者として最新技術を追うことや完璧を求めることも大事だけど、今自分が持っている技術がどう世の中に役に立つのかと考えて実践するというのは本質的により重要なことだなと改めて考えさせられました。自分の技術なんて大したことないやと卑屈にならずに、少しでも世の中が変わる、少しでも世の中に役に立つはずと信じてサービスを提供していきたいなと思いました。