順列と辞書順の相互変換

問題設定

　どこかで見たことのあるような問題ですが、ふと以下のような問題を考えてみたくなりました。

"ABCDE....XYZ"のpermutationを考える。7777777777番目（0-based）のpermutationを求めよ。
例えば、 ABCDEFGHIJKLMNOPQRSTUVWXYZは0番目のpermutation。 ABCDEFGHIJKLMNOPQRSTUVWXZYは1番目のpermutation。 ..... と続きます。

　以前TopCoderで似たような問題を解いたことがあったので、スムーズに書けました。悩ましいのは23行目のifのところに等号をつけるかどうかですが、「index番目をくれ」と言われたらindex+1以上持っている必要があり（0-basedだから）index個では足りないので次の文字まで行きます。
　ついでに、逆変換する関数（permutationが与えられるので、辞書順で何番目かを返す関数）も書きました。

ソースコード

view plainprint?

1. #include <iostream>  
2. #include <cstring>  
3. #include <algorithm>  
4. #include <cassert>  
5.   
6. using namespace std;  
7.   
8. const long long INF = 1LL << 50;  
9. long long f[26];  
10.   
11. // return the index-th(0-based) permutation of "ABCD...Z"  
12. string toPermutation (long long index) {  
13.     bool used[26];  
14.     char permutation[26+1];  
15.   
16.     memset(used, 0, sizeof(used));  
17.     memset(permutation, 0, sizeof(permutation));  
18.   
19.     for (int i = 0; i < 26; i++) {  
20.         for (int j = 0; j < 26; j++) {  
21.             if (used[j])  
22.                 continue;  
23.             if (f[25-i] <= index)  
24.                 index -= f[25-i];  
25.             else {  
26.                 permutation[i] = static_cast<char>('A'+j);  
27.                 used[j] = 1;  
28.                 break;  
29.             }  
30.         }  
31.     }  
32.   
33.     return permutation;  
34. }  
35.   
36. // return the lexicological order(0-based) of a permutation  
37. long long toIndex(string permutation) {  
38.     bool used[26];  
39.   
40.     memset(used, 0, sizeof(used));  
41.     long long ret = 0;  
42.     for (int i = 0; i < 26; i++) {  
43.         int c = permutation[i] - 'A';  
44.         for (int j = c-1; j > 0; j--) {  
45.             if (!used[j])  
46.                 ret += f[25-i];  
47.         }  
48.         used[c] = 1;  
49.     }  
50.   
51.     return ret;  
52. }  
53.   
54. int main(int argc, char **argv) {  
55.     // calculate factorials  
56.     f[0] = 1;  
57.     for (int i = 1; i < 26; i++)  
58.         f[i] = min(i*f[i-1], INF);  
59.   
60.     long long index;  
61.     cout << "input an integer:(up to 10 digits)" << endl;  
62.     cin >> index;  
63.     assert(index < 1e10);  
64.   
65.     cout << "The " << index << "-th permutation is " << toPermutation(index) << endl;  
66.   
67.     // for debug use  
68.     assert(toIndex(toPermutation(index)) == index);  
69.   
70.     return 0;  
71. }  

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cassert>

using namespace std;

const long long INF = 1LL << 50;
long long f[26];

// return the index-th(0-based) permutation of "ABCD...Z"
string toPermutation (long long index) {
    bool used[26];
    char permutation[26+1];

    memset(used, 0, sizeof(used));
    memset(permutation, 0, sizeof(permutation));

    for (int i = 0; i < 26; i++) {
        for (int j = 0; j < 26; j++) {
            if (used[j])
                continue;
            if (f[25-i] <= index)
                index -= f[25-i];
            else {
                permutation[i] = static_cast<char>('A'+j);
                used[j] = 1;
                break;
            }
        }
    }

    return permutation;
}

// return the lexicological order(0-based) of a permutation
long long toIndex(string permutation) {
    bool used[26];

    memset(used, 0, sizeof(used));
    long long ret = 0;
    for (int i = 0; i < 26; i++) {
        int c = permutation[i] - 'A';
        for (int j = c-1; j > 0; j--) {
            if (!used[j])
                ret += f[25-i];
        }
        used[c] = 1;
    }

    return ret;
}

int main(int argc, char **argv) {
    // calculate factorials
    f[0] = 1;
    for (int i = 1; i < 26; i++)
        f[i] = min(i*f[i-1], INF);

    long long index;
    cout << "input an integer:(up to 10 digits)" << endl;
    cin >> index;
    assert(index < 1e10);

    cout << "The " << index << "-th permutation is " << toPermutation(index) << endl;

    // for debug use
    assert(toIndex(toPermutation(index)) == index);

    return 0;
}

vectorの比較

　C++のvectorは辞書順比較です。以下の比較はいずれもxが小さいと判定されます。

view plainprint?

1. void compare1() {  
2.     vector<int> x;  
3.     vector<int> y;  
4.   
5.     x.push_back(10);  
6.     x.push_back(42432);  
7.     x.push_back(543252);  
8.     x.push_back(53453453);  
9.   
10.     y.push_back(12);  
11.     y.push_back(0);  
12.   
13.     cout << (x < y) << endl;     // true  
14. }  
15.   
16. void compare2() {  
17.     vector<int> x;  
18.     vector<int> y;  
19.   
20.     x.push_back(1);  
21.     x.push_back(2);  
22.   
23.     y.push_back(1);  
24.     y.push_back(2);  
25.     y.push_back(-100);  
26.   
27.     cout << (x < y) << endl;     // true  
28. }  

void compare1() {
    vector<int> x;
    vector<int> y;

    x.push_back(10);
    x.push_back(42432);
    x.push_back(543252);
    x.push_back(53453453);

    y.push_back(12);
    y.push_back(0);

    cout << (x < y) << endl;     // true
}

void compare2() {
    vector<int> x;
    vector<int> y;

    x.push_back(1);
    x.push_back(2);

    y.push_back(1);
    y.push_back(2);
    y.push_back(-100);

    cout << (x < y) << endl;     // true
}

タイピング矯正キーバインド

ホームポジションから手を離さなくするための矯正ギプス（emacs）。

(global-set-key (kbd "<return>") 'beep)
(global-set-key (kbd "<backspace>") 'beep)
(global-set-key (kbd "<delete>") 'beep)
(global-set-key (kbd "<up>") 'beep)
(global-set-key (kbd "<down>") 'beep)
(global-set-key (kbd "<left>") 'beep)
(global-set-key (kbd "<right>") 'beep)
(global-set-key (kbd "<tab>") 'beep)

英単語を覚えるwebアプリ

　英単語を覚えるためのwebアプリを作りました。とりあえず今のところは自分専用ですが、使ってみたいという人がいたら複数人で使えるような形にしようかなと思います。

出来たもの

http://goodpreparations.co.cc/wordmemorizer/main.php

※動作確認環境　Google Chrome (ver 17.0.963.79)

英単語を覚えることについて

　英語初級レベル（TOEIC700未満くらい）だと英単語を覚えるという作業は不要だと思います。英単語を覚える暇があったら、たくさん文章を読んだ方がいいと思います。文章を読んで前後の文脈から知らない単語の意味を推測する力を付けるのです。また、このレベルだと知らない単語といっても頻出単語が多いと思います。知らない単語に出会う、意味を推測する、それがあってるか確かめる、これを繰り返していれば自然と語彙は増えていきます。

　中級レベル（TOEIC900超えたくらい）になると、語彙が大切になってくると思います。まず知らない単語に出会ったとして次にその単語に出会う頻度が確実に低くなります。なので、初級レベルで行うような方法では知ってる単語数を効率的に増やすことは難しいです。そもそもそんな滅多に出会わないような単語覚えなくてもいいんじゃない？という考え方もありますが、上級レベルに達したい場合は難しい単語も積極的に覚えていきたいわけです。

　また、TOEICで基本的なリーディング、リスニングができるようになると、次はスピーキング、ライティング力を鍛えるようになります。特にスピーキングは語彙が重要です。例えば、「中指を突き指した。」「頭にたんこぶができた。」「足がつった。」など日常よく使いそうな言葉でもなかなか表現がぱっとでて来ません。もちろん、「中指が痛い」とか「頭をぶつけて痛い」とか伝わるレベルの表現ならできますが、より詳細に伝えたい場合は豊富な語彙が必要になります。

工夫した点

　英才教育を受ける園児が紙に書いた何かを高速で見せられているのをテレビでみました。最初はスピードが遅くて、徐々に速くしていくというものです。単純にこれをjavascriptで実装しました。

　また、新しいことを覚える場合には

1. 新しいことを覚える
2. 次の日に覚えたことを確認する
3. １週間後にもう一度確認する
4. １カ月後に確認する（忘れていたものがあったら、重点的に見る）
5. 半年後に確認する （忘れていたものがあったら、重点的に見る）

ということをするとよいと脳科学的に推奨されていました。（期間はうろ覚えです。。）これを参考に、

1. 直近で登録された100単語のみをランダムで出す
2. 覚えていなかったものから100単語をランダムに出す
3. すべての単語から100単語をランダムに出す

をできるようにしました。今のところ、効率的に覚えられていると思います。（まだ、100単語しか登録してないですが。。）

技術的な話

　今回jsonを利用した非同期通信に初めてチャレンジしました。1つ目は、非同期通信によるデータベース更新です。

1. チェックボックスの変化をjavascriptのイベントハンドラでキャッチする。
2. 更新したいデータをGETパラメータに入れてjQuery.get()でCGI（php）にアクセスする。
3. CGI側で、GETで受け取ったパラメータに応じてDBを更新。更新結果をjson形式で出力する。
4. 3.の出力内容に応じてコールバック処理を実行する。

　2つ目は、テキストエリア内に表示する単語リストの更新です。

1. ラジオボタンの変化をjavascriptのイベントハンドラでキャッチする。
2. 選択されたボタンタイプをGETパラメータに入れてjQuery.get()でCGI（php）にアクセスする。
3. CGI側で、GETで受け取ったパラメータに応じてSQLを発行し結果をjson形式で出力する。
4. 3.の内容をコールバック関数内でローカルな変数（DOMで読みとるデータ）にコピーする。

　簡単なことですが、感動しました。「これが、ajaxか！！」と。だいぶ時代遅れですいません。あとは、今回からgitを使ってきちんとソースコードを管理するようにしました。エクセル方眼系エンジニアな私ですが、web系エンジニアさん達との技術の差をちょっとでも埋められるように地道にがんばります。

SRM 537 DIV1 275 KingXNewCurrency

問題

　正の整数A, B, Xが与えられる。任意の非負正数p, qに対してAp + Bq = Xp' + Yq'となるような非負正数p', q'が存在するような正の整数Yの個数を求めよ。

方針

　あるYにおいて、任意の非負整数p, qに対して問題の等式が成り立つような(p', q')が存在するとする。このとき特に(p, q) = (1, 0)とすると、A = Xp' + Yq'が成り立つ。同様に、(p, q) = (0, 1)のときは、B = Xp' + Yq'が成り立つ。つまり、AとBは、X, Yの非負線形結合で表すことができる。

　逆に、AとBの両方がX, Yの非負線形結合で表されるとする。このとき、明らかに任意のp, qに対して問題の等式を満たすp', q'が存在する。

　よって、問題の等式を満たすYの個数は、A, BをX, Yの非負線形結合で表すことのできるようなYの個数と同じ。

ソースコード

　O(N²)バージョンと、拡張ユークリッド互除法を用いたO(N (log(N))²)バージョンを載せて起きます。今回の問題では、O(N²)で十分です。

view plainprint?

1. class KingXNewCurrency {  
2. public:  
3.     int howMany(int A, int B, int X) {  
4.         if (A % X == 0 && B % X == 0)  
5.             return -1;  
6.   
7.         int ret = 0;  
8.         for (int Y = 1; Y <= 200; Y++) {  
9.             bool cana = false;  
10.             bool canb = false;  
11.   
12.             for (int t = A; t >= 0; t -= X)  
13.                 if (t % Y == 0)  
14.                     cana = true;  
15.   
16.             for (int t = B; t >= 0; t -= X)  
17.                 if (t % Y == 0)  
18.                     canb = true;  
19.   
20.             if (cana && canb)  
21.                 ++ret;  
22.         }  
23.   
24.         return ret;  
25.     }  
26. };  

class KingXNewCurrency {
public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int ret = 0;
        for (int Y = 1; Y <= 200; Y++) {
            bool cana = false;
            bool canb = false;

            for (int t = A; t >= 0; t -= X)
                if (t % Y == 0)
                    cana = true;

            for (int t = B; t >= 0; t -= X)
                if (t % Y == 0)
                    canb = true;

            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};

view plainprint?

1. int extGcd (int a, int b, int &x, int &y) {  
2.     if (b == 0) {  
3.         x = 1;  
4.         y = 0;  
5.         return a;  
6.     }  
7.     int d = extGcd(b, a%b, y, x);  
8.     y -= a/b * x;  
9.     return d;  
10. }  
11.   
12. class KingXNewCurrency {  
13.     bool canMake(int A, int x, int y, int g, int p, int q) {  
14.         int lcm = x * y / g;  
15.         int dp = lcm / x;  
16.         int dq = lcm / y;  
17.         p = A * p / g;  
18.         q = A * q / g;  
19.   
20.         if (p < 0) {  
21.             int add = (-p + dp - 1) / dp;  
22.             p += add * dp;  
23.             q -= add * dq;  
24.         }  
25.         else if (q < 0) {  
26.             int add = (-q + dq - 1) / dq;  
27.             p -= add * dp;  
28.             q += add * dq;  
29.         }  
30.   
31.         return p >= 0 && q >= 0;  
32.     }  
33.   
34. public:  
35.     int howMany(int A, int B, int X) {  
36.         if (A % X == 0 && B % X == 0)  
37.             return -1;  
38.   
39.         int p, q, g, ret = 0;  
40.         bool cana, canb;  
41.         for (int Y = 1; Y <= 200; Y++) {  
42.             g = extGcd(X, Y, p, q);  
43.   
44.             cana = (A % g) ? false : canMake(A, X, Y, g, p, q);  
45.             canb = (B % g) ? false : canMake(B, X, Y, g, p, q);  
46.             if (cana && canb)  
47.                 ++ret;  
48.         }  
49.   
50.         return ret;  
51.     }  
52. };  

int extGcd (int a, int b, int &x, int &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    int d = extGcd(b, a%b, y, x);
    y -= a/b * x;
    return d;
}

class KingXNewCurrency {
    bool canMake(int A, int x, int y, int g, int p, int q) {
        int lcm = x * y / g;
        int dp = lcm / x;
        int dq = lcm / y;
        p = A * p / g;
        q = A * q / g;

        if (p < 0) {
            int add = (-p + dp - 1) / dp;
            p += add * dp;
            q -= add * dq;
        }
        else if (q < 0) {
            int add = (-q + dq - 1) / dq;
            p -= add * dp;
            q += add * dq;
        }

        return p >= 0 && q >= 0;
    }

public:
    int howMany(int A, int B, int X) {
        if (A % X == 0 && B % X == 0)
            return -1;

        int p, q, g, ret = 0;
        bool cana, canb;
        for (int Y = 1; Y <= 200; Y++) {
            g = extGcd(X, Y, p, q);

            cana = (A % g) ? false : canMake(A, X, Y, g, p, q);
            canb = (B % g) ? false : canMake(B, X, Y, g, p, q);
            if (cana && canb)
                ++ret;
        }

        return ret;
    }
};

SRM 299 DIV2 1000 StrangeParticles

問題概要

　空間を飛び回る粒子があります。２つの粒子がぶつかると、以下の３つのうちどれかが起きます。

1. 最初の粒子が消滅する
2. ２つ目の粒子が消滅する
3. 何も起こらない

粒子の数は50個以下です。任意のペアの粒子が衝突した場合、上の1-3のうちどれが起こるかという情報が与えられます。その情報を元にランダムな回数・順番で粒子同士が衝突したとき、最終的に残る粒子の数の最小値を求めよ。

方針

　強連結成分（SCC）分解して、DAGにして、DAGの根の数が答え。強連結成分分解は、DFSを二回やる方法が有名ですが、この問題では節点数が小さいのでワーシャルフロイド法を利用したやり方でもできます。

1. 粒子Aが粒子Bを消すことができるとき、AからBへ有向枝をはる。
2. ワーシャルフロイドで、1.の推移閉包を求める。
3. i->jパス、j->iパスが同時に存在するとき、閉路と考える。これを利用して、SCCにグルーピングしていく。
4. SCCを1つの節点とみなして、枝をはり直してDAGにする。
5. 各接点の入次数を数える。

まあソース見た方が早いです。DFS2回バージョンは直感的に理解するのが難しいですが、こっちのワーシャルフロイドバージョンは直感的につかみやすいですねー。実装量も少ないので、計算量に余裕がある場合はこっちのほうがいいかもしれません。

ソースコード

view plainprint?

1. bool win[50][50];  
2. int id[50];  
3. int d[50];  
4.   
5. class StrangeParticles {  
6. public:  
7.     int remain(vector<string> interacts) {  
8.         int N = interacts.size();  
9.   
10.         memset(win, 0, sizeof(win));  
11.         REP(i, N) REP(j, N) if (i == j || interacts[i][j] == '-') win[i][j] = 1;  
12.         REP(k, N) REP(i, N) REP(j, N) win[i][j] |= win[i][k] & win[k][j];  
13.   
14.         memset(id, -1, sizeof(id));  
15.         int p = 0;  
16.         REP(i, N) {  
17.             if (id[i] == -1) {  
18.                 FOR (j, i, N) if (win[i][j] & win[j][i]) id[j] = p;  
19.                 ++p;  
20.             }  
21.         }  
22.   
23.         memset(d, 0, sizeof(d));  
24.         REP(i, N) REP(j, N) if (win[i][j]) {  
25.             if (id[i] != id[j])  
26.                 d[id[j]]++;  
27.         }  
28.   
29.         int ret = 0;  
30.         REP(i, p) if (d[i] == 0) ++ret;  
31.   
32.         return ret;  
33.     }  
34. };  

bool win[50][50];
int id[50];
int d[50];

class StrangeParticles {
public:
    int remain(vector<string> interacts) {
        int N = interacts.size();

        memset(win, 0, sizeof(win));
        REP(i, N) REP(j, N) if (i == j || interacts[i][j] == '-') win[i][j] = 1;
        REP(k, N) REP(i, N) REP(j, N) win[i][j] |= win[i][k] & win[k][j];

        memset(id, -1, sizeof(id));
        int p = 0;
        REP(i, N) {
            if (id[i] == -1) {
                FOR (j, i, N) if (win[i][j] & win[j][i]) id[j] = p;
                ++p;
            }
        }

        memset(d, 0, sizeof(d));
        REP(i, N) REP(j, N) if (win[i][j]) {
            if (id[i] != id[j])
                d[id[j]]++;
        }

        int ret = 0;
        REP(i, p) if (d[i] == 0) ++ret;

        return ret;
    }
};

読書「心がスーッとなるブッダの言葉」

社会人一年目のときに仕事が上手くいかなくて買った本。途中まで読んで、本棚にしまっていたけど、ふと気になってもう一度最初から読んでみました。

　仏教（テーラワーダ仏教）の教えがいろいろと書いてあります。人生に迷ったとき、心配ごとが尽きないとき、心を鍛えたいとき読むと心がスーッとします。仏教と聞くと、宗教で信仰染みた如何わしいものだと思っていましたが、テーラワーダ仏教は大変論理的で科学的です。「神様に祈っても何も解決しない。問題を解決したければ自分で動け。」という姿勢で教えを説きます。

　いろいろなことが書いてありましたが、特に印象に残ったのは「今を生きろ」ということです。人間は過去や未来を変えることはできない。大切なのは今ですと。作者が講演会で話をするとき、以下のような質問をするそうです。

「皆さんは今悩み事がありますか？」

すると、みんな「たくさん悩みがある。」と答えるそうです。そこでもう一回、

「それでは、今この瞬間どうにも耐えられない我慢できない苦痛、悩みがありますか？」

すると、みんなそれは無いと答えるそうです。そして作者はこう続けるそうです。

「あなたが生きているのは"今"この瞬間です。人生は、”今”の積み重ねです。"今"現在具体的な悩みや苦痛がないなら、この先も大丈夫なはずです。」と。

　人間の悩みの大半は、変えることのできない過去に対する後悔や、悩んでも仕方のない将来の不安です。終わったことは終わったこと。将来問題が起こったら起きたときに対応すればいい。自分たちにできるのは今を生きること。今を楽しんで、今できることを自分たちの出来る範囲でやっていればいいのです。

　人間の心というのは本来汚いもので、自然に良くなるということは無いと思います。私自身、この本を読んで自分の心が汚れていて、そのせいで自分は不幸になっていると確信しました。心を鍛えたいです。

スライド区間に対するクエリのまとめ

問題設定

　スライド区間に対するクエリ処理の種類とそれに対するアルゴリズムをいくつか紹介します。まず、「スライド区間」の定義ですが、窓関数のようなものを想像してください。例えば、[2,5,10,-1,0,4,...]というデータに対してサイズ3の窓関数をスライドさせると、[2,5,10], [5,10,-1],[10,-1,0],.....と複数の連続する区間ができます。これらの区間に対して以下のようなクエリを考えます。

1. 平均値/合計値
2. 最小値/最大値
3. 中央値/x番目に小さい値

　データサイズが小さい場合は愚直な方法で計算しても問題ありませんが、データサイズが大きい場合やオンライン処理で次々にデータが来る場合は高速な処理が求められます。天気予報システムや金融システムなどではこのような需要があると思います。例えば、ある時間幅内での最高気温・最低気温・平均気温を計算したり、リアルタイムに株価の高値・低値を計算するなどです。

　以下では、i番目のデータをdata[i]、データサイズをN、窓サイズをKと表記します。

平均値/合計値

　平均値/合計値の計算は簡単です。合計値が分かればそれをKで割ることで平均値が分かるので、以下では合計値に絞って議論します。単純な実装だとすべての窓に対して毎回合計値をフロムスクラッチから計算します。この場合、１クエリにつきO(K)、合計でO(NK)の計算量が必要になります。しかし、以下の関係を利用すると１クエリがO(1)で捌けます。

　１つ前の区間の和から一番古いデータを引いて、新しいデータを足したものが、現在の区間の和になるというわけです。文字列検索のRabin-Karp Algorithmで使用されるローリングハッシュと同様のやり方です。

最小値/最大値

　次に、最小値/最大値クエリを考えます。PKU2823 Sliding Windowがこの問題そのものなので、この問題を解いてみます。この場合も愚直な実装をすると、１クエリにつきO(K)の時間がかかってしまいます。高速に計算するためには、主に以下の方法が考えられます。

• multisetを用いた方法
• 両端キューを用いた方法
• 平方分割によるバケット法
• セグメント木

　平方分割とセグメント木はデータ値集合が有限個の場合のみ利用できます。この２つはより一般的なx番目に小さな値を取り出すクエリに利用できるので、次の節で説明します。ここではmultisetを用いた方法と両端キューを用いた方法を説明します。

　

　まず、multisetを用いた方法です。以下のように各区間内の要素をmultisetに格納しておくことで、区間の更新（古いデータの削除、新しいデータの挿入）とクエリ処理がO(lg K)で可能です。

view plainprint?

1. const int SIZE = 1e6;  
2. int data[SIZE+1];  
3. int maximum[SIZE+1];  
4. int minimum[SIZE+1];  
5.   
6. int main() {  
7.     int N, K;  
8.   
9.     while (~scanf("%d %d", &N, &K)) {  
10.         for (int i = 0; i < N; i++)  
11.             scanf("%d", data+i);  
12.   
13.         multiset<int> nums;  
14.         int p = 0;  
15.         multiset<int>::iterator itr;  
16.         for (int i = 0; i < N; i++) {  
17.             nums.insert(data[i]);  
18.   
19.             if (i >= K)  
20.                 nums.erase(nums.find(data[i-K]));  
21.             if (i >= K-1) {  
22.                 minimum[p] = *nums.begin();  
23.                 itr = nums.end();  
24.                 maximum[p] = *(--itr);  
25.                 ++p;  
26.             }  
27.         }  
28.   
29.         for (int i = 0; i < p; i++)  
30.             printf("%d ", minimum[i]);  
31.         puts("");  
32.         for (int i = 0; i < p; i++)  
33.             printf("%d ", maximum[i]);  
34.         puts("");  
35.     }  
36.   
37.     return 0;  
38. }  

const int SIZE = 1e6;
int data[SIZE+1];
int maximum[SIZE+1];
int minimum[SIZE+1];

int main() {
    int N, K;

    while (~scanf("%d %d", &N, &K)) {
        for (int i = 0; i < N; i++)
            scanf("%d", data+i);

        multiset<int> nums;
        int p = 0;
        multiset<int>::iterator itr;
        for (int i = 0; i < N; i++) {
            nums.insert(data[i]);

            if (i >= K)
                nums.erase(nums.find(data[i-K]));
            if (i >= K-1) {
                minimum[p] = *nums.begin();
                itr = nums.end();
                maximum[p] = *(--itr);
                ++p;
            }
        }

        for (int i = 0; i < p; i++)
            printf("%d ", minimum[i]);
        puts("");
        for (int i = 0; i < p; i++)
            printf("%d ", maximum[i]);
        puts("");
    }

    return 0;
}

この考え方は後で説明するバケット法に似ていると思います。予め決められた数のバケツを線形に並べて用意しておくのではなくて、木構造でバケツに値を入れていくようなイメージです。

　残念ながら、上記のO(lg K)の処理ではTime Limit Exceededになってしまいましたので、より高速なアルゴリズムが必要となります。両端キュー(deque)を利用すると、平均O(1)で１つのクエリを捌くことができます。両端キューとは、スタックとキューの両方の性質を持ったデータ構造で以下の処理がO(1)で可能です。

push_back()	キューの最後尾にデータを挿入する
push_front()	キューの先頭にデータを挿入する
pop_back()	キューの最後尾のデータをポップする
pop_front()	キューの先頭のデータをポップする

　それでは両端キューを利用したクエリ処理の方法について説明します。以下では最小値クエリについて説明します。データは、キューの最後尾に足していきます。ただし、現在追加したデータより大きな値を持つ値は無駄なのでポップしていきます。そして、キューの先頭に最小値があるような状態を保ちます。分かりにくいので例を使って説明します。K=4として、[1,3,5,2,4,6]に対する処理を考えます。キューにデータを詰めていって[1,3,5]の状態まで来たとします。次に2を最後尾にプッシュします。[1,3,5,2]となりますが、2は3,5より時系列で見て新しいデータなので3,5より窓区間内に残る期間が長いです。つまり、3,5の立場からすると、自分たちがポップされるまではずっと区間内に2がいることになります。よってこの時点で、3,5をキュー内に保持する意味はありません。ということで、3,5はポップして2をプッシュします。このような処理を繰り返していきます。以下のコードで無事ACです。（※ちなみに、クエリ処理とは関係ないですが、出力処理が重かったのでstringstreamに一旦バッファリングしてから一気に吐き出すという処理を行っています。この方法は時間制限が厳しく、出力が多いオンラインジャッジの問題には有効な技だと思います。）

view plainprint?

1. const int SIZE = 1e6;  
2. int data[SIZE+1];  
3.   
4. int main() {  
5.     int N, K;  
6.   
7.     while (~scanf("%d %d", &N, &K)) {  
8.         int *p = data;  
9.         for (int i = 0; i < N; i++)  
10.             scanf("%d", p++);  
11.   
12.         // minimum values  
13.         deque<int> nums;  
14.         ostringstream ss;  
15.         for (int i = 0; i < N; i++) {  
16.             while (!nums.empty() && data[i] < nums.back())  
17.                 nums.pop_back();  
18.             nums.push_back(data[i]);  
19.             if (i >= K && nums.front() == data[i-K])  
20.                 nums.pop_front();  
21.             if (i >= K-1)  
22.                 ss << nums.front() << " ";  
23.         }  
24.         cout << ss.str() << endl;  
25.   
26.         // maximum values  
27.         ss.str("");  
28.         while (!nums.empty())  
29.             nums.pop_back();  
30.         for (int i = 0; i < N; i++) {  
31.             while (!nums.empty() && data[i] > nums.back())  
32.                 nums.pop_back();  
33.             nums.push_back(data[i]);  
34.             if (i >= K && nums.front() == data[i-K])  
35.                 nums.pop_front();  
36.             if (i >= K-1)  
37.                 ss << nums.front() << " ";  
38.         }  
39.         cout << ss.str() << endl;  
40.     }  
41.   
42.     return 0;  
43. }  

const int SIZE = 1e6;
int data[SIZE+1];

int main() {
    int N, K;

    while (~scanf("%d %d", &N, &K)) {
        int *p = data;
        for (int i = 0; i < N; i++)
            scanf("%d", p++);

        // minimum values
        deque<int> nums;
        ostringstream ss;
        for (int i = 0; i < N; i++) {
            while (!nums.empty() && data[i] < nums.back())
                nums.pop_back();
            nums.push_back(data[i]);
            if (i >= K && nums.front() == data[i-K])
                nums.pop_front();
            if (i >= K-1)
                ss << nums.front() << " ";
        }
        cout << ss.str() << endl;

        // maximum values
        ss.str("");
        while (!nums.empty())
            nums.pop_back();
        for (int i = 0; i < N; i++) {
            while (!nums.empty() && data[i] > nums.back())
                nums.pop_back();
            nums.push_back(data[i]);
            if (i >= K && nums.front() == data[i-K])
                nums.pop_front();
            if (i >= K-1)
                ss << nums.front() << " ";
        }
        cout << ss.str() << endl;
    }

    return 0;
}

中央値/x番目に小さい値

　最後に中央値、より一般的にx番目に小さい値を取り出すクエリについて考えます。

　まず、平方分割を用いた方法です。平方分割の前に単純なバケット法を利用した場合のクエリ処理を説明します。例えば、データの取り得る値が1,2,3,...,8だった場合は、1,2,3,...8の８個のバケツを用意します。そして、それぞれのバケツにその値が窓内にいくつ表れるかを保持します。

　上図のように、窓が一つずれると古いデータの値のバケツの値を1減らし、新しく来たデータのバケツの値を1増やします。バケツを走査することで、x番目に小さい値が分かります。上図ではK=4としていますが、K=100でも、K=100000でも8つのバケツを走査するだけでクエリが捌けます。一般にデータの値域のサイズをrとすると、この方法では一つのクエリにつきO(r)の計算が必要になります。

　rが大きくなると単純なバケット法では十分な速度が期待できません。よって何らかの工夫が必要となります。データの値域が1,2,3,....1000000のときを考えます。このとき1000000個のバケツを1000個ずつのグループに分け、各グループにおいて自分のグループ内のバケツにデータがいくつ入っているかを記憶させておけばO(sqrt(r))で効率的なバケツの走査ができます。一般にr個のバケツを分ける分け方は、半分にするとか、10個ずつにするとか、いろいろ考えられますが、sqrt(r)個ずつに分けるのが最適で、そのような分け方を平方分割と言います。

　バケツの走査の仕方には、平方分割よりも効率的なものがあります。二分探索のようなやり方で区間を半分にして、

• 前半の区間にx個以上要素があれば、前半の区間を探す
• そうでなければ、後半の区間から(x-前半の区間のバケツ内に含まれるデータの数)番目に小さいデータを探す

というような方法が可能です。これはセグメント木で実装することができ、各クエリがO(ln r)で捌けます。

　SRM 310 FloatingMedianがスライド区間の中央値を求める問題ですので、それを平方分割で解いたプログラムと、セグメント木で解いたプログラムを載せておきます。

view plainprint?

1. const int MOD = 65536;  
2. const int SIZE = 256;  
3.   
4. int bucket[SIZE][SIZE];  
5. int nums[SIZE];  
6.   
7. class FloatingMedian {  
8.     void inc(int x) {  
9.         ++bucket[x/SIZE][x%SIZE];  
10.         ++nums[x/SIZE];  
11.     }  
12.   
13.     void dec(int x) {  
14.         --bucket[x/SIZE][x%SIZE];  
15.         --nums[x/SIZE];  
16.     }  
17.   
18.     int get(int x) {  
19.         int p = 0;  
20.         for (; p < SIZE; p++) {  
21.             if (nums[p] < x)  
22.                 x -= nums[p];  
23.             else  
24.                 break;  
25.         }  
26.   
27.         REP(i, SIZE) {  
28.             x -= bucket[p][i];  
29.             if (x <= 0)  
30.                 return p*SIZE+i;  
31.         }  
32.         return -1;  
33.     }  
34.   
35. public:  
36.     long long sumOfMedians(int seed, int mul, int add, int N, int K) {  
37.         memset(bucket, 0, sizeof(bucket));  
38.         memset(nums, 0, sizeof(nums));  
39.   
40.         vector<long long>t;  
41.         t.push_back(seed);  
42.         FOR (i, 1, N)  
43.             t.push_back((t[i-1]*mul+add)%MOD);  
44.   
45.         long long ret = 0;  
46.         REP(i, N) {  
47.             inc(t[i]);  
48.             if (i >= K)  
49.                 dec(t[i-K]);  
50.             if (i >= K-1)  
51.                 ret += get((K+1)/2);  
52.         }  
53.   
54.         return ret;  
55.     }  
56. };  

const int MOD = 65536;
const int SIZE = 256;

int bucket[SIZE][SIZE];
int nums[SIZE];

class FloatingMedian {
    void inc(int x) {
        ++bucket[x/SIZE][x%SIZE];
        ++nums[x/SIZE];
    }

    void dec(int x) {
        --bucket[x/SIZE][x%SIZE];
        --nums[x/SIZE];
    }

    int get(int x) {
        int p = 0;
        for (; p < SIZE; p++) {
            if (nums[p] < x)
                x -= nums[p];
            else
                break;
        }

        REP(i, SIZE) {
            x -= bucket[p][i];
            if (x <= 0)
                return p*SIZE+i;
        }
        return -1;
    }

public:
    long long sumOfMedians(int seed, int mul, int add, int N, int K) {
        memset(bucket, 0, sizeof(bucket));
        memset(nums, 0, sizeof(nums));

        vector<long long>t;
        t.push_back(seed);
        FOR (i, 1, N)
            t.push_back((t[i-1]*mul+add)%MOD);

        long long ret = 0;
        REP(i, N) {
            inc(t[i]);
            if (i >= K)
                dec(t[i-K]);
            if (i >= K-1)
                ret += get((K+1)/2);
        }

        return ret;
    }
};

view plainprint?

1. const int MOD = 65536;  
2. int seg[1<<18];  
3.   
4. class FloatingMedian {  
5.     void inc(int k, int left, int right, int x) {  
6.         if (left == right)  
7.             seg[k]++;  
8.         else {  
9.             int mid = (left+right)/2;  
10.             if (x <= mid)  
11.                 inc(2*k+1, left, mid, x);  
12.             else  
13.                 inc(2*k+2, mid+1, right, x);  
14.             seg[k] = seg[2*k+1] + seg[2*k+2];  
15.         }  
16.     }  
17.   
18.     void dec(int k, int left, int right, int x) {  
19.         if (left == right)  
20.             seg[k]--;  
21.         else {  
22.             int mid = (left+right)/2;  
23.             if (x <= mid)  
24.                 dec(2*k+1, left, mid, x);  
25.             else  
26.                 dec(2*k+2, mid+1, right, x);  
27.             seg[k] = seg[2*k+1] + seg[2*k+2];  
28.         }  
29.     }  
30.   
31.     int get(int k, int left, int right, int x) {  
32.         if (left == right)  
33.             return left;  
34.         else {  
35.             int mid = (left+right)/2;  
36.             if (seg[2*k+1] >= x)  
37.                 return get(2*k+1, left, mid, x);  
38.             else  
39.                 return get(2*k+2, mid+1, right, x-seg[2*k+1]);  
40.         }  
41.     }  
42.   
43.   
44. public:  
45.     long long sumOfMedians(int seed, int mul, int add, int N, int K) {  
46.         memset(seg, 0, sizeof(seg));  
47.   
48.         vector<long long>t;  
49.         t.push_back(seed);  
50.         FOR (i, 1, N)  
51.             t.push_back((t[i-1]*mul+add)%MOD);  
52.   
53.         long long ret = 0;  
54.         REP(i, N) {  
55.             inc(0, 0, 65535, t[i]);  
56.             if (i >= K)  
57.                 dec(0, 0, 65535, t[i-K]);  
58.   
59.             if (i >= K-1)  
60.                 ret += get(0, 0, 65535, (K+1)/2);  
61.         }  
62.         return ret;  
63.     }  
64. };  

const int MOD = 65536;
int seg[1<<18];

class FloatingMedian {
    void inc(int k, int left, int right, int x) {
        if (left == right)
            seg[k]++;
        else {
            int mid = (left+right)/2;
            if (x <= mid)
                inc(2*k+1, left, mid, x);
            else
                inc(2*k+2, mid+1, right, x);
            seg[k] = seg[2*k+1] + seg[2*k+2];
        }
    }

    void dec(int k, int left, int right, int x) {
        if (left == right)
            seg[k]--;
        else {
            int mid = (left+right)/2;
            if (x <= mid)
                dec(2*k+1, left, mid, x);
            else
                dec(2*k+2, mid+1, right, x);
            seg[k] = seg[2*k+1] + seg[2*k+2];
        }
    }

    int get(int k, int left, int right, int x) {
        if (left == right)
            return left;
        else {
            int mid = (left+right)/2;
            if (seg[2*k+1] >= x)
                return get(2*k+1, left, mid, x);
            else
                return get(2*k+2, mid+1, right, x-seg[2*k+1]);
        }
    }


public:
    long long sumOfMedians(int seed, int mul, int add, int N, int K) {
        memset(seg, 0, sizeof(seg));

        vector<long long>t;
        t.push_back(seed);
        FOR (i, 1, N)
            t.push_back((t[i-1]*mul+add)%MOD);

        long long ret = 0;
        REP(i, N) {
            inc(0, 0, 65535, t[i]);
            if (i >= K)
                dec(0, 0, 65535, t[i-K]);

            if (i >= K-1)
                ret += get(0, 0, 65535, (K+1)/2);
        }
        return ret;
    }
};

サーバー奮闘記（20） javascript-mode導入

"Borneo sunset" by angela7dreams

やったこと

Emacsにjavascriptモードを入れました。js2-modeというのを入れました。js2-modeは、正規表現で文法のチェックをするのではなくて、abstract syntax treeに実際にコードをparseします。これによって複雑な文法チェックにも対応できます。

参考サイトのとおりなんですが、一応やったことを書いておきます。

1. js2-modeのホームページからelファイルをダウンロード
2. M-x byte-compile-file [RET] js2.el [RET] でコンパイル
3. .emacsに以下を追記

(autoload 'js2-mode "js2" nil t)
(add-to-list 'auto-mode-alist '("\\.js$" . js2-mode))

参考サイト

1. http://d.hatena.ne.jp/m-hiyama/20080627/1214549228
2. http://mihai.bazon.net/projects/editing-javascript-with-emacs-js2-mode

jQueryチートシート

　いつも同じようなことを調べている気がしたのでまとめました。自分用チートシート。

セレクタの指定方法

表記	意味
$("#hoge")	idがhogeのオブジェクト
$(".hoge")	クラス名がhogeのオブジェクト
$("div")	divタグ
$("div.hoge")	クラス名がhogeのdivタグ
$("p")	pタグ
$("p.hoge")	クラス名がhogeのpタグ
$("*")	すべてのタグ
$("div,span,p")	divタグとspanタグとpタグ
$("div p")	divの子孫のpタグ
$("div>p")	divの子のpタグ（※直接の子タグだけ。孫以下は含まない。）
$("div+p")	divの直後にあるpタグ
$("div", this)	thisの子孫のdivタグ
$("div", $(this).parent())	thisの親の子孫のdivタグ（※同様に、siblings()やprev()などでthisの○○の△△という指定ができる。）

DOM操作

メソッド	意味
html("val")	指定した要素にvalをセットする。（セットした文字列はHTMLとして解釈される。）
text("val")	指定した要素にvalをセットする。（セットした文字列はplain textとして解釈される。）
append("val")	指定した要素にvalを追記する。（追記した文字列はHTMLとして解釈される。）

スタイルシート操作

メソッド	意味
css("color", "red")	指定した要素の文字色を赤に変更する。
css("background-color", "blue")	指定した要素の背景色を青に変更する。
css({ "color" : "red", "background-color" : "blue"});	指定した要素の複数のプロパティを一括変更する。
addClass("hoge")	指定した要素にhogeクラスを追加する。
removeClass("hoge")	指定した要素からhogeクラスを取り除く。
toggleClass("hoge")	指定した要素にhogeクラスがあれば取り除く。無ければ追加する。

イベント処理

メソッド	意味
ready(function(){//処理})	DOMがロードされたときに実行する処理を指定する。
click(function(){//処理})	指定した要素がクリックされたときに実行する処理を指定する。（※ready()内に書くこと。以下のコールバック指定も同様。）
mouseover(function(){//処理})	指定した要素にマウスオーバーしたときに実行する処理を指定する。
mouseout(function(){//処理})	指定した要素にマウスアウトしたときに実行する処理を指定する。
hover(function(){//処理1}, function(){//処理2})	マウスオーバーしたときの処理を処理1に、マウスアウトしたときの処理を処理2に指定する。

非同期通信

メソッド	意味
load("file")	指定した要素にファイルから読み込んだ値をセットする。
jQuery.get("url","data",function(){//処理})	urlにgetで値dataを送信し、帰ってきた内容に対してコールバック関数で設定した処理を適用する。
jQuery.post("url","data",function(){//処理})	urlにpostで値dataを送信し、帰ってきた内容に対してコールバック関数で設定した処理を適用する。