Search on the blog

2011年5月30日月曜日

複数のアプローチ

一つの問題には複数のアプローチがあることを改めて学びました。一つの問題に時間をかけて取り組むことは大事。

下の問題にチャレンジしましょう。

国王が、秘書に頼んでN人の大臣に個人宛の手紙をくばりました。しかし、ドジな秘書はそれに気付かずにランダムに手紙を配ってしまいました。秘書は、自分のミスに気付いてK人の大臣に、「受け取った手紙は宛先が適切か?」と聞きましたが、全員違うと答えました。秘書が配った手紙の配り方のパターン数を求めなさい。

数学的な問題に帰着すると、以下のようになります。
A1, A2, ..., Anという数列がある。この数列は、Ai != i, i=1,2,...,kを満たす。このような数列のパターンは何パターンあるか?

Approach 1:
ビットDPで解く。i = 1, ..,kまではAi != iの縛りがあります。1からkまでの間でどの値が使用されたかを記憶してDPをすればいいです。これは考察はそれほどいらないけど、実装が重いです。
#define MOD 1000000007LL
LL dp[15][1<<15];
LL fact[1024];

class CarelessSecretary {
public:
int howMany(int N, int K) {
fact[0] = 1;
for (int i = 1; i < 1024; i++)
fact[i] = i * fact[i-1] % MOD;

memset(dp, 0, sizeof(dp));

dp[0][0] = 1LL;
for (int i = 0; i < K; i++) {
for (int mask = 0; mask < (1<<K); mask++) {
if (!dp[i][mask]) continue;
for (int j = 0; j < K; j++) {
if (j == i) continue;
if (mask >> j & 1)
continue;
dp[i+1][(1<<j)|mask] = (dp[i+1][(1<<j)|mask] + dp[i][mask]) % MOD;
}

int rm = N - K - (i - __builtin_popcount(mask));
dp[i+1][mask] = (dp[i+1][mask] + rm * dp[i][mask]) % MOD;
}
}

LL ret = 0;
for (int mask = 0; mask < (1<<K); mask++) {
LL patr = fact[N-K] * dp[K][mask] % MOD;
ret = (ret + patr) % MOD;
}

return (int)(ret % MOD);
}
};

Approach 2:
Editorial解法。4パターンに分解します。動的計画の式の立て方を勉強する良い例題だと思います。これおは実装は軽いけど、なかなか思いつかないです。あと、場合分けや特殊ケースの処理でミスコーディングする可能性が高いです。
LL ans[1024][16];

class CarelessSecretary {
public:
int howMany(int N, int K) {
for (int i = 0; i <= N; i++) for (int j = 0; j <= K; j++) {
if (i == 0 && j == 0) ans[i][j] = 1LL;
else if (i == 0) ans[i][j] = 0LL;
else if (j == 0) ans[i][j] = i*ans[i-1][j] % MOD;
else ans [i][j] = ((i-j)*(ans[i-2][j-1] + ans[i-1][j]) + (j-1)*(ans[i-2][j-2] + ans[i-1][j-1]))%MOD;
}

return (int)ans[N][K];
}
};

Approach 3:
rng解。ぱない。i=1,..,kまでは1つも被らない。を逆から見て、少なくとも1つは被っているパターン数を包除原理を使って数えています。実装も軽いし、言われてみると確かにこの発想はありかなという感じです。ミスコーディングの可能性の低さからも、この解法がベストだと思います。
#define MOD 1000000007LL

class CarelessSecretary {
public:
int howMany(int N, int K) {
LL F[1024];

F[0] = 1;
FOR (i, 1, 1024) F[i] = i * F[i-1] % MOD;

LL ret = 0LL;
REP(ptrn, 1<<K) {
int c = __builtin_popcount(ptrn);
if (c % 2)
ret = (ret - F[N-c] + MOD) % MOD;
else
ret = (ret + F[N-c]) % MOD;
}

return (int)ret;
}
};

2011年5月28日土曜日

ビット演算魔術、部分集合を高速に出すの巻

 以下のビット演算が何を意味するのか知ってる人は読まなくていいです。
--y &= x

 次の問題を解いているときに出会いました。
[SRM474 SquaresCovering]
2次元平面上に分散するN個の点を正方形で多いたい。正方形はK種類あり、それぞれ大きさと使用するためのコストが異なる。すべての点を覆うには最低いくらコストが必要か?ただし、正方形は無限個あり、同じ正方形を複数回使用しても構わない。

N<=16, K<=50
0 < xi < 10^9, i=1,..,n
0 < yi < 10^9, i=1,..,n

 ぱっと見普通のビットDPで解けそう。が、2秒縛りがキツイ。straightforwardに解くとO(2^{2N})なので、なんとかしたい。
何とかできなかった。。
以下rngさんの回答。やっぱ数学オリンピック金メダリストは違う。。と思ったけど、アリーナからコピペ出来なかったので、私のヘタレソースで我慢してください。(横にはみ出していて、見にくい場合はview plainで見てください。)
const long long int INF = 999999999999999LL;
long long int dp[1<<16];

class SquaresCovering {
public:
int minCost(vector<int> x, vector<int> y, vector<int> cost, vector<int> sides) {
int N = x.size();
int K = sides.size();

REP(mask, 1<<N) {
LL xmin = INF, xmax = -1;
LL ymin = INF, ymax = -1;

REP(i, N) {
if (mask >> i & 1) {
xmin = MIN(x[i], xmin);
xmax = MAX(x[i], xmax);
ymin = MIN(y[i], ymin);
ymax = MAX(y[i], ymax);
}
}

LL val = INF;
int diff = max(xmax-xmin, ymax-ymin);
REP(i, K)
if (diff <= sides[i])
val = MIN(val, cost[i]);
dp[mask] = val;
}

REP(x, 1<<N) {
for (int y = x; y > 0; --y &= x)
dp[x] = min(dp[x], dp[y]+dp[x^y]);
}

return (int)dp[(1<<N)-1];
}
};

 --y & xは、集合xの部分集合をすべて列挙することができます。これはかなりカッコいいです。ピンと来ない人は次のソースを実行してみましょう。
#include <bitset>
int main() {
int x = 202;

for (int y = x; y > 0; --y &= x)
cout << bitset<8>(y) << endl;
}
上の実行結果を見れば何がしたいか分かるはずです。

 最後に、比較してみましょう。SRMの問題を愚直な2重ループでやると、4*10^9くらいかかります。
この方法を使用すれば、2^16 * 2^8 = 2^24 ~16*10^6くらいには収まるかなという予想です。
int main() {
LL x = 0;
REP(mask1, 1<<16)
REP(mask2, 1<<16)
x++;

LL y = 0;
REP(mask1, 1<<16)
for (int mask2 = mask1; mask2 > 0; --mask2 &= mask1)
y++;

cout << x << endl;
cout << y << endl;

return 0;
}
上のプログラムを実行した場合、出力される数値は、
4294967296
42981185
です。まあこんなもんでしょうか。100倍くらい速くなります。



2011年5月24日火曜日

Beatty sequence making full integer set

Here's the definition of Beatty sequence:

[a], [2*a], [3*a], [4*a],....

where a is an irrational number, and [] is a floor function, which returns the maximum integer less than its input value.
As you can guess, there are tons of types of Beatty sequence out there.

What tickled my fancy was that the following theorem holds:

Two Beatty sequences
[a], [2*a], [3*a], .....
[b], [2*b], [3*b], ....
makes the whole integer set without any overlaps if 1/a + 1/b = 1.
It's like separating numbers into odd and even.

So, of course, you can select these two sequence so that the condition below is met:
1/a + 1/(a^2) = 1.

What do you associate with the preceding equation?? Yes, it's the "golden ratio."
I tried this out today. And it seemed to act like what I expected.
import qualified Data.Set as Set

beattySequence :: Double -> Set.Set Int
beattySequence x = foldr Set.insert Set.empty . map (floor . (*x)) $ [1..100]

main = do
let phi = (1+sqrt(5)) / 2

a = beattySequence phi
b = beattySequence $ phi^2

print $ Set.union a b
print $ Set.intersection a b
From these two sequence, integer set can be generated mutually exclusive and collectively exhaustive.

2011年5月22日日曜日

二分探索の精度

さっき書いたGoogle Code Jam Round 1のエントリーについて。
実は、largeを通すときに気を使った。
doubleの精度は15桁程度と知っていたので、hiを大きくとり過ぎると、誤差死するのではと思った。

しかし、よく考えるとこれは違うようだ。
二分探索では、hiとloが近づいていくので、hiの初期値によらず、十分な回数ループを回せば目的の値に対して相対誤差(10^-15)で収束するはず。

実際に、以下の例でもhi = 12.345678901234502と目的の値まで収束した。
二分探索では、探索の幅が狭まるにつれて、値に対する精度もよくなっていく。
普通、ループを回せば誤差が蓄積されていくと考えてしまうが、二分探索の場合は誤差が伝搬されない(前回の計算結果より高い精度で今回の計算を実施するため)と考えてよさそうだ。

int main() {
double x = 12.3456789012345;

double hi = 1e100;
double lo = 0;

REP(i, 1000) {
double mid = (hi + lo)/2;

if (mid > x)
hi = mid;
else
lo = mid;
}

printf("%.15lf\n", hi);
return 0;
}

余談だが、二分探索のループはwhileで書かない方がいい。よくバグが潜んでしまう。例えば以下の絶対誤差を停止条件にしたソースは一生停止しない。

int main() {
double x = 1234567890123.45;

double hi = 1e100;
double lo = 0;

while (hi-lo > 1e-6) {
double mid = (hi + lo)/2;

if (mid > x)
hi = mid;
else
lo = mid;
cout << lo << ":" << hi<< endl;
}

printf("%.15lf\n", hi);
return 0;
}
これは、目的の値が非常に大きいため、コンピュータ上で、1e-6という細かい精度で値を表現できないためである。

Google Code Jam 2011 Round1B

ぼろ負けでした。

集中力がなかったです。
変数名の重複とか、違う変数を参照していたりとか初歩的なミスが多すぎました。

Problem Bの二分探索が面白かったので簡単に解説。
基本的なアイディアはtに対して二分探索をかけます。与えられたtに対してすべての商人がdの間隔を保って拡散できるなら、tを小さく、できないならtを大きくします。

問題は、与えられたtに対して、商人が十分に拡散できるかどうか。。
これは一番左にいる商人から処理をしていけばいいです。一番左の人は他の人からより離れるためできる限り左に行きます。左から二番目の人も同様にできる限り(一番左の人との間隔がd以下にならない範囲で)左にいきます。これを続ければいいです。
途中で、どうがんばっても自分の左の人からd以上離れることができないとなった時点で、そのtでは十分に拡散できないと判断します。
ということで、binary search + greedyで解ける問題でした。

以下練習で通したソース。
largeの問題は、商人の人数および、間隔dが10^6なので、二分探索の上限は10^6 * 10^6程度です。ちょっと余裕をもって10^13としています。

int main() {
int t;
cin >> t;

REP(ii, t) {
int c, d;
cin >> c >> d;

int v, vs = 0;
vector<int>ps;
int p;
REP(i, c) {
cin >> p >> v;
vs += v;
REP(j, v)
ps.push_back(p);
}
SORT(ps);
double hi = 1.0E+13; // 10^6 * 10^6 < 10^13
double lo = 0;
double ret;

REP(i, 100) {
ret = (hi + lo) / 2;

bool ck = true;
double next = -1e100; // -inf
REP(j, vs) {
if (ps[j] + ret < next) {
ck = false;
break;
}
next = MAX(next + d, ps[j]- ret + d);
}
if (ck)
hi = ret;
else
lo = ret;
}
printf("Case #%d: %lf\n", ii+1,ret);
}

return 0;
}


2011年5月20日金曜日

サーバー奮闘記(13)

ひさびさの更新。
MySQLの設定をしてみた。
  1. ユーザーパスワードの変更
  2. 一般ユーザーの作成
  3. 文字コードの設定
1. ユーザーパスワードの変更
rootのパスワードを変えたくなったので変えた。

まず以下でログイン。(注意: -pの後はスペースを入れないこと!!)
mysql -u root -ppassword
>SET PASSWORD FOR root@localhost=PASSWORD('new_password');
でパスワード変更。

せっかくなので適当にDBをつくった。
>create database new_database_name;
>show databases;

2. 一般ユーザーの作成
>grant all privileges on new_database_name.* to usr_name identified by 'password';
で新しく作ったデータベースに対してすべての権限を持つユーザーを作成。
アプリケーション毎にユーザーを分ける予定。

3. 文字コードの設定
>status
で現在の文字コードを確認。Latinなんちゃらになってる。
また、以下の構文でスキーマやテーブルの文字コードを調べられるようです。
>show create database database_name;
>show create table table_name \G;

文字コードをUTF-8にするため以下ファイルをいじります。
/etc/my.cnf
以下のように書きます。
[client]
default-character-set=utf8

[mysqld]
default-character-set = utf8
skip-character-set-client-handshake
character-set-server = utf8
collation-server = utf8_general_ci
init-connect = SET NAMES utf8

で、再起動。
> /usr/bin/mysqladmin shutdown -u root -ppassword
> /usr/bin/mysqld_safe --user=mysql &

とやってみましたが、既存のスキーマ、テーブルは文字コードがLatinのままでした。。
一旦スキーマ毎消して、文字コードを指定してスキーマを作りました。
>create database database_name default character set utf8;
でOK。日本語が使えるようになりました。

参考ページ:


サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

2011年5月19日木曜日

チームワークは必要か?理想のチーム像とは?

今日、面白いarticleをいくつか読んだので紹介。
技術者や研究職に身を置かれる方々には是非とも読んでいただきたいです。
あと、マネージメントや経営陣の方々にもお勧めです。


と、読んでみて確かにその通りだなと思う点が多々あった。
チームワーク、チームワークとよく言うが本当のチームワークって何なのか?
考えてみました。

 私が至った結論から先に言うと、
「チームワークは所詮手段であって、目標ではない。チームワークの目標は生産性をあげることである。
生産性があがらないなら、チームは必要ない。会社は生産性をあげるチーム作りに細心の注意を払わないといけない。」です。

 上3つのarticleに書かれていた内容を部分的に説明します。(注:私の解釈が含まれている可能性があります)
①環境は個人の裁量にまかせる
 世の中にはチーム内で力を発揮する人、一人で働くことで力を発揮する人など様々です。
研究によると、自分の好きな環境で働いた場合は、環境を強制された場合と比べ、83%も高いパフォーマンスを発揮したそうです。
 画一的なチーム管理に疑問符を投げかける良いデータだと思います。
個人プレイヤは個人で、チームプレイヤはチームで仕事をできる環境というものを会社は用意しなければならないと思います。

②1つの仕事は1人に責任を持たせる
 人は誰かが同じタスクをしている場合には、無意識のうちに自分一人でやっている場合より手を抜くらしいです。また、誰かと同じタスクをしている場合は、他の人はどうやってるんだろう?自分よりうまくやっているのかな?などと余計なことを考えてしまい集中力が落ちるそうです。

③強力なリーダーはチームをダメにする
 スマートな人が集まると良いチームはできません。なぜなら個人の知性とチームのパフォーマンスは直結しないからです。チームワークに必要なのはむしろEQです。
 また、強力な個性はパフォーマンスを悪化させます。チームの決定権を握った強力な支配者がいる場合はチームはうまく機能しません。

①②は大きく賛成。
③は部分的に賛成。確かにチームを活かすにはコミュニケーションスキルが必要。
ただし、コミュニケーションスキルだけ得意な(他は何の専門性もない)人が10人集まって何かcreativeなものが生まれるだろうか?No。チームには専門家とEQにたけた人、両方必要だと思う。
 強力な個性~~の部分は賛成。チームリーダーにはEQ力の高い人を選ぶべき。
”EQ=自己主張能力”と勘違いされがちだけど、本当のEQとは、記事にあるようにsocially sensitiveとかcommunally-mindedといった能力だと思う。
 おそらくすべての会社は、自己主張が強い人達をマネージメント層に採用していると思うけど、この研究結果を見て早く気付くべきだ。自己主張の強いリーダーはチームの生産性を落としているだけだ(会社に不利益をもたらしている)と。

以下、私の中の理想チーム像が満たすべき条件。。

・個人が独立して機能し、
・各個人が専門の分野を有しており、
・自分の担当領域においては自分が裁量権を持っており、
・コミュニケーションは、主に、他の領域の専門家であるチームメンバーに意見を求めることから構成される

この条件をみたすには、具体的に何をすればいいか?
 まず、Doerレベルの人は、自分が誰にも負けない専門分野を身につけることです。
それは、技術的なスキルでもいいですし、コミュニケーションスキルでもいいです。
この分野ならチームの誰にも負けないというものを作ることです。
 Managementレベルの人は、チームメンバーにもっと裁量権を持たせるべき。
資料を作ったら、課長に見せて、OKもらったら、部長に見せて、OKだったら、役員に見せて、・・・
こういうのは新人教育の場合以外は止めた方がいい。時間の無駄だし、個人の成長を抑制している。
 加えて、このような縦割り(ヒエラルキー型)の分業のコミュニケーションは、立場が上の人の自己満足に終わることが多く、どうでもいいことに言及しがち。
(例;ここのフォントはこの方がいいね。このシートのデザインだけどさ・・。ここの文章の表現だけどね・・。ここ図の色だけど・・。)
対して、横割りの分業(つまり個々の専門性を活かし、かつ、個々に裁量権を持たせた仕事配分)を行った場合、コミュニケーションは本質的なものになりやすい。
(例:プログラムの観点からはA案よりB案がいいのですが、DB構成の観点から見るとどうですか?)

 で、私の理想とするチームが身近なところにありました。
それはワンピースのルフィー海賊団です(なんとっ)。それぞれのキャラクターは誰にも負けない得意分野があります。そして、リーダーであるルフィーは、それぞれの専門家に適切な裁量権を与えています。
(ルフィーは、ナミの航海術に反対しませんし、サンジの調理方法に細かく口出ししません。)
 また、病人がでたらチョッパーに診断をお願いし、古代の文章が出てきたらロビンに教えを請う。これこそが専門性をベースにしたコミュニケーションだと思います。
 かつ、ルフィーは独裁的なリーダーじゃありません。どこか抜けているリーダーのもとでメンバーは、思い思いに自分の好きなことをやっているように見えます。そして彼らにはメンバーに対して絶対の信頼を持っています。
これこそ理想のチーム像では?

2011年5月16日月曜日

サルでも分かるFFT(1)

「サルでも分かる」と書きましたが、始めに断っておきます。サルは私です。
大学時代、信号処理の授業は「優」で通っていたはずなのに自分の無恥さを知りました。
今日は、フーリエ変換の概念とDFTのプログラムサンプルを書きます。(間違いがありましたら、ご指摘ください。)

 まず、フーリエ級数展開について。一言でいうと、「すべての周期関数は、複数のサイン波の重ね合わせで表現できる。」です。ここでポイントなのは、対象が”周期関数”であるということです。

 そして、フーリエ級数展開を非周期関数に適用可能にしたものがフーリエ変換です。実際の信号は周期性がないものがほとんどですので、フーリエ変換が必要になるわけです。

 次に、離散フーリエ変換(DFT)。実際の信号(音や光など)は連続関数です。しかし、コンピュータ上で連続な信号を扱うことは難しいです。なので、サンプリングという操作を行います。実際には連続な信号を0.1msに1個とかいう間隔で信号の値を取得して離散信号として扱います。この離散化された信号(デジタル信号)に対するフーリエ変換がDFTです。

 そして、いよいよFFT。FFTはDFTを高速に計算するためのアルゴリズムです。別にFFTなくてもデジタル信号のフーリエ変換はできます。どれくらい速くなるかというと、O(N^2)がO(Nlog N)まで減ります。基本ソートとクイックソートくらい違います。

 で、DFTを実装してみます。Wikipediaにある下の式を使います。

 f_j = \sum_{k=0}^{N-1} x_k \exp\left( - \frac{2 \pi i j k}{N} \right) \qquad j = 0,\dots,N-1

Xkが入力データ(ある時刻における振幅)、fjがDFTの結果で周波数に直したときの特性を示します。
具体的には、
ABS(fj) がその周波数のスペクトル、ArcTan (Img(fi)/Re(fj))がその周波数成分の位相を表します。(fjは複素数であることに注意)

と、ここまでは知ってました。今日改めて気付いたのは、サンプリング点がN個の場合は、N個の周波数成分に分解できるということです。連続信号を離散で取っているので、周波数成分への分割の方法は複数パターン可能(特にNが小さければ無数にある)だと思いますが、DFTの結果って、どういう分割になっているのだろう。。。
あとfjのjって何??っていう疑問がわきました。これは、サンプリング間隔周波数のj倍の周波数成分と予想してるのですが、どうでしょう・・・。(うわ、全然分かってないな。。あとで調べよう。 OR 誰か教えてください笑)

以下、今日書いてみたDFTのコード。
複素数の扱いが簡単なPythonで書きました。(例題サンプルをいくつか見つけて検算したので合っているはず。)
import sys
import math

# input data
x = []
for line in sys.stdin:
x.append(float(line))

# construct matrix
n = len(x)
W = [[0 for j in range(n)] for i in range(n)]
for i in range(n):
for j in range(n):
W[i][j] = math.cos(2*i*j*math.pi/n) - math.sin(2*i*j*math.pi/n)*1J

# calc
f = [0] * n
for i in range(n):
for j in range(n):
f[i] += W[i][j] * x[j]
f[i] /= n

# display result
for i in range(n):
print f[i]

2011年5月15日日曜日

A few types of vector constructors

Here are some vector constructors I show you today.
  1. default constructor
  2. copy constructor
  3. initializing constructor
The first one is pretty simple:
vector<int> x;
Nothing special.

The second one is also a famous type of constructor:
vector<int> x;
x.push_back(1);
x.push_back(2);

vector<int> y(x.begin(), x.end());
REP(i, y.size())
cout << y[i] << endl;
With it, you can copy the contents of another vector. In the example above, you'll get a new vector y, whose contents is copied from vector x.

The last but not least is the initializing constructor. Literally you can initialize vectors at the same time as declaring them.
vector<int> x(10, 0);
You're creating a vector whose value is composed of 10 zeros.

2011年5月14日土曜日

サーバー奮闘記(12)

 2、3か月前に友人からjavascriptが熱いことを聞いた。
そして、もはやjavascriptを利用したweb開発のデファクトスタンダードになったjquery。
Ubuntuのwebサーバーで試してみます。

1. 例題ソースの取得
2. jquery取得配置

1. 例題ソースの取得
 gihyoさんで紹介されたjquery入門ページのソースを取得します。

ちなみにここに載っているソースはjsdo.it(リンク)というクラウド上の開発プラットフォームです。
お互いのソースを自由に見たり、自由に改変したりすることができます。

2. jquery取得配置
 jsdo.itはクラウド上のプラットフォームなので、ディレクトリ配置とかファイルの読み込みは自動でやってくれます。
しかし、自分のサーバーでやる場合は、ディレクトリ配置、読み込み設定などをやらないといけません。その手順を書きます。

 まず取得したソースをFTPでサーバーに転送しましょう。
ディレクトリ構造は、
test
-- sample.html
-- js
  -- sample.js
-- css
  -- sample.css
みたいな感じでOK。

 次にhtmlとcssに読みとり権限、jsに読みとり、実行権限を付加します。
 chmod 644 sample.html
 chmod 644 css/sample.css
 chmod 755 js/sample.js
あと、testディレクトリに実行権限がないと表示されないようです。
モジュールを格納するtestディレクトリにも
 chmod 755 test
としておきます。

 最後に、sample.htmlファイルをいじります。
jsdo.itにはbodyの中身しか書いていませんので、javascriptやcssの設定をヘッダに追記します。
具体的には、以下のようにします。
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
<script type="text/javascript" src="js/jquery.js"></script>
<script type="text/javascript" src="js/sample.js"></script>
<link rel="stylesheet" type="text/css" href="css/sample.css">
</head>
<body>
ここにjsdo.itのHTMLソースが入る
</body>
</html>

 おっと、肝心のjqueryを忘れてた。公式サイトから取得します。
testディレクトリで以下を実行。
 wget http://code.jquery.com/jquery-1.6.1.js
 mv jquery-X.X.X.js js/jquery.js
 chmod 755 js/jquery.js
(※X.X.Xはバージョン番号。)

 あれ、、、動かない。。そうか。
sample.jsもjsdo.itにあるものから少し変更が必要です。
jsdo.itの場合は、自動で関数をロードしますが、自分のサーバーでやるときは関数のロードを
明記します。
$(document).ready(function(){
  ※ここにjsdo.itのjsソースが入る
});
お、出来た。

[まとめ]
  • jqueryは簡単。使いやすい。
  • jqueryの本体は1つのjsファイルから出来ていることにびっくり。
  • うまくいかないときはApacheのlogを見る

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

サーバー奮闘記(11)

自分のwebサーバーにfaviconというのを付けた。
faviconとは、favorite iconの略で、お気に入りに登録したときやページのタブの部分に出てくるiconのこと。ブロガーの場合は、オレンジの四角の中に白色でBと書いているやつである。

設置の順序は以下のとおり
  1. faviconの作成
  2. faviconの設置
  3. Apacheで設定
1. faviconの作成
 さてさて、まずfaviconを設置するには、faviconを作成しなければならない。
web上でフリーで作成できるサービスがある。


上記のサービスを使うと自分でデザインしたfaviconがiso形式で取得できる。

2. faviconの設置
 作成したisoファイルをサーバーにファイル転送する。
配置後は、読みとり権限を付けることを忘れないように。(これ忘れるとクライアント側のブラウザから見れない。)
 chmod 644 favicon.iso

3. Apacheで設定
 設置したfaviconをページと紐づけます。例によってUbuntuではhttpd.confが無いので、以下のファイルで設定します。
 sudo vi /etc/apache2/sites-available/default
AddType image/xicon .ico                                                                               |
<Files favicon.ico> |
ErrorDocument 404 /favicon.ico |
</Files>
上記内容を最上位のVirtualHostディレクティブに追加します。
すると、ルート配下すべてのページにfaviconが設定されます。

こんな感じ。


サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

2011年5月13日金曜日

サーバー奮闘記(10)

今日はphp、MySQLを入れた。
あと、apacheの設定をちょっといじった。
  1. php、MySQLのインストール
  2. php-modeのインストール
  3. index of の非表示

1. php、MySQLのインストール
以下でインストール
 sudo apt-get install apache2 php5 php5-gd mysql-server php5-mysql

apacheでphpの使用を有効にする。
 sudo a2enmod php5
 sudo /etc/init.d/apache2 restart

再起動で警告が出る。
sudo: unable to resolve host hogehogehoge
* Restarting web server apache2 apache2: apr_sockaddr_info_get() failed for hogehogehoge
apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.0.1 for ServerName
... waiting apache2: apr_sockaddr_info_get() failed for hogehogehoge
apache2: Could not reliably determine the server's fully qualified domain name, using 127.0.0.1 for ServerName
(注:hogehogehogeはマシン名)

hostsの設定だな。
 sudo vi /etc/hosts
で以下のように変更。
 127.0.0.1 localhost.localdomain hogehogehoge
再び再起動。OK。


2.php-modeのインストール
apt-getでインストールできない。バイトコンパイルをしてみた。
  wget http://sourceforge.net/projects/php-mode/files/php-mode/1.5.0/php-mode-1.5.0.zip
 unzip php-mode-1.5.0.zip
 sudo mv php-mode-1.5.0.zip /usr/share/emacs/site-lisp
emacsを開いて
 M-x byte-compile-file
でelispファイルをコンパイル。

~/.emacsに追記
(load-library "php-mode")
(require 'php-mode)

動かない。。haskel-modeのディレクトリ構成をまねて
ソースファイルは
 /usr/share/emacs/site-lisp
コンパイル後のファイルは
 /usr/share/emacs/22.2/site-lisp
においてみる。出来た!色が付いた。わーい


3. index of の非表示
webページアクセスの際に、ファイル名を指定しないとそのディレクトリの内容が表示されてしまう。
これはちょっとかっこ悪い+セキュリティ的にも問題あり。なので、設定を変えてみる。

ネットで探していろいろ試すが、うまくいかない。。そもそもUbuntuにはhttpd.conf無いし。
OSによってapacheのディレクトリ構成が違うようです。Debian系はここにいろいろ良い情報が載ってました。
http://www.linux.net-japan.info/install08.html

sites-availableディレクトリに設定があるのか。
 sudo vi /etc/apache2\sites-available/default
でRoot DirectoryのOptionsの"Indexes"という部分(↓の太字部分)を消せばOK。

  Options Indexes FollowSymlinks MultiViews
  AllowOverride None
  Order allow,deny
  allow from all

で再起動。起動、再起動系はapache2ctlよりinit.dの方がいいみたい。
 sudo /etc/init.d/apache2 stop
 sudo /etc/init.d/apache2 start
出来た。ディレクトリの中身見れない。index.htmlを作成すると、ディレクトリ指定の場合は、index.htmlに飛ぶらしいので、作った。


phpを試してみた。次世代のfizzbuzzをやってみた。




サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

(参考サイト)
http://blog.kcg.ne.jp/blog/sato_si/5488
http://ubuntuforums.org/showthread.php?t=723361

2011年5月11日水曜日

サーバー奮闘記(9)

Emacsの設定を追加しました。
  1. Haskellモードのインストール
  2. auto-completeのac-modes追加
1. Haskellモードのインストール
以下を実行します。
 sudo apt-get install haskell-mode

そのあと、~/.emacsに以下を追記します。
 (load "haskell-site-file")
 (add-hook 'haskell-mode-hook 'turn-on-haskell-doc-mode)
 (add-hook 'haskell-mode-hook 'turn-on-haskell-indent)
 (add-hook 'haskell-mode-hook 'font-lock-mode)
 (add-hook 'haskell-mode-hook 'imenu-add-menubar-index)

2. auto-completeのac-modes追加
Haskellモードが正しく認識されるようになったことを確認して、major-modeの設定を追加します。
Haskellモードの場合も、自動補完が実施されるようにします。
以下をauto-complete.elに追記。
(defcustom ac-modes
'(emacs-lisp-mode lisp-interaction-mode
c-mode cc-mode c++-mode java-mode
perl-mode cperl-mode python-mode ruby-mode
ecmascript-mode javascript-mode js2-mode php-mode css-mode
makefile-mode sh-mode fortran-mode f90-mode ada-mode
xml-mode sgml-mode haskell-mode)

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

2011年5月9日月曜日

完全順列とモンモール数

数列
 Ai, 1 <= i <= n
が条件
 Ai != i, 1 <= i <= n
を満たす場合、Aを完全順列(またの名を乱列)と呼びます。例えば、3, 1, 2など。

そして長さnの完全順列のパターン数をXnとすると、X1, X2, X3, ....をモンモール数列と呼びます。

実は、このモンモール数はアルゴリズムコンテストによく出ます。最近だと、Facebook Hacker Cup 2011、Google Code Jam2011に出て来ました。

長さi-1の完全順列の後ろに要素を1つ足して、最後の1つと別の任意の要素を入れ替えると、それは長さiの完全順列になります。加えて、1箇所を除けば完全順列になっているような長さi-1の数列に、1つ要素を加えて、Ai = iとなっている要素と入れ替えると、それも完全順列になります。

以上のことから、第i番目のモンモール数列は、
 Xi = (i-1) * (Xi-1 + Xi-2)
と書けます。
X1 = 0, X2 = 1は自明。

コンピュータ上で実装する場合は、フィボナッチ数列と同じようにメモ化再帰 OR 動的計画(末尾再起)で書くとよいです。また、見てのとおりとても大きな数になるので、Moduloを取って計算させる問題が多いみたいです。

確率のお勉強

 Code Jamの予選で期待値の問題が出たので、ちょっと確率について復習してみた。
  1. 独立で同一な分布とは?
  2. ベイズの定理
を復習しました。(間違いがありましたら、ご指摘ください。)

1. 独立で同一な分布とは?
 これは勘違いしやすいです。何が何と独立で、何が同一なのか、よくごっちゃになってしまいます。(私だけ?)簡単な例で説明します。
1から6の目がある普通のサイコロをn回投げるとします。

 このとき、i回目に出る目と、i+1回目に出る目の確率分布はお互いに依存しません。
i回目に"6"が出たから、i+1回目に"6"の出る確率が低くなるということはありません。これが「独立」の意味です。

 同一の意味は、サイコロを振ったときに何がでるかは毎回同一の確率分布に従う(この場合は、すべて1/6)という意味です。

独立性は、事象がお互いに干渉しないこと、同一は確率分布が変化しないことを表しています。

2. ベイズの定理
 これは、いわゆる条件付き確率というやつです。○○という条件のもとで、××である確率はいくらか?というような問題を解く場合に使います。
BのもとでAが起こる確率をP(A|B) と書くと、
 P(A|B) = P(A ∩ B) / P(B)
という式で表されます。
面白い問題が2つあったので紹介します。

問題①
2人の子供がいる家があります。家の庭で女の子が遊んでいたので、1人は女の子であることが分かりました。もう一人も女の子である確率はいくらでしょう?

問題②
5回に1回の割合で帽子を忘れるくせのあるK君が、正月に A、B、Cの3軒を順に年始回りをして家に帰ったとき、帽子を忘れてきたことに気がついた。2軒目の家 B に忘れてきた確率を求めよ。

答え ①1/3 ②20/61

2011年5月8日日曜日

Google Code Jam 2011 Qualification Round 解答編

Code Jam終わったので自分の解法を晒します。まずは総合的な感想から。

 今回は、去年と比べて問題のレベルが上がりました。
でも上位陣は4問を1時間内に解いてしまってます。。何食べたらそんなに頭がよくなるのだろう??

 Aは境界値条件、分岐方法の正確さが求められました。Bは、データ構造方法の問題でした。
Cはビット演算の知識、Dは確率の知識が必要な問題でした。

 せっかく24時間あるので、今年は3つの言語で解くという遊びにチャレンジ。
  • 問題A、BはC++
  • 問題CはHaskell
  • 問題DはPython
で解きました。

では、それぞれの問題の解法。。もっといい解き方があったら教えてくださいーー。


Problem A. Bot Trust
[解法]
まず、お仕事リストを
 vector timeline
に格納。(値は、BOBBOOなどになる。)

それとは別に、ロボットが押すべきボタンの位置をそれぞれ
 vector blue;
 vector orange;
に格納。
あとは、timelineをループでまわしていけばOK。
ロボットが負の方向に動く場合もあるので、正の方向と負の方向に動く場合で場合分けすると実装しやすいです。

[提出コード]

int main() {
    int t, n;
    scanf("%d", &t);

    REP(i, t) {
        scanf("%d", &n);

        vector<char> timeline;
        vector<int> blue;
        vector<int> orange;

        REP(j, n) {
            int x;
            char r;

            scanf(" %c %d", &r, &x);
            timeline.push_back(r);
            if (r == 'B')
                blue.push_back(x);
            else
                orange.push_back(x);
        }

        int sz = timeline.size();
        int szBlue = blue.size(), szOrange = orange.size();
        int p = 0, q = 0;
        int bpos = 1, opos = 1;
        int ret = 0;

        REP(j, sz) {
            if (timeline[j] == 'B') {
                int pos = blue[p++];
                ret += ABS(pos - bpos) + 1;
                if (q < szOrange) {
                    int move = ABS(pos - bpos) + 1;
                    if (opos < orange[q])
                        opos = min(opos + move, orange[q]);
                    else
                        opos = max(opos - move, orange[q]);
                }
                bpos = pos;
            } else {
                int pos = orange[q++];
                ret += ABS(pos - opos) + 1;
                if (p < szBlue) {
                    int move = ABS(pos - opos) + 1;
                    if (bpos < blue[p])
                        bpos = min(bpos + move, blue[p]);
                    else
                        bpos = max(bpos - move, blue[p]);
                }
                opos = pos;
            }
        }
        printf("Case #%d: %d\n", i+1, ret);
    }

    return 0;
}




Problem B. Magicka
[解法]
呪文合成規則を
 char combine[26][26];
に、呪文組み合わせ規則を
 bool opposed[26][26];
に格納。
となえる呪文をstackに詰めていき、逐次上記2つの規則をチェックする。
呪文組み合わせチェックは、26*26見ているけど、これだとLargeの場合タイムオーバーになりそうなので、
基本エレメントだけを取り出して、組み合わせチェックをするといい。(てか最初から8*8でつくれよっ。)

[提出コード]

char combine[26][26];
bool opposed[26][26];
char tmp[16];
char magic[128];
bool emerge[26];
string base = "QWERASDF";

bool isOppose(stack<char> stk) {
    bool hasBase[8] = {0};

    while (!stk.empty()) {
        char t = stk.top();
        int pos = -1;

        REP(i, 8)
            if (base[i] == t)
                pos = i;
        if (~pos)
            hasBase[pos] = 1;

        stk.pop();
    }

    REP(i, 8) REP(j, 8) {
        if (!hasBase[i] || !hasBase[j])
            continue;
        if (opposed[base[i]-'A'][base[j]-'A'])
            return true;
    }

    return false;
}


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

    REP(i, t) {
        int c, d, n;

        memset(combine, 0x00, sizeof(combine));
        memset(opposed, 0x00, sizeof(opposed));

        // read combine
        scanf("%d", &c);
        REP(j, c) {
            scanf("%s", tmp);
            combine[tmp[0]-'A'][tmp[1]-'A'] = tmp[2];
            combine[tmp[1]-'A'][tmp[0]-'A'] = tmp[2];
        }
        // read opposed
        scanf("%d", &d);
        REP(j, d) {
            scanf("%s", tmp);
            opposed[tmp[0]-'A'][tmp[1]-'A'] = 1;
            opposed[tmp[1]-'A'][tmp[0]-'A'] = 1;
        }
        // read magic list
        scanf("%d", &n);
        scanf("%s", magic);

        // solve
        stack<char> ret;
        REP(j, n) {
            if (ret.empty()) {
                ret.push(magic[j]);
                continue;
            }

            int pre = ret.top()-'A';
            int next = magic[j]-'A';

            if (combine[pre][next]) {
                ret.pop();
                ret.push(combine[pre][next]);
            }
            else {
                ret.push(magic[j]);
                if (isOppose(ret)) {
                    while (!ret.empty())
                        ret.pop();
                }
            }
        }

        // print
        string res = "]";
        while (!ret.empty()) {
            res = ret.top() + res;
            ret.pop();
            if (!ret.empty())
                res = ", " + res;
        }
        res = "[" + res;
        printf("Case #%d: %s\n", i+1, res.c_str());
    }

    return 0;
}



Problem C. Candy Splitting
[解法]
Smallは全件探索してもO(2^15)なので間にあいます。LargeはO(2^1000)になるので全探索は不可能。
よく考えると、すべての飴玉のかたまりで排他的論理和を取って0になれば、”エセ”二等分ができることに気付きます。
排他的論理和が0以外なら、No。
0の場合は、(飴玉の総数) - (一番少ないかたまりの中にある飴玉の数)
が答え。

[提出コード]

import Data.Bits
import Text.Printf

getInt = do
n <- getLine
return (read n::Int)

getInts = do
n <- getLine
return (map (\x -> read x::Int) (words n))

gcjMain x = do
m <- getInt
nums <- getInts
printf "Case #%d: %s\n" x (solve nums)

solve nums
| foldl (xor) 0 nums /= 0 = "NO"
| otherwise = show $ solve' nums
where solve' num = (sum nums) - foldl (min) inf nums
inf = 100000000
main = do
n <- getInt
mapM_ (\x -> gcjMain x) [1..n]




Problem D. GoroSort
[解法]
これは、強烈。もっと簡単な解法があれば教えてください。。
やり方としては、
①まず数字をdisjoint(共通部分がない or 循環しない)なグループに分ける。
②それぞれのグループで期待値を求める。
③②で求めた期待値を足す。
という流れ。

サイズNのdisjoint groupに対する期待値は、
Xn = 1 + Sigma_{i=0}^n (nCi * f(i) * Xi / n! ), n >= 3
X0 = 0
X1 = 0
X2 = 2

という漸化式で表すことができる。
f(i)は、Nの中で正しい位置にいない要素の数がi個であるもののパターン数。
これは、
fn = (n-1) (f(n-1) + f(n-2)), n >= 2
f0 = 1
f1 = 0
という式で表すことが出来る。

上の式を頑張って手計算すると、ふむふむ、どうやら、
Xn = n, n >= 2
だな。と気付く。

これに気付けば、実装するだけです。

[提出コード]

import sys

n = raw_input()
n = int(n)

for i in range(n):
m = raw_input()
m = int(m)

nums = raw_input()
nums = nums.split(" ")
nums = map(int, nums)
nums = map(lambda x:x-1, nums)

grp = []
used = [0] * m
for j in range(m):
if nums[j] == j:
continue
if used[j]:
continue

cnt = 0
k = j
while used[k] == 0:
used[k] = 1
k = nums[k]
cnt = cnt + 1

grp = grp + [cnt]

print "Case #%d: %.6lf" % (i+1, sum(grp))

Google Code Jam 2011 Qualification Round 日本語訳

昨日、Google Code Jamの予選が開催されました。
世界中から10,000人以上の腕に覚えのあるプログラマーたちが参加しました。

プログラムは得意だけど、英語が苦手で参加できないという方のために日本語要約をつくりました。あと、参加したけど英語がよく分からなかったという人も読むといいかもしれません。

実際の問題(英文)はこちら:


Problem A. Bot Trust
[問題概要]
 BlueとOrangeというロボットを2つの廊下に置いて仕事をさせる。
仕事の内容は、地点xにあるボタンを押すというもの。
仕事のリストは、
O 2, B 1, B 2, O 4
のように与えられる。上記の意味は、
 まず、Orangeが地点2のボタンを押す
 次に、Blueが地点1のボタンを押す
 次に、Blueが地点2のボタンを押す
 最後に、Orangeが地点4のボタンを押す
ということ。

 初期状態で、2つのロボットは地点1にいるものとし、地点xから地点yまでは時間 |x-y|で移動できる。
このとき、リストの仕事を完了させるのにかかる最小時間を求めよ。
但し、仕事リストの順番は順守しないといけないことに注意。(例えば、Blueがボタンを押せる状態でも、先行のOrangeのタスクが完了していない場合は、Blueはその完了を待たないといけない)


Problem B. Magicka
[問題概要]
 魔法使いが、呪文を唱える。
呪文の基本エレメントは、 {Q, W, E, R, A, S, D, F}から成り立つ。
呪文合成リスト、呪文組み合わせ禁止リストが与えられるので、最終的な呪文を求める。

 呪文合成リストとは、基本エレメントから基本エレメントにない呪文を生成するルールを表す。
例えば、合成リストの中に、"QFT"という要素があれば、呪文を読んでいる時点で"QF"または、"FQ"が連続した場合、
それは"T"になることを意味する。

 呪文組み合わせ禁止リストとは、呪文中に同時に存在してはいけない基本エレメントの組を定義したものである。
禁止リストにある組み合わせが呪文中に存在した場合、いままで唱えた呪文はクリアされる。

 魔法使いが唱える呪文が与えられたとき、最終的に呪文はどう変化するか求める。
呪文合成、呪文組み合わせチェックは、逐次的に評価されることに注意。
呪文組み合わせチェックより先に呪文合成が評価される。


Problem C. Candy Splitting
 兄弟が複数個ある飴のかたまり(一つの塊にはCi個の飴が入っている)を分ける。
まず、兄が適当に2分割して、それを弟に渡す。
弟は、分割された飴を見て、それが2等分されていない場合は泣いてしまう。

 しかし弟はまだ幼いので、足算ができない。でも何故か二進数の足算はできる(どんなコンピュータおたくだよっ笑)
二進数で足算はできるが、繰り上がりをすることができない。

例えば、12+5は、
1100
+ 0101
------
1001
のように計算してしまう。よって弟が計算すると、12+5=9になる。

 兄は、正しく足算ができる。兄は弟を泣かせることなく、飴のかたまりを2分割して多い方を自分が取りたい。(悪い兄貴。。)
弟を泣かせない方法が存在しない場合はNoと出力、存在する場合は、弟を泣かせずに兄がもらうことのできる飴玉の総数の最大値を求める。


Problem D. GoroSort
 五郎とよばれる謎の生物がいる。五郎は腕が4本、指がN本ある。(エイリアン??想像すると、怖い。。)
五郎は、N個の数字がランダムにならんだ配列を持っている。(積み木の箱に数字が書かれたブロックがN個あるのをイメージしてください)
五郎は、配列を昇順にソートしたいがアルゴリズムが得意じゃない。

 毎回五郎は、N個の数字のうち、M個の数字を抑えて、配列をテーブルに叩きつける。
抑えつけたM個の数字は動かないが、それ以外の数字は空中に飛んで、バラバラになって、また配列に戻ってくる。
このバラバラになるという過程で数字がソートされる。ソートのされ方は、同一で一様な分布とする。

 五郎は、毎回配列のおさえるべき部分を賢くえらぶ。どこを抑えれば速くソートされるかを知っている。
(アルゴリズム得意じゃないとか言いながら、実は賢い生物だね。)

 配列の初期状態が与えられたとき、五郎がソートするために必要な、テーブルにたたきつける数の期待値を求める。


2011年5月6日金曜日

サーバー奮闘記(8)

やったー、ようやく日本語が使えるようになりました(泣
もはや日本語なんて要らないとか思ってたけど、WEBページを作成するときに日本語使えないときついなーと思っていました。(ページの閲覧者は日本人を想定しているので・・)

まず、今まで使えなかった原因ですが、teratermのインストールのときに言語を「English」にしたからでした。UIで使用される言語だろうと思ってEnglishにしたのですが、Englishにするとteratermアプリケーション上で日本語が表示できないみたいです。(昔は行けたような気がするけど。。新バージョンのバグ??)

ということで、いろいろ設定したのでメモ書き。

1. shellのwarning設定 (warning、マニュアルは英語で出したい。)
~/.bashrcに以下を追記
export LC_ALL=C

2. viの文字コード設定
~/.vimrcに以下を追記
:set encoding=utf-8
:set fileencodings=ucs-bom,iso-2022-jp-3,iso-2022-jp,eucjp-ms,euc-jisx0213,euc-jp,sjis,cp932,utf-8

3. lessの文字コード設定
~/.bashrcに以下を追記
export LESSCHARSET=utf-8

4. emacsの文字コード設定
~/.emacsに以下を追記
(set-language-environment "Japanese")
(set-default-coding-systems 'utf-8)
(prefer-coding-system 'utf-8)
(set-terminal-coding-system 'utf-8)
(set-keyboard-coding-system 'utf-8)
(set-buffer-file-coding-system 'utf-8)
(setq default-buffer-file-coding-systems 'utf-8)

少しずつサーバーの機能が充実してきました。よかったよかった。
あとは、emacsの設定を追加しました。
・初期設定でウィンドウが3分割されるようにする。(eclipseみたいにしたい)
・*compilation* バッファが開いた場合に、ウィンドウの比率が初期設定から変わらないようにする。

以下を~./emacsに追記です。
(setq even-window-heights nil)
(split-window-horizontally 120)
(split-window-vertically 32)

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

2011年5月5日木曜日

サーバー奮闘記(7)

Apacheの設定も終わったので、ドメインを設定しました。
co.jpのドメインを取得すると、年間5,000-10,000円くらいかかるらしいですが、お金がないので無料ドメインを取得。
数ある無料ドメイン提供業者の中から、最も信頼があるといわれている「co.cc」を利用しました。

 取得方法はこちらのサイトに詳しく書いていますが、肝心なDNSのサイトの設定が書かれていなかったので、紹介します。

co.ccでは、以下3つの方法でDNS - IPアドレスのマッピングができます。
  1. DNS serverを指定
  2. zone recordを設定
  3. URL Forwardingを設定
まず、1ですが、使用するDNS Serverを指定します。そのあと、DNS Serverで自分のIPと欲しいドメインをマッピングします。この方法は、自分でDNS Serverを立てている or プロバイダーのDNS Serverに設定依頼をする場合に使えます。が、個人用サーバーの設定としては、あまり一般的ではないと思います。

次に2.について。これは本命。
zone recordでオプションAを選択します。

Host:使いたいドメイン名
TTL:1D(デフォルト)
Type/Priority:A
Value:serverのIPアドレス

と設定してあげるとOK。おそらく業者側でDNSの設定をしてくれるのだと思われます。

最後に3.について。これは、短いドメインを取得したあと、既に保有している長いドメインへforwardingを行うサービスのようです。初めてドメインを取得する場合は関係ない話です。

ちなみに、今回取得したドメインは、「goodpreparations」。本田圭佑を尊敬してるので。
しょーもないサンプルページ作りました。

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

Emacs 入門(5)

Emacs上でShellを使用する方法、設定についてメモ書き。

Emacs上でShellを使用する方法は主に以下3つがある。
  1. Emacs::shell
  2. Emacs::eshell
  3. Emacs::ansi-term

1. 一番よく使われるemacs上のシェル。M-x shellで起動。
ちょっと癖があるのは、1つ前のコマンドを参照するときは「M-p」、1つ次のコマンドを参照するときは「M-n」と入力する。あと頻繁に文字化けする。

2. lispを使用したシェル。M-x eshellで起動。起動に時間がかかる。

3. M-x ansi-termで起動。今日初めて使ったけど、3つの中では最強な気がする。ほぼ普通のshellな気がする。

ということで、3.のansi-termを使うことにしよう。

2011年5月4日水曜日

Haskell勉強記(6)

ひさびさにHaskell。

今日は、配列の要素取得について。
配列からi番目の要素を取り出したいときにどうするかです。

Haskellには!!という演算子が定義されています。
(!!) :: [a] -> Int -> a

以下に第n番目のfibonacci数を出力するプログラムを書いてみます。
遅延評価+末尾再帰によって、無限長のfibonacci数列を定義できます。
main = print $ fib 10
where fib n = (fib' 1 1) !! n
fib' a b = a : fib' b (a+b)

2011年5月3日火曜日

サーバー奮闘記(6)

 開発用マシンとしてだけでなく、Webサーバーとしても使いたい。
ということで、Webサーバーの設定をやってみた。

 Apache2がもともと入っていたので、インストールは必要ありませんでした。

/etc/apache2/httpd.conf ルートディレクトリなどを設定するファイル。なぜかUbuntuでは空ファイル。(Apache2からは空になったという情報もあり。。)
/etc/apache2/apache2.conf 設定ファイル。(もともとはhttpd.confにあったものも含まれているよう)

 いろいろ調べた結果、自分でルートディレクトリの設定はできないようでした。
仕方ないので、デフォルトのルートディレクトリを使います。

/var/www/html          html、jpg、cssなどを置くディレクトリ
/var/www/data          DBを置くディレクトリ(拡張子dbのファイルがあった。。)
/var/www/cgi-bin         cgiファイルを置くディレクトリ

上の3つの中に各コンテンツを入れていけばよさそうです。

/var/www/html/app1
/var/www/html/app2
・・・・・・
/var/www/html/app10/main.html
/var/www/html/app10/page1.html

みたいな構成になるはずです。

 ごちゃごちゃしてきそうなので、シンボリックリンクをはることにします。httpd.confにaliasの設定を記述するのが正攻法な気がしますが無いので、
 link -s ~/hogehoge/html /var/www/html/hogehoge
 link -s ~/hogehoge/data /var/www/data/hogehoge
 link -s ~/hogehoge/cgi-bin /var/www/cgi-bin/hogehoge
で一旦しのいでおきます。

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

サーバー奮闘記(5)

ファイル転送をしたくなったので、FTPサーバーを入れました。

手順は以下のとおり。

1. vsftpdのインストール
 sudo apt-get install vsftpd

2. 設定ファイルの変更
 sudo vi /etc/vsftpd.conf
変更のポイントは以下
①anonymous_enable=NO
一般公開用のファイルをサーバーにおく場合は匿名ユーザーの接続を許可しますが、今回作りたいのは個人用なので「NO」にします。「YES」にすると、不特定多数の人にファイルを公開することになるので注意。

②local_enable=YES
一般ユーザーの接続を許可します。普段使っているユーザー名とパスワードでの接続を可能にします。

③write_enable=YES
サーバー側への書き込みを許可します。

④chroot_local_user=YES
ユーザー毎に(読みとり可能な)ルートディレクトリを変更します。これを「YES」にすることで、ユーザーのHOMEディレクトリより上の階層のディレクトリはFTPから参照できません。
「NO」にすると、HOMEディレクトリより上のファイル・ディレクトリが見えます。これはセキュリティ上危ないので、「YES」がいいと思います。

3. FTPサーバーの再起動
変更した設定内容を反映させるため、vsftpdを再起動します。
 sudo /etc/init.d/vsftpd restart
でもOKですが、「Rather than invoking init scripts through /etc/init.d, use the service(8) utility, e.g. service vsftpd restart」という警告がでるので、
 sudo restart vsftpd
を使った方がいいです。

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

参考ページ:

サーバー奮闘記(4)

とりあえず、いろいろな言語をインストールして"Hello World"してみた。
phpはMySQLと一緒に入れる予定。

rubyは書いたことないけど、一応いれました。暇なとき勉強します。
pythonはデフォルトで入ってました。

1. Java
 sudo apt-get install openjdk-6-jdk

2. Haskell
 sudo apt-get install ghc

3. ruby
 sudo apt-get install ruby

今日はサーバー設定は満足したので、rubyで遊んでみます。
サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

2011年5月2日月曜日

サーバー奮闘記(3)

sudoを使うと以下のエラーが出ました。
 hogehoge is not in the sudoers file.

sudo権限がないみたいです。
以下で権限を付与できます。

1. rootにsu
2. visudoでsudoers fileをオープン
3. 以下の内容を追記
 hogehoge ALL=(ALL) ALL

visudoは、/etc/sudoersを編集するためのコマンドらしいです。
実行すると、viが開いて/etc/sudoersを編集できます。

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

サーバー奮闘記(2)

DTIのホスティングサービスでは、デフォルトではrootのsshログインができます。
これはちょっとセキュリティ的にあぶないので、rootのsshログインを禁止します。

手順は以下
  1. root以外のユーザー作成
  2. sshd_configの設定変更
  3. sshサーバー再起動
1. root以外のユーザー変更
以下の設定をすると、ssh経由でrootログインできなくなります。hosting serviceを利用している場合は、先にroot以外のユーザーを作っておきましょう。でないとサーバーに入れなくなってしまいます(笑)

2. sshd_configの設定変更
 vi /etc/ssh/sshd_config
で設定ファイルを変更します。
 PermitRootLogin yes
 PermitRootLogin no
に変更します。
※「ssh_config」ではなく「sshd_config」です。ファイルを間違えないように注意!

3. sshサーバー再起動
 /etc/init.d/ssh restart
でsshを再起動します。

1. - 3.までを実行して、ルートでsshログインができなくなっていることを確認しましょう。

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?

サーバー奮闘記(1)

ついにサーバーデビュー。

DTIのvpsを申し込んだ。

申し込んでから10分くらいたったら、使えるようになっていた。素晴らしいです。

今日やったのは、
  1. emacsの導入
  2. gcc/g++インストール
  3. ユーザー作成
までです。それぞれやったことをメモしておきます。

1. emacsの導入
 apt-get install emacs22
と入力したけど、「404 Not Found」が出ました。URLが古い?
 apt-get update
でパッケージリストを最新にして、もう一度
 apt-get install emacs22
とすると、インストールできました。

2. gcc/g++インストール
 apt-get install gcc
 apt-get install g++
と入力するだけ。

3. ユーザー作成
 adduser ユーザー名
と入力します。あとは、対話式にいろいろ聞かれるので適切な値を入力します。

1.-3.までやった後C++でHello Wolrdしました。
ちょっと感動(笑)

サーバー奮闘記一覧はこちらから。ここに書いていることを順にやれば、いろいろできるようになるかも!?